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