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 1759309 : exps_simplify_exp(visitor *v, list *exps)
26 : {
27 1759309 : if (list_empty(exps))
28 : return exps;
29 :
30 1759309 : int needed = 0;
31 3797174 : for (node *n=exps->h; n && !needed; n = n->next) {
32 2037865 : sql_exp *e = n->data;
33 :
34 2176558 : needed = (exp_is_true(e) || exp_is_false(e) || (is_compare(e->type) && e->flag == cmp_or));
35 : }
36 1759309 : if (needed) {
37 : /* if there's only one expression and it is false, we have to keep it */
38 138693 : if (list_length(exps) == 1 && exp_is_false(exps->h->data))
39 : return exps;
40 75184 : list *nexps = sa_list(v->sql->sa);
41 166602 : for (node *n=exps->h; n; n = n->next) {
42 91816 : sql_exp *e = n->data;
43 :
44 : /* TRUE or X -> TRUE
45 : * FALSE or X -> X */
46 91816 : if (is_compare(e->type) && e->flag == cmp_or) {
47 74767 : list *l = e->l = exps_simplify_exp(v, e->l);
48 74767 : list *r = e->r = exps_simplify_exp(v, e->r);
49 :
50 74767 : if (list_length(l) == 1) {
51 70111 : sql_exp *ie = l->h->data;
52 :
53 70111 : if (exp_is_true(ie)) {
54 0 : v->changes++;
55 0 : continue;
56 70111 : } else if (exp_is_false(ie)) {
57 138 : v->changes++;
58 138 : nexps = list_merge(nexps, r, (fdup)NULL);
59 138 : continue;
60 : }
61 4656 : } else if (list_length(l) == 0) { /* left is true */
62 31 : v->changes++;
63 31 : continue;
64 : }
65 74598 : if (list_length(r) == 1) {
66 67634 : sql_exp *ie = r->h->data;
67 :
68 67634 : if (exp_is_true(ie)) {
69 0 : v->changes++;
70 0 : continue;
71 67634 : } else if (exp_is_false(ie)) {
72 215 : nexps = list_merge(nexps, l, (fdup)NULL);
73 215 : v->changes++;
74 215 : continue;
75 : }
76 6964 : } else if (list_length(r) == 0) { /* right is true */
77 31 : v->changes++;
78 31 : continue;
79 : }
80 : }
81 : /* TRUE and X -> X */
82 91401 : if (exp_is_true(e)) {
83 1966 : v->changes++;
84 1966 : continue;
85 : /* FALSE and X -> FALSE */
86 89435 : } else if (exp_is_false(e)) {
87 398 : v->changes++;
88 398 : return append(sa_list(v->sql->sa), e);
89 : } else {
90 89037 : append(nexps, e);
91 : }
92 : }
93 74786 : 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 9039457 : rewrite_simplify_exp(visitor *v, sql_rel *rel, sql_exp *e, int depth)
112 : {
113 9039457 : if (!e)
114 : return e;
115 :
116 9039457 : v->changes = 0;
117 9039457 : (void)rel; (void)depth;
118 :
119 9039457 : sql_subfunc *sf = e->f;
120 9039457 : if (is_func(e->type) && list_length(e->l) == 1 && is_not_func(sf)) {
121 4959 : list *args = e->l;
122 4959 : sql_exp *ie = args->h->data;
123 :
124 4959 : if (!ie)
125 : return e;
126 :
127 4959 : sql_subfunc *sf = ie->f;
128 4959 : 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 4959 : 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 4959 : 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 9039458 : if (is_compare(e->type) && e->flag == cmp_equal) { /* predicate_func = TRUE */
187 235973 : sql_exp *l = e->l, *r = e->r;
188 235973 : 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 235968 : 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 5625974 : rewrite_simplify(visitor *v, uint8_t cycle, bool value_based_opt, sql_rel *rel)
204 : {
205 5625974 : if (!rel)
206 : return rel;
207 :
208 5625974 : if ((is_select(rel->op) || is_join(rel->op) || is_semi(rel->op)) && !list_empty(rel->exps)) {
209 1609775 : int changes = v->changes;
210 1609775 : 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 1609775 : if (value_based_opt && (v->changes > changes || cycle == 0) && (is_select(rel->op) || is_innerjoin(rel->op)) &&
213 180247 : !is_single(rel) && list_length(rel->exps) == 1 && (exp_is_false(rel->exps->h->data) || exp_is_null(rel->exps->h->data))) {
214 3132 : list *nexps = sa_list(v->sql->sa), *toconvert = rel_projections(v->sql, rel->l, NULL, 1, 1);
215 3132 : if (is_innerjoin(rel->op))
216 148 : toconvert = list_merge(toconvert, rel_projections(v->sql, rel->r, NULL, 1, 1), NULL);
217 :
218 25487 : for (node *n = toconvert->h ; n ; n = n->next) {
219 22355 : sql_exp *e = n->data, *a = exp_atom(v->sql->sa, atom_general(v->sql->sa, exp_subtype(e), NULL, 0));
220 22355 : exp_prop_alias(v->sql->sa, a, e);
221 22355 : list_append(nexps, a);
222 : }
223 3132 : rel_destroy(rel->l);
224 3132 : if (is_innerjoin(rel->op)) {
225 148 : rel_destroy(rel->r);
226 148 : rel->r = NULL;
227 148 : rel->op = op_select;
228 : }
229 : /* make sure the single expression is false, so the generate NULL values won't match */
230 3132 : rel->exps->h->data = exp_atom_bool(v->sql->sa, 0);
231 3132 : rel->l = rel_project(v->sql->sa, NULL, nexps);
232 3132 : set_count_prop(v->sql->sa, rel->l, 1);
233 3132 : set_count_prop(v->sql->sa, rel, 0);
234 3132 : rel->card = CARD_ATOM;
235 3132 : v->changes++;
236 : }
237 : }
238 5625974 : if (is_join(rel->op) && list_empty(rel->exps))
239 69676 : rel->exps = NULL; /* crossproduct */
240 5625974 : 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 879082 : name_find_column( sql_rel *rel, const char *rname, const char *name, int pnr, sql_rel **bt )
268 : {
269 1323578 : sql_exp *alias = NULL;
270 1323578 : sql_column *c = NULL;
271 :
272 1323578 : switch (rel->op) {
273 499300 : case op_basetable: {
274 499300 : sql_table *t = rel->l;
275 :
276 499300 : if (rel->exps) {
277 499300 : sql_exp *e;
278 :
279 499300 : if (rname)
280 498501 : e = exps_bind_column2(rel->exps, rname, name, NULL);
281 : else
282 799 : e = exps_bind_column(rel->exps, name, NULL, NULL, 0);
283 499668 : if (!e || e->type != e_column)
284 : return NULL;
285 431565 : if (e->l)
286 431565 : rname = e->l;
287 431565 : name = e->r;
288 : }
289 431565 : if (rname && strcmp(t->base.name, rname) != 0)
290 : return NULL;
291 430321 : sql_table *mt = rel_base_get_mergetable(rel);
292 430098 : if (ol_length(t->columns)) {
293 3595363 : for (node *cn = ol_first_node(t->columns); cn; cn = cn->next) {
294 3494046 : sql_column *c = cn->data;
295 3494046 : if (strcmp(c->base.name, name) == 0) {
296 329154 : if (bt)
297 73350 : *bt = rel;
298 329369 : if (pnr < 0 || (mt &&
299 0 : find_member_pos(mt->members, c->t) == pnr))
300 329154 : return c;
301 : }
302 : }
303 : }
304 101338 : if (name[0] == '%' && ol_length(t->idxs)) {
305 41922 : for (node *cn = ol_first_node(t->idxs); cn; cn = cn->next) {
306 31865 : sql_idx *i = cn->data;
307 31865 : if (strcmp(i->base.name, name+1 /* skip % */) == 0) {
308 1881 : if (bt)
309 737 : *bt = rel;
310 1881 : if (pnr < 0 || (mt &&
311 0 : find_member_pos(mt->members, i->t) == pnr)) {
312 1881 : sql_kc *c = i->columns->h->data;
313 1881 : 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 217859 : case op_join:
328 : case op_left:
329 : case op_right:
330 : case op_full:
331 : /* first right (possible subquery) */
332 217859 : c = name_find_column( rel->r, rname, name, pnr, bt);
333 : /* fall through */
334 : case op_semi:
335 : case op_anti:
336 217859 : if (!c)
337 173859 : c = name_find_column( rel->l, rname, name, pnr, bt);
338 173859 : if (!c && !list_empty(rel->attr)) {
339 19200 : if (rname)
340 19183 : 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 85508 : case op_select:
346 : case op_topn:
347 : case op_sample:
348 85508 : return name_find_column( rel->l, rname, name, pnr, bt);
349 21402 : case op_union:
350 : case op_inter:
351 : case op_except:
352 :
353 21402 : if (pnr >= 0 || pnr == -2) {
354 : /* first right (possible subquery) */
355 21402 : c = name_find_column( rel->r, rname, name, pnr, bt);
356 21402 : if (!c)
357 20735 : c = name_find_column( rel->l, rname, name, pnr, bt);
358 667 : return c;
359 : }
360 : return NULL;
361 :
362 4051 : case op_munion:
363 4051 : if (pnr >= 0 || pnr == -2) {
364 9600 : for (node *n = ((list*)rel->l)->h; n; n = n->next) {
365 6858 : if ((c = name_find_column(n->data, rname, name, pnr, bt)) != NULL)
366 1309 : return c;
367 : }
368 : }
369 : return NULL;
370 487332 : case op_project:
371 : case op_groupby:
372 487332 : if (!rel->exps)
373 : break;
374 487332 : if (rname)
375 473845 : alias = exps_bind_column2(rel->exps, rname, name, NULL);
376 : else
377 13487 : alias = exps_bind_column(rel->exps, name, NULL, NULL, 1);
378 487332 : if (is_groupby(rel->op) && alias && alias->type == e_column && !list_empty(rel->r)) {
379 154585 : if (alias->l)
380 148726 : alias = exps_bind_column2(rel->r, alias->l, alias->r, NULL);
381 : else
382 5859 : alias = exps_bind_column(rel->r, alias->r, NULL, NULL, 1);
383 : }
384 487332 : if (is_groupby(rel->op) && !alias && rel->l) {
385 : /* Group by column not found as alias in projection
386 : * list, fall back to check plain input columns */
387 : return name_find_column( rel->l, rname, name, pnr, bt);
388 : }
389 : break;
390 : case op_insert:
391 : case op_update:
392 : case op_delete:
393 : case op_truncate:
394 : case op_merge:
395 : break;
396 : }
397 491360 : if (alias && !is_join(rel->op)) { /* we found an expression with the correct name, but
398 : we need sql_columns */
399 359521 : if (rel->l && alias->type == e_column) /* real alias */
400 332224 : return name_find_column(rel->l, alias->l, alias->r, pnr, bt);
401 : }
402 : return NULL;
403 : }
404 :
405 : sql_column *
406 108999 : exp_find_column( sql_rel *rel, sql_exp *exp, int pnr)
407 : {
408 108999 : if (exp->type == e_column)
409 106351 : return name_find_column(rel, exp->l, exp->r, pnr, NULL);
410 : return NULL;
411 : }
412 :
413 : int
414 1781266 : exp_joins_rels(sql_exp *e, list *rels)
415 : {
416 1781266 : sql_rel *l = NULL, *r = NULL;
417 :
418 1781266 : assert (e->type == e_cmp);
419 :
420 1781266 : if (e->flag == cmp_or) {
421 : l = NULL;
422 1781266 : } else if (e->flag == cmp_filter) {
423 4 : list *ll = e->l;
424 4 : list *lr = e->r;
425 :
426 4 : l = find_rel(rels, ll->h->data);
427 4 : r = find_rel(rels, lr->h->data);
428 1781262 : } else if (e->flag == cmp_in || e->flag == cmp_notin) {
429 0 : list *lr = e->r;
430 :
431 0 : l = find_rel(rels, e->l);
432 0 : if (lr && lr->h)
433 0 : r = find_rel(rels, lr->h->data);
434 : } else {
435 1781262 : l = find_rel(rels, e->l);
436 1781262 : r = find_rel(rels, e->r);
437 : }
438 :
439 1781266 : if (l && r)
440 345965 : return 0;
441 : return -1;
442 : }
443 :
444 : static int
445 97 : rel_is_unique(sql_rel *rel)
446 : {
447 97 : switch(rel->op) {
448 0 : case op_semi:
449 : case op_anti:
450 : case op_inter:
451 : case op_except:
452 : case op_topn:
453 : case op_sample:
454 0 : return rel_is_unique(rel->l);
455 : case op_table:
456 : case op_basetable:
457 : return 1;
458 97 : default:
459 97 : return 0;
460 : }
461 : }
462 :
463 : int
464 5968 : kc_column_cmp(sql_kc *kc, sql_column *c)
465 : {
466 : /* return on equality */
467 5968 : return !(c == kc->c);
468 : }
469 :
470 : /* WARNING exps_unique doesn't check for duplicate NULL values */
471 : int
472 24916 : exps_unique(mvc *sql, sql_rel *rel, list *exps)
473 : {
474 24916 : int nr = 0, need_check = 0;
475 24916 : sql_ukey *k = NULL;
476 :
477 24916 : if (list_empty(exps))
478 : return 0;
479 74812 : for(node *n = exps->h; n ; n = n->next) {
480 49896 : sql_exp *e = n->data;
481 49896 : prop *p;
482 :
483 49896 : if (!is_unique(e)) { /* ignore unique columns */
484 49289 : need_check++;
485 49289 : if (!k && (p = find_prop(e->p, PROP_HASHCOL))) /* at the moment, use only one k */
486 102 : k = p->value.pval;
487 : }
488 : }
489 24916 : if (!need_check) /* all have unique property return */
490 : return 1;
491 24495 : if (!k || list_length(k->k.columns) != need_check)
492 24396 : return 0;
493 99 : if (rel) {
494 99 : char *matched = SA_ZNEW_ARRAY(sql->sa, char, list_length(k->k.columns));
495 99 : fcmp cmp = (fcmp)&kc_column_cmp;
496 199 : for(node *n = exps->h; n; n = n->next) {
497 100 : sql_exp *e = n->data;
498 100 : sql_column *c;
499 100 : node *m;
500 :
501 100 : if (is_unique(e))
502 0 : continue;
503 100 : if ((c = exp_find_column(rel, e, -2)) != NULL && (m = list_find(k->k.columns, c, cmp)) != NULL) {
504 98 : int pos = list_position(k->k.columns, m->data);
505 98 : if (!matched[pos])
506 98 : nr++;
507 98 : matched[pos] = 1;
508 : }
509 : }
510 99 : if (nr == list_length(k->k.columns))
511 97 : return rel_is_unique(rel);
512 : }
513 : return 0;
514 : }
515 :
516 : BUN
517 660640 : get_rel_count(sql_rel *rel)
518 : {
519 660640 : prop *found = find_prop(rel->p, PROP_COUNT);
520 660646 : return found ? found->value.lval : BUN_NONE;
521 : }
522 :
523 : void
524 1309663 : set_count_prop(allocator *sa, sql_rel *rel, BUN val)
525 : {
526 1309663 : if (val != BUN_NONE) {
527 1277298 : prop *found = find_prop(rel->p, PROP_COUNT);
528 :
529 1277153 : if (found) {
530 254797 : found->value.lval = val;
531 : } else {
532 1022356 : prop *p = rel->p = prop_create(sa, PROP_COUNT, rel->p);
533 1022297 : p->value.lval = val;
534 : }
535 : }
536 1309459 : }
|
