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_exp.h"
17 : #include "rel_select.h"
18 :
19 : static void
20 0 : rel_no_rename_exps( list *exps )
21 : {
22 0 : for (node *n = exps->h; n; n = n->next) {
23 0 : sql_exp *e = n->data;
24 :
25 0 : exp_setalias(e, e->alias.label, e->l, e->r);
26 : }
27 0 : list_hash_clear(exps);
28 0 : }
29 :
30 : /* positional renames ! */
31 : /* get the names (aka aliases) from the src_exps list and rename the dest_exps list */
32 : void
33 81111 : rel_rename_exps( mvc *sql, list *src_exps, list *dest_exps)
34 : {
35 81111 : node *n, *m;
36 :
37 81111 : (void)sql;
38 : /* check if a column uses an alias earlier in the list */
39 :
40 81111 : assert(list_length(src_exps) <= list_length(dest_exps));
41 681153 : for (n = src_exps->h, m = dest_exps->h; n && m; n = n->next, m = m->next) {
42 600042 : sql_exp *s = n->data;
43 600042 : sql_exp *d = m->data;
44 600042 : const char *rname = exp_relname(s);
45 :
46 600042 : exp_setalias(d, s->alias.label, rname, exp_name(s));
47 : }
48 81111 : list_hash_clear(dest_exps);
49 81111 : }
50 :
51 : sql_rel *
52 223337 : rel_find_ref( sql_rel *r)
53 : {
54 679860 : while (!rel_is_ref(r) && r->l &&
55 588133 : (is_project(r->op) || is_select(r->op) /*|| is_join(r->op)*/))
56 : r = r->l;
57 223337 : if (rel_is_ref(r))
58 81704 : return r;
59 : return NULL;
60 : }
61 :
62 : /* merge projection */
63 :
64 : /* push an expression through a projection.
65 : * The result should again be used in a projection.
66 : */
67 : static list *
68 56060 : exps_push_down_prj(mvc *sql, list *exps, sql_rel *f, sql_rel *t, bool keepalias)
69 : {
70 56060 : node *n;
71 56060 : list *nl = new_exp_list(sql->sa);
72 :
73 194767 : for(n = exps->h; n; n = n->next) {
74 141090 : sql_exp *arg = n->data, *narg = NULL;
75 :
76 141090 : narg = exp_push_down_prj(sql, arg, f, t);
77 141090 : if (!narg)
78 : return NULL;
79 138707 : narg = exp_propagate(sql->sa, narg, arg);
80 138707 : if (!keepalias && narg->type == e_column)
81 39765 : exp_setalias(narg, arg->alias.label, narg->l, narg->r);
82 138707 : append(nl, narg);
83 : }
84 : return nl;
85 : }
86 :
87 : sql_exp *
88 2716019 : exp_push_down_prj(mvc *sql, sql_exp *e, sql_rel *f, sql_rel *t)
89 : {
90 2716019 : sql_exp *ne = NULL, *l = NULL, *r = NULL, *r2 = NULL;
91 :
92 2716019 : assert(is_project(f->op));
93 :
94 2716019 : switch(e->type) {
95 2288051 : case e_column:
96 2288051 : assert(e->nid);
97 2288051 : ne = exps_bind_nid(f->exps, e->nid);
98 2288051 : if (!ne || (ne->type != e_column && (ne->type != e_atom || ne->f)))
99 : return NULL;
100 1952908 : while (ne && (has_label(ne) || is_selfref(ne) /*inside this list */) && is_simple_project(f->op) && ne->type == e_column) {
101 11905 : sql_exp *oe = e, *one = ne;
102 :
103 11905 : e = ne;
104 11905 : ne = NULL;
105 11905 : if (e->nid)
106 11905 : ne = exps_bind_nid(f->exps, e->nid);
107 11905 : if (ne && ne != one && list_position(f->exps, ne) >= list_position(f->exps, one))
108 11905 : ne = NULL;
109 11905 : if (!ne || ne == one) {
110 : ne = one;
111 1952509 : e = oe;
112 : break;
113 : }
114 399 : if (ne->type != e_column && (ne->type != e_atom || ne->f))
115 : return NULL;
116 : }
117 : /* possibly a groupby/project column is renamed */
118 1952509 : if (is_groupby(f->op) && !list_empty(f->r) && ne->type == e_column) {
119 131 : sql_exp *gbe = NULL;
120 131 : if (ne->nid)
121 131 : gbe = exps_bind_nid(f->exps, ne->nid);
122 131 : ne = gbe;
123 131 : if (!ne || (ne->type != e_column && (ne->type != e_atom || ne->f)))
124 0 : return NULL;
125 : }
126 1952509 : return exp_copy(sql, ne);
127 58819 : case e_cmp:
128 58819 : if (e->flag == cmp_or || e->flag == cmp_filter) {
129 3509 : list *l = NULL, *r = NULL;
130 :
131 3509 : if (!(l = exps_push_down_prj(sql, e->l, f, t, true)) || !(r = exps_push_down_prj(sql, e->r, f, t, true)))
132 1226 : return NULL;
133 2283 : if (e->flag == cmp_filter) {
134 1013 : ne = exp_filter(sql->sa, l, r, e->f, is_anti(e));
135 : } else {
136 1270 : ne = exp_or(sql->sa, l, r, is_anti(e));
137 : }
138 55310 : } else if (e->flag == cmp_in || e->flag == cmp_notin) {
139 5720 : list *r = NULL;
140 :
141 5720 : if (!(l = exp_push_down_prj(sql, e->l, f, t)) || !(r = exps_push_down_prj(sql, e->r, f, t, true)))
142 5213 : return NULL;
143 507 : ne = exp_in(sql->sa, l, r, e->flag);
144 : } else {
145 49590 : if (!(l = exp_push_down_prj(sql, e->l, f, t)) || !(r = exp_push_down_prj(sql, e->r, f, t)) || (e->f && !(r2 = exp_push_down_prj(sql, e->f, f, t))))
146 24159 : return NULL;
147 25431 : if (e->f) {
148 741 : ne = exp_compare2(sql->sa, l, r, r2, e->flag, is_symmetric(e));
149 : } else {
150 24690 : ne = exp_compare(sql->sa, l, r, e->flag);
151 : }
152 : }
153 28221 : if (!ne)
154 : return NULL;
155 28221 : return exp_propagate(sql->sa, ne, e);
156 218026 : case e_convert:
157 218026 : if (!(l = exp_push_down_prj(sql, e->l, f, t)))
158 : return NULL;
159 148349 : ne = exp_convert(sql, l, exp_fromtype(e), exp_totype(e));
160 148349 : return exp_propagate(sql->sa, ne, e);
161 48857 : case e_aggr:
162 : case e_func: {
163 48857 : list *l = e->l, *nl = NULL;
164 48857 : sql_exp *ne = NULL;
165 :
166 48857 : if (e->type == e_func && exp_unsafe(e, false, false))
167 : return NULL;
168 48841 : if (!list_empty(l)) {
169 48841 : nl = exps_push_down_prj(sql, l, f, t, false);
170 48841 : if (!nl)
171 : return NULL;
172 : }
173 47694 : if (e->type == e_func)
174 47694 : ne = exp_op(sql->sa, nl, e->f);
175 : else
176 0 : ne = exp_aggr(sql->sa, nl, e->f, need_distinct(e), need_no_nil(e), e->card, has_nil(e));
177 47694 : return exp_propagate(sql->sa, ne, e);
178 : }
179 102266 : case e_atom: {
180 102266 : list *l = e->f, *nl = NULL;
181 :
182 102266 : if (!list_empty(l)) {
183 766 : nl = exps_push_down_prj(sql, l, f, t, false);
184 766 : if (!nl)
185 : return NULL;
186 756 : ne = exp_values(sql->sa, nl);
187 : } else {
188 101500 : ne = exp_copy(sql, e);
189 : }
190 102256 : return exp_propagate(sql->sa, ne, e);
191 : }
192 : case e_psm:
193 : if (e->type == e_atom && e->f) /* value list */
194 : return NULL;
195 : return e;
196 : }
197 : return NULL;
198 : }
199 :
200 : atom *
201 628 : exp_flatten(mvc *sql, bool value_based_opt, sql_exp *e)
202 : {
203 628 : if (e->type == e_atom) {
204 379 : return value_based_opt ? exp_value(sql, e) : (atom *) e->l;
205 249 : } else if (e->type == e_convert) {
206 51 : atom *v = exp_flatten(sql, value_based_opt, e->l);
207 :
208 51 : if (v)
209 24 : return atom_cast(sql->sa, v, exp_subtype(e));
210 198 : } else if (e->type == e_func) {
211 198 : sql_subfunc *f = e->f;
212 198 : list *l = e->l;
213 198 : sql_arg *res = (f->func->res)?(f->func->res->h->data):NULL;
214 :
215 : /* TODO handle date + x months */
216 198 : if (!f->func->s && strcmp(f->func->base.name, "sql_add") == 0 && list_length(l) == 2 && res && EC_NUMBER(res->type.type->eclass)) {
217 24 : atom *l1 = exp_flatten(sql, value_based_opt, l->h->data);
218 24 : atom *l2 = exp_flatten(sql, value_based_opt, l->h->next->data);
219 24 : if (l1 && l2)
220 3 : return atom_add(sql->sa, l1, l2);
221 174 : } else if (!f->func->s && strcmp(f->func->base.name, "sql_sub") == 0 && list_length(l) == 2 && res && EC_NUMBER(res->type.type->eclass)) {
222 10 : atom *l1 = exp_flatten(sql, value_based_opt, l->h->data);
223 10 : atom *l2 = exp_flatten(sql, value_based_opt, l->h->next->data);
224 10 : if (l1 && l2)
225 9 : return atom_sub(sql->sa, l1, l2);
226 : }
227 : }
228 : return NULL;
229 : }
230 :
231 : int
232 150 : exp_range_overlap(atom *min, atom *max, atom *emin, atom *emax, bool min_exclusive, bool max_exclusive)
233 : {
234 150 : if (!min || !max || !emin || !emax || min->isnull || max->isnull || emin->isnull || emax->isnull)
235 : return 0;
236 :
237 150 : if ((!min_exclusive && VALcmp(&(emax->data), &(min->data)) < 0) || (min_exclusive && VALcmp(&(emax->data), &(min->data)) <= 0))
238 29 : return 0;
239 121 : if ((!max_exclusive && VALcmp(&(emin->data), &(max->data)) > 0) || (max_exclusive && VALcmp(&(emin->data), &(max->data)) >= 0))
240 34 : return 0;
241 : return 1;
242 : }
243 :
244 :
245 : /* if local_proj is >= -1, the current expression is from the same projection
246 : if local_proj is -1, then we don't care about self references (eg used to check for order by exps) */
247 : static int exp_mark_used(sql_rel *subrel, sql_exp *e, int local_proj);
248 :
249 : static int
250 800063 : exps_mark_used(sql_rel *subrel, list *l, int local_proj)
251 : {
252 800063 : int nr = 0;
253 800063 : if (list_empty(l))
254 : return nr;
255 :
256 2586390 : for (node *n = l->h; n != NULL; n = n->next)
257 1786391 : nr += exp_mark_used(subrel, n->data, local_proj);
258 : return nr;
259 : }
260 :
261 : static int
262 6932482 : exp_mark_used(sql_rel *subrel, sql_exp *e, int local_proj)
263 : {
264 7143809 : int nr = 0;
265 7143809 : sql_exp *ne = NULL;
266 :
267 7143809 : switch(e->type) {
268 4725398 : case e_column:
269 4725398 : ne = rel_find_exp(subrel, e);
270 : /* if looking in the same projection, make sure 'ne' is projected before the searched column */
271 4725406 : if (ne && local_proj > -1 && list_position(subrel->exps, ne) >= local_proj)
272 5930279 : ne = NULL;
273 : break;
274 211327 : case e_convert:
275 211327 : return exp_mark_used(subrel, e->l, local_proj);
276 762466 : case e_aggr:
277 : case e_func: {
278 762466 : if (e->l)
279 730599 : nr += exps_mark_used(subrel, e->l, local_proj);
280 762466 : assert(!e->r);
281 : break;
282 : }
283 442407 : case e_cmp:
284 442407 : if (e->flag == cmp_or || e->flag == cmp_filter) {
285 21256 : nr += exps_mark_used(subrel, e->l, local_proj);
286 21256 : nr += exps_mark_used(subrel, e->r, local_proj);
287 421151 : } else if (e->flag == cmp_in || e->flag == cmp_notin) {
288 21189 : nr += exp_mark_used(subrel, e->l, local_proj);
289 21189 : nr += exps_mark_used(subrel, e->r, local_proj);
290 : } else {
291 399962 : nr += exp_mark_used(subrel, e->l, local_proj);
292 399962 : nr += exp_mark_used(subrel, e->r, local_proj);
293 399962 : if (e->f)
294 6432 : nr += exp_mark_used(subrel, e->f, local_proj);
295 : }
296 : break;
297 1002211 : case e_atom:
298 : /* atoms are used in e_cmp */
299 1002211 : e->used = 1;
300 : /* return 0 as constants may require a full column ! */
301 1002211 : if (e->f)
302 5763 : nr += exps_mark_used(subrel, e->f, local_proj);
303 : return nr;
304 0 : case e_psm:
305 0 : if (e->flag & PSM_SET || e->flag & PSM_RETURN || e->flag & PSM_EXCEPTION) {
306 0 : nr += exp_mark_used(subrel, e->l, local_proj);
307 0 : } else if (e->flag & PSM_WHILE || e->flag & PSM_IF) {
308 0 : nr += exp_mark_used(subrel, e->l, local_proj);
309 0 : nr += exps_mark_used(subrel, e->r, local_proj);
310 0 : if (e->flag == PSM_IF && e->f)
311 0 : nr += exps_mark_used(subrel, e->f, local_proj);
312 : }
313 0 : e->used = 1;
314 0 : break;
315 : }
316 5930279 : if (ne && e != ne) {
317 2576288 : if (local_proj == -2 || ne->type != e_column || (has_label(ne) || (ne->alias.rname && ne->alias.rname[0] == '%')) || (subrel->l && !is_munion(subrel->op) && !rel_find_exp(subrel->l, e)))
318 2452141 : ne->used = 1;
319 2576288 : return ne->used;
320 : }
321 : return nr;
322 : }
323 :
324 : static void
325 44531 : positional_exps_mark_used( sql_rel *rel, sql_rel *subrel )
326 : {
327 44531 : assert(rel->exps);
328 :
329 44531 : if ((is_topn(subrel->op) || is_sample(subrel->op)) && subrel->l)
330 44531 : subrel = subrel->l;
331 : /* everything is used within the set operation */
332 44531 : if (rel->exps && subrel->exps) {
333 44531 : node *m;
334 376837 : for (m=subrel->exps->h; m; m = m->next) {
335 332306 : sql_exp *se = m->data;
336 :
337 332306 : se->used = 1;
338 : }
339 : }
340 44531 : }
341 :
342 : static void
343 767910 : rel_exps_mark_used(allocator *sa, sql_rel *rel, sql_rel *subrel)
344 : {
345 767910 : int nr = 0;
346 :
347 767910 : if (rel->r && (is_simple_project(rel->op) || is_groupby(rel->op))) {
348 32408 : list *l = rel->r;
349 32408 : node *n;
350 :
351 111386 : for (n=l->h; n; n = n->next) {
352 78978 : sql_exp *e = n->data;
353 :
354 78978 : e->used = 1;
355 78978 : exp_mark_used(rel, e, -1);
356 : }
357 : }
358 767910 : if (rel->attr) {
359 26212 : for (node *n = rel->attr->h; n; n = n->next) {
360 13106 : sql_exp *e = n->data;
361 :
362 13106 : if (e->type != e_aggr) /* keep all group by's */
363 13106 : e->used = 1;
364 13106 : if (e->used)
365 13106 : nr += exp_mark_used(subrel, e, -2);
366 : }
367 : }
368 767910 : if (rel->exps) {
369 728915 : node *n;
370 728915 : int len = list_length(rel->exps), i;
371 728915 : sql_exp **exps = SA_NEW_ARRAY(sa, sql_exp*, len);
372 :
373 3584302 : for (n=rel->exps->h, i = 0; n; n = n->next, i++) {
374 2855387 : sql_exp *e = exps[i] = n->data;
375 :
376 2855387 : nr += e->used;
377 : }
378 :
379 728915 : if (!nr && is_project(rel->op) && len > 0) /* project at least one column if exists */
380 6657 : exps[0]->used = 1;
381 :
382 3584309 : for (i = len-1; i >= 0; i--) {
383 2855394 : sql_exp *e = exps[i];
384 :
385 2855394 : if (!is_project(rel->op) || (e->used && !is_set(rel->op))) {
386 2283176 : if (is_project(rel->op))
387 1864172 : nr += exp_mark_used(rel, e, i);
388 2283178 : nr += exp_mark_used(subrel, e, -2);
389 : }
390 : }
391 : }
392 : /* for count/rank we need at least one column */
393 767910 : if (!nr && subrel && (is_project(subrel->op) || is_base(subrel->op)) && !list_empty(subrel->exps) &&
394 23987 : (is_simple_project(rel->op) && project_unsafe(rel, false))) {
395 34 : sql_exp *e = subrel->exps->h->data;
396 34 : e->used = 1;
397 : }
398 767910 : if (rel->r && (is_simple_project(rel->op) || is_groupby(rel->op))) {
399 32408 : list *l = rel->r;
400 32408 : node *n;
401 :
402 111386 : for (n=l->h; n; n = n->next) {
403 78978 : sql_exp *e = n->data;
404 :
405 78978 : e->used = 1;
406 : /* possibly project/groupby uses columns from the inner */
407 78978 : exp_mark_used(subrel, e, -2);
408 : }
409 : }
410 767910 : }
411 :
412 : static void exps_used(list *l);
413 :
414 : static void
415 3546482 : exp_used(sql_exp *e)
416 : {
417 3578122 : if (e) {
418 3559678 : e->used = 1;
419 :
420 3559678 : switch (e->type) {
421 30444 : case e_convert:
422 30444 : exp_used(e->l);
423 30444 : break;
424 97232 : case e_func:
425 : case e_aggr:
426 97232 : exps_used(e->l);
427 97232 : break;
428 7919 : case e_cmp:
429 7919 : if (e->flag == cmp_or || e->flag == cmp_filter) {
430 1042 : exps_used(e->l);
431 1042 : exps_used(e->r);
432 6877 : } else if (e->flag == cmp_in || e->flag == cmp_notin) {
433 232 : exp_used(e->l);
434 232 : exps_used(e->r);
435 : } else {
436 6645 : exp_used(e->l);
437 6645 : exp_used(e->r);
438 6645 : if (e->f)
439 : exp_used(e->f);
440 : }
441 : break;
442 : default:
443 : break;
444 : }
445 : }
446 3546482 : }
447 :
448 : static void
449 887394 : exps_used(list *l)
450 : {
451 887394 : if (l) {
452 4419140 : for (node *n = l->h; n; n = n->next)
453 3531872 : exp_used(n->data);
454 : }
455 887391 : }
456 :
457 : static void
458 825197 : rel_used(sql_rel *rel)
459 : {
460 825197 : if (!rel)
461 : return;
462 781393 : if (is_join(rel->op) || is_set(rel->op) || is_semi(rel->op) || is_modify(rel->op)) {
463 73161 : rel_used(rel->l);
464 73158 : rel_used(rel->r);
465 : } else if (rel->op == op_munion) {
466 11967 : list *l = rel->l;
467 36316 : for(node *n = l->h; n; n = n->next)
468 24349 : rel_used(n->data);
469 : } else if (is_topn(rel->op) || is_select(rel->op) || is_sample(rel->op)) {
470 20697 : rel_used(rel->l);
471 20696 : rel = rel->l;
472 : } else if (is_ddl(rel->op)) {
473 404654 : if (rel->flag == ddl_output || rel->flag == ddl_create_seq || rel->flag == ddl_alter_seq || rel->flag == ddl_alter_table || rel->flag == ddl_create_table || rel->flag == ddl_create_view) {
474 36945 : rel_used(rel->l);
475 : } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
476 282 : rel_used(rel->l);
477 282 : rel_used(rel->r);
478 : } else if (rel->flag == ddl_psm) {
479 7 : exps_used(rel->exps);
480 : }
481 : } else if (rel->op == op_table) {
482 1090 : if (IS_TABLE_PROD_FUNC(rel->flag) || rel->flag == TABLE_FROM_RELATION)
483 1090 : rel_used(rel->l);
484 1090 : exp_used(rel->r);
485 : }
486 892871 : if (rel && rel->exps) {
487 768327 : exps_used(rel->exps);
488 768322 : if (rel->r && (is_simple_project(rel->op) || is_groupby(rel->op)))
489 19513 : exps_used(rel->r);
490 : }
491 : }
492 :
493 : static void
494 1265543 : rel_mark_used(mvc *sql, sql_rel *rel, int proj)
495 : {
496 1879535 : if (proj && (need_distinct(rel)))
497 10169 : rel_used(rel);
498 :
499 1879536 : switch(rel->op) {
500 : case op_basetable:
501 : case op_truncate:
502 : case op_insert:
503 : break;
504 :
505 13412 : case op_table:
506 :
507 13412 : if (rel->l && rel->flag != TRIGGER_WRAPPER) {
508 144 : rel_used(rel);
509 144 : if (rel->r)
510 144 : exp_mark_used(rel->l, rel->r, -2);
511 144 : rel_mark_used(sql, rel->l, proj);
512 : }
513 : break;
514 :
515 16692 : case op_topn:
516 : case op_sample:
517 16692 : if (proj) {
518 16609 : rel = rel ->l;
519 16609 : rel_mark_used(sql, rel, proj);
520 16609 : break;
521 : }
522 : /* fall through */
523 : case op_project:
524 : case op_groupby:
525 514471 : if (proj && rel->l) {
526 294269 : rel_exps_mark_used(sql->sa, rel, rel->l);
527 294269 : rel_mark_used(sql, rel->l, 0);
528 10968 : } else if (proj) {
529 10885 : rel_exps_mark_used(sql->sa, rel, NULL);
530 : }
531 : break;
532 7746 : case op_update:
533 : case op_delete:
534 7746 : if (proj && rel->r) {
535 6192 : rel_used(rel);
536 6192 : sql_rel *r = rel->r;
537 :
538 6192 : if (!list_empty(r->exps)) {
539 7292 : for (node *n = r->exps->h; n; n = n->next) {
540 6193 : sql_exp *e = n->data;
541 6193 : const char *nname = exp_name(e);
542 :
543 6193 : if (nname && nname[0] == '%' && strcmp(nname, TID) == 0) { /* TID is used */
544 5093 : e->used = 1;
545 5093 : break;
546 : }
547 : }
548 : }
549 6192 : rel_exps_mark_used(sql->sa, rel, rel->r);
550 6192 : rel_mark_used(sql, rel->r, 0);
551 : }
552 : break;
553 :
554 400854 : case op_ddl:
555 400854 : if (rel->flag == ddl_output || rel->flag == ddl_create_seq || rel->flag == ddl_alter_seq || rel->flag == ddl_alter_table || rel->flag == ddl_create_table || rel->flag == ddl_create_view) {
556 33145 : if (rel->l)
557 : rel_mark_used(sql, rel->l, 0);
558 : } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
559 282 : if (rel->l)
560 282 : rel_mark_used(sql, rel->l, 0);
561 282 : if (rel->r)
562 : rel_mark_used(sql, rel->r, 0);
563 : }
564 : break;
565 :
566 109825 : case op_select:
567 109825 : if (rel->l) {
568 109825 : rel_exps_mark_used(sql->sa, rel, rel->l);
569 109825 : rel_mark_used(sql, rel->l, 0);
570 : }
571 : break;
572 :
573 5144 : case op_union:
574 : case op_inter:
575 : case op_except:
576 : /* For now we mark all union expression as used */
577 :
578 : /* Later we should (in case of union all) remove unused
579 : * columns from the projection.
580 : *
581 : * Project part of union is based on column position.
582 : */
583 5144 : if (proj && (need_distinct(rel) || !rel->exps)) {
584 2334 : rel_used(rel);
585 2334 : if (!rel->exps) {
586 0 : rel_used(rel->l);
587 0 : rel_used(rel->r);
588 : }
589 2334 : rel_mark_used(sql, rel->l, 0);
590 2334 : rel_mark_used(sql, rel->r, 0);
591 482 : } else if (proj && !need_distinct(rel)) {
592 482 : sql_rel *l = rel->l;
593 :
594 482 : positional_exps_mark_used(rel, l);
595 482 : rel_exps_mark_used(sql->sa, rel, l);
596 482 : rel_mark_used(sql, rel->l, 0);
597 : /* based on child check set expression list */
598 482 : if (is_project(l->op) && need_distinct(l))
599 0 : positional_exps_mark_used(l, rel);
600 482 : positional_exps_mark_used(rel, rel->r);
601 482 : rel_exps_mark_used(sql->sa, rel, rel->r);
602 482 : rel_mark_used(sql, rel->r, 0);
603 : }
604 : break;
605 :
606 48498 : case op_munion:
607 48498 : assert(rel->l);
608 : // TODO: here we blindly follow the same logic as op_union. RE-evaluate
609 48498 : if (proj && (need_distinct(rel) || !rel->exps)) {
610 1980 : rel_used(rel);
611 1980 : if (!rel->exps) {
612 0 : for (node *n = ((list*)rel->l)->h; n; n = n->next) {
613 0 : rel_used(n->data);
614 0 : rel_mark_used(sql, n->data, 0);
615 : }
616 : }
617 21620 : } else if (proj && !need_distinct(rel)) {
618 21620 : bool first = true;
619 65187 : for (node *n = ((list*)rel->l)->h; n; n = n->next) {
620 43567 : sql_rel *l = n->data;
621 :
622 43567 : positional_exps_mark_used(rel, l);
623 43567 : rel_exps_mark_used(sql->sa, rel, l);
624 43567 : rel_mark_used(sql, l, 0);
625 : /* based on child check set expression list */
626 43567 : if (first && is_project(l->op) && need_distinct(l))
627 0 : positional_exps_mark_used(l, rel);
628 43567 : first = false;
629 : }
630 : }
631 : break;
632 151104 : case op_join:
633 : case op_left:
634 : case op_right:
635 : case op_full:
636 : case op_semi:
637 : case op_anti:
638 : case op_merge:
639 151104 : rel_exps_mark_used(sql->sa, rel, rel->l);
640 151104 : rel_exps_mark_used(sql->sa, rel, rel->r);
641 151104 : rel_mark_used(sql, rel->l, 0);
642 151104 : rel_mark_used(sql, rel->r, 0);
643 151104 : break;
644 : }
645 1265544 : }
646 :
647 : static sql_rel * rel_dce_sub(mvc *sql, sql_rel *rel);
648 :
649 : static sql_rel *
650 1124234 : rel_remove_unused(mvc *sql, sql_rel *rel)
651 : {
652 1124234 : int needed = 0;
653 :
654 1124234 : if (!rel)
655 : return rel;
656 :
657 1117375 : switch(rel->op) {
658 302597 : case op_basetable: {
659 302597 : sql_table *t = rel->l;
660 :
661 302597 : if (t && isReplicaTable(t)) /* TODO fix rewriting in rel_distribute.c */
662 : return rel;
663 : }
664 : /* fall through */
665 : case op_table:
666 309436 : if (rel->exps && (rel->op != op_table || !IS_TABLE_PROD_FUNC(rel->flag))) {
667 1347241 : for(node *n=rel->exps->h; n && !needed; n = n->next) {
668 1044664 : sql_exp *e = n->data;
669 :
670 1044664 : if (!e->used)
671 227309 : needed = 1;
672 : }
673 :
674 302577 : if (!needed)
675 : return rel;
676 :
677 1344115 : for(node *n=rel->exps->h; n;) {
678 1116806 : node *next = n->next;
679 1116806 : sql_exp *e = n->data;
680 :
681 : /* at least one (needed for crossproducts, count(*), rank() and single value projections) !, handled by rel_exps_mark_used */
682 1116806 : if (!e->used && list_length(rel->exps) > 1)
683 377214 : list_remove_node(rel->exps, NULL, n);
684 : n = next;
685 : }
686 : }
687 234168 : if (rel->op == op_table && (IS_TABLE_PROD_FUNC(rel->flag) || rel->flag == TABLE_FROM_RELATION))
688 6859 : rel->l = rel_remove_unused(sql, rel->l);
689 : return rel;
690 :
691 16610 : case op_topn:
692 : case op_sample:
693 :
694 16610 : if (rel->l)
695 16610 : rel->l = rel_remove_unused(sql, rel->l);
696 : return rel;
697 :
698 305166 : case op_project:
699 : case op_groupby:
700 :
701 305166 : if (/*rel->l &&*/ rel->exps) {
702 1912142 : for(node *n=rel->exps->h; n && !needed; n = n->next) {
703 1606976 : sql_exp *e = n->data;
704 :
705 1606976 : if (!e->used)
706 25461 : needed = 1;
707 : }
708 305166 : if (!needed)
709 : return rel;
710 :
711 589240 : for(node *n=rel->exps->h; n;) {
712 563779 : node *next = n->next;
713 563779 : sql_exp *e = n->data;
714 :
715 : /* at least one (needed for crossproducts, count(*), rank() and single value projections) */
716 563779 : if (!e->used && list_length(rel->exps) > 1)
717 427979 : list_remove_node(rel->exps, NULL, n);
718 : n = next;
719 : }
720 : }
721 : return rel;
722 :
723 3150 : case op_join:
724 : case op_left:
725 : case op_right:
726 : case op_full:
727 3150 : if (list_length(rel->attr) > 1) {
728 0 : for(node *n=rel->attr->h; n && !needed; n = n->next) {
729 0 : sql_exp *e = n->data;
730 :
731 0 : if (!e->used)
732 0 : needed = 1;
733 : }
734 0 : if (!needed)
735 : return rel;
736 :
737 0 : for(node *n=rel->attr->h; n;) {
738 0 : node *next = n->next;
739 0 : sql_exp *e = n->data;
740 :
741 0 : if (!e->used)
742 0 : list_remove_node(rel->attr, NULL, n);
743 : n = next;
744 : }
745 : }
746 : return rel;
747 :
748 : case op_union:
749 : case op_inter:
750 : case op_except:
751 : case op_munion:
752 :
753 : case op_insert:
754 : case op_update:
755 : case op_delete:
756 : case op_truncate:
757 : case op_merge:
758 :
759 : case op_select:
760 :
761 : case op_semi:
762 : case op_anti:
763 : return rel;
764 400538 : case op_ddl:
765 400538 : if (rel->flag == ddl_output || rel->flag == ddl_create_seq || rel->flag == ddl_alter_seq || rel->flag == ddl_alter_table || rel->flag == ddl_create_table || rel->flag == ddl_create_view) {
766 32873 : if (rel->l)
767 32513 : rel->l = rel_remove_unused(sql, rel->l);
768 : } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
769 238 : if (rel->l)
770 238 : rel->l = rel_remove_unused(sql, rel->l);
771 238 : if (rel->r)
772 238 : rel->r = rel_remove_unused(sql, rel->r);
773 : }
774 : return rel;
775 : }
776 : return rel;
777 : }
778 :
779 : static void
780 1311893 : rel_dce_refs(mvc *sql, sql_rel *rel, list *refs)
781 : {
782 1311893 : if (!rel || (rel_is_ref(rel) && list_find(refs, rel, NULL)))
783 14170 : return ;
784 :
785 1297723 : switch(rel->op) {
786 401540 : case op_table:
787 : case op_topn:
788 : case op_sample:
789 : case op_project:
790 : case op_groupby:
791 : case op_select:
792 :
793 401540 : if (rel->l && (rel->op != op_table || rel->flag != TRIGGER_WRAPPER))
794 385559 : rel_dce_refs(sql, rel->l, refs);
795 : break;
796 :
797 : case op_basetable:
798 : case op_insert:
799 : case op_truncate:
800 : break;
801 :
802 6544 : case op_update:
803 : case op_delete:
804 :
805 6544 : if (rel->r)
806 6192 : rel_dce_refs(sql, rel->r, refs);
807 : break;
808 :
809 144523 : case op_union:
810 : case op_inter:
811 : case op_except:
812 : case op_join:
813 : case op_left:
814 : case op_right:
815 : case op_full:
816 : case op_semi:
817 : case op_anti:
818 : case op_merge:
819 :
820 144523 : if (rel->l)
821 144523 : rel_dce_refs(sql, rel->l, refs);
822 144523 : if (rel->r)
823 144523 : rel_dce_refs(sql, rel->r, refs);
824 : break;
825 22887 : case op_munion:
826 22887 : assert(rel->l);
827 69281 : for (node *n = ((list*)rel->l)->h; n; n = n->next)
828 46394 : rel_dce_refs(sql, n->data, refs);
829 : break;
830 401953 : case op_ddl:
831 :
832 401953 : if (rel->flag == ddl_output || rel->flag == ddl_create_seq || rel->flag == ddl_alter_seq || rel->flag == ddl_alter_table || rel->flag == ddl_create_table || rel->flag == ddl_create_view) {
833 34244 : if (rel->l)
834 33884 : rel_dce_refs(sql, rel->l, refs);
835 : } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
836 282 : if (rel->l)
837 282 : rel_dce_refs(sql, rel->l, refs);
838 282 : if (rel->r)
839 248 : rel_dce_refs(sql, rel->r, refs);
840 : } break;
841 : }
842 :
843 1297723 : if (rel_is_ref(rel) && !list_find(refs, rel, NULL))
844 16669 : list_prepend(refs, rel);
845 : }
846 :
847 : static sql_rel *
848 1868921 : rel_dce_down(mvc *sql, sql_rel *rel, int skip_proj)
849 : {
850 1868921 : if (!rel)
851 : return rel;
852 :
853 1868921 : if (!skip_proj && rel_is_ref(rel))
854 : return rel;
855 :
856 1838619 : switch(rel->op) {
857 553709 : case op_basetable:
858 : case op_table:
859 :
860 553709 : if (skip_proj && rel->l && rel->op == op_table && rel->flag != TRIGGER_WRAPPER)
861 83 : rel->l = rel_dce_down(sql, rel->l, 0);
862 276609 : if (!skip_proj)
863 276609 : rel_dce_sub(sql, rel);
864 : /* fall through */
865 :
866 : case op_truncate:
867 : return rel;
868 :
869 7457 : case op_insert:
870 7457 : rel_used(rel->r);
871 7457 : rel_dce_sub(sql, rel->r);
872 7457 : return rel;
873 :
874 7746 : case op_update:
875 : case op_delete:
876 :
877 7746 : if (skip_proj && rel->r)
878 6192 : rel->r = rel_dce_down(sql, rel->r, 0);
879 1202 : if (!skip_proj)
880 1202 : rel_dce_sub(sql, rel);
881 : return rel;
882 :
883 526521 : case op_topn:
884 : case op_sample:
885 : case op_project:
886 : case op_groupby:
887 :
888 526521 : if (skip_proj && rel->l)
889 310838 : rel->l = rel_dce_down(sql, rel->l, is_topn(rel->op) || is_sample(rel->op));
890 204820 : if (!skip_proj)
891 204820 : rel_dce_sub(sql, rel);
892 : return rel;
893 :
894 5137 : case op_union:
895 : case op_inter:
896 : case op_except:
897 5137 : if (skip_proj) {
898 2816 : if (rel->l)
899 2816 : rel->l = rel_dce_down(sql, rel->l, 0);
900 2816 : if (rel->r)
901 2816 : rel->r = rel_dce_down(sql, rel->r, 0);
902 : }
903 2321 : if (!skip_proj)
904 2321 : rel_dce_sub(sql, rel);
905 : return rel;
906 :
907 45530 : case op_munion:
908 45530 : if (skip_proj) {
909 71125 : for (node *n = ((list*)rel->l)->h; n; n = n->next)
910 47527 : n->data = rel_dce_down(sql, n->data, 0);
911 : }
912 21932 : if (!skip_proj)
913 21932 : rel_dce_sub(sql, rel);
914 : return rel;
915 102274 : case op_select:
916 102274 : if (rel->l)
917 102274 : rel->l = rel_dce_down(sql, rel->l, 0);
918 : return rel;
919 :
920 147641 : case op_join:
921 : case op_left:
922 : case op_right:
923 : case op_full:
924 : case op_semi:
925 : case op_anti:
926 : case op_merge:
927 147641 : if (rel->l)
928 147641 : rel->l = rel_dce_down(sql, rel->l, 0);
929 147641 : if (rel->r)
930 147641 : rel->r = rel_dce_down(sql, rel->r, 0);
931 147641 : if (!skip_proj && !list_empty(rel->attr))
932 3150 : rel_dce_sub(sql, rel);
933 : return rel;
934 :
935 400660 : case op_ddl:
936 400660 : if (rel->flag == ddl_output || rel->flag == ddl_create_seq || rel->flag == ddl_alter_seq || rel->flag == ddl_alter_table || rel->flag == ddl_create_table || rel->flag == ddl_create_view) {
937 32951 : if (rel->l)
938 32785 : rel->l = rel_dce_down(sql, rel->l, 0);
939 : } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
940 282 : if (rel->l)
941 282 : rel->l = rel_dce_down(sql, rel->l, 0);
942 282 : if (rel->r)
943 248 : rel->r = rel_dce_down(sql, rel->r, 0);
944 : }
945 : return rel;
946 : }
947 : return rel;
948 : }
949 :
950 : /* DCE
951 : *
952 : * Based on top relation expressions mark sub expressions as used.
953 : * Then recurse down until the projections. Clean them up and repeat.
954 : */
955 :
956 : static sql_rel *
957 1067775 : rel_dce_sub(mvc *sql, sql_rel *rel)
958 : {
959 1067775 : if (!rel)
960 : return rel;
961 :
962 : /*
963 : * Mark used up until the next project
964 : * For setops we need to first mark, then remove
965 : * because of positional dependency
966 : */
967 1067775 : rel_mark_used(sql, rel, 1);
968 1067776 : rel = rel_remove_unused(sql, rel);
969 1067778 : rel_dce_down(sql, rel, 1);
970 1067778 : return rel;
971 : }
972 :
973 : /* add projects under set ops */
974 : static sql_rel *
975 2082357 : rel_add_projects(mvc *sql, sql_rel *rel)
976 : {
977 2082357 : if (!rel)
978 : return rel;
979 :
980 2082357 : switch(rel->op) {
981 : case op_basetable:
982 : case op_truncate:
983 : return rel;
984 14001 : case op_insert:
985 : case op_update:
986 : case op_delete:
987 14001 : if (rel->r)
988 13649 : rel->r = rel_add_projects(sql, rel->r);
989 : return rel;
990 2912 : case op_union:
991 : case op_inter:
992 : case op_except:
993 : /* We can only reduce the list of expressions of an set op
994 : * if the projection under it can also be reduced.
995 : */
996 2912 : if (rel->l) {
997 2912 : sql_rel *l = rel->l;
998 :
999 2912 : if (!is_project(l->op) && !need_distinct(rel))
1000 1 : l = rel_project(sql->sa, l, rel_projections(sql, l, NULL, 1, 1));
1001 2912 : rel->l = rel_add_projects(sql, l);
1002 : }
1003 2912 : if (rel->r) {
1004 2912 : sql_rel *r = rel->r;
1005 :
1006 2912 : if (!is_project(r->op) && !need_distinct(rel))
1007 1 : r = rel_project(sql->sa, r, rel_projections(sql, r, NULL, 1, 1));
1008 2912 : rel->r = rel_add_projects(sql, r);
1009 : }
1010 : return rel;
1011 34098 : case op_munion:
1012 34098 : assert(rel->l);
1013 152029 : for (node *n = ((list*)rel->l)->h; n; n = n->next) {
1014 117931 : sql_rel* r = n->data;
1015 117931 : if (!is_project(r->op) && !need_distinct(rel))
1016 23 : r = rel_project(sql->sa, r, rel_projections(sql, r, NULL, 1, 1));
1017 117931 : r = rel_add_projects(sql, r);
1018 117931 : n->data = r;
1019 : }
1020 : return rel;
1021 789486 : case op_topn:
1022 : case op_sample:
1023 : case op_project:
1024 : case op_groupby:
1025 : case op_select:
1026 : case op_table:
1027 789486 : if (rel->l && (rel->op != op_table || rel->flag != TRIGGER_WRAPPER))
1028 759121 : rel->l = rel_add_projects(sql, rel->l);
1029 : return rel;
1030 300431 : case op_join:
1031 : case op_left:
1032 : case op_right:
1033 : case op_full:
1034 : case op_semi:
1035 : case op_anti:
1036 : case op_merge:
1037 300431 : if (rel->l)
1038 300431 : rel->l = rel_add_projects(sql, rel->l);
1039 300431 : if (rel->r)
1040 300431 : rel->r = rel_add_projects(sql, rel->r);
1041 : return rel;
1042 402221 : case op_ddl:
1043 402221 : if (rel->flag == ddl_output || rel->flag == ddl_create_seq || rel->flag == ddl_alter_seq || rel->flag == ddl_alter_table || rel->flag == ddl_create_table || rel->flag == ddl_create_view) {
1044 34512 : if (rel->l)
1045 34152 : rel->l = rel_add_projects(sql, rel->l);
1046 : } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
1047 282 : if (rel->l)
1048 282 : rel->l = rel_add_projects(sql, rel->l);
1049 282 : if (rel->r)
1050 248 : rel->r = rel_add_projects(sql, rel->r);
1051 : }
1052 : return rel;
1053 : }
1054 : return rel;
1055 : }
1056 :
1057 : static sql_rel *
1058 550288 : rel_dce_(mvc *sql, sql_rel *rel)
1059 : {
1060 550288 : list *refs = sa_list(sql->sa);
1061 :
1062 550287 : rel_dce_refs(sql, rel, refs);
1063 550288 : if (refs) {
1064 566956 : for(node *n = refs->h; n; n = n->next) {
1065 16669 : sql_rel *i = n->data;
1066 :
1067 16669 : while (!rel_is_ref(i) && i->l && !is_base(i->op))
1068 : i = i->l;
1069 16669 : if (i)
1070 16669 : rel_used(i);
1071 : }
1072 : }
1073 550287 : rel = rel_add_projects(sql, rel);
1074 550288 : rel_used(rel);
1075 550283 : rel_dce_sub(sql, rel);
1076 550287 : return rel;
1077 : }
1078 :
1079 :
1080 : /* Remove unused expressions */
1081 : static sql_rel *
1082 550288 : rel_dce(visitor *v, global_props *gp, sql_rel *rel)
1083 : {
1084 550288 : (void) gp;
1085 550288 : return rel_dce_(v->sql, rel);
1086 : }
1087 :
1088 : /* keep export for other projects */
1089 : sql_rel *
1090 0 : rel_deadcode_elimination(mvc *sql, sql_rel *rel)
1091 : {
1092 0 : return rel_dce_(sql, rel);
1093 : }
1094 :
1095 : run_optimizer
1096 626148 : bind_dce(visitor *v, global_props *gp)
1097 : {
1098 626148 : int flag = v->sql->sql_optimizer;
1099 626148 : return gp->opt_cycle == 0 && gp->opt_level == 1 && (flag & dce) ? rel_dce : NULL;
1100 : }
1101 :
1102 :
1103 : static int
1104 84607 : topn_sample_safe_exps( list *exps, bool nil_limit )
1105 : {
1106 : /* Limit only expression lists are always save */
1107 84607 : if (list_length(exps) == 1)
1108 : return 1;
1109 1352 : for (node *n = exps->h; n; n = n->next ) {
1110 921 : sql_exp *e = n->data;
1111 :
1112 921 : if (!e || e->type != e_atom || (!nil_limit && exp_is_null(e)))
1113 59 : return 0;
1114 : }
1115 : return 1;
1116 : }
1117 :
1118 : static list *
1119 129 : sum_limit_offset(mvc *sql, sql_rel *rel)
1120 : {
1121 : /* for sample we always propagate, or if the expression list only consists of a limit expression, we copy it */
1122 129 : if (is_sample(rel->op) || list_length(rel->exps) == 1)
1123 126 : return exps_copy(sql, rel->exps);
1124 3 : assert(list_length(rel->exps) == 2);
1125 3 : sql_subtype *lng = sql_bind_localtype("lng");
1126 3 : sql_exp *add = rel_binop_(sql, NULL, exp_copy(sql, rel->exps->h->data), exp_copy(sql, rel->exps->h->next->data), "sys", "sql_add", card_value, true);
1127 : /* for remote plans, make sure the output type is a bigint */
1128 3 : if (subtype_cmp(lng, exp_subtype(add)) != 0)
1129 3 : add = exp_convert(sql, add, exp_subtype(add), lng);
1130 3 : return list_append(sa_list(sql->sa), add);
1131 : }
1132 :
1133 : /*
1134 : * Push TopN (only LIMIT, no ORDER BY) down through projections underneath crossproduct, i.e.,
1135 : *
1136 : * topn( topn(
1137 : * project( project(
1138 : * crossproduct( crossproduct(
1139 : * L, => topn( L )[ n ],
1140 : * R topn( R )[ n ]
1141 : * ) )
1142 : * )[ Cs ]* )[ Cs ]*
1143 : * )[ n ] )[ n ]
1144 : *
1145 : * (TODO: in case of n==1 we can omit the original top-level TopN)
1146 : *
1147 : * also push topn under (non reordering) projections.
1148 : */
1149 : static sql_rel *
1150 137510 : rel_push_topn_and_sample_down_(visitor *v, sql_rel *rel)
1151 : {
1152 137510 : sql_rel *rp = NULL, *r = rel->l, *rpp = NULL;
1153 :
1154 137510 : if (is_topn(rel->op) && !rel_is_ref(rel) &&
1155 50383 : r && r->op == op_table && r->flag != TRIGGER_WRAPPER && !rel_is_ref(r) && r->r) {
1156 3 : sql_exp *op = r->r;
1157 3 : sql_subfunc *f = op->f;
1158 :
1159 3 : if (is_func(op->type) && strcmp(f->func->base.name, "file_loader") == 0 && !sql_func_mod(f->func)[0] && !sql_func_imp(f->func)[0]) {
1160 : /* push limit, to arguments of file_loader */
1161 0 : list *args = op->l;
1162 0 : if (list_length(args) == 2) {
1163 0 : sql_exp *topN = rel->exps->h->data;
1164 0 : sql_exp *offset = rel->exps->h->next? rel->exps->h->next->data:NULL;
1165 0 : atom *topn = topN->l;
1166 0 : if (offset) {
1167 0 : atom *b1 = (atom *)offset->l, *c = atom_add(v->sql->sa, b1, topn);
1168 :
1169 0 : if (!c)
1170 : return rel;
1171 0 : if (atom_cmp(c, topn) < 0) /* overflow */
1172 : return rel;
1173 : topn = c;
1174 : }
1175 0 : append(args, exp_atom(v->sql->sa, topn));
1176 0 : v->changes++;
1177 : }
1178 : }
1179 : }
1180 :
1181 137510 : if ((is_topn(rel->op) || is_sample(rel->op)) && topn_sample_safe_exps(rel->exps, true)) {
1182 50468 : sql_rel *(*func) (allocator *, sql_rel *, list *) = is_topn(rel->op) ? rel_topn : rel_sample;
1183 :
1184 : /* nested topN relations */
1185 50468 : if (r && is_topn(rel->op) && is_topn(r->op) && !rel_is_ref(r)) {
1186 0 : sql_exp *topN1 = rel->exps->h->data, *topN2 = r->exps->h->data;
1187 0 : sql_exp *offset1 = list_length(rel->exps) > 1 ? rel->exps->h->next->data : NULL;
1188 0 : sql_exp *offset2 = list_length(r->exps) > 1 ? r->exps->h->next->data : NULL;
1189 :
1190 0 : if (topN1->l && topN2->l && (!offset1 || offset1->l) && (!offset2 || offset2->l)) { /* no parameters */
1191 0 : bool changed = false;
1192 :
1193 0 : if ((!offset1 || (offset1->type == e_atom && offset1->l)) && (!offset2 || (offset2->type == e_atom && offset2->l))) { /* only atoms */
1194 0 : if (!offset1 && offset2) {
1195 0 : list_append(rel->exps, exp_copy(v->sql, offset2));
1196 0 : changed = true;
1197 0 : } else if (offset1 && offset2) { /* sum offsets */
1198 0 : atom *b1 = (atom *)offset1->l, *b2 = (atom *)offset2->l, *c = atom_add(v->sql->sa, b1, b2);
1199 :
1200 0 : if (!c) /* error, don't apply optimization, WARNING because of this the offset optimization must come before the limit one */
1201 : return rel;
1202 0 : if (atom_cmp(c, b2) < 0) /* overflow */
1203 0 : c = atom_int(v->sql->sa, sql_bind_localtype("lng"), GDK_lng_max);
1204 0 : offset1->l = c;
1205 0 : changed = true;
1206 : }
1207 : }
1208 :
1209 0 : if (topN1->type == e_atom && topN1->l && topN2->type == e_atom && topN2->l) { /* only atoms */
1210 0 : atom *a1 = (atom *)topN1->l, *a2 = (atom *)topN2->l;
1211 :
1212 0 : if (!a2->isnull && (a1->isnull || atom_cmp(a1, a2) >= 0)) { /* topN1 is not set or is larger than topN2 */
1213 0 : rel->exps->h->data = exp_copy(v->sql, topN2);
1214 0 : changed = true;
1215 : }
1216 : }
1217 :
1218 0 : if (changed) {
1219 0 : rel->l = r->l;
1220 0 : r->l = NULL;
1221 0 : rel_destroy(r);
1222 0 : v->changes++;
1223 0 : return rel;
1224 : }
1225 : }
1226 : }
1227 :
1228 50468 : if (r && is_simple_project(r->op) && need_distinct(r))
1229 : return rel;
1230 :
1231 : /* push topn/sample under projections */
1232 50463 : if (!rel_is_ref(rel) && r && is_simple_project(r->op) && !need_distinct(r) && !rel_is_ref(r) && r->l && list_empty(r->r)) {
1233 : sql_rel *x = r, *px = x;
1234 :
1235 32669 : while (is_simple_project(x->op) && !need_distinct(x) && !rel_is_ref(x) && x->l && list_empty(x->r)) {
1236 16346 : px = x;
1237 16346 : x = x->l;
1238 : }
1239 : /* only push topn once */
1240 16323 : if (x && x->op == rel->op)
1241 : return rel;
1242 :
1243 16314 : rel->l = x;
1244 16314 : px->l = rel;
1245 16314 : rel = r;
1246 16314 : v->changes++;
1247 16314 : return rel;
1248 : }
1249 :
1250 34140 : if (!topn_sample_safe_exps(rel->exps, false))
1251 : return rel;
1252 :
1253 : /* duplicate topn/sample direct under union or crossproduct */
1254 34081 : if (r && !rel_is_ref(r) && r->l && r->r && ((is_union(r->op) && r->exps) || (r->op == op_join && list_empty(r->exps)))) {
1255 150 : sql_rel *u = r, *x;
1256 150 : sql_rel *ul = u->l;
1257 150 : sql_rel *ur = u->r;
1258 150 : bool changed = false;
1259 :
1260 150 : x = ul;
1261 156 : while (is_simple_project(x->op) && !need_distinct(x) && !rel_is_ref(x) && x->l && list_empty(x->r))
1262 6 : x = x->l;
1263 150 : if (x && x->op != rel->op) { /* only push topn once */
1264 60 : ul = func(v->sql->sa, ul, sum_limit_offset(v->sql, rel));
1265 60 : set_processed(ul);
1266 60 : u->l = ul;
1267 60 : changed = true;
1268 : }
1269 :
1270 150 : x = ur;
1271 158 : while (is_simple_project(x->op) && !need_distinct(x) && !rel_is_ref(x) && x->l && list_empty(x->r))
1272 8 : x = x->l;
1273 150 : if (x && x->op != rel->op) { /* only push topn once */
1274 61 : ur = func(v->sql->sa, ur, sum_limit_offset(v->sql, rel));
1275 61 : set_processed(ur);
1276 61 : u->r = ur;
1277 61 : changed = true;
1278 : }
1279 :
1280 150 : if (changed)
1281 61 : v->changes++;
1282 150 : return rel;
1283 : }
1284 :
1285 : /* duplicate topn/sample + [ project-order ] under union */
1286 : if (r && !rp)
1287 33931 : rp = r->l;
1288 33931 : if (r && r->exps && is_simple_project(r->op) && !rel_is_ref(r) && !list_empty(r->r) && r->l && is_union(rp->op)) {
1289 0 : sql_rel *u = rp, *ou = u, *x, *ul = u->l, *ur = u->r;
1290 0 : list *rcopy = NULL;
1291 :
1292 : /* only push topn/sample once */
1293 0 : x = ul;
1294 0 : while (is_simple_project(x->op) && !need_distinct(x) && !rel_is_ref(x) && x->l && list_empty(x->r))
1295 0 : x = x->l;
1296 0 : if (x && x->op == rel->op)
1297 : return rel;
1298 : x = ur;
1299 0 : while (is_simple_project(x->op) && !need_distinct(x) && !rel_is_ref(x) && x->l && list_empty(x->r))
1300 0 : x = x->l;
1301 0 : if (x && x->op == rel->op)
1302 : return rel;
1303 :
1304 0 : rcopy = exps_copy(v->sql, r->r);
1305 0 : for (node *n = rcopy->h ; n ; n = n->next) {
1306 0 : sql_exp *e = n->data;
1307 0 : set_descending(e); /* remove ordering properties for projected columns */
1308 0 : set_nulls_first(e);
1309 : }
1310 0 : ul = rel_dup(ul);
1311 0 : ur = rel_dup(ur);
1312 0 : if (!is_project(ul->op))
1313 0 : ul = rel_project(v->sql->sa, ul,
1314 : rel_projections(v->sql, ul, NULL, 1, 1));
1315 0 : if (!is_project(ur->op))
1316 0 : ur = rel_project(v->sql->sa, ur,
1317 : rel_projections(v->sql, ur, NULL, 1, 1));
1318 0 : rel_rename_exps(v->sql, u->exps, ul->exps);
1319 0 : rel_rename_exps(v->sql, u->exps, ur->exps);
1320 :
1321 : /* introduce projects under the set */
1322 0 : ul = rel_project(v->sql->sa, ul, NULL);
1323 0 : ul->exps = exps_copy(v->sql, r->exps);
1324 : /* possibly add order by column */
1325 0 : ul->exps = list_distinct(list_merge(ul->exps, exps_copy(v->sql, rcopy), NULL), (fcmp) exp_equal, (fdup) NULL);
1326 0 : ul->nrcols = list_length(ul->exps);
1327 0 : ul->r = exps_copy(v->sql, r->r);
1328 0 : set_processed(ul);
1329 0 : ul = func(v->sql->sa, ul, sum_limit_offset(v->sql, rel));
1330 0 : set_processed(ul);
1331 :
1332 0 : ur = rel_project(v->sql->sa, ur, NULL);
1333 0 : ur->exps = exps_copy(v->sql, r->exps);
1334 : /* possibly add order by column */
1335 0 : ur->exps = list_distinct(list_merge(ur->exps, exps_copy(v->sql, rcopy), NULL), (fcmp) exp_equal, (fdup) NULL);
1336 0 : ur->nrcols = list_length(ur->exps);
1337 0 : ur->r = exps_copy(v->sql, r->r);
1338 0 : set_processed(ur);
1339 0 : ur = func(v->sql->sa, ur, sum_limit_offset(v->sql, rel));
1340 0 : set_processed(ur);
1341 :
1342 0 : u = rel_setop(v->sql->sa, ul, ur, op_union);
1343 0 : u->exps = exps_alias(v->sql, r->exps);
1344 0 : u->nrcols = list_length(u->exps);
1345 0 : set_processed(u);
1346 : /* possibly add order by column */
1347 0 : u->exps = list_distinct(list_merge(u->exps, rcopy, NULL), (fcmp) exp_equal, (fdup) NULL);
1348 0 : if (need_distinct(r)) {
1349 0 : set_distinct(ul);
1350 0 : set_distinct(ur);
1351 : }
1352 :
1353 : /* zap names */
1354 0 : rel_no_rename_exps(u->exps);
1355 0 : rel_destroy(ou);
1356 :
1357 0 : ur = rel_project(v->sql->sa, u, exps_alias(v->sql, r->exps));
1358 0 : ur->r = r->r;
1359 0 : r->l = NULL;
1360 :
1361 0 : if (need_distinct(r))
1362 0 : set_distinct(ur);
1363 :
1364 0 : rel_destroy(r);
1365 0 : rel->l = ur;
1366 0 : v->changes++;
1367 0 : return rel;
1368 : }
1369 : /* a left outer join b order by a.* limit L, can be copied into a */
1370 : /* topn ( project (orderby)( optional project ( left ())
1371 : * rel r rp */
1372 33931 : if (r && !rp)
1373 66 : rp = r->l;
1374 33931 : if (r && rp && is_simple_project(rp->op) && !rp->r && rp->l)
1375 33931 : rpp = rp->l;
1376 33931 : if (r && r->exps && is_simple_project(r->op) && !rel_is_ref(r) && r->r && r->l && ((!rpp && is_left(rp->op)) ||
1377 300 : (rpp && is_left(rpp->op)))) {
1378 24 : sql_rel *lj = rpp?rpp:rp;
1379 24 : sql_rel *l = lj->l;
1380 24 : list *obes = r->r, *nobes = sa_list(v->sql->sa);
1381 24 : int fnd = 1;
1382 63 : for (node *n = obes->h; n && fnd; n = n->next) {
1383 41 : sql_exp *obe = n->data;
1384 41 : int asc = is_ascending(obe);
1385 41 : int nl = nulls_last(obe);
1386 : /* only simple rename expressions */
1387 41 : sql_exp *pe = exps_find_exp(r->exps, obe);
1388 41 : if (pe && rpp)
1389 33 : pe = exps_find_exp(rp->exps, pe);
1390 41 : if (pe)
1391 41 : pe = rel_find_exp(l, pe);
1392 41 : if (pe) {
1393 41 : if (exp_is_atom(pe))
1394 : return rel;
1395 39 : pe = exp_ref(v->sql, pe);
1396 39 : if (asc)
1397 29 : set_ascending(pe);
1398 39 : if (nl)
1399 5 : set_nulls_last(pe);
1400 39 : append(nobes, pe);
1401 : }
1402 : else
1403 : fnd = 0;
1404 : }
1405 22 : if (fnd && ((is_topn(rel->op) && !is_topn(l->op)) || (is_sample(rel->op) && !is_sample(l->op)))) {
1406 : /* inject topn */
1407 : /* Todo add order by */
1408 8 : sql_rel *ob = lj->l = rel_project(v->sql->sa, lj->l, rel_projections(v->sql, lj->l, NULL, 1, 1));
1409 8 : ob->r = nobes;
1410 8 : lj->l = func(v->sql->sa, lj->l, sum_limit_offset(v->sql, rel));
1411 8 : v->changes++;
1412 8 : return rel;
1413 : }
1414 : }
1415 : }
1416 : return rel;
1417 : }
1418 :
1419 : static sql_rel *
1420 33666 : rel_push_topn_and_sample_down(visitor *v, global_props *gp, sql_rel *rel)
1421 : {
1422 33666 : (void) gp;
1423 33666 : return rel_visitor_topdown(v, rel, &rel_push_topn_and_sample_down_);
1424 : }
1425 :
1426 : run_optimizer
1427 626147 : bind_push_topn_and_sample_down(visitor *v, global_props *gp)
1428 : {
1429 626147 : int flag = v->sql->sql_optimizer;
1430 625951 : return gp->opt_level == 1 && (gp->cnt[op_topn] || gp->cnt[op_sample]) &&
1431 659813 : (flag & push_topn_and_sample_down) ? rel_push_topn_and_sample_down : NULL;
1432 : }
|
