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_private.h"
15 : #include "rel_exp.h"
16 : #include "rel_select.h"
17 :
18 : static void
19 72 : rel_no_rename_exps( list *exps )
20 : {
21 443 : for (node *n = exps->h; n; n = n->next) {
22 371 : sql_exp *e = n->data;
23 :
24 371 : exp_setalias(e, e->l, e->r);
25 : }
26 72 : list_hash_clear(exps);
27 72 : }
28 :
29 : void
30 74391 : rel_rename_exps( mvc *sql, list *exps1, list *exps2)
31 : {
32 74391 : int pos = 0;
33 74391 : node *n, *m;
34 :
35 74391 : (void)sql;
36 : /* check if a column uses an alias earlier in the list */
37 621034 : for (n = exps1->h, m = exps2->h; n && m; n = n->next, m = m->next, pos++) {
38 546643 : sql_exp *e2 = m->data;
39 :
40 546643 : if (e2->type == e_column) {
41 509616 : sql_exp *ne = NULL;
42 :
43 509616 : if (e2->l)
44 472267 : ne = exps_bind_column2(exps2, e2->l, e2->r, NULL);
45 509616 : if (!ne && !e2->l)
46 37349 : ne = exps_bind_column(exps2, e2->r, NULL, NULL, 1);
47 329911 : if (ne) {
48 179952 : int p = list_position(exps2, ne);
49 :
50 179952 : if (p < pos) {
51 24 : ne = list_fetch(exps1, p);
52 24 : if (e2->l)
53 24 : e2->l = (void *) exp_relname(ne);
54 24 : e2->r = (void *) exp_name(ne);
55 : }
56 : }
57 : }
58 : }
59 :
60 74391 : assert(list_length(exps1) <= list_length(exps2));
61 621034 : for (n = exps1->h, m = exps2->h; n && m; n = n->next, m = m->next) {
62 546643 : sql_exp *e1 = n->data;
63 546643 : sql_exp *e2 = m->data;
64 546643 : const char *rname = exp_relname(e1);
65 :
66 546643 : if (!rname && e1->type == e_column && e1->l && exp_relname(e2) &&
67 0 : strcmp(e1->l, exp_relname(e2)) == 0)
68 0 : rname = exp_relname(e2);
69 546643 : exp_setalias(e2, rname, exp_name(e1));
70 : }
71 74391 : list_hash_clear(exps2);
72 74391 : }
73 :
74 : sql_rel *
75 128998 : rel_find_ref( sql_rel *r)
76 : {
77 11537071 : while (!rel_is_ref(r) && r->l &&
78 11532646 : (is_project(r->op) || is_select(r->op) /*|| is_join(r->op)*/))
79 : r = r->l;
80 128998 : if (rel_is_ref(r))
81 3131 : return r;
82 : return NULL;
83 : }
84 :
85 : /* merge projection */
86 :
87 : /* push an expression through a projection.
88 : * The result should again used in a projection.
89 : */
90 : static list *
91 62139 : exps_push_down_prj(mvc *sql, list *exps, sql_rel *f, sql_rel *t, bool keepalias)
92 : {
93 62139 : node *n;
94 62139 : list *nl = new_exp_list(sql->sa);
95 :
96 200560 : for(n = exps->h; n; n = n->next) {
97 146026 : sql_exp *arg = n->data, *narg = NULL;
98 :
99 146026 : narg = exp_push_down_prj(sql, arg, f, t);
100 146026 : if (!narg)
101 : return NULL;
102 138421 : narg = exp_propagate(sql->sa, narg, arg);
103 138421 : if (!keepalias && narg->type == e_column)
104 21369 : exp_setalias(narg, narg->l, narg->r);
105 138421 : append(nl, narg);
106 : }
107 : return nl;
108 : }
109 :
110 : sql_exp *
111 1889159 : exp_push_down_prj(mvc *sql, sql_exp *e, sql_rel *f, sql_rel *t)
112 : {
113 1889159 : sql_exp *ne = NULL, *l = NULL, *r = NULL, *r2 = NULL;
114 :
115 1889159 : assert(is_project(f->op));
116 :
117 1889159 : switch(e->type) {
118 1510361 : case e_column:
119 1510361 : if (e->l)
120 1448412 : ne = exps_bind_column2(f->exps, e->l, e->r, NULL);
121 1510361 : if (!ne && !e->l)
122 61949 : ne = exps_bind_column(f->exps, e->r, NULL, NULL, 1);
123 1510361 : if (!ne || (ne->type != e_column && (ne->type != e_atom || ne->f)))
124 208018 : return NULL;
125 1302356 : while (ne && (has_label(ne) || is_selfref(ne) /*inside this list */) && is_simple_project(f->op) && ne->type == e_column) {
126 15884 : sql_exp *oe = e, *one = ne;
127 :
128 15884 : e = ne;
129 15884 : ne = NULL;
130 15884 : if (e->l)
131 15872 : ne = exps_bind_column2(f->exps, e->l, e->r, NULL);
132 15884 : if (!ne && !e->l)
133 12 : ne = exps_bind_column(f->exps, e->r, NULL, NULL, 1);
134 15884 : if (ne && ne != one && list_position(f->exps, ne) >= list_position(f->exps, one))
135 15884 : ne = NULL;
136 15884 : if (!ne || ne == one) {
137 : ne = one;
138 : e = oe;
139 : break;
140 : }
141 317 : if (ne->type != e_column && (ne->type != e_atom || ne->f))
142 : return NULL;
143 : }
144 : /* possibly a groupby/project column is renamed */
145 1302039 : if (is_groupby(f->op) && !list_empty(f->r) && ne->type == e_column) {
146 131 : sql_exp *gbe = NULL;
147 131 : if (ne->l)
148 130 : gbe = exps_bind_column2(f->r, ne->l, ne->r, NULL);
149 131 : if (!gbe && !e->l)
150 1 : gbe = exps_bind_column(f->r, ne->r, NULL, NULL, 1);
151 132 : ne = gbe;
152 131 : if (!ne || (ne->type != e_column && (ne->type != e_atom || ne->f)))
153 16 : return NULL;
154 : }
155 1302023 : if (ne->type == e_atom)
156 26546 : e = exp_copy(sql, ne);
157 : else
158 1275477 : e = exp_alias(sql->sa, exp_relname(e), exp_name(e), ne->l, ne->r, exp_subtype(e), e->card, has_nil(e), is_unique(e), is_intern(e));
159 1302023 : return exp_propagate(sql->sa, e, ne);
160 58513 : case e_cmp:
161 58513 : if (e->flag == cmp_or || e->flag == cmp_filter) {
162 4091 : list *l = NULL, *r = NULL;
163 :
164 4091 : if (!(l = exps_push_down_prj(sql, e->l, f, t, true)) || !(r = exps_push_down_prj(sql, e->r, f, t, true)))
165 1143 : return NULL;
166 2948 : if (e->flag == cmp_filter) {
167 964 : ne = exp_filter(sql->sa, l, r, e->f, is_anti(e));
168 : } else {
169 1984 : ne = exp_or(sql->sa, l, r, is_anti(e));
170 : }
171 54422 : } else if (e->flag == cmp_in || e->flag == cmp_notin) {
172 4042 : list *r = NULL;
173 :
174 4042 : if (!(l = exp_push_down_prj(sql, e->l, f, t)) || !(r = exps_push_down_prj(sql, e->r, f, t, true)))
175 3602 : return NULL;
176 440 : ne = exp_in(sql->sa, l, r, e->flag);
177 : } else {
178 50380 : 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))))
179 22937 : return NULL;
180 27443 : if (e->f) {
181 693 : ne = exp_compare2(sql->sa, l, r, r2, e->flag, is_symmetric(e));
182 : } else {
183 26750 : ne = exp_compare(sql->sa, l, r, e->flag);
184 : }
185 : }
186 30831 : if (!ne)
187 : return NULL;
188 30831 : return exp_propagate(sql->sa, ne, e);
189 171716 : case e_convert:
190 171716 : if (!(l = exp_push_down_prj(sql, e->l, f, t)))
191 : return NULL;
192 124099 : ne = exp_convert(sql->sa, l, exp_fromtype(e), exp_totype(e));
193 124099 : return exp_propagate(sql->sa, ne, e);
194 54526 : case e_aggr:
195 : case e_func: {
196 54526 : list *l = e->l, *nl = NULL;
197 54526 : sql_exp *ne = NULL;
198 :
199 54526 : if (e->type == e_func && exp_unsafe(e,0))
200 : return NULL;
201 54502 : if (!list_empty(l)) {
202 54502 : nl = exps_push_down_prj(sql, l, f, t, false);
203 54502 : if (!nl)
204 : return NULL;
205 : }
206 48040 : if (e->type == e_func)
207 48040 : ne = exp_op(sql->sa, nl, e->f);
208 : else
209 0 : ne = exp_aggr(sql->sa, nl, e->f, need_distinct(e), need_no_nil(e), e->card, has_nil(e));
210 48040 : return exp_propagate(sql->sa, ne, e);
211 : }
212 94043 : case e_atom: {
213 94043 : list *l = e->f, *nl = NULL;
214 :
215 94043 : if (!list_empty(l)) {
216 0 : nl = exps_push_down_prj(sql, l, f, t, false);
217 0 : if (!nl)
218 : return NULL;
219 0 : ne = exp_values(sql->sa, nl);
220 : } else {
221 94043 : ne = exp_copy(sql, e);
222 : }
223 94043 : return exp_propagate(sql->sa, ne, e);
224 : }
225 : case e_psm:
226 : if (e->type == e_atom && e->f) /* value list */
227 : return NULL;
228 : return e;
229 : }
230 : return NULL;
231 : }
232 :
233 : atom *
234 1223 : exp_flatten(mvc *sql, bool value_based_opt, sql_exp *e)
235 : {
236 1223 : if (e->type == e_atom) {
237 781 : return value_based_opt ? exp_value(sql, e) : (atom *) e->l;
238 442 : } else if (e->type == e_convert) {
239 147 : atom *v = exp_flatten(sql, value_based_opt, e->l);
240 :
241 147 : if (v)
242 44 : return atom_cast(sql->sa, v, exp_subtype(e));
243 295 : } else if (e->type == e_func) {
244 263 : sql_subfunc *f = e->f;
245 263 : list *l = e->l;
246 263 : sql_arg *res = (f->func->res)?(f->func->res->h->data):NULL;
247 :
248 : /* TODO handle date + x months */
249 263 : if (!f->func->s && strcmp(f->func->base.name, "sql_add") == 0 && list_length(l) == 2 && res && EC_NUMBER(res->type.type->eclass)) {
250 27 : atom *l1 = exp_flatten(sql, value_based_opt, l->h->data);
251 27 : atom *l2 = exp_flatten(sql, value_based_opt, l->h->next->data);
252 27 : if (l1 && l2)
253 3 : return atom_add(sql->sa, l1, l2);
254 236 : } else if (!f->func->s && strcmp(f->func->base.name, "sql_sub") == 0 && list_length(l) == 2 && res && EC_NUMBER(res->type.type->eclass)) {
255 17 : atom *l1 = exp_flatten(sql, value_based_opt, l->h->data);
256 17 : atom *l2 = exp_flatten(sql, value_based_opt, l->h->next->data);
257 17 : if (l1 && l2)
258 17 : return atom_sub(sql->sa, l1, l2);
259 : }
260 : }
261 : return NULL;
262 : }
263 :
264 : int
265 200 : exp_range_overlap(atom *min, atom *max, atom *emin, atom *emax, bool min_exclusive, bool max_exclusive)
266 : {
267 200 : if (!min || !max || !emin || !emax || min->isnull || max->isnull || emin->isnull || emax->isnull)
268 : return 0;
269 :
270 200 : if ((!min_exclusive && VALcmp(&(emax->data), &(min->data)) < 0) || (min_exclusive && VALcmp(&(emax->data), &(min->data)) <= 0))
271 29 : return 0;
272 171 : if ((!max_exclusive && VALcmp(&(emin->data), &(max->data)) > 0) || (max_exclusive && VALcmp(&(emin->data), &(max->data)) >= 0))
273 36 : return 0;
274 : return 1;
275 : }
276 :
277 :
278 : /* if local_proj is >= -1, the current expression is from the same projection
279 : if local_proj is -1, then we don't care about self references (eg used to check for order by exps) */
280 : static int exp_mark_used(sql_rel *subrel, sql_exp *e, int local_proj);
281 :
282 : static int
283 983350 : exps_mark_used(sql_rel *subrel, list *l, int local_proj)
284 : {
285 983350 : int nr = 0;
286 983350 : if (list_empty(l))
287 : return nr;
288 :
289 2862309 : for (node *n = l->h; n != NULL; n = n->next)
290 1879025 : nr += exp_mark_used(subrel, n->data, local_proj);
291 : return nr;
292 : }
293 :
294 : static int
295 13754368 : exp_mark_used(sql_rel *subrel, sql_exp *e, int local_proj)
296 : {
297 15947293 : int nr = 0;
298 15947293 : sql_exp *ne = NULL;
299 :
300 15947293 : switch(e->type) {
301 7475219 : case e_column:
302 7475219 : ne = rel_find_exp(subrel, e);
303 : /* if looking in the same projection, make sure 'ne' is projected before the searched column */
304 7475246 : if (ne && local_proj > -1 && list_position(subrel->exps, ne) >= local_proj)
305 10776035 : ne = NULL;
306 : break;
307 2192925 : case e_convert:
308 2192925 : return exp_mark_used(subrel, e->l, local_proj);
309 667695 : case e_aggr:
310 : case e_func: {
311 667695 : if (e->l)
312 655166 : nr += exps_mark_used(subrel, e->l, local_proj);
313 667695 : assert(!e->r);
314 : break;
315 : }
316 2633094 : case e_cmp:
317 2633094 : if (e->flag == cmp_or || e->flag == cmp_filter) {
318 152703 : nr += exps_mark_used(subrel, e->l, local_proj);
319 152703 : nr += exps_mark_used(subrel, e->r, local_proj);
320 2480391 : } else if (e->flag == cmp_in || e->flag == cmp_notin) {
321 18758 : nr += exp_mark_used(subrel, e->l, local_proj);
322 18758 : nr += exps_mark_used(subrel, e->r, local_proj);
323 : } else {
324 2461633 : nr += exp_mark_used(subrel, e->l, local_proj);
325 2461632 : nr += exp_mark_used(subrel, e->r, local_proj);
326 2461632 : if (e->f)
327 6434 : nr += exp_mark_used(subrel, e->f, local_proj);
328 : }
329 : break;
330 2978360 : case e_atom:
331 : /* atoms are used in e_cmp */
332 2978360 : e->used = 1;
333 : /* return 0 as constants may require a full column ! */
334 2978360 : if (e->f)
335 4020 : nr += exps_mark_used(subrel, e->f, local_proj);
336 : return nr;
337 0 : case e_psm:
338 0 : if (e->flag & PSM_SET || e->flag & PSM_RETURN || e->flag & PSM_EXCEPTION) {
339 0 : nr += exp_mark_used(subrel, e->l, local_proj);
340 0 : } else if (e->flag & PSM_WHILE || e->flag & PSM_IF) {
341 0 : nr += exp_mark_used(subrel, e->l, local_proj);
342 0 : nr += exps_mark_used(subrel, e->r, local_proj);
343 0 : if (e->flag == PSM_IF && e->f)
344 0 : nr += exps_mark_used(subrel, e->f, local_proj);
345 : }
346 0 : e->used = 1;
347 0 : break;
348 : }
349 10776035 : if (ne && e != ne) {
350 4703647 : if (local_proj == -2 || ne->type != e_column || (has_label(ne) || (ne->alias.rname && ne->alias.rname[0] == '%')) || (subrel->l && !rel_find_exp(subrel->l, e)))
351 4609835 : ne->used = 1;
352 4703647 : return ne->used;
353 : }
354 : return nr;
355 : }
356 :
357 : static void
358 39996 : positional_exps_mark_used( sql_rel *rel, sql_rel *subrel )
359 : {
360 39996 : assert(rel->exps);
361 :
362 39996 : if ((is_topn(subrel->op) || is_sample(subrel->op)) && subrel->l)
363 39996 : subrel = subrel->l;
364 : /* everything is used within the set operation */
365 39996 : if (rel->exps && subrel->exps) {
366 39996 : node *m;
367 339646 : for (m=subrel->exps->h; m; m = m->next) {
368 299650 : sql_exp *se = m->data;
369 :
370 299650 : se->used = 1;
371 : }
372 : }
373 39996 : }
374 :
375 : static void
376 1967258 : rel_exps_mark_used(sql_allocator *sa, sql_rel *rel, sql_rel *subrel)
377 : {
378 1967258 : int nr = 0;
379 :
380 1967258 : if (rel->r && (is_simple_project(rel->op) || is_groupby(rel->op))) {
381 29956 : list *l = rel->r;
382 29956 : node *n;
383 :
384 104176 : for (n=l->h; n; n = n->next) {
385 74219 : sql_exp *e = n->data;
386 :
387 74219 : e->used = 1;
388 74219 : exp_mark_used(rel, e, -1);
389 : }
390 : }
391 1967259 : if (rel->attr) {
392 1074003 : for (node *n = rel->attr->h; n; n = n->next) {
393 537002 : sql_exp *e = n->data;
394 :
395 537002 : if (e->type != e_aggr) /* keep all group by's */
396 537002 : e->used = 1;
397 537002 : if (e->used)
398 537002 : nr += exp_mark_used(subrel, e, -2);
399 : }
400 : }
401 1967258 : if (rel->exps) {
402 1939777 : node *n;
403 1939777 : int len = list_length(rel->exps), i;
404 1939779 : sql_exp **exps = SA_NEW_ARRAY(sa, sql_exp*, len);
405 :
406 6748560 : for (n=rel->exps->h, i = 0; n; n = n->next, i++) {
407 4808782 : sql_exp *e = exps[i] = n->data;
408 :
409 4808782 : nr += e->used;
410 : }
411 :
412 1939778 : if (!nr && is_project(rel->op) && len > 0) /* project at least one column if exists */
413 4904 : exps[0]->used = 1;
414 :
415 6748569 : for (i = len-1; i >= 0; i--) {
416 4808792 : sql_exp *e = exps[i];
417 :
418 4808792 : if (!is_project(rel->op) || e->used) {
419 4292198 : if (is_project(rel->op))
420 1949158 : nr += exp_mark_used(rel, e, i);
421 4292198 : nr += exp_mark_used(subrel, e, -2);
422 : }
423 : }
424 : }
425 : /* for count/rank we need atleast one column */
426 1967258 : if (!nr && subrel && (is_project(subrel->op) || is_base(subrel->op)) && !list_empty(subrel->exps) &&
427 11654 : (is_simple_project(rel->op) && project_unsafe(rel, 0))) {
428 46 : sql_exp *e = subrel->exps->h->data;
429 46 : e->used = 1;
430 : }
431 1967258 : if (rel->r && (is_simple_project(rel->op) || is_groupby(rel->op))) {
432 29956 : list *l = rel->r;
433 29956 : node *n;
434 :
435 104176 : for (n=l->h; n; n = n->next) {
436 74220 : sql_exp *e = n->data;
437 :
438 74220 : e->used = 1;
439 : /* possibly project/groupby uses columns from the inner */
440 74220 : exp_mark_used(subrel, e, -2);
441 : }
442 : }
443 1967258 : }
444 :
445 : static void exps_used(list *l);
446 :
447 : static void
448 3239414 : exp_used(sql_exp *e)
449 : {
450 3281576 : if (e) {
451 3263742 : e->used = 1;
452 :
453 3263742 : switch (e->type) {
454 40963 : case e_convert:
455 40963 : exp_used(e->l);
456 40963 : break;
457 114216 : case e_func:
458 : case e_aggr:
459 114216 : exps_used(e->l);
460 114216 : break;
461 8685 : case e_cmp:
462 8685 : if (e->flag == cmp_or || e->flag == cmp_filter) {
463 888 : exps_used(e->l);
464 888 : exps_used(e->r);
465 7797 : } else if (e->flag == cmp_in || e->flag == cmp_notin) {
466 238 : exp_used(e->l);
467 238 : exps_used(e->r);
468 : } else {
469 7559 : exp_used(e->l);
470 7559 : exp_used(e->r);
471 7559 : if (e->f)
472 : exp_used(e->f);
473 : }
474 : break;
475 : default:
476 : break;
477 : }
478 : }
479 3239414 : }
480 :
481 : static void
482 868395 : exps_used(list *l)
483 : {
484 868395 : if (l) {
485 4089399 : for (node *n = l->h; n; n = n->next)
486 3222484 : exp_used(n->data);
487 : }
488 868394 : }
489 :
490 : static void
491 762901 : rel_used(sql_rel *rel)
492 : {
493 762901 : if (!rel)
494 : return;
495 719069 : if (is_join(rel->op) || is_set(rel->op) || is_semi(rel->op) || is_modify(rel->op)) {
496 73084 : rel_used(rel->l);
497 73083 : rel_used(rel->r);
498 : } else if (is_topn(rel->op) || is_select(rel->op) || is_sample(rel->op)) {
499 20653 : rel_used(rel->l);
500 20652 : rel = rel->l;
501 : } else if (is_ddl(rel->op)) {
502 399268 : 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) {
503 33747 : rel_used(rel->l);
504 : } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
505 280 : rel_used(rel->l);
506 280 : rel_used(rel->r);
507 : } else if (rel->flag == ddl_psm) {
508 22112 : exps_used(rel->exps);
509 : }
510 : } else if (rel->op == op_table) {
511 1576 : if (IS_TABLE_PROD_FUNC(rel->flag) || rel->flag == TABLE_FROM_RELATION)
512 1576 : rel_used(rel->l);
513 1576 : exp_used(rel->r);
514 : }
515 849865 : if (rel && rel->exps) {
516 711868 : exps_used(rel->exps);
517 711867 : if (rel->r && (is_simple_project(rel->op) || is_groupby(rel->op)))
518 18185 : exps_used(rel->r);
519 : }
520 : }
521 :
522 : static void
523 2177195 : rel_mark_used(mvc *sql, sql_rel *rel, int proj)
524 : {
525 3775954 : if (proj && (need_distinct(rel)))
526 9892 : rel_used(rel);
527 :
528 3775953 : switch(rel->op) {
529 : case op_basetable:
530 : case op_truncate:
531 : case op_insert:
532 : break;
533 :
534 11667 : case op_table:
535 :
536 11667 : if (rel->l && rel->flag != TRIGGER_WRAPPER) {
537 118 : rel_used(rel);
538 118 : if (rel->r)
539 118 : exp_mark_used(rel->l, rel->r, -2);
540 118 : rel_mark_used(sql, rel->l, proj);
541 : }
542 : break;
543 :
544 16625 : case op_topn:
545 : case op_sample:
546 16625 : if (proj) {
547 16557 : rel = rel ->l;
548 16557 : rel_mark_used(sql, rel, proj);
549 16557 : break;
550 : }
551 : /* fall through */
552 : case op_project:
553 : case op_groupby:
554 943473 : if (proj && rel->l) {
555 503493 : rel_exps_mark_used(sql->sa, rel, rel->l);
556 503493 : rel_mark_used(sql, rel->l, 0);
557 6610 : } else if (proj) {
558 6542 : rel_exps_mark_used(sql->sa, rel, NULL);
559 : }
560 : break;
561 6991 : case op_update:
562 : case op_delete:
563 6991 : if (proj && rel->r) {
564 5703 : sql_rel *r = rel->r;
565 :
566 5703 : if (!list_empty(r->exps)) {
567 6794 : for (node *n = r->exps->h; n; n = n->next) {
568 5704 : sql_exp *e = n->data;
569 5704 : const char *nname = exp_name(e);
570 :
571 5704 : if (nname && nname[0] == '%' && strcmp(nname, TID) == 0) { /* TID is used */
572 4613 : e->used = 1;
573 4613 : break;
574 : }
575 : }
576 : }
577 5703 : rel_exps_mark_used(sql->sa, rel, rel->r);
578 5703 : rel_mark_used(sql, rel->r, 0);
579 : }
580 : break;
581 :
582 397898 : case op_ddl:
583 397898 : 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) {
584 32377 : if (rel->l)
585 : rel_mark_used(sql, rel->l, 0);
586 : } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
587 280 : if (rel->l)
588 280 : rel_mark_used(sql, rel->l, 0);
589 280 : if (rel->r)
590 : rel_mark_used(sql, rel->r, 0);
591 : }
592 : break;
593 :
594 621353 : case op_select:
595 621353 : if (rel->l) {
596 621353 : rel_exps_mark_used(sql->sa, rel, rel->l);
597 621352 : rel_mark_used(sql, rel->l, 0);
598 : }
599 : break;
600 :
601 48712 : case op_union:
602 : case op_inter:
603 : case op_except:
604 : /* For now we mark all union expression as used */
605 :
606 : /* Later we should (in case of union all) remove unused
607 : * columns from the projection.
608 : *
609 : * Project part of union is based on column position.
610 : */
611 48712 : if (proj && (need_distinct(rel) || !rel->exps)) {
612 4181 : rel_used(rel);
613 4181 : if (!rel->exps) {
614 0 : rel_used(rel->l);
615 0 : rel_used(rel->r);
616 : }
617 4181 : rel_mark_used(sql, rel->l, 0);
618 4181 : rel_mark_used(sql, rel->r, 0);
619 19998 : } else if (proj && !need_distinct(rel)) {
620 19998 : sql_rel *l = rel->l;
621 :
622 19998 : positional_exps_mark_used(rel, l);
623 19998 : rel_exps_mark_used(sql->sa, rel, l);
624 19998 : rel_mark_used(sql, rel->l, 0);
625 : /* based on child check set expression list */
626 19998 : if (is_project(l->op) && need_distinct(l))
627 0 : positional_exps_mark_used(l, rel);
628 19998 : positional_exps_mark_used(rel, rel->r);
629 19998 : rel_exps_mark_used(sql->sa, rel, rel->r);
630 19998 : rel_mark_used(sql, rel->r, 0);
631 : }
632 : break;
633 :
634 395086 : case op_join:
635 : case op_left:
636 : case op_right:
637 : case op_full:
638 : case op_semi:
639 : case op_anti:
640 : case op_merge:
641 395086 : rel_exps_mark_used(sql->sa, rel, rel->l);
642 395086 : rel_exps_mark_used(sql->sa, rel, rel->r);
643 395086 : rel_mark_used(sql, rel->l, 0);
644 395086 : rel_mark_used(sql, rel->r, 0);
645 395086 : break;
646 : }
647 2177193 : }
648 :
649 : static sql_rel * rel_dce_sub(mvc *sql, sql_rel *rel);
650 :
651 : static sql_rel *
652 1812167 : rel_remove_unused(mvc *sql, sql_rel *rel)
653 : {
654 1812167 : int needed = 0;
655 :
656 1812167 : if (!rel)
657 : return rel;
658 :
659 1806477 : switch(rel->op) {
660 667304 : case op_basetable: {
661 667304 : sql_table *t = rel->l;
662 :
663 667304 : if (t && isReplicaTable(t)) /* TODO fix rewriting in rel_distribute.c */
664 : return rel;
665 : }
666 : /* fall through */
667 : case op_table:
668 672957 : if (rel->exps && (rel->op != op_table || !IS_TABLE_PROD_FUNC(rel->flag))) {
669 7914439 : for(node *n=rel->exps->h; n && !needed; n = n->next) {
670 7247172 : sql_exp *e = n->data;
671 :
672 7247172 : if (!e->used)
673 199429 : needed = 1;
674 : }
675 :
676 667267 : if (!needed)
677 : return rel;
678 :
679 1234335 : for(node *n=rel->exps->h; n;) {
680 1034907 : node *next = n->next;
681 1034907 : sql_exp *e = n->data;
682 :
683 : /* atleast one (needed for crossproducts, count(*), rank() and single value projections) !, handled by rel_exps_mark_used */
684 1034907 : if (!e->used && list_length(rel->exps) > 1)
685 360078 : list_remove_node(rel->exps, NULL, n);
686 : n = next;
687 : }
688 : }
689 205118 : if (rel->op == op_table && (IS_TABLE_PROD_FUNC(rel->flag) || rel->flag == TABLE_FROM_RELATION))
690 5690 : rel->l = rel_remove_unused(sql, rel->l);
691 : return rel;
692 :
693 16559 : case op_topn:
694 : case op_sample:
695 :
696 16559 : if (rel->l)
697 16559 : rel->l = rel_remove_unused(sql, rel->l);
698 : return rel;
699 :
700 510070 : case op_project:
701 : case op_groupby:
702 :
703 510070 : if (/*rel->l &&*/ rel->exps) {
704 2219535 : for(node *n=rel->exps->h; n && !needed; n = n->next) {
705 1709465 : sql_exp *e = n->data;
706 :
707 1709465 : if (!e->used)
708 22264 : needed = 1;
709 : }
710 510070 : if (!needed)
711 : return rel;
712 :
713 531928 : for(node *n=rel->exps->h; n;) {
714 509664 : node *next = n->next;
715 509664 : sql_exp *e = n->data;
716 :
717 : /* atleast one (needed for crossproducts, count(*), rank() and single value projections) */
718 509664 : if (!e->used && list_length(rel->exps) > 1)
719 396683 : list_remove_node(rel->exps, NULL, n);
720 : n = next;
721 : }
722 : }
723 : return rel;
724 :
725 134125 : case op_join:
726 : case op_left:
727 : case op_right:
728 : case op_full:
729 134125 : if (list_length(rel->attr) > 1) {
730 0 : for(node *n=rel->attr->h; n && !needed; n = n->next) {
731 0 : sql_exp *e = n->data;
732 :
733 0 : if (!e->used)
734 0 : needed = 1;
735 : }
736 0 : if (!needed)
737 : return rel;
738 :
739 0 : for(node *n=rel->attr->h; n;) {
740 0 : node *next = n->next;
741 0 : sql_exp *e = n->data;
742 :
743 0 : if (!e->used)
744 0 : list_remove_node(rel->attr, NULL, n);
745 : n = next;
746 : }
747 : }
748 : return rel;
749 :
750 : case op_union:
751 : case op_inter:
752 : case op_except:
753 :
754 : case op_insert:
755 : case op_update:
756 : case op_delete:
757 : case op_truncate:
758 : case op_merge:
759 :
760 : case op_select:
761 :
762 : case op_semi:
763 : case op_anti:
764 : return rel;
765 397627 : case op_ddl:
766 397627 : 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) {
767 32150 : if (rel->l)
768 31798 : rel->l = rel_remove_unused(sql, rel->l);
769 : } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
770 236 : if (rel->l)
771 236 : rel->l = rel_remove_unused(sql, rel->l);
772 236 : if (rel->r)
773 236 : rel->r = rel_remove_unused(sql, rel->r);
774 : }
775 : return rel;
776 : }
777 : return rel;
778 : }
779 :
780 : static void
781 1213653 : rel_dce_refs(mvc *sql, sql_rel *rel, list *refs)
782 : {
783 1213653 : if (!rel || (rel_is_ref(rel) && list_find(refs, rel, NULL)))
784 12612 : return ;
785 :
786 1201041 : switch(rel->op) {
787 352096 : case op_table:
788 : case op_topn:
789 : case op_sample:
790 : case op_project:
791 : case op_groupby:
792 : case op_select:
793 :
794 352096 : if (rel->l && (rel->op != op_table || rel->flag != TRIGGER_WRAPPER))
795 340002 : rel_dce_refs(sql, rel->l, refs);
796 : break;
797 :
798 : case op_basetable:
799 : case op_insert:
800 : case op_truncate:
801 : break;
802 :
803 5807 : case op_update:
804 : case op_delete:
805 :
806 5807 : if (rel->r)
807 5703 : rel_dce_refs(sql, rel->r, refs);
808 : break;
809 :
810 151725 : case op_union:
811 : case op_inter:
812 : case op_except:
813 : case op_join:
814 : case op_left:
815 : case op_right:
816 : case op_full:
817 : case op_semi:
818 : case op_anti:
819 : case op_merge:
820 :
821 151725 : if (rel->l)
822 151725 : rel_dce_refs(sql, rel->l, refs);
823 151725 : if (rel->r)
824 151725 : rel_dce_refs(sql, rel->r, refs);
825 : break;
826 398988 : case op_ddl:
827 :
828 398988 : 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) {
829 33467 : if (rel->l)
830 33115 : rel_dce_refs(sql, rel->l, refs);
831 : } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
832 280 : if (rel->l)
833 280 : rel_dce_refs(sql, rel->l, refs);
834 280 : if (rel->r)
835 246 : rel_dce_refs(sql, rel->r, refs);
836 : } break;
837 : }
838 :
839 1201043 : if (rel_is_ref(rel) && !list_find(refs, rel, NULL))
840 11799 : list_prepend(refs, rel);
841 : }
842 :
843 : static sql_rel *
844 3761074 : rel_dce_down(mvc *sql, sql_rel *rel, int skip_proj)
845 : {
846 3761074 : if (!rel)
847 : return rel;
848 :
849 3761074 : if (!skip_proj && rel_is_ref(rel))
850 : return rel;
851 :
852 3735231 : switch(rel->op) {
853 1282221 : case op_basetable:
854 : case op_table:
855 :
856 1282221 : if (skip_proj && rel->l && rel->op == op_table && rel->flag != TRIGGER_WRAPPER)
857 59 : rel->l = rel_dce_down(sql, rel->l, 0);
858 640893 : if (!skip_proj)
859 640893 : rel_dce_sub(sql, rel);
860 : /* fall through */
861 :
862 : case op_truncate:
863 : return rel;
864 :
865 3352 : case op_insert:
866 3352 : rel_used(rel->r);
867 3352 : rel_dce_sub(sql, rel->r);
868 3352 : return rel;
869 :
870 6991 : case op_update:
871 : case op_delete:
872 :
873 6991 : if (skip_proj && rel->r)
874 5703 : rel->r = rel_dce_down(sql, rel->r, 0);
875 1184 : if (!skip_proj)
876 1184 : rel_dce_sub(sql, rel);
877 : return rel;
878 :
879 951708 : case op_topn:
880 : case op_sample:
881 : case op_project:
882 : case op_groupby:
883 :
884 951708 : if (skip_proj && rel->l)
885 520012 : rel->l = rel_dce_down(sql, rel->l, is_topn(rel->op) || is_sample(rel->op));
886 425154 : if (!skip_proj)
887 425154 : rel_dce_sub(sql, rel);
888 : return rel;
889 :
890 46266 : case op_union:
891 : case op_inter:
892 : case op_except:
893 46266 : if (skip_proj) {
894 24177 : if (rel->l)
895 24177 : rel->l = rel_dce_down(sql, rel->l, 0);
896 24177 : if (rel->r)
897 24177 : rel->r = rel_dce_down(sql, rel->r, 0);
898 : }
899 22089 : if (!skip_proj)
900 22089 : rel_dce_sub(sql, rel);
901 : return rel;
902 :
903 613855 : case op_select:
904 613855 : if (rel->l)
905 613855 : rel->l = rel_dce_down(sql, rel->l, 0);
906 : return rel;
907 :
908 391446 : case op_join:
909 : case op_left:
910 : case op_right:
911 : case op_full:
912 : case op_semi:
913 : case op_anti:
914 : case op_merge:
915 391446 : if (rel->l)
916 391446 : rel->l = rel_dce_down(sql, rel->l, 0);
917 391446 : if (rel->r)
918 391446 : rel->r = rel_dce_down(sql, rel->r, 0);
919 391446 : if (!skip_proj && !list_empty(rel->attr))
920 134125 : rel_dce_sub(sql, rel);
921 : return rel;
922 :
923 397705 : case op_ddl:
924 397705 : 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) {
925 32184 : if (rel->l)
926 32025 : rel->l = rel_dce_down(sql, rel->l, 0);
927 : } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
928 280 : if (rel->l)
929 280 : rel->l = rel_dce_down(sql, rel->l, 0);
930 280 : if (rel->r)
931 246 : rel->r = rel_dce_down(sql, rel->r, 0);
932 : }
933 : return rel;
934 : }
935 : return rel;
936 : }
937 :
938 : /* DCE
939 : *
940 : * Based on top relation expressions mark sub expressions as used.
941 : * Then recurse down until the projections. Clean them up and repeat.
942 : */
943 :
944 : static sql_rel *
945 1757650 : rel_dce_sub(mvc *sql, sql_rel *rel)
946 : {
947 1757650 : if (!rel)
948 : return rel;
949 :
950 : /*
951 : * Mark used up until the next project
952 : * For setops we need to first mark, then remove
953 : * because of positional dependency
954 : */
955 1757650 : rel_mark_used(sql, rel, 1);
956 1757647 : rel = rel_remove_unused(sql, rel);
957 1757648 : rel_dce_down(sql, rel, 1);
958 1757648 : return rel;
959 : }
960 :
961 : /* add projects under set ops */
962 : static sql_rel *
963 1981631 : rel_add_projects(mvc *sql, sql_rel *rel)
964 : {
965 1981631 : if (!rel)
966 : return rel;
967 :
968 1981631 : switch(rel->op) {
969 : case op_basetable:
970 : case op_truncate:
971 : return rel;
972 9159 : case op_insert:
973 : case op_update:
974 : case op_delete:
975 9159 : if (rel->r)
976 9055 : rel->r = rel_add_projects(sql, rel->r);
977 : return rel;
978 83413 : case op_union:
979 : case op_inter:
980 : case op_except:
981 : /* We can only reduce the list of expressions of an set op
982 : * if the projection under it can also be reduced.
983 : */
984 83413 : if (rel->l) {
985 83413 : sql_rel *l = rel->l;
986 :
987 83413 : if (!is_project(l->op) && !need_distinct(rel))
988 2 : l = rel_project(sql->sa, l, rel_projections(sql, l, NULL, 1, 1));
989 83413 : rel->l = rel_add_projects(sql, l);
990 : }
991 83413 : if (rel->r) {
992 83413 : sql_rel *r = rel->r;
993 :
994 83413 : if (!is_project(r->op) && !need_distinct(rel))
995 19 : r = rel_project(sql->sa, r, rel_projections(sql, r, NULL, 1, 1));
996 83413 : rel->r = rel_add_projects(sql, r);
997 : }
998 : return rel;
999 708868 : case op_topn:
1000 : case op_sample:
1001 : case op_project:
1002 : case op_groupby:
1003 : case op_select:
1004 : case op_table:
1005 708868 : if (rel->l && (rel->op != op_table || rel->flag != TRIGGER_WRAPPER))
1006 685464 : rel->l = rel_add_projects(sql, rel->l);
1007 : return rel;
1008 277762 : case op_join:
1009 : case op_left:
1010 : case op_right:
1011 : case op_full:
1012 : case op_semi:
1013 : case op_anti:
1014 : case op_merge:
1015 277762 : if (rel->l)
1016 277762 : rel->l = rel_add_projects(sql, rel->l);
1017 277762 : if (rel->r)
1018 277762 : rel->r = rel_add_projects(sql, rel->r);
1019 : return rel;
1020 399253 : case op_ddl:
1021 399253 : 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) {
1022 33732 : if (rel->l)
1023 33380 : rel->l = rel_add_projects(sql, rel->l);
1024 : } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
1025 280 : if (rel->l)
1026 280 : rel->l = rel_add_projects(sql, rel->l);
1027 280 : if (rel->r)
1028 246 : rel->r = rel_add_projects(sql, rel->r);
1029 : }
1030 : return rel;
1031 : }
1032 : return rel;
1033 : }
1034 :
1035 : static sql_rel *
1036 530857 : rel_dce_(mvc *sql, sql_rel *rel)
1037 : {
1038 530857 : list *refs = sa_list(sql->sa);
1039 :
1040 530857 : rel_dce_refs(sql, rel, refs);
1041 530857 : if (refs) {
1042 542656 : for(node *n = refs->h; n; n = n->next) {
1043 11799 : sql_rel *i = n->data;
1044 :
1045 11799 : while (!rel_is_ref(i) && i->l && !is_base(i->op))
1046 : i = i->l;
1047 11799 : if (i)
1048 11799 : rel_used(i);
1049 : }
1050 : }
1051 530857 : rel = rel_add_projects(sql, rel);
1052 530856 : rel_used(rel);
1053 530853 : rel_dce_sub(sql, rel);
1054 530851 : return rel;
1055 : }
1056 :
1057 : /* Remove unused expressions */
1058 : static sql_rel *
1059 530857 : rel_dce(visitor *v, global_props *gp, sql_rel *rel)
1060 : {
1061 530857 : (void) gp;
1062 530857 : return rel_dce_(v->sql, rel);
1063 : }
1064 :
1065 : run_optimizer
1066 596803 : bind_dce(visitor *v, global_props *gp)
1067 : {
1068 596803 : int flag = v->sql->sql_optimizer;
1069 596803 : return gp->opt_cycle == 0 && gp->opt_level == 1 && (flag & dce) ? rel_dce : NULL;
1070 : }
1071 :
1072 :
1073 : static int
1074 85106 : topn_sample_safe_exps( list *exps, bool nil_limit )
1075 : {
1076 : /* Limit only expression lists are always save */
1077 85106 : if (list_length(exps) == 1)
1078 : return 1;
1079 1358 : for (node *n = exps->h; n; n = n->next ) {
1080 925 : sql_exp *e = n->data;
1081 :
1082 925 : if (!e || e->type != e_atom || (!nil_limit && exp_is_null(e)))
1083 59 : return 0;
1084 : }
1085 : return 1;
1086 : }
1087 :
1088 : static list *
1089 309 : sum_limit_offset(mvc *sql, sql_rel *rel)
1090 : {
1091 : /* for sample we always propagate, or if the expression list only consists of a limit expression, we copy it */
1092 309 : if (is_sample(rel->op) || list_length(rel->exps) == 1)
1093 304 : return exps_copy(sql, rel->exps);
1094 5 : assert(list_length(rel->exps) == 2);
1095 5 : sql_subtype *lng = sql_bind_localtype("lng");
1096 5 : 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);
1097 : /* for remote plans, make sure the output type is a bigint */
1098 5 : if (subtype_cmp(lng, exp_subtype(add)) != 0)
1099 5 : add = exp_convert(sql->sa, add, exp_subtype(add), lng);
1100 5 : return list_append(sa_list(sql->sa), add);
1101 : }
1102 :
1103 : /*
1104 : * Push TopN (only LIMIT, no ORDER BY) down through projections underneath crossproduct, i.e.,
1105 : *
1106 : * topn( topn(
1107 : * project( project(
1108 : * crossproduct( crossproduct(
1109 : * L, => topn( L )[ n ],
1110 : * R topn( R )[ n ]
1111 : * ) )
1112 : * )[ Cs ]* )[ Cs ]*
1113 : * )[ n ] )[ n ]
1114 : *
1115 : * (TODO: in case of n==1 we can omit the original top-level TopN)
1116 : *
1117 : * also push topn under (non reordering) projections.
1118 : */
1119 : static sql_rel *
1120 134090 : rel_push_topn_and_sample_down_(visitor *v, sql_rel *rel)
1121 : {
1122 134090 : sql_rel *rp = NULL, *r = rel->l, *rpp = NULL;
1123 :
1124 134090 : if (is_topn(rel->op) && !rel_is_ref(rel) &&
1125 50637 : r && r->op == op_table && r->flag != TRIGGER_WRAPPER && !rel_is_ref(r) && r->r) {
1126 3 : sql_exp *op = r->r;
1127 3 : sql_subfunc *f = op->f;
1128 :
1129 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]) {
1130 : /* push limit, to arguments of file_loader */
1131 0 : list *args = op->l;
1132 0 : if (list_length(args) == 2) {
1133 0 : sql_exp *topN = rel->exps->h->data;
1134 0 : sql_exp *offset = rel->exps->h->next? rel->exps->h->next->data:NULL;
1135 0 : atom *topn = topN->l;
1136 0 : if (offset) {
1137 0 : atom *b1 = (atom *)offset->l, *c = atom_add(v->sql->sa, b1, topn);
1138 :
1139 0 : if (!c)
1140 : return rel;
1141 0 : if (atom_cmp(c, topn) < 0) /* overflow */
1142 : return rel;
1143 : topn = c;
1144 : }
1145 0 : append(args, exp_atom(v->sql->sa, topn));
1146 0 : v->changes++;
1147 : }
1148 : }
1149 : }
1150 :
1151 134090 : if ((is_topn(rel->op) || is_sample(rel->op)) && topn_sample_safe_exps(rel->exps, true)) {
1152 50723 : sql_rel *(*func) (sql_allocator *, sql_rel *, list *) = is_topn(rel->op) ? rel_topn : rel_sample;
1153 :
1154 : /* nested topN relations */
1155 50723 : if (r && is_topn(rel->op) && is_topn(r->op) && !rel_is_ref(r)) {
1156 0 : sql_exp *topN1 = rel->exps->h->data, *topN2 = r->exps->h->data;
1157 0 : sql_exp *offset1 = list_length(rel->exps) > 1 ? rel->exps->h->next->data : NULL;
1158 0 : sql_exp *offset2 = list_length(r->exps) > 1 ? r->exps->h->next->data : NULL;
1159 :
1160 0 : if (topN1->l && topN2->l && (!offset1 || offset1->l) && (!offset2 || offset2->l)) { /* no parameters */
1161 0 : bool changed = false;
1162 :
1163 0 : if ((!offset1 || (offset1->type == e_atom && offset1->l)) && (!offset2 || (offset2->type == e_atom && offset2->l))) { /* only atoms */
1164 0 : if (!offset1 && offset2) {
1165 0 : list_append(rel->exps, exp_copy(v->sql, offset2));
1166 0 : changed = true;
1167 0 : } else if (offset1 && offset2) { /* sum offsets */
1168 0 : atom *b1 = (atom *)offset1->l, *b2 = (atom *)offset2->l, *c = atom_add(v->sql->sa, b1, b2);
1169 :
1170 0 : if (!c) /* error, don't apply optimization, WARNING because of this the offset optimization must come before the limit one */
1171 : return rel;
1172 0 : if (atom_cmp(c, b2) < 0) /* overflow */
1173 0 : c = atom_int(v->sql->sa, sql_bind_localtype("lng"), GDK_lng_max);
1174 0 : offset1->l = c;
1175 0 : changed = true;
1176 : }
1177 : }
1178 :
1179 0 : if (topN1->type == e_atom && topN1->l && topN2->type == e_atom && topN2->l) { /* only atoms */
1180 0 : atom *a1 = (atom *)topN1->l, *a2 = (atom *)topN2->l;
1181 :
1182 0 : if (!a2->isnull && (a1->isnull || atom_cmp(a1, a2) >= 0)) { /* topN1 is not set or is larger than topN2 */
1183 0 : rel->exps->h->data = exp_copy(v->sql, topN2);
1184 0 : changed = true;
1185 : }
1186 : }
1187 :
1188 0 : if (changed) {
1189 0 : rel->l = r->l;
1190 0 : r->l = NULL;
1191 0 : rel_destroy(r);
1192 0 : v->changes++;
1193 0 : return rel;
1194 : }
1195 : }
1196 : }
1197 :
1198 50723 : if (r && is_simple_project(r->op) && need_distinct(r))
1199 : return rel;
1200 :
1201 : /* push topn/sample under projections */
1202 50718 : if (!rel_is_ref(rel) && r && is_simple_project(r->op) && !need_distinct(r) && !rel_is_ref(r) && r->l && list_empty(r->r)) {
1203 : sql_rel *x = r, *px = x;
1204 :
1205 32697 : while (is_simple_project(x->op) && !need_distinct(x) && !rel_is_ref(x) && x->l && list_empty(x->r)) {
1206 16368 : px = x;
1207 16368 : x = x->l;
1208 : }
1209 : /* only push topn once */
1210 16328 : if (x && x->op == rel->op)
1211 : return rel;
1212 :
1213 16315 : rel->l = x;
1214 16315 : px->l = rel;
1215 16315 : rel = r;
1216 16315 : v->changes++;
1217 16315 : return rel;
1218 : }
1219 :
1220 34389 : if (!topn_sample_safe_exps(rel->exps, false))
1221 : return rel;
1222 :
1223 : /* duplicate topn/sample direct under union or crossproduct */
1224 34330 : if (r && !rel_is_ref(r) && r->l && r->r && ((is_union(r->op) && r->exps) || (r->op == op_join && list_empty(r->exps)))) {
1225 196 : sql_rel *u = r, *x;
1226 196 : sql_rel *ul = u->l;
1227 196 : sql_rel *ur = u->r;
1228 196 : bool changed = false;
1229 :
1230 196 : x = ul;
1231 256 : while (is_simple_project(x->op) && !need_distinct(x) && !rel_is_ref(x) && x->l && list_empty(x->r))
1232 60 : x = x->l;
1233 196 : if (x && x->op != rel->op) { /* only push topn once */
1234 79 : ul = func(v->sql->sa, ul, sum_limit_offset(v->sql, rel));
1235 79 : set_processed(ul);
1236 79 : u->l = ul;
1237 79 : changed = true;
1238 : }
1239 :
1240 196 : x = ur;
1241 249 : while (is_simple_project(x->op) && !need_distinct(x) && !rel_is_ref(x) && x->l && list_empty(x->r))
1242 53 : x = x->l;
1243 196 : if (x && x->op != rel->op) { /* only push topn once */
1244 78 : ur = func(v->sql->sa, ur, sum_limit_offset(v->sql, rel));
1245 78 : set_processed(ur);
1246 78 : u->r = ur;
1247 78 : changed = true;
1248 : }
1249 :
1250 196 : if (changed)
1251 80 : v->changes++;
1252 196 : return rel;
1253 : }
1254 :
1255 : /* duplicate topn/sample + [ project-order ] under union */
1256 : if (r && !rp)
1257 34134 : rp = r->l;
1258 34134 : if (r && r->exps && is_simple_project(r->op) && !rel_is_ref(r) && !list_empty(r->r) && r->l && is_union(rp->op)) {
1259 178 : sql_rel *u = rp, *ou = u, *x, *ul = u->l, *ur = u->r;
1260 178 : list *rcopy = NULL;
1261 :
1262 : /* only push topn/sample once */
1263 178 : x = ul;
1264 223 : while (is_simple_project(x->op) && !need_distinct(x) && !rel_is_ref(x) && x->l && list_empty(x->r))
1265 45 : x = x->l;
1266 178 : if (x && x->op == rel->op)
1267 : return rel;
1268 : x = ur;
1269 161 : while (is_simple_project(x->op) && !need_distinct(x) && !rel_is_ref(x) && x->l && list_empty(x->r))
1270 89 : x = x->l;
1271 72 : if (x && x->op == rel->op)
1272 : return rel;
1273 :
1274 72 : rcopy = exps_copy(v->sql, r->r);
1275 239 : for (node *n = rcopy->h ; n ; n = n->next) {
1276 167 : sql_exp *e = n->data;
1277 167 : set_descending(e); /* remove ordering properties for projected columns */
1278 167 : set_nulls_first(e);
1279 : }
1280 72 : ul = rel_dup(ul);
1281 72 : ur = rel_dup(ur);
1282 72 : if (!is_project(ul->op))
1283 1 : ul = rel_project(v->sql->sa, ul,
1284 : rel_projections(v->sql, ul, NULL, 1, 1));
1285 72 : if (!is_project(ur->op))
1286 1 : ur = rel_project(v->sql->sa, ur,
1287 : rel_projections(v->sql, ur, NULL, 1, 1));
1288 72 : rel_rename_exps(v->sql, u->exps, ul->exps);
1289 72 : rel_rename_exps(v->sql, u->exps, ur->exps);
1290 :
1291 : /* introduce projects under the set */
1292 72 : ul = rel_project(v->sql->sa, ul, NULL);
1293 72 : ul->exps = exps_copy(v->sql, r->exps);
1294 : /* possibly add order by column */
1295 72 : ul->exps = list_distinct(list_merge(ul->exps, exps_copy(v->sql, rcopy), NULL), (fcmp) exp_equal, (fdup) NULL);
1296 72 : ul->nrcols = list_length(ul->exps);
1297 72 : ul->r = exps_copy(v->sql, r->r);
1298 72 : set_processed(ul);
1299 72 : ul = func(v->sql->sa, ul, sum_limit_offset(v->sql, rel));
1300 72 : set_processed(ul);
1301 :
1302 72 : ur = rel_project(v->sql->sa, ur, NULL);
1303 72 : ur->exps = exps_copy(v->sql, r->exps);
1304 : /* possibly add order by column */
1305 72 : ur->exps = list_distinct(list_merge(ur->exps, exps_copy(v->sql, rcopy), NULL), (fcmp) exp_equal, (fdup) NULL);
1306 72 : ur->nrcols = list_length(ur->exps);
1307 72 : ur->r = exps_copy(v->sql, r->r);
1308 72 : set_processed(ur);
1309 72 : ur = func(v->sql->sa, ur, sum_limit_offset(v->sql, rel));
1310 72 : set_processed(ur);
1311 :
1312 72 : u = rel_setop(v->sql->sa, ul, ur, op_union);
1313 72 : u->exps = exps_alias(v->sql, r->exps);
1314 72 : u->nrcols = list_length(u->exps);
1315 72 : set_processed(u);
1316 : /* possibly add order by column */
1317 72 : u->exps = list_distinct(list_merge(u->exps, rcopy, NULL), (fcmp) exp_equal, (fdup) NULL);
1318 72 : if (need_distinct(r)) {
1319 0 : set_distinct(ul);
1320 0 : set_distinct(ur);
1321 : }
1322 :
1323 : /* zap names */
1324 72 : rel_no_rename_exps(u->exps);
1325 72 : rel_destroy(ou);
1326 :
1327 72 : ur = rel_project(v->sql->sa, u, exps_alias(v->sql, r->exps));
1328 72 : ur->r = r->r;
1329 72 : r->l = NULL;
1330 :
1331 72 : if (need_distinct(r))
1332 0 : set_distinct(ur);
1333 :
1334 72 : rel_destroy(r);
1335 72 : rel->l = ur;
1336 72 : v->changes++;
1337 72 : return rel;
1338 : }
1339 : /* a left outer join b order by a.* limit L, can be copied into a */
1340 : /* topn ( project (orderby)( optional project ( left ())
1341 : * rel r rp */
1342 33956 : if (r && !rp)
1343 64 : rp = r->l;
1344 33956 : if (r && rp && is_simple_project(rp->op) && !rp->r && rp->l)
1345 33956 : rpp = rp->l;
1346 33956 : if (r && r->exps && is_simple_project(r->op) && !rel_is_ref(r) && r->r && r->l && ((!rpp && is_left(rp->op)) ||
1347 543 : (rpp && is_left(rpp->op)))) {
1348 23 : sql_rel *lj = rpp?rpp:rp;
1349 23 : sql_rel *l = lj->l;
1350 23 : list *obes = r->r, *nobes = sa_list(v->sql->sa);
1351 23 : int fnd = 1;
1352 63 : for (node *n = obes->h; n && fnd; n = n->next) {
1353 40 : sql_exp *obe = n->data;
1354 40 : int asc = is_ascending(obe);
1355 40 : int nl = nulls_last(obe);
1356 : /* only simple rename expressions */
1357 40 : sql_exp *pe = exps_find_exp(r->exps, obe);
1358 40 : if (pe && rpp)
1359 31 : pe = exps_find_exp(rp->exps, pe);
1360 40 : if (pe)
1361 40 : pe = rel_find_exp(l, pe);
1362 40 : if (pe) {
1363 40 : pe = exp_ref(v->sql, pe);
1364 40 : if (asc)
1365 30 : set_ascending(pe);
1366 40 : if (nl)
1367 5 : set_nulls_last(pe);
1368 40 : append(nobes, pe);
1369 : }
1370 : else
1371 : fnd = 0;
1372 : }
1373 23 : if (fnd && ((is_topn(rel->op) && !is_topn(l->op)) || (is_sample(rel->op) && !is_sample(l->op)))) {
1374 : /* inject topn */
1375 : /* Todo add order by */
1376 8 : sql_rel *ob = lj->l = rel_project(v->sql->sa, lj->l, rel_projections(v->sql, lj->l, NULL, 1, 1));
1377 8 : ob->r = nobes;
1378 8 : lj->l = func(v->sql->sa, lj->l, sum_limit_offset(v->sql, rel));
1379 8 : v->changes++;
1380 8 : return rel;
1381 : }
1382 : }
1383 : }
1384 : return rel;
1385 : }
1386 :
1387 : static sql_rel *
1388 33411 : rel_push_topn_and_sample_down(visitor *v, global_props *gp, sql_rel *rel)
1389 : {
1390 33411 : (void) gp;
1391 33411 : return rel_visitor_topdown(v, rel, &rel_push_topn_and_sample_down_);
1392 : }
1393 :
1394 : run_optimizer
1395 596797 : bind_push_topn_and_sample_down(visitor *v, global_props *gp)
1396 : {
1397 596797 : int flag = v->sql->sql_optimizer;
1398 596609 : return gp->opt_level == 1 && (gp->cnt[op_topn] || gp->cnt[op_sample]) &&
1399 630209 : (flag & push_topn_and_sample_down) ? rel_push_topn_and_sample_down : NULL;
1400 : }
|
