Line data Source code
1 : /*
2 : * SPDX-License-Identifier: MPL-2.0
3 : *
4 : * This Source Code Form is subject to the terms of the Mozilla Public
5 : * License, v. 2.0. If a copy of the MPL was not distributed with this
6 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7 : *
8 : * Copyright 2024 MonetDB Foundation;
9 : * Copyright August 2008 - 2023 MonetDB B.V.;
10 : * Copyright 1997 - July 2008 CWI.
11 : */
12 :
13 : #include "monetdb_config.h"
14 : #include "rel_rewriter.h"
15 : #include "rel_exp.h"
16 : #include "rel_dump.h"
17 : #include "rel_basetable.h"
18 :
19 : /* simplify expressions, such as not(not(x)) */
20 : /* exp visitor */
21 :
22 : #define is_not_anyequal(sf) (strcmp((sf)->func->base.name, "sql_not_anyequal") == 0)
23 :
24 : static list *
25 1863089 : exps_simplify_exp(visitor *v, list *exps)
26 : {
27 1863089 : if (list_empty(exps))
28 : return exps;
29 :
30 1863089 : int needed = 0;
31 4015616 : for (node *n=exps->h; n && !needed; n = n->next) {
32 2152527 : sql_exp *e = n->data;
33 :
34 2293215 : needed = (exp_is_true(e) || exp_is_false(e) || (is_compare(e->type) && e->flag == cmp_or));
35 : }
36 1863089 : if (needed) {
37 : /* if there's only one expression and it is false, we have to keep it */
38 140688 : if (list_length(exps) == 1 && exp_is_false(exps->h->data))
39 : return exps;
40 75622 : list *nexps = sa_list(v->sql->sa);
41 167586 : for (node *n=exps->h; n; n = n->next) {
42 92388 : sql_exp *e = n->data;
43 :
44 : /* TRUE or X -> TRUE
45 : * FALSE or X -> X */
46 92388 : if (is_compare(e->type) && e->flag == cmp_or) {
47 75059 : list *l = e->l = exps_simplify_exp(v, e->l);
48 75059 : list *r = e->r = exps_simplify_exp(v, e->r);
49 :
50 75059 : if (list_length(l) == 1) {
51 70358 : sql_exp *ie = l->h->data;
52 :
53 70358 : if (exp_is_true(ie)) {
54 0 : v->changes++;
55 0 : continue;
56 70358 : } else if (exp_is_false(ie)) {
57 150 : v->changes++;
58 150 : nexps = list_merge(nexps, r, (fdup)NULL);
59 150 : continue;
60 : }
61 4701 : } else if (list_length(l) == 0) { /* left is true */
62 35 : v->changes++;
63 35 : continue;
64 : }
65 74874 : if (list_length(r) == 1) {
66 67866 : sql_exp *ie = r->h->data;
67 :
68 67866 : if (exp_is_true(ie)) {
69 0 : v->changes++;
70 0 : continue;
71 67866 : } else if (exp_is_false(ie)) {
72 227 : nexps = list_merge(nexps, l, (fdup)NULL);
73 227 : v->changes++;
74 227 : continue;
75 : }
76 7008 : } else if (list_length(r) == 0) { /* right is true */
77 33 : v->changes++;
78 33 : continue;
79 : }
80 : }
81 : /* TRUE and X -> X */
82 91943 : if (exp_is_true(e)) {
83 2096 : v->changes++;
84 2096 : continue;
85 : /* FALSE and X -> FALSE */
86 89847 : } else if (exp_is_false(e)) {
87 424 : v->changes++;
88 424 : return append(sa_list(v->sql->sa), e);
89 : } else {
90 89423 : append(nexps, e);
91 : }
92 : }
93 75198 : return nexps;
94 : }
95 : return exps;
96 : }
97 :
98 : static sql_exp *
99 1 : exp_exists(mvc *sql, sql_exp *le, int exists)
100 : {
101 1 : sql_subfunc *exists_func = NULL;
102 :
103 2 : if (!(exists_func = sql_bind_func(sql, "sys", exists ? "sql_exists" : "sql_not_exists", exp_subtype(le), NULL, F_FUNC, true, true)))
104 0 : return sql_error(sql, 02, SQLSTATE(42000) "exist operator on type %s missing", exp_subtype(le) ? exp_subtype(le)->type->base.name : "unknown");
105 1 : sql_exp *res = exp_unop(sql->sa, le, exists_func);
106 1 : set_has_no_nil(res);
107 1 : return res;
108 : }
109 :
110 : sql_exp *
111 9419768 : rewrite_simplify_exp(visitor *v, sql_rel *rel, sql_exp *e, int depth)
112 : {
113 9419768 : if (!e)
114 : return e;
115 :
116 9419768 : v->changes = 0;
117 9419768 : (void)rel; (void)depth;
118 :
119 9419768 : sql_subfunc *sf = e->f;
120 9419768 : if (is_func(e->type) && list_length(e->l) == 1 && is_not_func(sf)) {
121 5186 : list *args = e->l;
122 5186 : sql_exp *ie = args->h->data;
123 :
124 5186 : if (!ie)
125 : return e;
126 :
127 5186 : sql_subfunc *sf = ie->f;
128 5186 : if (is_func(ie->type) && list_length(ie->l) == 1 && is_not_func(sf)) {
129 0 : args = ie->l;
130 :
131 0 : ie = args->h->data;
132 0 : if (exp_name(e))
133 0 : exp_prop_alias(v->sql->sa, ie, e);
134 0 : v->changes++;
135 0 : return ie;
136 : }
137 5186 : if (is_func(ie->type) && list_length(ie->l) == 2 && is_not_anyequal(sf)) {
138 0 : args = ie->l;
139 :
140 0 : sql_exp *l = args->h->data;
141 0 : sql_exp *vals = args->h->next->data;
142 :
143 0 : if (!(ie = exp_in_func(v->sql, l, vals, 1, 0)))
144 : return NULL;
145 0 : if (exp_name(e))
146 0 : exp_prop_alias(v->sql->sa, ie, e);
147 0 : v->changes++;
148 0 : return ie;
149 : }
150 : /* TRUE or X -> TRUE
151 : * FALSE or X -> X */
152 5186 : if (is_compare(e->type) && e->flag == cmp_or) {
153 0 : list *l = e->l = exps_simplify_exp(v, e->l);
154 0 : list *r = e->r = exps_simplify_exp(v, e->r);
155 :
156 0 : if (list_length(l) == 1) {
157 0 : sql_exp *ie = l->h->data;
158 :
159 0 : if (exp_is_true(ie)) {
160 0 : v->changes++;
161 0 : return ie;
162 0 : } else if (exp_is_false(ie) && list_length(r) == 1) {
163 0 : v->changes++;
164 0 : return r->h->data;
165 : }
166 0 : } else if (list_length(l) == 0) { /* left is true */
167 0 : v->changes++;
168 0 : return exp_atom_bool(v->sql->sa, 1);
169 : }
170 0 : if (list_length(r) == 1) {
171 0 : sql_exp *ie = r->h->data;
172 :
173 0 : if (exp_is_true(ie)) {
174 0 : v->changes++;
175 0 : return ie;
176 0 : } else if (exp_is_false(ie) && list_length(l) == 1) {
177 0 : v->changes++;
178 0 : return l->h->data;
179 : }
180 0 : } else if (list_length(r) == 0) { /* right is true */
181 0 : v->changes++;
182 0 : return exp_atom_bool(v->sql->sa, 1);
183 : }
184 : }
185 : }
186 9419768 : if (is_compare(e->type) && e->flag == cmp_equal) { /* predicate_func = TRUE */
187 239745 : sql_exp *l = e->l, *r = e->r;
188 239745 : if (is_func(l->type) && exp_is_true(r) && (is_anyequal_func(((sql_subfunc*)l->f)) || is_exists_func(((sql_subfunc*)l->f))))
189 : return l;
190 239740 : if (is_func(l->type) && exp_is_false(r) && (is_anyequal_func(((sql_subfunc*)l->f)) || is_exists_func(((sql_subfunc*)l->f)))) {
191 2 : sql_subfunc *sf = l->f;
192 2 : if (is_anyequal_func(sf))
193 1 : return exp_in_func(v->sql, ((list*)l->l)->h->data, ((list*)l->l)->h->next->data, !is_anyequal(sf), 0);
194 1 : if (is_exists_func(sf))
195 1 : return exp_exists(v->sql, ((list*)l->l)->h->data, !is_exists(sf));
196 : return l;
197 : }
198 : }
199 : return e;
200 : }
201 :
202 : sql_rel *
203 5798747 : rewrite_simplify(visitor *v, uint8_t cycle, bool value_based_opt, sql_rel *rel)
204 : {
205 5798747 : if (!rel)
206 : return rel;
207 :
208 5798747 : if ((is_select(rel->op) || is_join(rel->op) || is_semi(rel->op)) && !list_empty(rel->exps)) {
209 1712971 : int changes = v->changes;
210 1712971 : rel->exps = exps_simplify_exp(v, rel->exps);
211 : /* At a select or inner join relation if the single expression is false, eliminate the inner relations with a dummy projection */
212 1712971 : if (value_based_opt && (v->changes > changes || cycle == 0) && (is_select(rel->op) || is_innerjoin(rel->op)) &&
213 183331 : !is_single(rel) && list_length(rel->exps) == 1 && (exp_is_false(rel->exps->h->data) || exp_is_null(rel->exps->h->data))) {
214 3185 : list *nexps = sa_list(v->sql->sa), *toconvert = rel_projections(v->sql, rel->l, NULL, 1, 1);
215 3185 : if (is_innerjoin(rel->op))
216 161 : toconvert = list_merge(toconvert, rel_projections(v->sql, rel->r, NULL, 1, 1), NULL);
217 :
218 26273 : for (node *n = toconvert->h ; n ; n = n->next) {
219 23088 : sql_exp *e = n->data, *a = exp_atom(v->sql->sa, atom_general(v->sql->sa, exp_subtype(e), NULL, 0));
220 23088 : exp_prop_alias(v->sql->sa, a, e);
221 23088 : list_append(nexps, a);
222 : }
223 3185 : rel_destroy(rel->l);
224 3185 : if (is_innerjoin(rel->op)) {
225 161 : rel_destroy(rel->r);
226 161 : rel->r = NULL;
227 161 : rel->op = op_select;
228 : }
229 : /* make sure the single expression is false, so the generate NULL values won't match */
230 3185 : rel->exps->h->data = exp_atom_bool(v->sql->sa, 0);
231 3185 : rel->l = rel_project(v->sql->sa, NULL, nexps);
232 3185 : set_count_prop(v->sql->sa, rel->l, 1);
233 3185 : set_count_prop(v->sql->sa, rel, 0);
234 3185 : rel->card = CARD_ATOM;
235 3185 : v->changes++;
236 : }
237 : }
238 5798747 : if (is_join(rel->op) && list_empty(rel->exps))
239 70716 : rel->exps = NULL; /* crossproduct */
240 5798747 : return try_remove_empty_select(v, rel);
241 : }
242 :
243 : int
244 0 : find_member_pos(list *l, sql_table *t)
245 : {
246 0 : int i = 0;
247 0 : if (l) {
248 0 : for (node *n = l->h; n ; n = n->next, i++) {
249 0 : sql_part *pt = n->data;
250 0 : if (pt->member == t->base.id)
251 0 : return i;
252 : }
253 : }
254 : return -1;
255 : }
256 :
257 : /* The important task of the relational optimizer is to optimize the
258 : join order.
259 :
260 : The current implementation chooses the join order based on
261 : select counts, ie if one of the join sides has been reduced using
262 : a select this join is choosen over one without such selections.
263 : */
264 :
265 : /* currently we only find simple column expressions */
266 : sql_column *
267 943988 : name_find_column( sql_rel *rel, const char *rname, const char *name, int pnr, sql_rel **bt )
268 : {
269 1426586 : sql_exp *alias = NULL;
270 1426586 : sql_column *c = NULL;
271 :
272 1426586 : switch (rel->op) {
273 534228 : case op_basetable: {
274 534228 : sql_table *t = rel->l;
275 :
276 534228 : if (rel->exps) {
277 534228 : sql_exp *e;
278 :
279 534228 : if (rname)
280 533370 : e = exps_bind_column2(rel->exps, rname, name, NULL);
281 : else
282 858 : e = exps_bind_column(rel->exps, name, NULL, NULL, 0);
283 534229 : if (!e || e->type != e_column)
284 : return NULL;
285 460323 : if (e->l)
286 460323 : rname = e->l;
287 460323 : name = e->r;
288 : }
289 460323 : if (rname && strcmp(t->base.name, rname) != 0)
290 : return NULL;
291 459075 : sql_table *mt = rel_base_get_mergetable(rel);
292 459076 : if (ol_length(t->columns)) {
293 3713967 : for (node *cn = ol_first_node(t->columns); cn; cn = cn->next) {
294 3605224 : sql_column *c = cn->data;
295 3605224 : if (strcmp(c->base.name, name) == 0) {
296 350332 : if (bt)
297 79048 : *bt = rel;
298 350332 : if (pnr < 0 || (mt &&
299 0 : find_member_pos(mt->members, c->t) == pnr))
300 350333 : return c;
301 : }
302 : }
303 : }
304 108743 : if (name[0] == '%' && ol_length(t->idxs)) {
305 44595 : for (node *cn = ol_first_node(t->idxs); cn; cn = cn->next) {
306 33489 : sql_idx *i = cn->data;
307 33489 : if (strcmp(i->base.name, name+1 /* skip % */) == 0) {
308 1925 : if (bt)
309 739 : *bt = rel;
310 1925 : if (pnr < 0 || (mt &&
311 0 : find_member_pos(mt->members, i->t) == pnr)) {
312 1925 : sql_kc *c = i->columns->h->data;
313 1925 : return c->c;
314 : }
315 : }
316 : }
317 : }
318 : break;
319 : }
320 : case op_table:
321 : /* table func */
322 : return NULL;
323 : case op_ddl:
324 0 : if (is_updateble(rel))
325 0 : return name_find_column( rel->l, rname, name, pnr, bt);
326 : return NULL;
327 240238 : case op_join:
328 : case op_left:
329 : case op_right:
330 : case op_full:
331 : /* first right (possible subquery) */
332 240238 : c = name_find_column( rel->r, rname, name, pnr, bt);
333 : /* fall through */
334 : case op_semi:
335 : case op_anti:
336 240238 : if (!c)
337 184675 : c = name_find_column( rel->l, rname, name, pnr, bt);
338 184675 : if (!c && !list_empty(rel->attr)) {
339 19610 : if (rname)
340 19593 : alias = exps_bind_column2(rel->attr, rname, name, NULL);
341 : else
342 17 : alias = exps_bind_column(rel->attr, name, NULL, NULL, 1);
343 : }
344 : return c;
345 91928 : case op_select:
346 : case op_topn:
347 : case op_sample:
348 91928 : return name_find_column( rel->l, rname, name, pnr, bt);
349 29972 : case op_union:
350 : case op_inter:
351 : case op_except:
352 :
353 29972 : if (pnr >= 0 || pnr == -2) {
354 : /* first right (possible subquery) */
355 29972 : c = name_find_column( rel->r, rname, name, pnr, bt);
356 29972 : if (!c)
357 26502 : c = name_find_column( rel->l, rname, name, pnr, bt);
358 3470 : return c;
359 : }
360 : return NULL;
361 :
362 521772 : case op_project:
363 : case op_groupby:
364 521772 : if (!rel->exps)
365 : break;
366 521772 : if (rname)
367 505412 : alias = exps_bind_column2(rel->exps, rname, name, NULL);
368 : else
369 16360 : alias = exps_bind_column(rel->exps, name, NULL, NULL, 1);
370 521771 : if (is_groupby(rel->op) && alias && alias->type == e_column && !list_empty(rel->r)) {
371 163926 : if (alias->l)
372 156850 : alias = exps_bind_column2(rel->r, alias->l, alias->r, NULL);
373 : else
374 7076 : alias = exps_bind_column(rel->r, alias->r, NULL, NULL, 1);
375 : }
376 521769 : if (is_groupby(rel->op) && !alias && rel->l) {
377 : /* Group by column not found as alias in projection
378 : * list, fall back to check plain input columns */
379 : return name_find_column( rel->l, rname, name, pnr, bt);
380 : }
381 : break;
382 : case op_insert:
383 : case op_update:
384 : case op_delete:
385 : case op_truncate:
386 : case op_merge:
387 : break;
388 : }
389 526667 : if (alias && !is_join(rel->op)) { /* we found an expression with the correct name, but
390 : we need sql_columns */
391 386946 : if (rel->l && alias->type == e_column) /* real alias */
392 357960 : return name_find_column(rel->l, alias->l, alias->r, pnr, bt);
393 : }
394 : return NULL;
395 : }
396 :
397 : sql_column *
398 120635 : exp_find_column( sql_rel *rel, sql_exp *exp, int pnr)
399 : {
400 120635 : if (exp->type == e_column)
401 117935 : return name_find_column(rel, exp->l, exp->r, pnr, NULL);
402 : return NULL;
403 : }
404 :
405 : int
406 1841040 : exp_joins_rels(sql_exp *e, list *rels)
407 : {
408 1841040 : sql_rel *l = NULL, *r = NULL;
409 :
410 1841040 : assert (e->type == e_cmp);
411 :
412 1841040 : if (e->flag == cmp_or) {
413 : l = NULL;
414 1841040 : } else if (e->flag == cmp_filter) {
415 4 : list *ll = e->l;
416 4 : list *lr = e->r;
417 :
418 4 : l = find_rel(rels, ll->h->data);
419 4 : r = find_rel(rels, lr->h->data);
420 1841036 : } else if (e->flag == cmp_in || e->flag == cmp_notin) {
421 0 : list *lr = e->r;
422 :
423 0 : l = find_rel(rels, e->l);
424 0 : if (lr && lr->h)
425 0 : r = find_rel(rels, lr->h->data);
426 : } else {
427 1841036 : l = find_rel(rels, e->l);
428 1841036 : r = find_rel(rels, e->r);
429 : }
430 :
431 1841040 : if (l && r)
432 395293 : return 0;
433 : return -1;
434 : }
435 :
436 : static int
437 99 : rel_is_unique(sql_rel *rel)
438 : {
439 99 : switch(rel->op) {
440 0 : case op_semi:
441 : case op_anti:
442 : case op_inter:
443 : case op_except:
444 : case op_topn:
445 : case op_sample:
446 0 : return rel_is_unique(rel->l);
447 : case op_table:
448 : case op_basetable:
449 : return 1;
450 99 : default:
451 99 : return 0;
452 : }
453 : }
454 :
455 : int
456 15519 : kc_column_cmp(sql_kc *kc, sql_column *c)
457 : {
458 : /* return on equality */
459 15519 : return !(c == kc->c);
460 : }
461 :
462 : /* WARNING exps_unique doesn't check for duplicate NULL values */
463 : int
464 28117 : exps_unique(mvc *sql, sql_rel *rel, list *exps)
465 : {
466 28117 : int nr = 0, need_check = 0;
467 28117 : sql_ukey *k = NULL;
468 :
469 28117 : if (list_empty(exps))
470 : return 0;
471 84630 : for(node *n = exps->h; n ; n = n->next) {
472 56513 : sql_exp *e = n->data;
473 56513 : prop *p;
474 :
475 56513 : if (!is_unique(e)) { /* ignore unique columns */
476 55701 : need_check++;
477 55701 : if (!k && (p = find_prop(e->p, PROP_HASHCOL))) /* at the moment, use only one k */
478 125 : k = p->value.pval;
479 : }
480 : }
481 28117 : if (!need_check) /* all have unique property return */
482 : return 1;
483 27577 : if (!k || list_length(k->k.columns) != need_check)
484 27476 : return 0;
485 101 : if (rel) {
486 101 : char *matched = SA_ZNEW_ARRAY(sql->sa, char, list_length(k->k.columns));
487 101 : fcmp cmp = (fcmp)&kc_column_cmp;
488 205 : for(node *n = exps->h; n; n = n->next) {
489 104 : sql_exp *e = n->data;
490 104 : sql_column *c;
491 104 : node *m;
492 :
493 104 : if (is_unique(e))
494 0 : continue;
495 104 : if ((c = exp_find_column(rel, e, -2)) != NULL && (m = list_find(k->k.columns, c, cmp)) != NULL) {
496 102 : int pos = list_position(k->k.columns, m->data);
497 102 : if (!matched[pos])
498 102 : nr++;
499 102 : matched[pos] = 1;
500 : }
501 : }
502 101 : if (nr == list_length(k->k.columns))
503 99 : return rel_is_unique(rel);
504 : }
505 : return 0;
506 : }
507 :
508 : BUN
509 689703 : get_rel_count(sql_rel *rel)
510 : {
511 689703 : prop *found = find_prop(rel->p, PROP_COUNT);
512 689703 : return found ? found->value.lval : BUN_NONE;
513 : }
514 :
515 : void
516 1354773 : set_count_prop(allocator *sa, sql_rel *rel, BUN val)
517 : {
518 1354773 : if (val != BUN_NONE) {
519 1323360 : prop *found = find_prop(rel->p, PROP_COUNT);
520 :
521 1323371 : if (found) {
522 260069 : found->value.lval = val;
523 : } else {
524 1063302 : prop *p = rel->p = prop_create(sa, PROP_COUNT, rel->p);
525 1063300 : p->value.lval = val;
526 : }
527 : }
528 1354782 : }
|
