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_optimizer.h"
15 : #include "rel_optimizer_private.h"
16 : #include "rel_rel.h"
17 : #include "rel_basetable.h"
18 : #include "rel_exp.h"
19 : #include "rel_propagate.h"
20 : #include "rel_statistics.h"
21 : #include "sql_privileges.h"
22 :
23 : static sql_rel *
24 4990400 : rel_properties(visitor *v, sql_rel *rel)
25 : {
26 4990400 : global_props *gp = (global_props*)v->data;
27 :
28 : /* Don't flag any changes here! */
29 4990400 : gp->cnt[(int)rel->op]++;
30 4990400 : gp->needs_distinct |= need_distinct(rel);
31 4990400 : if (gp->instantiate && is_basetable(rel->op)) {
32 734581 : mvc *sql = v->sql;
33 734581 : sql_table *t = (sql_table *) rel->l;
34 734581 : sql_part *pt;
35 :
36 : /* If the plan has a merge table or a child of one, then rel_merge_table_rewrite has to run */
37 734581 : gp->needs_mergetable_rewrite |= (isMergeTable(t) || (t->s && t->s->parts && (pt = partition_find_part(sql->session->tr, t, NULL))));
38 734596 : gp->needs_remote_replica_rewrite |= (isRemote(t) || isReplicaTable(t));
39 : }
40 4990415 : return rel;
41 : }
42 :
43 : typedef struct {
44 : atom *lval;
45 : atom *hval;
46 : bte anti:1,
47 : semantics:1;
48 : int flag;
49 : list *values;
50 : } range_limit;
51 :
52 : typedef struct {
53 : list *cols;
54 : list *ranges;
55 : sql_rel *sel;
56 : } merge_table_prune_info;
57 :
58 : static sql_rel *merge_table_prune_and_unionize(visitor *v, sql_rel *mt_rel, merge_table_prune_info *info);
59 :
60 : static sql_rel *
61 549 : rel_wrap_select_around_mt_child(visitor *v, sql_rel *t, merge_table_prune_info *info)
62 : {
63 : // TODO: it has to be a table (merge table component) add checks
64 549 : sql_table *subt = (sql_table *)t->l;
65 :
66 549 : if (isMergeTable(subt)) {
67 26 : if ((t = merge_table_prune_and_unionize(v, t, info)) == NULL)
68 : return NULL;
69 : }
70 :
71 549 : if (info) {
72 148 : t = rel_select(v->sql->sa, t, NULL);
73 148 : t->exps = exps_copy(v->sql, info->sel->exps);
74 148 : set_processed(t);
75 148 : set_processed(t);
76 : }
77 : return t;
78 : }
79 :
80 : #if 0
81 : static sql_rel *
82 : rel_unionize_mt_tables_balanced(visitor *v, sql_rel* mt, list* tables, merge_table_prune_info *info)
83 : {
84 : /* This function is creating the union tree in the tables list calling
85 : * itself recursively until the tables list has a single entry (the union tree)
86 : */
87 :
88 : /* base case */
89 : if (tables->cnt == 1) // XXX: or/and h->next == NULL
90 : return tables->h->data;
91 : /* merge (via union) every *two* consecutive nodes of the list */
92 : for (node *n = tables->h; n && n->next; n = n->next->next) {
93 : /* first (left) node */
94 : sql_rel *tl = rel_wrap_select_around_mt_child(v, n->data, info);
95 : /* second (right) node */
96 : sql_rel *tr = rel_wrap_select_around_mt_child(v, n->next->data, info);
97 : /* create the union */
98 : sql_rel *tu = rel_setop(v->sql->sa, tl, tr, op_union);
99 : rel_setop_set_exps(v->sql, tu, rel_projections(v->sql, mt, NULL, 1, 1), true);
100 : set_processed(tu);
101 : /* replace the two nodes with the new relation */
102 : list_append_before(tables, n, tu);
103 : list_remove_node(tables, NULL, n);
104 : list_remove_node(tables, NULL, n->next);
105 : // TODO: do i need to rebuild the hash of the list?
106 : }
107 : return rel_unionize_mt_tables_balanced(v, mt, tables, info);
108 : }
109 : #endif
110 :
111 : static sql_rel *
112 167 : rel_unionize_mt_tables_munion(visitor *v, sql_rel* mt, list* tables, merge_table_prune_info *info)
113 : {
114 : /* create the list of all the operand rels */
115 167 : list *rels = sa_list(v->sql->sa);
116 547 : for (node *n = tables->h; n; n = n->next) {
117 380 : sql_rel *r = rel_wrap_select_around_mt_child(v, n->data, info);
118 380 : append(rels, r);
119 : }
120 :
121 : /* create the munion */
122 167 : sql_rel *mu = rel_setop_n_ary(v->sql->sa, rels, op_munion);
123 167 : rel_setop_n_ary_set_exps(v->sql, mu, rel_projections(v->sql, mt, NULL, 1, 1), true);
124 167 : set_processed(mu);
125 :
126 167 : return mu;
127 : }
128 :
129 : static sql_rel *
130 356 : merge_table_prune_and_unionize(visitor *v, sql_rel *mt_rel, merge_table_prune_info *info)
131 : {
132 356 : if (mvc_highwater(v->sql))
133 0 : return sql_error(v->sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
134 :
135 356 : sql_rel *nrel = NULL;
136 356 : sql_table *mt = (sql_table*) mt_rel->l;
137 356 : const char *mtalias = exp_relname(mt_rel->exps->h->data);
138 356 : list *tables = sa_list(v->sql->sa);
139 :
140 1034 : for (node *nt = mt->members->h; nt; nt = nt->next) {
141 680 : sql_part *pd = nt->data;
142 680 : sql_table *pt = find_sql_table_id(v->sql->session->tr, mt->s, pd->member);
143 680 : sqlstore *store = v->sql->session->tr->store;
144 680 : int skip = 0;
145 :
146 : /* At the moment we throw an error in the optimizer, but later this rewriter should move out from the optimizers */
147 680 : if ((isMergeTable(pt) || isReplicaTable(pt)) && list_empty(pt->members))
148 2 : return sql_error(v->sql, 02, SQLSTATE(42000) "%s '%s'.'%s' should have at least one table associated",
149 2 : TABLE_TYPE_DESCRIPTION(pt->type, pt->properties), pt->s->base.name, pt->base.name);
150 : /* Do not include empty partitions */
151 678 : if (isTable(pt) && pt->access == TABLE_READONLY && !store->storage_api.count_col(v->sql->session->tr, ol_first_node(pt->columns)->data, 10)) /* count active rows only */
152 1 : continue;
153 :
154 1739 : for (node *n = mt_rel->exps->h; n && !skip; n = n->next) { /* for each column of the child table */
155 1062 : sql_exp *e = n->data;
156 1062 : int i = 0;
157 1062 : bool first_attempt = true;
158 1062 : atom *cmin = NULL, *cmax = NULL, *rmin = NULL, *rmax = NULL;
159 1062 : list *inlist = NULL;
160 1062 : const char *cname = e->r;
161 1062 : sql_column *mt_col = NULL, *col = NULL;
162 :
163 1062 : if (cname[0] == '%') /* Ignore TID and indexes here */
164 55 : continue;
165 :
166 1007 : mt_col = ol_find_name(mt->columns, cname)->data;
167 1007 : col = ol_fetch(pt->columns, mt_col->colnr);
168 1007 : assert(e && e->type == e_column && col);
169 :
170 1007 : if (isTable(pt) && info && !list_empty(info->cols) && ATOMlinear(exp_subtype(e)->type->localtype)) {
171 747 : for (node *nn = info->cols->h ; nn && !skip; nn = nn->next) { /* test if it passes all predicates around it */
172 388 : if (nn->data == e) {
173 262 : range_limit *next = list_fetch(info->ranges, i);
174 262 : atom *lval = next->lval, *hval = next->hval;
175 262 : list *values = next->values;
176 :
177 : /* I don't handle cmp_in or cmp_notin cases with anti or null semantics yet */
178 262 : if (next->flag == cmp_in && (next->anti || next->semantics))
179 0 : continue;
180 :
181 262 : assert(col && (lval || values));
182 262 : if (!skip && pt->access == TABLE_READONLY) {
183 : /* check if the part falls within the bounds of the select expression else skip this (keep at least on part-table) */
184 87 : if (!cmin && !cmax && first_attempt) {
185 87 : void *min = NULL, *max = NULL;
186 87 : if (sql_trans_ranges(v->sql->session->tr, col, &min, &max) && min && max) {
187 84 : cmin = atom_general_ptr(v->sql->sa, &col->type, min);
188 84 : cmax = atom_general_ptr(v->sql->sa, &col->type, max);
189 : }
190 87 : first_attempt = false; /* no more attempts to read from storage */
191 : }
192 :
193 87 : if (cmin && cmax) {
194 84 : if (lval) {
195 80 : if (!next->semantics && ((lval && lval->isnull) || (hval && hval->isnull))) {
196 : skip = 1; /* NULL values don't match, skip them */
197 80 : } else if (!next->semantics) {
198 80 : if (next->flag == cmp_equal) {
199 20 : skip |= next->anti ? exp_range_overlap(cmin, cmax, lval, hval, false, false) != 0 :
200 10 : exp_range_overlap(cmin, cmax, lval, hval, false, false) == 0;
201 70 : } else if (hval != lval) { /* range case */
202 70 : comp_type lower = range2lcompare(next->flag), higher = range2rcompare(next->flag);
203 140 : skip |= next->anti ? exp_range_overlap(cmin, cmax, lval, hval, higher == cmp_lt, lower == cmp_gt) != 0 :
204 70 : exp_range_overlap(cmin, cmax, lval, hval, higher == cmp_lt, lower == cmp_gt) == 0;
205 : } else {
206 0 : switch (next->flag) {
207 0 : case cmp_gt:
208 0 : skip |= next->anti ? VALcmp(&(lval->data), &(cmax->data)) < 0 : VALcmp(&(lval->data), &(cmax->data)) >= 0;
209 0 : break;
210 0 : case cmp_gte:
211 0 : skip |= next->anti ? VALcmp(&(lval->data), &(cmax->data)) <= 0 : VALcmp(&(lval->data), &(cmax->data)) > 0;
212 0 : break;
213 0 : case cmp_lt:
214 0 : skip |= next->anti ? VALcmp(&(lval->data), &(cmax->data)) < 0 : VALcmp(&(cmin->data), &(lval->data)) >= 0;
215 0 : break;
216 0 : case cmp_lte:
217 0 : skip |= next->anti ? VALcmp(&(lval->data), &(cmax->data)) <= 0 : VALcmp(&(cmin->data), &(lval->data)) > 0;
218 0 : break;
219 : default:
220 : break;
221 : }
222 : }
223 : }
224 4 : } else if (next->flag == cmp_in) {
225 4 : int nskip = 1;
226 10 : for (node *m = values->h; m && nskip; m = m->next) {
227 6 : atom *a = m->data;
228 :
229 6 : if (a->isnull)
230 0 : continue;
231 6 : nskip &= exp_range_overlap(cmin, cmax, a, a, false, false) == 0;
232 : }
233 4 : skip |= nskip;
234 : }
235 : }
236 : }
237 262 : if (!skip && isPartitionedByColumnTable(mt) && strcmp(mt->part.pcol->base.name, col->base.name) == 0) {
238 158 : if (!next->semantics && ((lval && lval->isnull) || (hval && hval->isnull))) {
239 : skip = 1; /* NULL values don't match, skip them */
240 158 : } else if (next->semantics) {
241 : /* TODO NOT NULL prunning for partitions that just hold NULL values is still missing */
242 20 : skip |= next->flag == cmp_equal && !next->anti && lval && lval->isnull ? pd->with_nills == 0 : 0; /* *= NULL case */
243 : } else {
244 143 : if (isRangePartitionTable(mt)) {
245 109 : if (!rmin || !rmax) { /* initialize lazily */
246 109 : rmin = atom_general_ptr(v->sql->sa, &col->type, pd->part.range.minvalue);
247 109 : rmax = atom_general_ptr(v->sql->sa, &col->type, pd->part.range.maxvalue);
248 : }
249 :
250 : /* Prune range partitioned tables */
251 109 : if (rmin->isnull && rmax->isnull) {
252 0 : if (pd->with_nills == 1) /* the partition just holds null values, skip it */
253 143 : skip = 1;
254 : /* otherwise it holds all values in the range, cannot be pruned */
255 109 : } else if (rmin->isnull) { /* MINVALUE to limit */
256 4 : if (lval) {
257 4 : if (hval != lval) { /* range case */
258 : /* There's need to call range2lcompare, because the partition's upper limit is always exclusive */
259 2 : skip |= next->anti ? VALcmp(&(lval->data), &(rmax->data)) < 0 : VALcmp(&(lval->data), &(rmax->data)) >= 0;
260 : } else {
261 2 : switch (next->flag) { /* upper limit always exclusive */
262 2 : case cmp_equal:
263 : case cmp_gt:
264 : case cmp_gte:
265 2 : skip |= next->anti ? VALcmp(&(lval->data), &(rmax->data)) < 0 : VALcmp(&(lval->data), &(rmax->data)) >= 0;
266 2 : break;
267 : default:
268 : break;
269 : }
270 : }
271 0 : } else if (next->flag == cmp_in) {
272 0 : int nskip = 1;
273 0 : for (node *m = values->h; m && nskip; m = m->next) {
274 0 : atom *a = m->data;
275 :
276 0 : if (a->isnull)
277 0 : continue;
278 0 : nskip &= VALcmp(&(a->data), &(rmax->data)) >= 0;
279 : }
280 0 : skip |= nskip;
281 : }
282 105 : } else if (rmax->isnull) { /* limit to MAXVALUE */
283 29 : if (lval) {
284 26 : if (hval != lval) { /* range case */
285 17 : comp_type higher = range2rcompare(next->flag);
286 17 : if (higher == cmp_lt) {
287 6 : skip |= next->anti ? VALcmp(&(rmin->data), &(hval->data)) < 0 : VALcmp(&(rmin->data), &(hval->data)) >= 0;
288 11 : } else if (higher == cmp_lte) {
289 11 : skip |= next->anti ? VALcmp(&(rmin->data), &(hval->data)) <= 0 : VALcmp(&(rmin->data), &(hval->data)) > 0;
290 : } else {
291 0 : assert(0);
292 : }
293 : } else {
294 9 : switch (next->flag) {
295 2 : case cmp_lt:
296 2 : skip |= next->anti ? VALcmp(&(rmin->data), &(hval->data)) < 0 : VALcmp(&(rmin->data), &(hval->data)) >= 0;
297 2 : break;
298 6 : case cmp_equal:
299 : case cmp_lte:
300 6 : skip |= next->anti ? VALcmp(&(rmin->data), &(hval->data)) <= 0 : VALcmp(&(rmin->data), &(hval->data)) > 0;
301 6 : break;
302 : default:
303 : break;
304 : }
305 : }
306 3 : } else if (next->flag == cmp_in) {
307 3 : int nskip = 1;
308 10 : for (node *m = values->h; m && nskip; m = m->next) {
309 7 : atom *a = m->data;
310 :
311 7 : if (a->isnull)
312 0 : continue;
313 7 : nskip &= VALcmp(&(rmin->data), &(a->data)) > 0;
314 : }
315 3 : skip |= nskip;
316 : }
317 : } else { /* limit1 to limit2 (general case), limit2 is exclusive */
318 76 : bool max_differ_min = ATOMcmp(col->type.type->localtype, &rmin->data.val, &rmax->data.val) != 0;
319 :
320 76 : if (lval) {
321 68 : if (next->flag == cmp_equal) {
322 24 : skip |= next->anti ? exp_range_overlap(rmin, rmax, lval, hval, false, max_differ_min) != 0 :
323 12 : exp_range_overlap(rmin, rmax, lval, hval, false, max_differ_min) == 0;
324 56 : } else if (hval != lval) { /* For the between case */
325 40 : comp_type higher = range2rcompare(next->flag);
326 70 : skip |= next->anti ? exp_range_overlap(rmin, rmax, lval, hval, higher == cmp_lt, max_differ_min) != 0 :
327 30 : exp_range_overlap(rmin, rmax, lval, hval, higher == cmp_lt, max_differ_min) == 0;
328 : } else {
329 16 : switch (next->flag) {
330 4 : case cmp_gt:
331 4 : skip |= next->anti ? VALcmp(&(lval->data), &(rmax->data)) < 0 : VALcmp(&(lval->data), &(rmax->data)) >= 0;
332 4 : break;
333 2 : case cmp_gte:
334 2 : if (max_differ_min)
335 2 : skip |= next->anti ? VALcmp(&(lval->data), &(rmax->data)) < 0 : VALcmp(&(lval->data), &(rmax->data)) >= 0;
336 : else
337 0 : skip |= next->anti ? VALcmp(&(lval->data), &(rmax->data)) <= 0 : VALcmp(&(lval->data), &(rmax->data)) > 0;
338 : break;
339 2 : case cmp_lt:
340 2 : skip |= next->anti ? VALcmp(&(rmin->data), &(lval->data)) < 0 : VALcmp(&(rmin->data), &(lval->data)) >= 0;
341 2 : break;
342 8 : case cmp_lte:
343 8 : skip |= next->anti ? VALcmp(&(rmin->data), &(lval->data)) <= 0 : VALcmp(&(rmin->data), &(lval->data)) > 0;
344 8 : break;
345 : default:
346 : break;
347 : }
348 : }
349 8 : } else if (next->flag == cmp_in) {
350 8 : int nskip = 1;
351 20 : for (node *m = values->h; m && nskip; m = m->next) {
352 12 : atom *a = m->data;
353 :
354 12 : if (a->isnull)
355 0 : continue;
356 12 : nskip &= exp_range_overlap(rmin, rmax, a, a, false, max_differ_min) == 0;
357 : }
358 8 : skip |= nskip;
359 : }
360 : }
361 : }
362 :
363 143 : if (isListPartitionTable(mt) && (next->flag == cmp_equal || next->flag == cmp_in) && !next->anti) {
364 : /* if we find a value equal to one of the predicates, we don't prune */
365 : /* if the partition just holds null values, it will be skipped */
366 33 : if (!inlist) { /* initialize lazily */
367 32 : inlist = sa_list(v->sql->sa);
368 106 : for (node *m = pd->part.values->h; m; m = m->next) {
369 74 : sql_part_value *spv = (sql_part_value*) m->data;
370 74 : atom *pa = atom_general_ptr(v->sql->sa, &col->type, spv->value);
371 :
372 74 : list_append(inlist, pa);
373 : }
374 : }
375 :
376 33 : if (next->flag == cmp_equal) {
377 12 : int nskip = 1;
378 38 : for (node *m = inlist->h; m && nskip; m = m->next) {
379 26 : atom *pa = m->data;
380 26 : assert(!pa->isnull);
381 26 : nskip &= VALcmp(&(pa->data), &(lval->data)) != 0;
382 : }
383 12 : skip |= nskip;
384 21 : } else if (next->flag == cmp_in) {
385 50 : for (node *o = values->h; o && !skip; o = o->next) {
386 29 : atom *a = o->data;
387 29 : int nskip = 1;
388 :
389 29 : if (a->isnull)
390 0 : continue;
391 87 : for (node *m = inlist->h; m && nskip; m = m->next) {
392 58 : atom *pa = m->data;
393 58 : assert(!pa->isnull);
394 58 : nskip &= VALcmp(&(pa->data), &(a->data)) != 0;
395 : }
396 29 : skip |= nskip;
397 : }
398 : }
399 : }
400 : }
401 : }
402 : }
403 388 : i++;
404 : }
405 : }
406 : }
407 677 : if (!skip)
408 549 : append(tables, rel_rename_part(v->sql, rel_basetable(v->sql, pt, pt->base.name), mt_rel, mtalias));
409 : }
410 354 : if (list_empty(tables)) { /* No table passed the predicates, generate dummy relation */
411 18 : list *converted = sa_list(v->sql->sa);
412 18 : nrel = rel_project_exp(v->sql, exp_atom_bool(v->sql->sa, 1));
413 18 : nrel = rel_select(v->sql->sa, nrel, exp_atom_bool(v->sql->sa, 0));
414 18 : set_processed(nrel);
415 :
416 41 : for (node *n = mt_rel->exps->h ; n ; n = n->next) {
417 23 : sql_exp *e = n->data, *a = exp_atom(v->sql->sa, atom_general(v->sql->sa, exp_subtype(e), NULL, 0));
418 23 : exp_prop_alias(v->sql->sa, a, e);
419 23 : list_append(converted, a);
420 : }
421 18 : nrel = rel_project(v->sql->sa, nrel, converted);
422 : } else { /* Unionize children tables */
423 :
424 336 : if (mvc_debug_on(v->sql, 16)) {
425 : /* In case of a single table there in nothing to unionize */
426 0 : if (tables->cnt == 1) {
427 0 : nrel = rel_wrap_select_around_mt_child(v, tables->h->data, info);
428 : } else {
429 : //nrel = rel_unionize_mt_tables_balanced(v, mt_rel, tables, info);
430 0 : nrel = rel_setop_n_ary(v->sql->sa, tables, op_munion);
431 : }
432 336 : } else if (mvc_debug_on(v->sql, 32)) {
433 0 : for (node *n = tables->h; n ; n = n->next) {
434 0 : sql_rel *next = n->data;
435 0 : sql_table *subt = (sql_table *) next->l;
436 :
437 0 : if (isMergeTable(subt)) { /* apply select predicate recursively for nested merge tables */
438 0 : if (!(next = merge_table_prune_and_unionize(v, next, info)))
439 : return NULL;
440 0 : } else if (info) { /* propagate select under union */
441 0 : next = rel_select(v->sql->sa, next, NULL);
442 0 : next->exps = exps_copy(v->sql, info->sel->exps);
443 0 : set_processed(next);
444 : }
445 :
446 0 : if (nrel) {
447 0 : nrel = rel_setop(v->sql->sa, nrel, next, op_union);
448 0 : rel_setop_set_exps(v->sql, nrel, rel_projections(v->sql, mt_rel, NULL, 1, 1), true);
449 0 : set_processed(nrel);
450 : } else {
451 : nrel = next;
452 : }
453 : }
454 : } else {
455 336 : if (tables->cnt == 1) {
456 169 : nrel = rel_wrap_select_around_mt_child(v, tables->h->data, info);
457 : } else {
458 167 : nrel = rel_unionize_mt_tables_munion(v, mt_rel, tables, info);
459 : }
460 : }
461 : }
462 : return nrel;
463 : }
464 :
465 : /* rewrite merge tables into union of base tables */
466 : static sql_rel *
467 13382 : rel_merge_table_rewrite_(visitor *v, sql_rel *rel)
468 : {
469 13382 : if (is_modify(rel->op)) {
470 1113 : sql_query *query = query_create(v->sql);
471 1113 : return rel_propagate(query, rel, &v->changes);
472 : } else {
473 12269 : sql_rel *bt = rel, *sel = NULL, *nrel = NULL;
474 :
475 12269 : if (is_select(rel->op)) {
476 1937 : sel = rel;
477 1937 : bt = rel->l;
478 : }
479 12269 : if (is_basetable(bt->op) && rel_base_table(bt) && isMergeTable((sql_table*)bt->l)) {
480 620 : sql_table *mt = rel_base_table(bt);
481 620 : merge_table_prune_info *info = NULL;
482 :
483 620 : if (list_empty(mt->members)) /* in DDL statement cases skip if mergetable is empty */
484 : return rel;
485 330 : if (sel && !list_empty(sel->exps)) { /* prepare prunning information once */
486 105 : info = SA_NEW(v->sql->sa, merge_table_prune_info);
487 210 : *info = (merge_table_prune_info) {
488 105 : .cols = sa_list(v->sql->sa),
489 105 : .ranges = sa_list(v->sql->sa),
490 : .sel = sel
491 : };
492 220 : for (node *n = sel->exps->h; n; n = n->next) {
493 115 : sql_exp *e = n->data, *c = e->l;
494 115 : int flag = e->flag;
495 :
496 115 : if (e->type != e_cmp || (!is_theta_exp(flag) && flag != cmp_in) || is_symmetric(e) || !(c = rel_find_exp(rel, c)))
497 7 : continue;
498 :
499 108 : if (flag == cmp_gt || flag == cmp_gte || flag == cmp_lte || flag == cmp_lt || flag == cmp_equal) {
500 93 : sql_exp *l = e->r, *h = e->f;
501 93 : atom *lval = exp_flatten(v->sql, v->value_based_opt, l);
502 93 : atom *hval = h ? exp_flatten(v->sql, v->value_based_opt, h) : lval;
503 :
504 93 : if (lval && hval) {
505 91 : range_limit *next = SA_NEW(v->sql->sa, range_limit);
506 :
507 91 : *next = (range_limit) {
508 : .lval = lval,
509 : .hval = hval,
510 : .flag = flag,
511 91 : .anti = is_anti(e),
512 91 : .semantics = is_semantics(e),
513 : };
514 91 : list_append(info->cols, c);
515 91 : list_append(info->ranges, next);
516 : }
517 : }
518 108 : if (flag == cmp_in) { /* handle in lists */
519 15 : list *vals = e->r, *vlist = sa_list(v->sql->sa);
520 :
521 15 : node *m = NULL;
522 48 : for (m = vals->h; m; m = m->next) {
523 33 : sql_exp *l = m->data;
524 33 : atom *lval = exp_flatten(v->sql, v->value_based_opt, l);
525 :
526 33 : if (!lval)
527 : break;
528 33 : list_append(vlist, lval);
529 : }
530 15 : if (!m) {
531 15 : range_limit *next = SA_NEW(v->sql->sa, range_limit);
532 :
533 15 : *next = (range_limit) {
534 : .values = vlist, /* mark high as value list */
535 : .flag = flag,
536 15 : .anti = is_anti(e),
537 15 : .semantics = is_semantics(e),
538 : };
539 15 : list_append(info->cols, c);
540 15 : list_append(info->ranges, next);
541 : }
542 : }
543 : }
544 : }
545 330 : if (!(nrel = merge_table_prune_and_unionize(v, bt, info)))
546 : return NULL;
547 : /* Always do relation inplace. If the mt relation has more than 1 reference, this is required */
548 328 : if (is_union(nrel->op)) {
549 0 : rel = rel_inplace_setop(v->sql, rel, nrel->l, nrel->r, op_union, nrel->exps);
550 : } else if (is_munion(nrel->op)) {
551 150 : rel = rel_inplace_setop_n_ary(v->sql, rel, nrel->l, op_munion, nrel->exps);
552 : } else if (is_select(nrel->op)) {
553 49 : rel = rel_inplace_select(rel, nrel->l, nrel->exps);
554 : } else if (is_basetable(nrel->op)) {
555 111 : rel = rel_inplace_basetable(rel, nrel);
556 : } else {
557 0 : assert(is_simple_project(nrel->op));
558 18 : rel = rel_inplace_project(v->sql->sa, rel, nrel->l, nrel->exps);
559 18 : rel->card = exps_card(nrel->exps);
560 : }
561 : /* make sure that we do NOT destroy the subrels */
562 328 : nrel->l = nrel->r = NULL;
563 328 : rel_destroy(nrel);
564 328 : v->changes++;
565 : }
566 : }
567 : return rel;
568 : }
569 :
570 : static sql_rel *
571 1994 : rel_merge_table_rewrite(visitor *v, global_props *gp, sql_rel *rel)
572 : {
573 1994 : (void) gp;
574 1994 : return rel_visitor_topdown(v, rel, &rel_merge_table_rewrite_);
575 : }
576 :
577 : run_optimizer
578 626077 : bind_merge_table_rewrite(visitor *v, global_props *gp)
579 : {
580 626077 : (void) v;
581 626077 : return gp->needs_mergetable_rewrite ? rel_merge_table_rewrite : NULL;
582 : }
583 :
584 : /* these optimizers/rewriters run in a cycle loop */
585 : const sql_optimizer pre_sql_optimizers[] = {
586 : { 0, "split_select", bind_split_select},
587 : { 1, "push_project_down", bind_push_project_down},
588 : { 2, "merge_projects", bind_merge_projects},
589 : { 3, "push_project_up", bind_push_project_up},
590 : { 4, "split_project", bind_split_project},
591 : { 5, "remove_redundant_join", bind_remove_redundant_join},
592 : { 6, "simplify_math", bind_simplify_math},
593 : { 7, "optimize_exps", bind_optimize_exps},
594 : { 8, "optimize_select_and_joins_bottomup", bind_optimize_select_and_joins_bottomup},
595 : { 9, "project_reduce_casts", bind_project_reduce_casts},
596 : {10, "optimize_unions_bottomup", bind_optimize_unions_bottomup},
597 : {11, "optimize_projections", bind_optimize_projections},
598 : {12, "optimize_joins", bind_optimize_joins},
599 : {13, "join_order", bind_join_order},
600 : {14, "optimize_semi_and_anti", bind_optimize_semi_and_anti},
601 : {15, "optimize_select_and_joins_topdown", bind_optimize_select_and_joins_topdown},
602 : {16, "optimize_unions_topdown", bind_optimize_unions_topdown},
603 : {17, "dce", bind_dce},
604 : {18, "push_func_and_select_down", bind_push_func_and_select_down},
605 : {19, "push_topn_and_sample_down", bind_push_topn_and_sample_down},
606 : {20, "distinct_project2groupby", bind_distinct_project2groupby},
607 : {21, "merge_table_rewrite", bind_merge_table_rewrite},
608 : { 0, NULL, NULL}
609 : };
610 :
611 : /* these optimizers/rewriters only run once after the cycle loop */
612 : const sql_optimizer post_sql_optimizers[] = {
613 : /* Merge table rewrites may introduce remote or replica tables */
614 : /* At the moment, make sure the remote table rewriters always run after the merge table one */
615 : {23, "rewrite_remote", bind_rewrite_remote},
616 : {24, "rewrite_replica", bind_rewrite_replica},
617 : {25, "remote_func", bind_remote_func},
618 : {26, "get_statistics", bind_get_statistics}, /* gather statistics */
619 : {27, "join_order2", bind_join_order2}, /* run join order one more time with statistics */
620 : {28, "final_optimization_loop", bind_final_optimization_loop}, /* run select and group by order with statistics gathered */
621 : { 0, NULL, NULL}
622 : /* If an optimizer is going to be added, don't forget to update NSQLREWRITERS macro */
623 : };
624 :
625 :
626 : /* for trivial queries don't run optimizers */
627 : static int
628 794941 : calculate_opt_level(mvc *sql, sql_rel *rel)
629 : {
630 986331 : if (rel->card <= CARD_ATOM) {
631 774198 : if (is_insert(rel->op))
632 109809 : return rel->r ? calculate_opt_level(sql, rel->r) : 0;
633 664389 : if (is_simple_project(rel->op))
634 250635 : return rel->l ? calculate_opt_level(sql, rel->l) : 0;
635 : }
636 : return 1;
637 : }
638 :
639 : static inline sql_rel *
640 1344933 : run_optimizer_set(visitor *v, sql_optimizer_run *runs, sql_rel *rel, global_props *gp, const sql_optimizer *set)
641 : {
642 : /* if 'runs' is set, it means profiling is intended */
643 19431036 : for (int i = 0 ; set[i].name ; i++) {
644 18086112 : run_optimizer opt = NULL;
645 :
646 18086112 : if ((opt = set[i].bind_optimizer(v, gp))) {
647 3555765 : if (runs) {
648 0 : sql_optimizer_run *run = &(runs[set[i].index]);
649 0 : run->name = set[i].name;
650 0 : int changes = v->changes;
651 0 : lng clk = GDKusec();
652 0 : rel = opt(v, gp, rel);
653 0 : run->time += (GDKusec() - clk);
654 0 : run->nchanges += (v->changes - changes);
655 : } else {
656 3555765 : rel = opt(v, gp, rel);
657 : }
658 : }
659 : }
660 1344924 : return rel;
661 : }
662 :
663 : /* 'profile' means to benchmark each individual optimizer run */
664 : /* 'instantiate' means to rewrite logical tables: (merge, remote, replica tables) */
665 : static sql_rel *
666 718869 : rel_optimizer_one(mvc *sql, sql_rel *rel, int profile, int instantiate, int value_based_opt, int storage_based_opt)
667 : {
668 1437738 : global_props gp = (global_props) {.cnt = {0}, .instantiate = (uint8_t)instantiate, .opt_cycle = 0,
669 718869 : .has_special_modify = rel && is_modify(rel->op) && rel->flag&UPD_COMP};
670 718869 : visitor v = { .sql = sql, .value_based_opt = value_based_opt, .storage_based_opt = storage_based_opt, .changes = 1, .data = &gp };
671 :
672 718869 : sql->runs = !(ATOMIC_GET(&GDKdebug) & TESTINGMASK) && profile ? sa_zalloc(sql->sa, NSQLREWRITERS * sizeof(sql_optimizer_run)) : NULL;
673 1344945 : for ( ;rel && gp.opt_cycle < 20 && v.changes; gp.opt_cycle++) {
674 794939 : v.changes = 0;
675 794939 : gp = (global_props) {.cnt = {0}, .instantiate = (uint8_t)instantiate, .opt_cycle = gp.opt_cycle, .has_special_modify = gp.has_special_modify};
676 794939 : rel = rel_visitor_topdown(&v, rel, &rel_properties); /* collect relational tree properties */
677 794941 : gp.opt_level = calculate_opt_level(sql, rel);
678 794941 : if (gp.opt_level == 0 && !gp.needs_mergetable_rewrite)
679 : break;
680 626083 : rel = run_optimizer_set(&v, sql->runs, rel, &gp, pre_sql_optimizers);
681 : }
682 : #ifndef NDEBUG
683 718864 : assert(gp.opt_cycle < 20);
684 : #endif
685 :
686 : /* these optimizers run statistics gathered by the last optimization cycle */
687 718864 : rel = run_optimizer_set(&v, sql->runs, rel, &gp, post_sql_optimizers);
688 718863 : return rel;
689 : }
690 :
691 : static sql_exp *
692 298858 : exp_optimize_one(visitor *v, sql_rel *rel, sql_exp *e, int depth )
693 : {
694 298858 : (void)rel;
695 298858 : (void)depth;
696 298858 : if (e->type == e_psm && e->flag == PSM_REL && e->l) {
697 19339 : e->l = rel_optimizer_one(v->sql, e->l, 0, v->changes, v->value_based_opt, v->storage_based_opt);
698 : }
699 298858 : return e;
700 : }
701 :
702 : sql_rel *
703 722100 : rel_optimizer(mvc *sql, sql_rel *rel, int profile, int instantiate, int value_based_opt, int storage_based_opt)
704 : {
705 722100 : if (rel && rel->op == op_ddl && rel->flag == ddl_psm) {
706 22576 : if (!list_empty(rel->exps)) {
707 22510 : bool changed = 0;
708 22510 : visitor v = { .sql = sql, .value_based_opt = value_based_opt, .storage_based_opt = storage_based_opt, .changes = instantiate };
709 62300 : for(node *n = rel->exps->h; n; n = n->next) {
710 39790 : sql_exp *e = n->data;
711 39790 : exp_visitor(&v, rel, e, 1, exp_optimize_one, true, true, true, &changed);
712 : }
713 : }
714 22576 : return rel;
715 : } else {
716 699524 : return rel_optimizer_one(sql, rel, profile, instantiate, value_based_opt, storage_based_opt);
717 : }
718 : }
|
