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, 2025 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_rel.h"
15 : #include "rel_basetable.h"
16 : #include "rel_exp.h"
17 : #include "rel_prop.h"
18 : #include "rel_unnest.h"
19 : #include "sql_semantic.h"
20 : #include "sql_mvc.h"
21 : #include "rel_rewriter.h"
22 : #include "sql_storage.h"
23 :
24 : void
25 193 : rel_set_exps(sql_rel *rel, list *exps)
26 : {
27 193 : rel->exps = exps;
28 193 : rel->nrcols = list_length(exps);
29 193 : }
30 :
31 : /* some projections results are order dependent (row_number etc) */
32 : int
33 1158288 : project_unsafe(sql_rel *rel, bool allow_identity)
34 : {
35 1158288 : sql_rel *sub = rel->l;
36 :
37 1158288 : if (need_distinct(rel) || rel->r /* order by */)
38 : return 1;
39 1091932 : if (list_empty(rel->exps))
40 : return 0;
41 : /* projects without sub and projects around ddl's cannot be changed */
42 1091921 : if (!sub || sub->op == op_ddl)
43 : return 1;
44 9379490 : for(node *n = rel->exps->h; n; n = n->next) {
45 8433834 : sql_exp *e = n->data, *ne;
46 :
47 : /* aggr func in project ! */
48 8433834 : if (exp_unsafe(e, allow_identity, false))
49 : return 1;
50 8392246 : if ((ne = rel_find_exp(rel, e)) && ne != e)
51 : return 1; /* no self referencing */
52 : }
53 : return 0;
54 : }
55 :
56 : /* we don't name relations directly, but sometimes we need the relation
57 : name. So we look it up in the first expression
58 :
59 : we should clean up (remove) this function.
60 : */
61 : sql_alias *
62 254932 : rel_name( sql_rel *r )
63 : {
64 259595 : if (is_basetable(r->op))
65 213921 : return rel_base_name(r);
66 50337 : if (!is_project(r->op) && !is_base(r->op) && r->l)
67 : return rel_name(r->l);
68 41011 : if (r->exps && list_length(r->exps)) {
69 41011 : sql_exp *e = r->exps->h->data;
70 41011 : if (exp_relname(e))
71 41011 : return exp_relname(e);
72 0 : if (e->type == e_column) {
73 0 : return e->l;
74 : }
75 : }
76 : return NULL;
77 : }
78 :
79 : sql_rel *
80 13912 : rel_distinct(sql_rel *l)
81 : {
82 13912 : set_distinct(l);
83 13912 : return l;
84 : }
85 :
86 : sql_rel *
87 783032 : rel_dup(sql_rel *r)
88 : {
89 783032 : sql_ref_inc(&r->ref);
90 783032 : return r;
91 : }
92 :
93 : static void
94 700125 : rel_destroy_(sql_rel *rel)
95 : {
96 700125 : if (!rel)
97 : return;
98 700125 : switch(rel->op){
99 : case op_basetable:
100 : break;
101 5213 : case op_table:
102 5213 : if ((IS_TABLE_PROD_FUNC(rel->flag) || rel->flag == TABLE_FROM_RELATION) && rel->l)
103 11 : rel_destroy(rel->l);
104 : break;
105 298274 : case op_join:
106 : case op_left:
107 : case op_right:
108 : case op_full:
109 : case op_semi:
110 : case op_anti:
111 : case op_union:
112 : case op_inter:
113 : case op_except:
114 : case op_insert:
115 : case op_update:
116 : case op_delete:
117 : case op_merge:
118 298274 : if (rel->l)
119 17761 : rel_destroy(rel->l);
120 298274 : if (rel->r)
121 17769 : rel_destroy(rel->r);
122 : break;
123 42772 : case op_munion:
124 : /* the rel->l might be in purpose NULL see rel_merge_table_rewrite_() */
125 42772 : if (rel->l)
126 128358 : for (node *n = ((list*)rel->l)->h; n; n = n->next)
127 85736 : rel_destroy(n->data);
128 : break;
129 339191 : case op_project:
130 : case op_groupby:
131 : case op_select:
132 : case op_topn:
133 : case op_sample:
134 : case op_truncate:
135 339191 : if (rel->l)
136 87113 : rel_destroy(rel->l);
137 : break;
138 0 : case op_ddl:
139 0 : 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) {
140 0 : if (rel->l)
141 0 : rel_destroy(rel->l);
142 : } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
143 0 : if (rel->l)
144 0 : rel_destroy(rel->l);
145 0 : if (rel->r)
146 0 : rel_destroy(rel->r);
147 : }
148 : break;
149 : }
150 : }
151 :
152 : void
153 1423563 : rel_destroy(sql_rel *rel)
154 : {
155 1423563 : if (!rel)
156 : return;
157 1423559 : if (sql_ref_dec(&rel->ref) > 0)
158 : return;
159 658130 : rel_destroy_(rel);
160 : }
161 :
162 : sql_rel*
163 3440596 : rel_create(allocator *sa)
164 : {
165 3440596 : sql_rel *r = SA_NEW(sa, sql_rel);
166 3440801 : if(!r)
167 : return NULL;
168 :
169 3440801 : *r = (sql_rel) {
170 : .card = CARD_ATOM,
171 : };
172 3440801 : sql_ref_init(&r->ref);
173 3440801 : return r;
174 : }
175 :
176 : sql_rel *
177 181 : rel_copy(mvc *sql, sql_rel *i, int deep)
178 : {
179 181 : sql_rel *rel;
180 :
181 181 : if (mvc_highwater(sql))
182 0 : return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
183 :
184 181 : rel = rel_create(sql->sa);
185 181 : if (!rel)
186 : return NULL;
187 :
188 181 : rel->op = i->op;
189 181 : switch(i->op) {
190 55 : case op_basetable:
191 55 : rel_base_copy(sql, i, rel);
192 55 : break;
193 0 : case op_table:
194 0 : if ((IS_TABLE_PROD_FUNC(i->flag) || i->flag == TABLE_FROM_RELATION) && i->l)
195 0 : rel->l = rel_copy(sql, i->l, deep);
196 0 : rel->r = i->r;
197 0 : break;
198 80 : case op_project:
199 : case op_groupby:
200 80 : if (i->l)
201 68 : rel->l = rel_copy(sql, i->l, deep);
202 80 : if (i->r) {
203 8 : if (!deep) {
204 0 : rel->r = list_dup(i->r, (fdup) NULL);
205 : } else {
206 8 : rel->r = exps_copy(sql, i->r);
207 : }
208 : }
209 : break;
210 2 : case op_munion:
211 2 : if (i->l)
212 2 : rel->l = list_dup(i->l, (fdup) rel_dup);
213 : break;
214 0 : case op_ddl:
215 0 : if (i->flag == ddl_output || i->flag == ddl_create_seq || i->flag == ddl_alter_seq || i->flag == ddl_alter_table || i->flag == ddl_create_table || i->flag == ddl_create_view) {
216 0 : if (i->l)
217 0 : rel->l = rel_copy(sql, i->l, deep);
218 0 : } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
219 0 : if (i->l)
220 0 : rel->l = rel_copy(sql, i->l, deep);
221 0 : if (i->r)
222 0 : rel->r = rel_copy(sql, i->r, deep);
223 : }
224 : break;
225 23 : case op_select:
226 : case op_topn:
227 : case op_sample:
228 : case op_truncate:
229 23 : if (i->l)
230 23 : rel->l = rel_copy(sql, i->l, deep);
231 : break;
232 21 : case op_join:
233 : case op_left:
234 : case op_right:
235 : case op_full:
236 : case op_semi:
237 : case op_anti:
238 :
239 : case op_union:
240 : case op_inter:
241 : case op_except:
242 :
243 : case op_insert:
244 : case op_update:
245 : case op_delete:
246 : case op_merge:
247 21 : if (i->l)
248 21 : rel->l = rel_copy(sql, i->l, deep);
249 21 : if (i->r)
250 21 : rel->r = rel_copy(sql, i->r, deep);
251 : break;
252 : }
253 :
254 181 : rel->card = i->card;
255 181 : rel->flag = i->flag;
256 181 : rel->nrcols = i->nrcols;
257 181 : rel->grouped = i->grouped;
258 181 : rel->used = i->used;
259 :
260 181 : if (is_processed(i))
261 119 : set_processed(rel);
262 181 : if (is_dependent(i))
263 0 : set_dependent(rel);
264 181 : if (is_outer(i))
265 10 : set_outer(rel);
266 181 : if (is_single(i))
267 4 : set_single(rel);
268 181 : if (need_distinct(i))
269 4 : set_distinct(rel);
270 :
271 181 : rel->p = prop_copy(sql->sa, i->p);
272 181 : rel->exps = (!i->exps)?NULL:deep?exps_copy(sql, i->exps):list_dup(i->exps, (fdup)NULL);
273 181 : rel->attr = (!i->attr)?NULL:deep?exps_copy(sql, i->attr):list_dup(i->attr, (fdup)NULL);
274 181 : return rel;
275 : }
276 :
277 : sql_rel *
278 3979 : rel_select_copy(allocator *sa, sql_rel *l, list *exps)
279 : {
280 3979 : sql_rel *rel = rel_create(sa);
281 3979 : if(!rel)
282 : return NULL;
283 :
284 3979 : rel->l = l;
285 3979 : rel->r = NULL;
286 3979 : rel->op = op_select;
287 3979 : rel->exps = exps?list_dup(exps, (fdup)NULL):NULL;
288 3979 : rel->card = CARD_ATOM; /* no relation */
289 3979 : if (l) {
290 3979 : rel->card = l->card;
291 3979 : rel->nrcols = l->nrcols;
292 : }
293 : return rel;
294 : }
295 :
296 : sql_exp *
297 8261808 : rel_bind_column( mvc *sql, sql_rel *rel, const char *cname, int f, int no_tname)
298 : {
299 8261808 : int ambiguous = 0, multi = 0;
300 :
301 8261808 : if (!rel)
302 : return NULL;
303 8261808 : if (mvc_highwater(sql))
304 0 : return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
305 :
306 8261808 : if (is_insert(rel->op))
307 0 : rel = rel->r;
308 8261808 : if ((is_project(rel->op) || is_base(rel->op))) {
309 4514906 : sql_exp *e = NULL;
310 :
311 4514906 : if (is_base(rel->op) && !rel->exps)
312 4089338 : return rel_base_bind_column(sql, rel, cname, no_tname);
313 425568 : if (!list_empty(rel->exps)) {
314 425429 : e = exps_bind_column(rel->exps, cname, &ambiguous, &multi, no_tname);
315 425429 : if (ambiguous || multi)
316 11 : return sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s' ambiguous", cname);
317 425418 : if (!e && is_groupby(rel->op) && rel->r) {
318 288 : sql_rel *l = rel->l;
319 288 : if (l)
320 288 : e = rel_bind_column( sql, l, cname, 0, no_tname);
321 288 : if (e) {
322 140 : e = exps_refers(e, rel->r);
323 140 : if (ambiguous || multi)
324 0 : return sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s' ambiguous", cname);
325 : return e;
326 : }
327 : }
328 : }
329 264574 : if (!e && (is_sql_sel(f) || is_sql_having(f) || !f) && is_groupby(rel->op) && rel->r) {
330 185 : e = exps_bind_column(rel->r, cname, &ambiguous, &multi, no_tname);
331 185 : if (ambiguous || multi)
332 0 : return sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s' ambiguous", cname);
333 185 : if (e) {
334 1 : e = exp_ref(sql, e);
335 1 : e->card = rel->card;
336 1 : return e;
337 : }
338 : }
339 160843 : if (e)
340 160843 : return exp_ref(sql, e);
341 : }
342 4011475 : if (is_simple_project(rel->op) && rel->l) {
343 243143 : if (!is_processed(rel))
344 0 : return rel_bind_column(sql, rel->l, cname, f, no_tname);
345 3768332 : } else if (is_set(rel->op)) {
346 20 : assert(is_processed(rel));
347 : return NULL;
348 : } else if (is_join(rel->op)) {
349 3241793 : sql_exp *e1 = rel_bind_column(sql, rel->l, cname, f, no_tname), *e2 = NULL, *res;
350 :
351 3241793 : if (e1 && (is_right(rel->op) || is_full(rel->op)))
352 8 : set_has_nil(e1);
353 1619220 : if (!e1 || !is_freevar(e1)) {
354 3241793 : e2 = rel_bind_column(sql, rel->r, cname, f, no_tname);
355 3241793 : if (e2 && (is_left(rel->op) || is_full(rel->op)))
356 54 : set_has_nil(e2);
357 3241793 : if (e1 && e2 && !is_dependent(rel))
358 21 : return sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s' ambiguous", cname);
359 : }
360 3241772 : if (!e1 && !e2 && !list_empty(rel->attr)) {
361 0 : e1 = exps_bind_column(rel->attr, cname, &ambiguous, &multi, no_tname);
362 0 : if (ambiguous || multi)
363 0 : return sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s' ambiguous", cname);
364 : }
365 3241772 : if (e1 && e2)
366 0 : res = !is_intern(e1) ? e1 : e2;
367 : else
368 3241772 : res = e1 ? e1 : e2;
369 1622573 : if (res)
370 1708363 : set_not_unique(res);
371 3241772 : return res;
372 : } else if (is_semi(rel->op) ||
373 : is_select(rel->op) ||
374 : is_topn(rel->op) ||
375 : is_sample(rel->op)) {
376 505109 : if (rel->l)
377 505109 : return rel_bind_column(sql, rel->l, cname, f, no_tname);
378 : }
379 : return NULL;
380 : }
381 :
382 : sql_exp *
383 4667863 : rel_bind_column2( mvc *sql, sql_rel *rel, sql_alias *tname, const char *cname, int f)
384 : {
385 4667863 : int ambiguous = 0, multi = 0;
386 :
387 4667863 : if (!rel)
388 : return NULL;
389 4667863 : if (mvc_highwater(sql))
390 0 : return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
391 :
392 4667863 : if ((is_project(rel->op) || is_base(rel->op))) {
393 2187354 : sql_exp *e = NULL;
394 :
395 2187354 : if (is_basetable(rel->op) && !rel->exps)
396 1403717 : return rel_base_bind_column2(sql, rel, tname, cname);
397 : /* in case of orderby we should also lookup the column in group by list (and use existing references) */
398 783637 : if (!list_empty(rel->exps)) {
399 783539 : e = exps_bind_column2(rel->exps, tname, cname, &multi);
400 783542 : if (multi)
401 1 : return sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s.%s' ambiguous", tname->name, cname);
402 783541 : if (!e && is_groupby(rel->op) && rel->r) {
403 89 : sql_rel *l = rel->l;
404 89 : if (l)
405 89 : e = rel_bind_column2( sql, l, tname, cname, 0);
406 89 : if (e) {
407 76 : e = exps_refers(e, rel->r);
408 76 : if (ambiguous || multi)
409 0 : return sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s%s%s' ambiguous",
410 : tname ? tname->name : "", tname ? "." : "", cname);
411 76 : if (e)
412 : return e;
413 : }
414 : }
415 : }
416 245281 : if (!e && (is_sql_sel(f) || is_sql_having(f) || !f) && is_groupby(rel->op) && rel->r) {
417 111 : e = exps_bind_column2(rel->r, tname, cname, &multi);
418 111 : if (multi)
419 0 : return sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s.%s' ambiguous", tname->name, cname);
420 111 : if (e) {
421 10 : e = exp_ref(sql, e);
422 10 : e->card = rel->card;
423 10 : return e;
424 : }
425 : }
426 538352 : if (e)
427 538352 : return exp_ref(sql, e);
428 : }
429 2725780 : if (is_simple_project(rel->op) && rel->l) {
430 236331 : if (!is_processed(rel))
431 9 : return rel_bind_column2(sql, rel->l, tname, cname, f);
432 2489449 : } else if (is_set(rel->op)) {
433 3 : assert(is_processed(rel));
434 : return NULL;
435 : } else if (is_join(rel->op)) {
436 1993408 : sql_exp *e = rel_bind_column2(sql, rel->l, tname, cname, f);
437 :
438 1993408 : if (e && (is_right(rel->op) || is_full(rel->op)))
439 195 : set_has_nil(e);
440 195 : if (!e) {
441 882428 : e = rel_bind_column2(sql, rel->r, tname, cname, f);
442 882428 : if (e && (is_left(rel->op) || is_full(rel->op)))
443 22556 : set_has_nil(e);
444 : }
445 418302 : if (!e && !list_empty(rel->attr)) {
446 1 : e = exps_bind_column2(rel->attr, tname, cname, &multi);
447 1 : if (multi)
448 0 : return sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s.%s' ambiguous", tname->name, cname);
449 : }
450 395746 : if (e)
451 1597663 : set_not_unique(e);
452 1993408 : return e;
453 : } else if (is_semi(rel->op) ||
454 : is_select(rel->op) ||
455 : is_topn(rel->op) ||
456 : is_sample(rel->op)) {
457 487101 : if (rel->l)
458 487101 : return rel_bind_column2(sql, rel->l, tname, cname, f);
459 : }
460 490463 : while (tname) { /* lookup direct (one step down) nested (composite) type field */
461 245263 : sql_exp *exp = NULL;
462 245263 : if (tname->parent) {
463 21 : exp = rel_bind_column2(sql, rel, tname->parent, tname->name, f);
464 : } else {
465 245242 : exp = rel_bind_column(sql, rel, tname->name, f, 0);
466 : }
467 245263 : if (exp && !exp->tpe.multiset) {
468 3009 : sql_exp *e = exps_bind_column(exp->f, cname, NULL, NULL, 0);
469 3009 : if (e) {
470 59 : e = exp_ref(sql, e);
471 59 : reset_intern(e);
472 59 : return e;
473 : }
474 : }
475 245204 : tname = tname->parent;
476 : }
477 : return NULL;
478 : }
479 :
480 : sql_exp *
481 0 : rel_first_column(mvc *sql, sql_rel *r)
482 : {
483 0 : if (is_simple_project(r->op))
484 0 : return r->exps->h->data;
485 :
486 0 : list *exps = rel_projections(sql, r, NULL, 1, 1);
487 :
488 0 : if (!list_empty(exps))
489 0 : return exps->h->data;
490 :
491 : return NULL;
492 : }
493 :
494 : /* rel_inplace_* used to convert a rel node into another flavor */
495 : static void
496 85497 : rel_inplace_reset_props(sql_rel *rel)
497 : {
498 85497 : rel->flag = 0;
499 85497 : rel->attr = NULL;
500 85497 : reset_dependent(rel);
501 85497 : set_processed(rel);
502 : }
503 :
504 : sql_rel *
505 112 : rel_inplace_basetable(sql_rel *rel, sql_rel *bt)
506 : {
507 112 : assert(is_basetable(bt->op));
508 :
509 112 : rel_destroy_(rel);
510 112 : rel_inplace_reset_props(rel);
511 112 : rel->l = bt->l;
512 112 : rel->r = bt->r;
513 112 : rel->op = op_basetable;
514 112 : rel->exps = bt->exps;
515 112 : rel->card = CARD_MULTI;
516 112 : rel->nrcols = bt->nrcols;
517 112 : return rel;
518 : }
519 :
520 : sql_rel *
521 20 : rel_inplace_setop(mvc *sql, sql_rel *rel, sql_rel *l, sql_rel *r, operator_type setop, list *exps)
522 : {
523 20 : rel_destroy_(rel);
524 20 : rel_inplace_reset_props(rel);
525 20 : rel->l = l;
526 20 : rel->r = r;
527 20 : rel->op = setop;
528 20 : rel->card = CARD_MULTI;
529 20 : rel_setop_set_exps(sql, rel, exps, false);
530 20 : return rel;
531 : }
532 :
533 : sql_rel *
534 40528 : rel_inplace_setop_n_ary(mvc *sql, sql_rel *rel, list *rl, operator_type setop, list *exps)
535 : {
536 : // TODO: for now we only deal with munion
537 40528 : assert(setop == op_munion);
538 40528 : rel_destroy_(rel);
539 40528 : rel_inplace_reset_props(rel);
540 : /* rl should be a list of relations */
541 40528 : rel->l = rl;
542 40528 : rel->r = NULL;
543 40528 : rel->op = setop;
544 40528 : rel->card = CARD_MULTI;
545 40528 : rel_setop_n_ary_set_exps(sql, rel, exps, false);
546 40528 : return rel;
547 : }
548 :
549 : sql_rel *
550 43554 : rel_inplace_project(allocator *sa, sql_rel *rel, sql_rel *l, list *e)
551 : {
552 43554 : if (!l) {
553 43501 : l = rel_create(sa);
554 43501 : if(!l)
555 : return NULL;
556 :
557 43501 : *l = *rel;
558 43501 : l->ref.refcnt = 1;
559 : } else {
560 53 : rel_destroy_(rel);
561 : }
562 43554 : rel_inplace_reset_props(rel);
563 43554 : rel->l = l;
564 43554 : rel->r = NULL;
565 43554 : rel->op = op_project;
566 43554 : rel->exps = e;
567 43554 : rel->card = CARD_MULTI;
568 43554 : if (l) {
569 43554 : rel->nrcols = l->nrcols;
570 43554 : assert (exps_card(rel->exps) <= rel->card);
571 : }
572 : return rel;
573 : }
574 :
575 : sql_rel *
576 758 : rel_inplace_select(sql_rel *rel, sql_rel *l, list *exps)
577 : {
578 758 : rel_destroy_(rel);
579 758 : rel_inplace_reset_props(rel);
580 758 : rel->l = l;
581 758 : rel->r = NULL;
582 758 : rel->op = op_select;
583 758 : rel->exps = exps;
584 758 : rel->card = CARD_ATOM; /* no relation */
585 758 : if (l) {
586 758 : rel->card = l->card;
587 758 : rel->nrcols = l->nrcols;
588 758 : if (is_single(l))
589 0 : set_single(rel);
590 : }
591 758 : return rel;
592 : }
593 :
594 : sql_rel *
595 525 : rel_inplace_groupby(sql_rel *rel, sql_rel *l, list *groupbyexps, list *exps )
596 : {
597 525 : rel_destroy_(rel);
598 525 : rel_inplace_reset_props(rel);
599 525 : rel->card = CARD_ATOM;
600 525 : if (groupbyexps)
601 420 : rel->card = CARD_AGGR;
602 525 : rel->l = l;
603 525 : rel->r = groupbyexps;
604 525 : rel->exps = exps;
605 525 : rel->nrcols = l->nrcols;
606 525 : rel->op = op_groupby;
607 525 : return rel;
608 : }
609 :
610 : sql_rel *
611 0 : rel_inplace_munion(sql_rel *rel, list *rels)
612 : {
613 0 : rel_destroy_(rel);
614 0 : rel_inplace_reset_props(rel);
615 : // TODO: what is the semantics of cardinality? is that right?
616 0 : rel->card = CARD_MULTI;
617 0 : rel->nrcols = 0;
618 0 : if (rels)
619 0 : rel->l = rels;
620 0 : if (rels) {
621 0 : for (node* n = rels->h; n; n = n->next) {
622 0 : sql_rel *r = n->data;
623 : // TODO: could we overflow the nrcols this way?
624 0 : rel->nrcols += r->nrcols;
625 : }
626 : }
627 0 : rel->r = NULL;
628 0 : rel->exps = NULL;
629 0 : rel->op = op_munion;
630 0 : return rel;
631 : }
632 :
633 : /* this function is to be used with the above rel_inplace_* functions */
634 : sql_rel *
635 719 : rel_dup_copy(allocator *sa, sql_rel *rel)
636 : {
637 719 : sql_rel *nrel = rel_create(sa);
638 :
639 719 : if (!nrel)
640 : return NULL;
641 719 : *nrel = *rel;
642 719 : nrel->ref.refcnt = 1;
643 719 : switch(nrel->op){
644 : case op_basetable:
645 : case op_ddl:
646 : break;
647 0 : case op_table:
648 0 : if ((IS_TABLE_PROD_FUNC(nrel->flag) || nrel->flag == TABLE_FROM_RELATION) && nrel->l)
649 0 : rel_dup(nrel->l);
650 : break;
651 709 : case op_join:
652 : case op_left:
653 : case op_right:
654 : case op_full:
655 : case op_semi:
656 : case op_anti:
657 : case op_union:
658 : case op_inter:
659 : case op_except:
660 : case op_insert:
661 : case op_update:
662 : case op_delete:
663 : case op_merge:
664 709 : if (nrel->l)
665 709 : rel_dup(nrel->l);
666 709 : if (nrel->r)
667 709 : rel_dup(nrel->r);
668 : break;
669 10 : case op_project:
670 : case op_groupby:
671 : case op_select:
672 : case op_topn:
673 : case op_sample:
674 : case op_truncate:
675 10 : if (nrel->l)
676 10 : rel_dup(nrel->l);
677 : break;
678 0 : case op_munion:
679 : // TODO: is that even right?
680 0 : if (nrel->l)
681 0 : nrel->l = list_dup(nrel->l, (fdup) rel_dup);
682 : break;
683 : }
684 : return nrel;
685 : }
686 :
687 : sql_rel *
688 2902 : rel_setop(allocator *sa, sql_rel *l, sql_rel *r, operator_type setop)
689 : {
690 2902 : sql_rel *rel = rel_create(sa);
691 2902 : if(!rel)
692 : return NULL;
693 2902 : rel->l = l;
694 2902 : rel->r = r;
695 2902 : rel->op = setop;
696 2902 : rel->exps = NULL;
697 2902 : rel->card = CARD_MULTI;
698 2902 : assert(l->nrcols == r->nrcols);
699 2902 : rel->nrcols = l->nrcols;
700 2902 : return rel;
701 : }
702 :
703 : sql_rel *
704 2484 : rel_setop_check_types(mvc *sql, sql_rel *l, sql_rel *r, list *ls, list *rs, operator_type op)
705 : {
706 2484 : list *nls = new_exp_list(sql->sa);
707 2484 : list *nrs = new_exp_list(sql->sa);
708 2484 : node *n, *m;
709 :
710 2484 : if(!nls || !nrs)
711 : return NULL;
712 :
713 5202 : for (n = ls->h, m = rs->h; n && m; n = n->next, m = m->next) {
714 2721 : sql_exp *le = n->data;
715 2721 : sql_exp *re = m->data;
716 :
717 2721 : if (rel_convert_types(sql, l, r, &le, &re, 1, type_set) < 0)
718 3 : return NULL;
719 2718 : if (!le->alias.label && le->type == e_convert)
720 0 : exp_label(sql->sa, le, ++sql->label);
721 2718 : if (!re->alias.label && re->type == e_convert)
722 0 : exp_label(sql->sa, re, ++sql->label);
723 2718 : append(nls, le);
724 2718 : append(nrs, re);
725 : }
726 2481 : l = rel_project(sql->sa, l, nls);
727 2481 : r = rel_project(sql->sa, r, nrs);
728 2481 : set_processed(l);
729 2481 : set_processed(r);
730 2481 : return rel_setop(sql->sa, l, r, op);
731 : }
732 :
733 : void
734 2881 : rel_setop_set_exps(mvc *sql, sql_rel *rel, list *exps, bool keep_props)
735 : {
736 2881 : sql_rel *l = rel->l, *r = rel->r;
737 2881 : list *lexps = l->exps, *rexps = r->exps;
738 :
739 2881 : if (!is_project(l->op))
740 23 : lexps = rel_projections(sql, l, NULL, 0, 1);
741 2881 : if (!is_project(r->op))
742 24 : rexps = rel_projections(sql, r, NULL, 0, 1);
743 :
744 2881 : assert(is_set(rel->op) /*&& list_length(lexps) == list_length(rexps) && list_length(exps) == list_length(lexps)*/);
745 :
746 11868 : for (node *n = exps->h, *m = lexps->h, *o = rexps->h ; m && n && o ; n = n->next, m = m->next,o = o->next) {
747 8987 : sql_exp *e = n->data, *f = m->data, *g = o->data;
748 :
749 8987 : assert(e->alias.label);
750 8987 : e->nid = 0; /* setops are positional */
751 8987 : if (is_union(rel->op)) { /* propagate set_has_no_nil only if it's applicable to both sides of the union*/
752 6045 : if (has_nil(f) || has_nil(g))
753 5149 : set_has_nil(e);
754 : else
755 896 : set_has_no_nil(e);
756 6045 : if (!keep_props) {
757 6045 : e->p = NULL; /* remove all the properties on unions on the general case */
758 6045 : set_not_unique(e);
759 : }
760 : }
761 8987 : e->card = CARD_MULTI; /* multi cardinality */
762 : }
763 2881 : rel->nrcols = l->nrcols;
764 2881 : rel->exps = exps;
765 2881 : }
766 :
767 : sql_rel *
768 66518 : rel_setop_n_ary(allocator *sa, list *rels, operator_type setop)
769 : {
770 : // TODO: for now we support only n-ary union
771 66518 : assert(setop == op_munion);
772 :
773 66518 : if (!rels)
774 : return NULL;
775 :
776 66518 : assert(list_length(rels) >= 2);
777 66518 : sql_rel *rel = rel_create(sa);
778 66518 : if(!rel)
779 : return NULL;
780 :
781 66518 : rel->l = rels;
782 66518 : rel->r = NULL;
783 66518 : rel->op = setop;
784 66518 : rel->exps = NULL;
785 66518 : rel->card = CARD_MULTI;
786 : // TODO: properly introduce the assertion over rels elements
787 : /*assert(l->nrcols == r->nrcols);*/
788 66518 : rel->nrcols = ((sql_rel*)rels->h->data)->nrcols;
789 66518 : return rel;
790 : }
791 :
792 : sql_rel *
793 62577 : rel_setop_n_ary_check_types(mvc *sql, sql_rel *l, sql_rel *r, list *ls, list *rs, operator_type op)
794 : {
795 : // TODO: for now we support only 2 relation in the list at ->l of
796 : // the n-ary operator. In the future this function should be variadic (?)
797 : // TODO: for now we support only n-ary union
798 62577 : assert(op == op_munion);
799 :
800 : /* NOTE: this is copied logic from rel_setop_check_types. A DRY-er approach
801 : * would be to call rel_setop_check_types which will return a binary
802 : * setop from which we could extract ->l and ->r and add them in a list
803 : * for the op_munion. This is kind of ugly though...
804 : */
805 62577 : list *nls = new_exp_list(sql->sa);
806 62577 : list *nrs = new_exp_list(sql->sa);
807 62577 : node *n, *m;
808 62577 : list* rels;
809 :
810 62577 : if(!nls || !nrs)
811 : return NULL;
812 :
813 499044 : for (n = ls->h, m = rs->h; n && m; n = n->next, m = m->next) {
814 436471 : sql_exp *le = n->data;
815 436471 : sql_exp *re = m->data;
816 :
817 436471 : if (rel_convert_types(sql, l, r, &le, &re, 1, type_set) < 0)
818 4 : return NULL;
819 436467 : append(nls, le);
820 436467 : append(nrs, re);
821 : }
822 62573 : l = rel_project(sql->sa, l, nls);
823 62573 : r = rel_project(sql->sa, r, nrs);
824 62573 : set_processed(l);
825 62573 : set_processed(r);
826 :
827 : /* create a list with only 2 sql_rel entries for the n-ary set op */
828 62573 : rels = sa_list(sql->sa);
829 62573 : append(rels, l);
830 62573 : append(rels, r);
831 :
832 62573 : return rel_setop_n_ary(sql->sa, rels, op);
833 : }
834 :
835 : void
836 105472 : rel_setop_n_ary_set_exps(mvc *sql, sql_rel *rel, list *exps, bool keep_props)
837 : {
838 105472 : list *rexps;
839 105472 : sql_rel *r;
840 :
841 : /* set the exps properties first */
842 839230 : for (node *m = exps->h; m; m = m->next) {
843 : /* the nil/no_nil property will be set in the next loop where
844 : * we go through the exps of every rel of the rels. For now no_nil
845 : */
846 733758 : sql_exp *e = (sql_exp*)m->data;
847 733758 : set_has_no_nil(e);
848 : /* remove all the properties on unions on the general case */
849 733758 : if (!keep_props) {
850 733465 : e->p = NULL;
851 733465 : set_not_unique(e);
852 : }
853 : }
854 :
855 : /* for every relation in the list of relations */
856 317090 : for (node *n = ((list*)rel->l)->h; n; n = n->next) {
857 211618 : r = n->data;
858 211618 : rexps = r->exps;
859 :
860 211618 : if (!is_project(r->op))
861 13622 : rexps = rel_projections(sql, r, NULL, 0, 1);
862 :
863 : /* go through the relation's exps */
864 1682159 : for (node *m = exps->h, *o = rexps->h; m && o; m = m->next, o = o->next) {
865 1470541 : sql_exp *e = m->data, *f = o->data;
866 : /* for multi-union if any operand has nil then set the nil prop for the op exp */
867 1470541 : if (is_munion(rel->op) && has_nil(f))
868 511959 : set_has_nil(e);
869 1470541 : e->card = CARD_MULTI;
870 : }
871 : }
872 :
873 105472 : rel->exps = exps;
874 : // TODO: probably setting nrcols is redundant as we have already done
875 : // that when we create the setop_n_ary. check rel_setop_n_ary()
876 105472 : rel->nrcols = ((sql_rel*)((list*)rel->l)->h->data)->nrcols;
877 105472 : }
878 :
879 : sql_rel *
880 538372 : rel_crossproduct(allocator *sa, sql_rel *l, sql_rel *r, operator_type join)
881 : {
882 538372 : sql_rel *rel = rel_create(sa);
883 538372 : if(!rel)
884 : return NULL;
885 :
886 538372 : rel->l = l;
887 538372 : rel->r = r;
888 538372 : rel->op = join;
889 538372 : rel->exps = NULL;
890 538372 : rel->card = CARD_MULTI;
891 538372 : rel->nrcols = l->nrcols + r->nrcols;
892 538372 : return rel;
893 : }
894 :
895 : sql_exp *
896 0 : rel_is_constant(sql_rel **R, sql_exp *e)
897 : {
898 0 : sql_rel *rel = *R;
899 :
900 0 : if (rel && rel->op == op_project && list_length(rel->exps) == 1 &&
901 0 : !rel->l && !rel->r && !rel_is_ref(rel) && e->type == e_column) {
902 0 : sql_exp *ne = rel_find_exp(rel, e);
903 0 : if (ne) {
904 0 : rel_destroy(rel);
905 0 : *R = NULL;
906 0 : return ne;
907 : }
908 : }
909 : return e;
910 : }
911 :
912 : sql_rel *
913 17082 : rel_topn(allocator *sa, sql_rel *l, list *exps )
914 : {
915 17082 : sql_rel *rel = rel_create(sa);
916 17083 : if(!rel)
917 : return NULL;
918 :
919 17083 : rel->l = l;
920 17083 : rel->r = NULL;
921 17083 : rel->op = op_topn;
922 17083 : rel->exps = exps;
923 17083 : rel->card = l->card;
924 17083 : rel->nrcols = l->nrcols;
925 17083 : return rel;
926 : }
927 :
928 : sql_rel *
929 23 : rel_sample(allocator *sa, sql_rel *l, list *exps )
930 : {
931 23 : sql_rel *rel = rel_create(sa);
932 23 : if(!rel)
933 : return NULL;
934 :
935 23 : rel->l = l;
936 23 : rel->r = NULL;
937 23 : rel->op = op_sample;
938 23 : rel->exps = exps;
939 23 : rel->card = l->card;
940 23 : rel->nrcols = l->nrcols;
941 23 : return rel;
942 : }
943 :
944 : sql_rel *
945 15415 : rel_label( mvc *sql, sql_rel *r, int all)
946 : {
947 15415 : int nr = ++sql->label;
948 15415 : char tname[16], *tnme;
949 15415 : char cname[16], *cnme = NULL;
950 :
951 15415 : tnme = sa_strdup(sql->sa, number2name(tname, sizeof(tname), nr));
952 15423 : sql_alias *ta = a_create(sql->sa, tnme);
953 15418 : if (!is_simple_project(r->op))
954 616 : r = rel_project(sql->sa, r, rel_projections(sql, r, NULL, 1, 1));
955 15418 : if (!list_empty(r->exps)) {
956 15418 : list_hash_clear(r->exps);
957 60410 : for (node *ne = r->exps->h; ne; ne = ne->next) {
958 44987 : sql_exp *e = ne->data;
959 :
960 44987 : if (!is_freevar(e)) {
961 44987 : if (all) {
962 44990 : nr = ++sql->label;
963 44990 : cnme = sa_strdup(sql->sa, number2name(cname, sizeof(cname), nr));
964 : }
965 44988 : exp_setname(sql, e, ta, cnme );
966 : }
967 : }
968 : }
969 : /* op_projects can have a order by list */
970 15428 : if (!list_empty(r->r)) {
971 0 : for (node *ne = ((list*)r->r)->h; ne; ne = ne->next) {
972 0 : if (all) {
973 0 : nr = ++sql->label;
974 0 : cnme = sa_strdup(sql->sa, number2name(cname, sizeof(cname), nr));
975 : }
976 0 : exp_setname(sql, ne->data, ta, cnme );
977 : }
978 : }
979 15423 : return r;
980 : }
981 :
982 : sql_exp *
983 32959 : rel_project_add_exp( mvc *sql, sql_rel *rel, sql_exp *e)
984 : {
985 32959 : assert(is_project(rel->op));
986 :
987 32959 : if (!e->alias.label)
988 111 : exp_label(sql->sa, e, ++sql->label);
989 32959 : if (is_simple_project(rel->op)) {
990 32955 : sql_rel *l = rel->l;
991 32955 : if (!rel->exps)
992 24 : rel->exps = new_exp_list(sql->sa);
993 32955 : if (l && is_groupby(l->op) && exp_card(e) <= CARD_ATOM && list_empty(l->exps))
994 4 : e = rel_project_add_exp(sql, l, e);
995 32955 : if (e->card > rel->card)
996 0 : rel->card = e->card;
997 32955 : append(rel->exps, e);
998 32955 : rel->nrcols++;
999 4 : } else if (is_groupby(rel->op)) {
1000 4 : return rel_groupby_add_aggr(sql, rel, e);
1001 : }
1002 32955 : e = exp_ref(sql, e);
1003 32955 : return e;
1004 : }
1005 :
1006 : sql_rel *
1007 292778 : rel_select_add_exp(allocator *sa, sql_rel *l, sql_exp *e)
1008 : {
1009 292778 : if ((l->op != op_select && !is_outerjoin(l->op)) || rel_is_ref(l))
1010 8300 : return rel_select(sa, l, e);
1011 :
1012 : /* allow during AST->relational for bool expressions as well
1013 : if (e->type != e_cmp && e->card > CARD_ATOM) {
1014 : sql_exp *t = exp_atom_bool(sa, 1);
1015 : e = exp_compare(sa, e, t, cmp_equal);
1016 : }
1017 : */
1018 284478 : if (!l->exps)
1019 3843 : l->exps = new_exp_list(sa);
1020 284478 : append(l->exps, e);
1021 284478 : return l;
1022 : }
1023 :
1024 : void
1025 499231 : rel_join_add_exp( allocator *sa, sql_rel *rel, sql_exp *e)
1026 : {
1027 499231 : assert(is_join(rel->op) || is_semi(rel->op) || is_select(rel->op));
1028 :
1029 499231 : if (!rel->exps)
1030 452261 : rel->exps = new_exp_list(sa);
1031 499231 : append(rel->exps, e);
1032 499231 : if (e->card > rel->card)
1033 0 : rel->card = e->card;
1034 499231 : }
1035 :
1036 : sql_exp *
1037 95671 : rel_groupby_add_aggr(mvc *sql, sql_rel *rel, sql_exp *e)
1038 : {
1039 95671 : sql_exp *m = NULL, *ne;
1040 :
1041 95671 : if (list_empty(rel->r))
1042 27157 : rel->card = e->card = CARD_ATOM;
1043 :
1044 95671 : if ((m=exps_any_match(rel->exps, e)) == NULL) {
1045 49540 : if (!exp_name(e))
1046 49516 : exp_label(sql->sa, e, ++sql->label);
1047 49540 : append(rel->exps, e);
1048 49540 : rel->nrcols++;
1049 49540 : m = e;
1050 : }
1051 95671 : ne = exp_ref(sql, m);
1052 95671 : return ne;
1053 : }
1054 :
1055 : sql_rel *
1056 276203 : rel_select(allocator *sa, sql_rel *l, sql_exp *e)
1057 : {
1058 276203 : sql_rel *rel;
1059 :
1060 276203 : if (l && is_outerjoin(l->op) && !is_processed(l)) {
1061 211 : if (e) {
1062 195 : if (!l->exps)
1063 180 : l->exps = new_exp_list(sa);
1064 195 : append(l->exps, e);
1065 : }
1066 211 : return l;
1067 : }
1068 :
1069 275992 : if (l && is_select(l->op) && !rel_is_ref(l)) { /* refine old select */
1070 16967 : if (e)
1071 8289 : rel_select_add_exp(sa, l, e);
1072 16967 : return l;
1073 : }
1074 259025 : rel = rel_create(sa);
1075 259025 : if(!rel)
1076 : return NULL;
1077 :
1078 259025 : rel->l = l;
1079 259025 : rel->r = NULL;
1080 259025 : rel->op = op_select;
1081 259025 : rel->exps = new_exp_list(sa);
1082 259025 : if (e)
1083 190478 : rel_select_add_exp(sa, rel, e);
1084 259025 : rel->card = CARD_ATOM; /* no relation */
1085 259025 : if (l) {
1086 259025 : rel->card = l->card;
1087 259025 : rel->nrcols = l->nrcols;
1088 259025 : if (is_single(l))
1089 1550 : set_single(rel);
1090 : }
1091 : return rel;
1092 : }
1093 :
1094 : sql_rel *
1095 41818 : rel_groupby(mvc *sql, sql_rel *l, list *groupbyexps )
1096 : {
1097 41818 : sql_rel *rel = rel_create(sql->sa);
1098 41818 : list *aggrs = new_exp_list(sql->sa);
1099 41818 : node *en;
1100 41818 : if(!rel || !aggrs) {
1101 0 : rel_destroy(rel);
1102 0 : return NULL;
1103 : }
1104 :
1105 41818 : rel->card = CARD_ATOM;
1106 : /* reduce duplicates in groupbyexps */
1107 41818 : if (groupbyexps && list_length(groupbyexps) > 1) {
1108 8232 : list *gexps = sa_list(sql->sa);
1109 :
1110 40300 : for (en = groupbyexps->h; en; en = en->next) {
1111 32068 : sql_exp *e = en->data, *ne = exps_find_exp(gexps, e);
1112 :
1113 32068 : if (!ne) {
1114 31965 : list_append(gexps, e);
1115 : } else {
1116 103 : sql_alias *ername = exp_relname(e), *nername = exp_relname(ne);
1117 103 : const char *ename = exp_name(e), *nename = exp_name(ne);
1118 103 : if ((ername && !nername) || (!ername && nername) ||
1119 97 : (ername && nername && !a_match(ername,nername)) || strcmp(ename,nename) != 0)
1120 10 : list_append(gexps, e);
1121 : }
1122 : }
1123 : groupbyexps = gexps;
1124 : }
1125 :
1126 14225 : if (groupbyexps) {
1127 14225 : rel->card = CARD_AGGR;
1128 52048 : for (en = groupbyexps->h; en; en = en->next) {
1129 37823 : sql_exp *e = en->data, *ne;
1130 :
1131 37823 : if (exp_is_atom(e) && a_no_name(&e->alias)) { /* numeric lookup done later */
1132 29 : rel->flag = 1;
1133 29 : continue;
1134 : }
1135 : /* after the group by the cardinality reduces */
1136 37794 : e->card = MIN(e->card, rel->card); /* if the column is an atom, the cardinality should not change */
1137 37794 : if (!e->alias.label)
1138 86 : exp_label(sql->sa, e, ++sql->label);
1139 37794 : ne = exp_ref(sql, e);
1140 37794 : ne = exp_propagate(sql->sa, ne, e);
1141 37794 : append(aggrs, ne);
1142 : }
1143 : }
1144 41818 : rel->l = l;
1145 41818 : rel->r = groupbyexps;
1146 41818 : rel->exps = aggrs;
1147 41818 : rel->nrcols = aggrs?list_length(aggrs):0;
1148 41818 : rel->op = op_groupby;
1149 41818 : rel->grouped = 1;
1150 41818 : return rel;
1151 : }
1152 :
1153 : sql_rel *
1154 1014722 : rel_project(allocator *sa, sql_rel *l, list *e)
1155 : {
1156 1014722 : sql_rel *rel = rel_create(sa);
1157 1014679 : if(!rel)
1158 : return NULL;
1159 :
1160 1014679 : rel->l = l;
1161 1014679 : rel->r = NULL;
1162 1014679 : rel->op = op_project;
1163 1014679 : rel->exps = e;
1164 1014679 : rel->card = exps_card(e);
1165 1014929 : if (l) {
1166 819965 : rel->card = l->card;
1167 819965 : if (e)
1168 760663 : rel->nrcols = list_length(e);
1169 : else
1170 59302 : rel->nrcols = l->nrcols;
1171 819963 : rel->single = is_single(l);
1172 : }
1173 1014927 : if (e && !list_empty(e)) {
1174 954956 : set_processed(rel);
1175 954956 : rel->nrcols = list_length(e);
1176 : }
1177 : return rel;
1178 : }
1179 :
1180 : sql_rel *
1181 72968 : rel_project_exp(mvc *sql, sql_exp *e)
1182 : {
1183 72968 : if (!exp_name(e))
1184 72992 : exp_label(sql->sa, e, ++sql->label);
1185 72963 : return rel_project(sql->sa, NULL, list_append(sa_list(sql->sa), e));
1186 : }
1187 :
1188 : sql_rel *
1189 121029 : rel_list(allocator *sa, sql_rel *l, sql_rel *r)
1190 : {
1191 121029 : sql_rel *rel = rel_create(sa);
1192 121029 : if (!rel)
1193 : return NULL;
1194 121029 : if (!l)
1195 : return r;
1196 568 : rel->l = l;
1197 568 : rel->r = r;
1198 568 : rel->op = op_ddl;
1199 568 : rel->flag = ddl_list;
1200 568 : return rel;
1201 : }
1202 :
1203 : sql_rel *
1204 157 : rel_exception(allocator *sa, sql_rel *l, sql_rel *r, list *exps)
1205 : {
1206 157 : sql_rel *rel = rel_create(sa);
1207 157 : if(!rel)
1208 : return NULL;
1209 157 : rel->r = r;
1210 157 : rel->exps = exps;
1211 157 : rel->op = op_ddl;
1212 157 : rel->flag = ddl_exception;
1213 157 : if (l)
1214 157 : return rel_list(sa, rel, l); /* keep base relation on the right ! */
1215 : return rel;
1216 : }
1217 :
1218 : sql_rel *
1219 313 : rel_relational_func(allocator *sa, sql_rel *l, list *exps)
1220 : {
1221 313 : sql_rel *rel = rel_create(sa);
1222 313 : if(!rel)
1223 : return NULL;
1224 :
1225 313 : rel->flag = TABLE_PROD_FUNC;
1226 313 : rel->l = l;
1227 313 : rel->op = op_table;
1228 313 : rel->exps = exps;
1229 313 : rel->card = CARD_MULTI;
1230 313 : rel->nrcols = list_length(exps);
1231 313 : return rel;
1232 : }
1233 :
1234 : sql_rel *
1235 17475 : rel_table_func(allocator *sa, sql_rel *l, sql_exp *f, list *exps, int kind)
1236 : {
1237 17475 : sql_rel *rel = rel_create(sa);
1238 17475 : if(!rel)
1239 : return NULL;
1240 :
1241 17475 : assert(kind > 0);
1242 17475 : rel->flag = kind;
1243 17475 : rel->l = l; /* relation before call */
1244 17475 : rel->r = f; /* expression (table func call) */
1245 17475 : rel->op = op_table;
1246 17475 : rel->exps = exps;
1247 17475 : rel->card = CARD_MULTI;
1248 17475 : rel->nrcols = list_length(exps);
1249 17475 : return rel;
1250 : }
1251 :
1252 : static void
1253 290924 : exps_reset_props(list *exps, bool setnil)
1254 : {
1255 290924 : if (!list_empty(exps)) {
1256 3169358 : for (node *m = exps->h; m; m = m->next) {
1257 2878948 : sql_exp *e = m->data;
1258 :
1259 2878948 : if (setnil)
1260 192573 : set_has_nil(e);
1261 2878948 : set_not_unique(e);
1262 : }
1263 : }
1264 290924 : }
1265 :
1266 : /* Return a list with all the projection expressions, that optionally
1267 : * refer to the tname relation, anywhere in the relational tree
1268 : */
1269 : list *
1270 1050027 : _rel_projections(mvc *sql, sql_rel *rel, sql_alias *tname, int settname, int intern, int basecol /* basecol only */ )
1271 : {
1272 1110020 : list *lexps, *rexps = NULL, *exps = NULL, *rels;
1273 :
1274 1110020 : if (mvc_highwater(sql))
1275 9 : return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
1276 :
1277 1110015 : if (!rel)
1278 0 : return new_exp_list(sql->sa);
1279 :
1280 1110015 : if (!tname && is_basetable(rel->op) && !is_processed(rel))
1281 276475 : rel_base_use_all( sql, rel);
1282 :
1283 1110017 : switch(rel->op) {
1284 145462 : case op_join:
1285 : case op_left:
1286 : case op_right:
1287 : case op_full:
1288 145462 : lexps = _rel_projections(sql, rel->l, tname, settname, intern, basecol);
1289 145462 : exps_reset_props(lexps, is_right(rel->op) || is_full(rel->op));
1290 145462 : if (!rel->attr)
1291 144948 : rexps = _rel_projections(sql, rel->r, tname, settname, intern, basecol);
1292 145462 : exps_reset_props(rexps, is_left(rel->op) || is_full(rel->op));
1293 145462 : if (rexps)
1294 144948 : lexps = list_merge(lexps, rexps, (fdup)NULL);
1295 145462 : if (rel->attr)
1296 514 : append(lexps, exp_ref(sql, rel->attr->h->data));
1297 : return lexps;
1298 7517 : case op_groupby:
1299 7517 : if (list_empty(rel->exps) && rel->r) {
1300 0 : list *r = rel->r;
1301 :
1302 0 : exps = new_exp_list(sql->sa);
1303 0 : for (node *en = r->h; en; en = en->next) {
1304 0 : sql_exp *e = en->data;
1305 :
1306 0 : if (basecol && !is_basecol(e))
1307 0 : continue;
1308 0 : if (intern || !is_intern(e)) {
1309 0 : sql_exp *ne = exp_ref(sql, e);
1310 0 : if (settname && tname)
1311 0 : exp_setname(sql, ne, tname, exp_name(e));
1312 0 : assert(ne->alias.label);
1313 0 : e = ne;
1314 0 : append(exps, e);
1315 : }
1316 : }
1317 : return exps;
1318 : }
1319 : /* fall through */
1320 : case op_project:
1321 : case op_basetable:
1322 : case op_table:
1323 :
1324 : case op_union:
1325 : case op_except:
1326 : case op_inter:
1327 : case op_munion:
1328 904562 : if (is_basetable(rel->op) && !rel->exps)
1329 105089 : return rel_base_projection(sql, rel, intern);
1330 799473 : if (rel->exps) {
1331 734340 : exps = new_exp_list(sql->sa);
1332 6101312 : for (node *en = rel->exps->h; en; en = en->next) {
1333 5366963 : sql_exp *e = en->data;
1334 :
1335 5366963 : if (basecol && !is_basecol(e))
1336 61 : continue;
1337 5366902 : if (intern || !is_intern(e)) {
1338 5366897 : if (!e->alias.label)
1339 22294 : en->data = e = exp_label(sql->sa, e, ++sql->label);
1340 5366897 : sql_exp *ne = exp_ref(sql, e);
1341 5366903 : if (settname && tname)
1342 0 : exp_setname(sql, ne, tname, exp_name(e));
1343 5366903 : assert(ne->alias.label);
1344 5366903 : e = ne;
1345 5366903 : append(exps, e);
1346 : }
1347 : }
1348 : return exps;
1349 : }
1350 : /* differentiate for the munion set op (for now) */
1351 65133 : if (is_munion(rel->op)) {
1352 62648 : sql_rel *r = NULL;
1353 62648 : assert(rel->l);
1354 : /* get the exps from the first relation */
1355 62648 : rels = rel->l;
1356 62648 : if (rels->h)
1357 62648 : r = rels->h->data;
1358 62648 : if (r)
1359 62648 : exps = _rel_projections(sql, r, tname, settname, intern, basecol);
1360 : /* it's a multi-union (expressions have to be the same in all the operands)
1361 : * so we are ok only with the expressions of the first operand
1362 : */
1363 62648 : if (exps) {
1364 499214 : for (node *en = exps->h; en; en = en->next) {
1365 436566 : sql_exp *e = en->data;
1366 :
1367 436566 : e->card = rel->card;
1368 436566 : if (!settname) /* noname use alias */
1369 436566 : exp_setname(sql, e, exp_relname(e), exp_name(e));
1370 : }
1371 62648 : if (!settname)
1372 62648 : list_hash_clear(rel->l);
1373 : }
1374 62648 : return exps;
1375 : }
1376 : /* I only expect set relations to hit here */
1377 2485 : assert(is_set(rel->op));
1378 2485 : lexps = _rel_projections(sql, rel->l, tname, settname, intern, basecol);
1379 2485 : rexps = _rel_projections(sql, rel->r, tname, settname, intern, basecol);
1380 2485 : if (lexps && rexps) {
1381 :
1382 2485 : assert(list_length(lexps) == list_length(rexps));
1383 5211 : for (node *en = lexps->h; en; en = en->next) {
1384 2726 : sql_exp *e = en->data;
1385 :
1386 2726 : e->card = rel->card;
1387 2726 : if (!settname) /* noname use alias */
1388 2726 : exp_setname(sql, e, exp_relname(e), exp_name(e));
1389 : }
1390 2485 : if (!settname)
1391 2485 : list_hash_clear(lexps);
1392 : }
1393 : return lexps;
1394 :
1395 59993 : case op_ddl:
1396 : case op_semi:
1397 : case op_anti:
1398 :
1399 : case op_select:
1400 : case op_topn:
1401 : case op_sample:
1402 59993 : return _rel_projections(sql, rel->l, tname, settname, intern, basecol);
1403 : default:
1404 : return NULL;
1405 : }
1406 : }
1407 :
1408 : list *
1409 648990 : rel_projections(mvc *sql, sql_rel *rel, sql_alias *tname, int settname, int intern)
1410 : {
1411 648990 : assert(tname == NULL);
1412 648990 : return _rel_projections(sql, rel, tname, settname, intern, 0);
1413 : }
1414 :
1415 : /* find the path to the relation containing the base of the expression
1416 : (e_column), in most cases this means go down the join tree and
1417 : find the base column.
1418 : */
1419 : static sql_rel *
1420 4205798 : rel_bind_path_(mvc *sql, sql_rel *rel, sql_exp *e, list *path )
1421 : {
1422 4205798 : sql_rel *found = NULL;
1423 :
1424 4205798 : if (mvc_highwater(sql)) {
1425 0 : sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
1426 0 : return 0;
1427 : }
1428 :
1429 4205798 : switch (rel->op) {
1430 1927520 : case op_join:
1431 : case op_left:
1432 : case op_right:
1433 : case op_full:
1434 : /* first right (possible subquery) */
1435 1927520 : found = rel_bind_path_(sql, rel->r, e, path);
1436 1927520 : if (!found)
1437 1618662 : found = rel_bind_path_(sql, rel->l, e, path);
1438 1618662 : if (!found && !list_empty(rel->attr)) {
1439 502 : assert(e->nid);
1440 502 : if (exps_bind_nid(rel->attr, e->nid))
1441 534327 : found = rel;
1442 : }
1443 : break;
1444 124993 : case op_semi:
1445 : case op_anti:
1446 : case op_select:
1447 : case op_topn:
1448 : case op_sample:
1449 124993 : found = rel_bind_path_(sql, rel->l, e, path);
1450 124993 : break;
1451 2153285 : case op_basetable:
1452 : case op_munion:
1453 : case op_union:
1454 : case op_inter:
1455 : case op_except:
1456 : case op_groupby:
1457 : case op_project:
1458 : case op_table:
1459 2153285 : if (is_basetable(rel->op) && !rel->exps) {
1460 1891145 : assert(e->nid);
1461 1891145 : if (rel_base_has_nid(rel, e->nid))
1462 534327 : found = rel;
1463 262140 : } else if (rel->exps) {
1464 262140 : assert(e->nid);
1465 262140 : if (exps_bind_nid(rel->exps, e->nid))
1466 534327 : found = rel;
1467 : }
1468 : break;
1469 : case op_insert:
1470 : case op_update:
1471 : case op_delete:
1472 : case op_truncate:
1473 : case op_merge:
1474 : case op_ddl:
1475 : break;
1476 : }
1477 4205798 : if (path && found)
1478 2450854 : list_prepend(path, rel);
1479 : return found;
1480 : }
1481 :
1482 : static list *
1483 510570 : rel_bind_path(mvc *sql, sql_rel *rel, sql_exp *e, list *path)
1484 : {
1485 510570 : if (!path)
1486 : return NULL;
1487 :
1488 510570 : if (e->type == e_convert) {
1489 23781 : if (!(path = rel_bind_path(sql, rel, e->l, path)))
1490 : return NULL;
1491 486789 : } else if (e->type == e_column) {
1492 481088 : if (rel) {
1493 481088 : if (!rel_bind_path_(sql, rel, e, path)) {
1494 : /* something is wrong */
1495 : return NULL;
1496 : }
1497 : }
1498 481088 : return path;
1499 : }
1500 : /* default the top relation */
1501 29482 : append(path, rel);
1502 29482 : return path;
1503 : }
1504 :
1505 : sql_rel *
1506 53535 : rel_bind_nid(mvc *sql, sql_rel *rel, sql_exp *e)
1507 : {
1508 53535 : return rel_bind_path_(sql, rel, e, NULL);
1509 : }
1510 :
1511 : static sql_rel *
1512 19751 : rel_select_push_exp_down(mvc *sql, sql_rel *rel, sql_exp *e)
1513 : {
1514 19751 : sql_rel *r = rel->l, *jl = r->l, *jr = r->r;
1515 19751 : int left = r->op == op_join || r->op == op_left;
1516 19751 : int right = r->op == op_join || r->op == op_right;
1517 19751 : int done = 0;
1518 :
1519 19751 : assert(is_select(rel->op));
1520 19751 : if (!is_full(r->op) && !is_single(r)) {
1521 19751 : if (left && rel_rebind_exp(sql, jl, e)) {
1522 9 : done = 1;
1523 9 : r->l = jl = rel_select_add_exp(sql->sa, jl, e);
1524 19742 : } else if (right && rel_rebind_exp(sql, jr, e)) {
1525 6 : done = 1;
1526 6 : r->r = jr = rel_select_add_exp(sql->sa, jr, e);
1527 : }
1528 : }
1529 15 : if (!done)
1530 19736 : rel_select_add_exp(sql->sa, rel, e);
1531 19751 : return rel;
1532 : }
1533 :
1534 : /* ls is the left expression of the select, e is the select expression. */
1535 : sql_rel *
1536 105564 : rel_push_select(mvc *sql, sql_rel *rel, sql_exp *ls, sql_exp *e, int f)
1537 : {
1538 105564 : list *l = rel_bind_path(sql, rel, ls, sa_list(sql->sa));
1539 105564 : node *n;
1540 105564 : sql_rel *lrel = NULL, *p = NULL;
1541 :
1542 105564 : if (!l)
1543 : return NULL;
1544 105564 : if (is_sql_or(f)) /* expression has no clear parent relation, so filter current with it */
1545 15809 : return rel_select(sql->sa, rel, e);
1546 :
1547 259406 : for (n = l->h; n; n = n->next ) {
1548 258668 : lrel = n->data;
1549 :
1550 258668 : if (rel_is_ref(lrel))
1551 : break;
1552 :
1553 : /* push down as long as the operators allow this */
1554 257986 : if (!is_select(lrel->op) &&
1555 238585 : !(is_semi(lrel->op) && !rel_is_ref(lrel->l)) &&
1556 88335 : lrel->op != op_join &&
1557 : lrel->op != op_left)
1558 : break;
1559 : /* pushing through left head of a left join is allowed */
1560 169655 : if (lrel->op == op_left && (!n->next || lrel->l != n->next->data))
1561 : break;
1562 169651 : p = lrel;
1563 : }
1564 89755 : if (!lrel)
1565 : return NULL;
1566 89755 : if (p && is_select(p->op) && !rel_is_ref(p)) { /* refine old select */
1567 16944 : p = rel_select_push_exp_down(sql, p, e);
1568 : } else {
1569 72811 : sql_rel *n = rel_select(sql->sa, lrel, e);
1570 :
1571 72811 : if (p && p != lrel) {
1572 68034 : assert(p->op == op_join || p->op == op_left || is_semi(p->op));
1573 68034 : if (p->l == lrel) {
1574 25186 : p->l = n;
1575 : } else {
1576 42848 : p->r = n;
1577 : }
1578 : } else {
1579 4777 : if (rel != lrel)
1580 0 : assert(0);
1581 : rel = n;
1582 : }
1583 : }
1584 : return rel;
1585 : }
1586 :
1587 : /* ls and rs are the left and right expression of the join, e is the
1588 : join expression.
1589 : */
1590 : sql_rel *
1591 190350 : rel_push_join(mvc *sql, sql_rel *rel, sql_exp *ls, sql_exp *rs, sql_exp *rs2, sql_exp *e, int f)
1592 : {
1593 190350 : list *l = NULL, *r = NULL, *r2 = NULL;
1594 190350 : node *ln, *rn;
1595 190350 : sql_rel *lrel = NULL, *rrel = NULL, *rrel2 = NULL, *p = NULL;
1596 :
1597 190350 : if (!(l = rel_bind_path(sql, rel, ls, sa_list(sql->sa))) ||
1598 190350 : !(r = rel_bind_path(sql, rel, rs, sa_list(sql->sa))) ||
1599 525 : (rs2 && !(r2 = rel_bind_path(sql, rel, rs2, sa_list(sql->sa)))))
1600 0 : return NULL;
1601 :
1602 190350 : if (is_sql_or(f))
1603 1591 : return rel_push_select(sql, rel, ls, e, f);
1604 :
1605 188759 : p = rel;
1606 188759 : if (r2) {
1607 518 : node *rn2;
1608 :
1609 1043 : for (ln = l->h, rn = r->h, rn2 = r2->h; ln && rn && rn2; ln = ln->next, rn = rn->next, rn2 = rn2->next ) {
1610 549 : lrel = ln->data;
1611 549 : rrel = rn->data;
1612 549 : rrel2 = rn2->data;
1613 :
1614 549 : if (rel_is_ref(lrel) || rel_is_ref(rrel) || rel_is_ref(rrel2) || is_processed(lrel) || is_processed(rrel))
1615 : break;
1616 :
1617 : /* push down as long as the operators allow this
1618 : and the relation is equal.
1619 : */
1620 543 : if (lrel != rrel || lrel != rrel2 ||
1621 525 : (!is_select(lrel->op) &&
1622 71 : !(is_semi(lrel->op) && !rel_is_ref(lrel->l)) &&
1623 0 : lrel->op != op_join &&
1624 : lrel->op != op_left))
1625 : break;
1626 : /* pushing through left head of a left join is allowed */
1627 525 : if (lrel->op == op_left && (!ln->next || lrel->l != ln->next->data))
1628 : break;
1629 525 : p = lrel;
1630 : }
1631 : } else {
1632 823817 : for (ln = l->h, rn = r->h; ln && rn; ln = ln->next, rn = rn->next ) {
1633 820966 : lrel = ln->data;
1634 820966 : rrel = rn->data;
1635 :
1636 820966 : if (rel_is_ref(lrel) || rel_is_ref(rrel) || is_processed(lrel) || is_processed(rrel))
1637 : break;
1638 :
1639 : /* push down as long as the operators allow this
1640 : and the relation is equal.
1641 : */
1642 780102 : if (lrel != rrel ||
1643 637232 : (!is_select(lrel->op) &&
1644 633776 : !(is_semi(lrel->op) && !rel_is_ref(lrel->l)) &&
1645 1656 : lrel->op != op_join &&
1646 : lrel->op != op_left))
1647 : break;
1648 : /* pushing through left head of a left join is allowed */
1649 635576 : if (lrel->op == op_left && (!ln->next || lrel->l != ln->next->data))
1650 : break;
1651 635576 : p = lrel;
1652 : }
1653 : }
1654 188759 : if (!lrel || !rrel || (r2 && !rrel2))
1655 : return NULL;
1656 :
1657 : /* filter on columns of this relation */
1658 188759 : if ((lrel == rrel && (!r2 || lrel == rrel2) && lrel->op != op_join) || rel_is_ref(p)) {
1659 2821 : if (is_select(lrel->op) && !rel_is_ref(lrel)) {
1660 1148 : lrel = rel_select_push_exp_down(sql, lrel, e);
1661 1673 : } else if (p && is_select(p->op) && !rel_is_ref(p)) {
1662 1659 : p = rel_select_push_exp_down(sql, p, e);
1663 : } else {
1664 14 : sql_rel *n = rel_select(sql->sa, lrel, e);
1665 :
1666 14 : if (p && p != lrel) {
1667 14 : if (p->l == lrel)
1668 5 : p->l = n;
1669 : else
1670 9 : p->r = n;
1671 : } else {
1672 : rel = n;
1673 : }
1674 : }
1675 2821 : return rel;
1676 : }
1677 :
1678 185938 : rel_join_add_exp( sql->sa, p, e);
1679 185938 : return rel;
1680 : }
1681 :
1682 : sql_rel *
1683 14559 : rel_or(mvc *sql, sql_rel *rel, sql_rel *l, sql_rel *r, list *oexps, list *lexps, list *rexps)
1684 : {
1685 14559 : sql_rel *ll = l->l, *rl = r->l;
1686 14559 : list *ls, *rs;
1687 :
1688 14559 : assert(!lexps || l == r);
1689 14559 : if (l == r && lexps) { /* merge both lists */
1690 42 : sql_exp *e = exp_or(sql->sa, lexps, rexps, 0);
1691 42 : list *nl = oexps?oexps:new_exp_list(sql->sa);
1692 :
1693 42 : rel_destroy(r);
1694 42 : append(nl, e);
1695 42 : if (is_outerjoin(l->op) && is_processed(l))
1696 0 : l = rel_select(sql->sa, l, NULL);
1697 42 : l->exps = nl;
1698 42 : return l;
1699 : }
1700 :
1701 : /* favor or expressions over union */
1702 14517 : if (l->op == r->op && is_select(l->op) &&
1703 14517 : ll == rl && ll == rel && !rel_is_ref(l) && !rel_is_ref(r)) {
1704 14517 : sql_exp *e = exp_or(sql->sa, l->exps, r->exps, 0);
1705 14517 : list *nl = new_exp_list(sql->sa);
1706 :
1707 14517 : rel_destroy(r);
1708 14517 : append(nl, e);
1709 14517 : l->exps = nl;
1710 :
1711 : /* merge and expressions */
1712 14517 : ll = l->l;
1713 16300 : while (ll && is_select(ll->op) && !rel_is_ref(ll)) {
1714 1783 : list_merge(l->exps, ll->exps, (fdup)NULL);
1715 1783 : l->l = ll->l;
1716 1783 : ll->l = NULL;
1717 1783 : rel_destroy(ll);
1718 1783 : ll = l->l;
1719 : }
1720 : return l;
1721 : }
1722 :
1723 0 : if (rel) {
1724 0 : ls = rel_projections(sql, rel, NULL, 1, 1);
1725 0 : rs = rel_projections(sql, rel, NULL, 1, 1);
1726 : } else {
1727 0 : ls = rel_projections(sql, l, NULL, 1, 1);
1728 0 : rs = rel_projections(sql, r, NULL, 1, 1);
1729 : }
1730 0 : set_processed(l);
1731 0 : set_processed(r);
1732 0 : rel = rel_setop_check_types(sql, l, r, ls, rs, op_union);
1733 0 : if (!rel)
1734 : return NULL;
1735 0 : rel_setop_set_exps(sql, rel, rel_projections(sql, rel, NULL, 1, 1), false);
1736 0 : set_processed(rel);
1737 0 : rel->nrcols = list_length(rel->exps);
1738 0 : rel = rel_distinct(rel);
1739 0 : if (!rel)
1740 : return NULL;
1741 0 : if (exps_card(l->exps) <= CARD_AGGR &&
1742 0 : exps_card(r->exps) <= CARD_AGGR)
1743 : {
1744 0 : rel->card = exps_card(l->exps);
1745 0 : exps_fix_card( rel->exps, rel->card);
1746 : }
1747 : return rel;
1748 : }
1749 :
1750 : sql_table *
1751 4166 : rel_ddl_table_get(sql_rel *r)
1752 : {
1753 4166 : if (r->flag == ddl_alter_table || r->flag == ddl_create_table || r->flag == ddl_create_view) {
1754 4166 : sql_exp *e = r->exps->t->data;
1755 4166 : atom *a = e->l;
1756 :
1757 4166 : return a->data.val.pval;
1758 : }
1759 : return NULL;
1760 : }
1761 :
1762 : sql_rel *
1763 3240 : rel_ddl_basetable_get(sql_rel *r)
1764 : {
1765 3240 : if (r->flag == ddl_alter_table || r->flag == ddl_create_table || r->flag == ddl_create_view) {
1766 3240 : return r->l;
1767 : }
1768 : return NULL;
1769 : }
1770 :
1771 : static sql_exp *
1772 81 : exps_find_identity(list *exps, sql_rel *p)
1773 : {
1774 81 : node *n;
1775 :
1776 215 : for (n=exps->h; n; n = n->next) {
1777 134 : sql_exp *e = n->data;
1778 :
1779 134 : if (is_identity(e, p))
1780 0 : return e;
1781 : }
1782 : return NULL;
1783 : }
1784 :
1785 : static sql_rel *
1786 131 : _rel_add_identity(mvc *sql, sql_rel *rel, sql_exp **exp)
1787 : {
1788 131 : list *exps = rel_projections(sql, rel, NULL, 1, 1);
1789 131 : sql_exp *e = NULL;
1790 :
1791 131 : if (list_empty(exps)) {
1792 0 : *exp = NULL;
1793 0 : return rel;
1794 : }
1795 131 : if (!is_simple_project(rel->op) || need_distinct(rel) || !list_empty(rel->r) || rel_is_ref(rel))
1796 52 : rel = rel_project(sql->sa, rel, exps);
1797 : /* filter parameters out */
1798 262 : for (node *n = rel->exps->h ; n && !e ; n = n->next) {
1799 131 : sql_exp *re = n->data;
1800 :
1801 131 : if (exp_subtype(re))
1802 131 : e = re;
1803 : }
1804 131 : if (!e)
1805 0 : return sql_error(sql, 10, SQLSTATE(42000) "Query projection must have at least one parameter with known SQL type");
1806 :
1807 131 : sql_exp *ne = exp_column(sql->sa, exp_relname(e), exp_name(e), exp_subtype(e), rel->card, has_nil(e), is_unique(e), is_intern(e));
1808 131 : ne->nid = e->alias.label;
1809 131 : assert(ne->nid);
1810 131 : e = ne;
1811 131 : e = exp_unop(sql->sa, e, sql_bind_func(sql, "sys", "identity", exp_subtype(e), NULL, F_FUNC, true, true));
1812 131 : set_intern(e);
1813 131 : set_has_no_nil(e);
1814 131 : set_unique(e);
1815 131 : e->p = prop_create(sql->sa, PROP_HASHCOL, e->p);
1816 131 : *exp = exp_label(sql->sa, e, ++sql->label);
1817 131 : (void) rel_project_add_exp(sql, rel, e);
1818 131 : return rel;
1819 : }
1820 :
1821 : sql_rel *
1822 158 : rel_add_identity(mvc *sql, sql_rel *rel, sql_exp **exp)
1823 : {
1824 158 : if (rel && is_basetable(rel->op)) { /* for base table relations just use TID column as identity */
1825 27 : *exp = basetable_get_tid_or_add_it(sql, rel);
1826 27 : return rel;
1827 : }
1828 131 : if (rel && is_simple_project(rel->op) && !need_distinct(rel) && (*exp = exps_find_identity(rel->exps, rel->l)) != NULL)
1829 : return rel;
1830 131 : return _rel_add_identity(sql, rel, exp);
1831 : }
1832 :
1833 : sql_rel *
1834 0 : rel_add_identity2(mvc *sql, sql_rel *rel, sql_exp **exp)
1835 : {
1836 0 : sql_rel *l = rel, *p = rel;
1837 :
1838 0 : if (rel && is_basetable(rel->op)) { /* for base table relations just use TID column as identity */
1839 0 : *exp = basetable_get_tid_or_add_it(sql, rel);
1840 0 : return rel;
1841 : }
1842 0 : if (rel && is_simple_project(rel->op) && !need_distinct(rel) && (*exp = exps_find_identity(rel->exps, rel->l)) != NULL)
1843 : return rel;
1844 0 : while(l && !is_set(l->op) && rel_has_freevar(sql, l) && l->l) {
1845 : p = l;
1846 : l = l->l;
1847 : }
1848 0 : if (l != p) {
1849 0 : sql_rel *o = rel;
1850 0 : sql_exp *id;
1851 :
1852 0 : if (!(p->l = _rel_add_identity(sql, l, exp)))
1853 : return NULL;
1854 0 : l = p->l;
1855 0 : id = exp_ref(sql, *exp);
1856 0 : while (o && o != l) {
1857 0 : *exp = id;
1858 0 : if (is_project(o->op))
1859 0 : rel_project_add_exp(sql, o, id);
1860 0 : o = o->l;
1861 : }
1862 : return rel;
1863 : }
1864 0 : return _rel_add_identity(sql, rel, exp);
1865 : }
1866 :
1867 : static sql_exp *
1868 1508 : rel_find_column_(mvc *sql, list *exps, sql_alias *tname, const char *cname)
1869 : {
1870 1508 : int ambiguous = 0, multi = 0;
1871 1508 : sql_exp *e = exps_bind_column2(exps, tname, cname, &multi);
1872 1508 : if (!e && cname[0] == '%' && !tname)
1873 0 : e = exps_bind_column(exps, cname, &ambiguous, &multi, 0);
1874 1508 : if (e && !ambiguous && !multi) {
1875 1507 : return exp_ref(sql, e);
1876 : }
1877 : return NULL;
1878 : }
1879 :
1880 : sql_exp *
1881 1508 : rel_find_column(mvc *sql, sql_rel *rel, sql_alias *tname, const char *cname )
1882 : {
1883 1807 : sql_exp *e = NULL;
1884 :
1885 1807 : if (!rel)
1886 : return NULL;
1887 1807 : if (rel->exps && (is_project(rel->op) || is_base(rel->op)) && (e = rel_find_column_(sql, rel->exps, tname, cname)))
1888 : return e;
1889 300 : if ((is_simple_project(rel->op) || is_groupby(rel->op)) && rel->l) {
1890 1 : if (!is_processed(rel))
1891 : return rel_find_column(sql, rel->l, tname, cname);
1892 299 : } else if (is_set(rel->op)) {
1893 0 : assert(is_processed(rel));
1894 : return NULL;
1895 : } else if (is_join(rel->op)) {
1896 0 : e = rel_find_column(sql, rel->l, tname, cname);
1897 :
1898 0 : if (e && (is_right(rel->op) || is_full(rel->op)))
1899 0 : set_has_nil(e);
1900 0 : if (!e) {
1901 0 : e = rel_find_column(sql, rel->r, tname, cname);
1902 0 : if (e && (is_left(rel->op) || is_full(rel->op)))
1903 0 : set_has_nil(e);
1904 : }
1905 0 : if (!e && !list_empty(rel->attr))
1906 0 : e = rel_find_column_(sql, rel->attr, tname, cname);
1907 0 : if (e)
1908 0 : set_not_unique(e);
1909 0 : return e;
1910 : } else if (is_semi(rel->op) ||
1911 : is_select(rel->op) ||
1912 : is_topn(rel->op) ||
1913 : is_sample(rel->op)) {
1914 299 : if (rel->l)
1915 : return rel_find_column(sql, rel->l, tname, cname);
1916 : }
1917 : return NULL;
1918 : }
1919 :
1920 : int
1921 0 : rel_in_rel(sql_rel *super, sql_rel *sub)
1922 : {
1923 0 : if (!super)
1924 : return 0;
1925 0 : if (super == sub)
1926 : return 1;
1927 0 : if (is_join(super->op) || is_semi(super->op) || is_set(super->op) || is_modify(super->op) || is_ddl(super->op))
1928 0 : return rel_in_rel(super->l, sub) || rel_in_rel(super->r, sub);
1929 : if (is_select(super->op) || is_simple_project(super->op) || is_groupby(super->op) || is_topn(super->op) || is_sample(super->op))
1930 0 : return rel_in_rel(super->l, sub);
1931 : return 0;
1932 : }
1933 :
1934 : sql_rel*
1935 14 : rel_parent(sql_rel *rel)
1936 : {
1937 14 : if (rel->l && (is_project(rel->op) || is_topn(rel->op) || is_sample(rel->op))) {
1938 14 : sql_rel *l = rel->l;
1939 14 : if (is_project(l->op))
1940 14 : return l;
1941 : }
1942 : return rel;
1943 : }
1944 :
1945 : sql_exp *
1946 29500 : lastexp(sql_rel *rel)
1947 : {
1948 29500 : if (!is_processed(rel) || is_topn(rel->op) || is_sample(rel->op))
1949 14 : rel = rel_parent(rel);
1950 29500 : assert(list_length(rel->exps));
1951 29500 : assert(is_project(rel->op) || rel->op == op_table);
1952 29500 : return rel->exps->t->data;
1953 : }
1954 :
1955 : sql_rel *
1956 5872 : rel_return_zero_or_one(mvc *sql, sql_rel *rel, exp_kind ek)
1957 : {
1958 5872 : if (ek.card < card_set && rel->card > CARD_ATOM) {
1959 4481 : list *exps = rel->exps;
1960 :
1961 4481 : assert (is_simple_project(rel->op) || is_mset(rel->op));
1962 4481 : rel = rel_groupby(sql, rel, NULL);
1963 8972 : for(node *n = exps->h; n; n=n->next) {
1964 4491 : sql_exp *e = n->data;
1965 4491 : if (!has_label(e))
1966 75 : exp_label(sql->sa, e, ++sql->label);
1967 4491 : sql_subtype *t = exp_subtype(e); /* parameters don't have a type defined, for those use 'void' one */
1968 4491 : sql_subfunc *zero_or_one = sql_bind_func(sql, "sys", "zero_or_one", t ? t : sql_bind_localtype("void"), NULL, F_AGGR, true, true);
1969 :
1970 4491 : e = exp_ref(sql, e);
1971 4491 : e = exp_aggr1(sql->sa, e, zero_or_one, 0, 0, CARD_ATOM, has_nil(e));
1972 4491 : (void)rel_groupby_add_aggr(sql, rel, e);
1973 : }
1974 4481 : set_processed(rel);
1975 : }
1976 5872 : return rel;
1977 : }
1978 :
1979 : sql_rel *
1980 38846 : rel_zero_or_one(mvc *sql, sql_rel *rel, exp_kind ek)
1981 : {
1982 38846 : if (is_topn(rel->op) || is_sample(rel->op))
1983 26 : rel = rel_project(sql->sa, rel, rel_projections(sql, rel, NULL, 1, 0));
1984 38846 : if (ek.card < card_set && rel->card > CARD_ATOM) {
1985 9557 : assert (is_simple_project(rel->op) || is_mset(rel->op));
1986 :
1987 9557 : list *exps = rel->exps;
1988 19142 : for(node *n = exps->h; n; n=n->next) {
1989 9585 : sql_exp *e = n->data;
1990 9585 : if (e->alias.label == 0)
1991 12 : exp_label(sql->sa, e, ++sql->label);
1992 : }
1993 9557 : set_single(rel);
1994 : } else {
1995 29289 : sql_exp *e = lastexp(rel);
1996 29289 : if (!has_label(e))
1997 29 : exp_label(sql->sa, e, ++sql->label);
1998 : }
1999 38846 : return rel;
2000 : }
2001 :
2002 : static sql_rel *
2003 10588 : refs_find_rel(list *refs, sql_rel *rel)
2004 : {
2005 10588 : node *n;
2006 :
2007 22786 : for(n=refs->h; n; n = n->next->next) {
2008 17601 : sql_rel *ref = n->data;
2009 17601 : sql_rel *s = n->next->data;
2010 :
2011 17601 : if (rel == ref)
2012 : return s;
2013 : }
2014 : return NULL;
2015 : }
2016 :
2017 : static int exp_deps(mvc *sql, sql_exp *e, list *refs, list *l);
2018 :
2019 : static int
2020 684941 : exps_deps(mvc *sql, list *exps, list *refs, list *l)
2021 : {
2022 :
2023 2846405 : for(node *n = exps->h; n; n = n->next)
2024 2161464 : if (exp_deps(sql, n->data, refs, l) != 0)
2025 : return -1;
2026 : return 0;
2027 : }
2028 :
2029 : static int
2030 6845778 : id_cmp(sql_base *id1, sql_base *id2)
2031 : {
2032 6845778 : if (id1->id == id2->id)
2033 93738 : return 0;
2034 : return -1;
2035 : }
2036 :
2037 : static list *
2038 729778 : cond_append(list *l, sql_base *b)
2039 : {
2040 729778 : if (b->id >= FUNC_OIDS && !list_find(l, b, (fcmp) &id_cmp))
2041 364425 : list_append(l, b);
2042 729778 : return l;
2043 : }
2044 :
2045 : static int rel_deps(mvc *sql, sql_rel *r, list *refs, list *l);
2046 :
2047 : static int
2048 2353357 : exp_deps(mvc *sql, sql_exp *e, list *refs, list *l)
2049 : {
2050 2463244 : if (mvc_highwater(sql)) {
2051 0 : (void) sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
2052 0 : return -1;
2053 : }
2054 :
2055 2463244 : switch(e->type) {
2056 45629 : case e_psm:
2057 45629 : if (e->flag & PSM_SET || e->flag & PSM_RETURN || e->flag & PSM_EXCEPTION) {
2058 19797 : return exp_deps(sql, e->l, refs, l);
2059 25832 : } else if (e->flag & PSM_VAR) {
2060 : return 0;
2061 21078 : } else if (e->flag & PSM_WHILE || e->flag & PSM_IF) {
2062 6324 : if (exp_deps(sql, e->l, refs, l) != 0 || exps_deps(sql, e->r, refs, l) != 0)
2063 0 : return -1;
2064 6324 : if (e->flag & PSM_IF && e->f)
2065 758 : return exps_deps(sql, e->f, refs, l);
2066 14754 : } else if (e->flag & PSM_REL) {
2067 14754 : sql_rel *rel = e->l;
2068 14754 : return rel_deps(sql, rel, refs, l);
2069 : }
2070 : break;
2071 858913 : case e_atom:
2072 858913 : if (e->f && exps_deps(sql, e->f, refs, l) != 0)
2073 : return -1;
2074 : break;
2075 : case e_column:
2076 : break;
2077 90059 : case e_convert:
2078 90059 : return exp_deps(sql, e->l, refs, l);
2079 279949 : case e_func: {
2080 279949 : sql_subfunc *f = e->f;
2081 :
2082 279949 : if (e->l && exps_deps(sql, e->l, refs, l) != 0)
2083 : return -1;
2084 279949 : cond_append(l, &f->func->base);
2085 279949 : if (e->l && list_length(e->l) == 2 && strcmp(f->func->base.name, "next_value_for") == 0) {
2086 : /* add dependency on seq nr */
2087 77 : list *nl = e->l;
2088 77 : sql_exp *schname = nl->h->data, *seqname = nl->t->data;
2089 77 : char *sch_name = is_atom(schname->type) && schname->l ? ((atom*)schname->l)->data.val.sval : NULL;
2090 77 : char *seq_name = is_atom(seqname->type) && seqname->l ? ((atom*)seqname->l)->data.val.sval : NULL;
2091 :
2092 77 : if (sch_name && seq_name) {
2093 77 : sql_schema *sche = mvc_bind_schema(sql, sch_name);
2094 77 : if (sche) {
2095 77 : sql_sequence *seq = find_sql_sequence(sql->session->tr, sche, seq_name);
2096 77 : if (seq)
2097 77 : cond_append(l, &seq->base);
2098 : }
2099 : }
2100 : }
2101 : } break;
2102 21128 : case e_aggr: {
2103 21128 : sql_subfunc *a = e->f;
2104 :
2105 21128 : if (e->l && exps_deps(sql, e->l, refs, l) != 0)
2106 : return -1;
2107 21128 : cond_append(l, &a->func->base);
2108 21128 : } break;
2109 95706 : case e_cmp: {
2110 95706 : if (e->flag == cmp_or || e->flag == cmp_filter) {
2111 729 : if (e->flag == cmp_filter) {
2112 490 : sql_subfunc *f = e->f;
2113 490 : cond_append(l, &f->func->base);
2114 : }
2115 1458 : if (exps_deps(sql, e->l, refs, l) != 0 ||
2116 729 : exps_deps(sql, e->r, refs, l) != 0)
2117 0 : return -1;
2118 94977 : } else if (e->flag == cmp_in || e->flag == cmp_notin) {
2119 8770 : if (exp_deps(sql, e->l, refs, l) != 0 ||
2120 4385 : exps_deps(sql, e->r, refs, l) != 0)
2121 0 : return -1;
2122 : } else {
2123 181184 : if (exp_deps(sql, e->l, refs, l) != 0 ||
2124 90592 : exp_deps(sql, e->r, refs, l) != 0)
2125 0 : return -1;
2126 90592 : if (e->f)
2127 : return exp_deps(sql, e->f, refs, l);
2128 : }
2129 : } break;
2130 : }
2131 : return 0;
2132 : }
2133 :
2134 : static int
2135 493904 : rel_deps(mvc *sql, sql_rel *r, list *refs, list *l)
2136 : {
2137 493904 : if (mvc_highwater(sql)) {
2138 0 : (void) sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
2139 0 : return -1;
2140 : }
2141 :
2142 493904 : if (!r)
2143 : return 0;
2144 :
2145 495715 : if (rel_is_ref(r) && refs_find_rel(refs, r)) /* already handled */
2146 : return 0;
2147 479724 : switch (r->op) {
2148 104088 : case op_basetable: {
2149 104088 : sql_table *t = r->l;
2150 :
2151 104088 : cond_append(l, &t->base);
2152 : /* find all used columns */
2153 442287 : for (node *en = r->exps->h; en; en = en->next) {
2154 338199 : sql_exp *exp = en->data;
2155 338199 : const char *oname = exp->r;
2156 :
2157 338199 : assert(!is_func(exp->type));
2158 338199 : if (oname[0] == '%' && strcmp(oname, TID) == 0) {
2159 18330 : continue;
2160 319869 : } else if (oname[0] == '%') {
2161 90 : sql_idx *i = find_sql_idx(t, oname+1);
2162 90 : if (i) {
2163 89 : cond_append(l, &i->base);
2164 89 : continue;
2165 : }
2166 : }
2167 319780 : sql_column *c = find_sql_column(t, oname);
2168 319780 : if (!c)
2169 : return -1;
2170 319780 : cond_append(l, &c->base);
2171 : }
2172 : } break;
2173 4177 : case op_table: {
2174 4177 : if ((IS_TABLE_PROD_FUNC(r->flag) || r->flag == TABLE_FROM_RELATION) && r->r) { /* table producing function, excluding rel_relational_func cases */
2175 4177 : sql_exp *op = r->r;
2176 4177 : sql_subfunc *f = op->f;
2177 4177 : cond_append(l, &f->func->base);
2178 : }
2179 : } break;
2180 71963 : case op_join:
2181 : case op_left:
2182 : case op_right:
2183 : case op_full:
2184 : case op_semi:
2185 : case op_anti:
2186 : case op_union:
2187 : case op_except:
2188 : case op_inter:
2189 :
2190 : case op_insert:
2191 : case op_update:
2192 : case op_delete:
2193 : case op_merge:
2194 143926 : if (rel_deps(sql, r->l, refs, l) != 0 ||
2195 71963 : rel_deps(sql, r->r, refs, l) != 0)
2196 0 : return -1;
2197 : break;
2198 5072 : case op_munion:
2199 21269 : for (node *n = ((list*)r->l)->h; n; n = n->next) {
2200 16197 : if (rel_deps(sql, n->data, refs, l) != 0)
2201 : return -1;
2202 : }
2203 : break;
2204 170143 : case op_project:
2205 : case op_select:
2206 : case op_groupby:
2207 : case op_topn:
2208 : case op_sample:
2209 : case op_truncate:
2210 170143 : if (rel_deps(sql, r->l, refs, l) != 0)
2211 : return -1;
2212 : break;
2213 124281 : case op_ddl:
2214 124281 : if (r->flag == ddl_output || r->flag == ddl_create_seq || r->flag == ddl_alter_seq || r->flag == ddl_alter_table || r->flag == ddl_create_table || r->flag == ddl_create_view) {
2215 21 : if (rel_deps(sql, r->l, refs, l) != 0)
2216 : return -1;
2217 : } else if (r->flag == ddl_list || r->flag == ddl_exception) {
2218 0 : if (rel_deps(sql, r->l, refs, l) != 0 ||
2219 0 : rel_deps(sql, r->r, refs, l) != 0)
2220 0 : return -1;
2221 : }
2222 : break;
2223 : }
2224 479724 : if (!is_base(r->op) && r->exps) {
2225 358912 : if (exps_deps(sql, r->exps, refs, l) != 0)
2226 : return -1;
2227 : }
2228 479724 : if ((is_simple_project(r->op) || is_groupby(r->op)) && r->r) {
2229 18810 : if (exps_deps(sql, r->r, refs, l) != 0)
2230 : return -1;
2231 : }
2232 479724 : if (rel_is_ref(r)) {
2233 5185 : list_append(refs, r);
2234 5185 : list_append(refs, l);
2235 : }
2236 : return 0;
2237 : }
2238 :
2239 : list *
2240 148863 : rel_dependencies(mvc *sql, sql_rel *r)
2241 : {
2242 148863 : list *refs = sa_list(sql->sa);
2243 148863 : list *l = sa_list(sql->sa);
2244 :
2245 148863 : if (rel_deps(sql, r, refs, l) != 0)
2246 0 : return NULL;
2247 : return l;
2248 : }
2249 :
2250 : static list *exps_exp_visitor(visitor *v, sql_rel *rel, list *exps, int depth, exp_rewrite_fptr exp_rewriter, bool topdown, bool relations_topdown, bool visit_relations_once);
2251 :
2252 : static inline list *
2253 41979 : exps_exps_exp_visitor(visitor *v, sql_rel *rel, list *lists, int depth, exp_rewrite_fptr exp_rewriter, bool topdown, bool relations_topdown, bool visit_relations_once)
2254 : {
2255 41979 : node *n;
2256 :
2257 41979 : if (list_empty(lists))
2258 : return lists;
2259 90720 : for (n = lists->h; n; n = n->next) {
2260 48741 : if (n->data && (n->data = exps_exp_visitor(v, rel, n->data, depth, exp_rewriter, topdown, relations_topdown, visit_relations_once)) == NULL)
2261 : return NULL;
2262 : }
2263 : return lists;
2264 : }
2265 :
2266 : static sql_rel *rel_exp_visitor(visitor *v, sql_rel *rel, exp_rewrite_fptr exp_rewriter, bool topdown, bool relations_topdown);
2267 :
2268 : sql_exp *
2269 72332322 : exp_visitor(visitor *v, sql_rel *rel, sql_exp *e, int depth, exp_rewrite_fptr exp_rewriter, bool topdown, bool relations_topdown, bool visit_relations_once, bool *changed)
2270 : {
2271 72332322 : if (mvc_highwater(v->sql))
2272 0 : return sql_error(v->sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
2273 :
2274 72397507 : assert(e);
2275 72397507 : if (topdown) {
2276 6967417 : int changes = v->changes;
2277 6967417 : if (!(e = exp_rewriter(v, rel, e, depth)))
2278 : return NULL;
2279 6968045 : *changed |= v->changes > changes;
2280 : }
2281 :
2282 72398135 : switch(e->type) {
2283 : case e_column:
2284 : break;
2285 1067285 : case e_convert:
2286 1067285 : if ((e->l = exp_visitor(v, rel, e->l, depth+1, exp_rewriter, topdown, relations_topdown, visit_relations_once, changed)) == NULL)
2287 : return NULL;
2288 : break;
2289 4249653 : case e_aggr:
2290 : case e_func:
2291 4249653 : if (e->r) /* rewrite rank -r is list of lists */
2292 41979 : if ((e->r = exps_exps_exp_visitor(v, rel, e->r, depth+1, exp_rewriter, topdown, relations_topdown, visit_relations_once)) == NULL)
2293 : return NULL;
2294 4249653 : if (e->l)
2295 4088581 : if ((e->l = exps_exp_visitor(v, rel, e->l, depth+1, exp_rewriter, topdown, relations_topdown, visit_relations_once)) == NULL)
2296 : return NULL;
2297 : break;
2298 2324537 : case e_cmp:
2299 2324537 : if (e->flag == cmp_or || e->flag == cmp_filter) {
2300 158302 : if ((e->l = exps_exp_visitor(v, rel, e->l, depth+1, exp_rewriter, topdown, relations_topdown, visit_relations_once)) == NULL)
2301 : return NULL;
2302 158302 : if ((e->r = exps_exp_visitor(v, rel, e->r, depth+1, exp_rewriter, topdown, relations_topdown, visit_relations_once)) == NULL)
2303 : return NULL;
2304 2166235 : } else if (e->flag == cmp_in || e->flag == cmp_notin) {
2305 151939 : if ((e->l = exp_visitor(v, rel, e->l, depth+1, exp_rewriter, topdown, relations_topdown, visit_relations_once, changed)) == NULL)
2306 : return NULL;
2307 151939 : if ((e->r = exps_exp_visitor(v, rel, e->r, depth+1, exp_rewriter, topdown, relations_topdown, visit_relations_once)) == NULL)
2308 : return NULL;
2309 : } else {
2310 2014296 : if ((e->l = exp_visitor(v, rel, e->l, depth+1, exp_rewriter, topdown, relations_topdown, visit_relations_once, changed)) == NULL)
2311 : return NULL;
2312 2014296 : if ((e->r = exp_visitor(v, rel, e->r, depth+1, exp_rewriter, topdown, relations_topdown, visit_relations_once, changed)) == NULL)
2313 : return NULL;
2314 2014296 : if (e->f && (e->f = exp_visitor(v, rel, e->f, depth+1, exp_rewriter, topdown, relations_topdown, visit_relations_once, changed)) == NULL)
2315 : return NULL;
2316 : }
2317 : break;
2318 387745 : case e_psm:
2319 387745 : if (e->flag & PSM_SET || e->flag & PSM_RETURN || e->flag & PSM_EXCEPTION) {
2320 126682 : if ((e->l = exp_visitor(v, rel, e->l, depth+1, exp_rewriter, topdown, relations_topdown, visit_relations_once, changed)) == NULL)
2321 : return NULL;
2322 261063 : } else if (e->flag & PSM_VAR) {
2323 : return e;
2324 231307 : } else if (e->flag & PSM_WHILE || e->flag & PSM_IF) {
2325 39743 : if ((e->l = exp_visitor(v, rel, e->l, depth+1, exp_rewriter, topdown, relations_topdown, visit_relations_once, changed)) == NULL)
2326 : return NULL;
2327 39743 : if ((e->r = exps_exp_visitor(v, rel, e->r, depth+1, exp_rewriter, topdown, relations_topdown, visit_relations_once)) == NULL)
2328 : return NULL;
2329 39743 : if (e->flag == PSM_IF && e->f && (e->f = exps_exp_visitor(v, rel, e->f, depth+1, exp_rewriter, topdown, relations_topdown, visit_relations_once)) == NULL)
2330 : return NULL;
2331 191564 : } else if (e->flag & PSM_REL) {
2332 191564 : if (!visit_relations_once && (e->l = rel_exp_visitor(v, e->l, exp_rewriter, topdown, relations_topdown)) == NULL)
2333 : return NULL;
2334 : }
2335 : break;
2336 27381740 : case e_atom:
2337 27381740 : if (e->f)
2338 918276 : if ((e->f = exps_exp_visitor(v, rel, e->f, depth+1, exp_rewriter, topdown, relations_topdown, visit_relations_once)) == NULL)
2339 : return NULL;
2340 : break;
2341 : }
2342 72368316 : if (!topdown) {
2343 65383995 : int changes = v->changes;
2344 65383995 : if (!(e = exp_rewriter(v, rel, e, depth)))
2345 : return NULL;
2346 65399713 : *changed |= v->changes > changes;
2347 : }
2348 : return e;
2349 : }
2350 :
2351 : static list *
2352 17932881 : exps_exp_visitor(visitor *v, sql_rel *rel, list *exps, int depth, exp_rewrite_fptr exp_rewriter, bool topdown, bool relations_topdown, bool visit_relations_once)
2353 : {
2354 17932881 : bool changed = false;
2355 17932881 : if (list_empty(exps))
2356 : return exps;
2357 84781493 : for (node *n = exps->h; n; n = n->next)
2358 66876450 : if (n->data && (n->data = exp_visitor(v, rel, n->data, depth, exp_rewriter, topdown, relations_topdown, visit_relations_once, &changed)) == NULL)
2359 : return NULL;
2360 17905043 : if (changed && depth == 0) /* only level 0 exps use hash, so remove only on those */
2361 23060 : list_hash_clear(exps);
2362 : return exps;
2363 : }
2364 :
2365 : static inline sql_rel *
2366 12934716 : rel_exp_visitor(visitor *v, sql_rel *rel, exp_rewrite_fptr exp_rewriter, bool topdown, bool relations_topdown)
2367 : {
2368 12934716 : if (mvc_highwater(v->sql))
2369 0 : return sql_error(v->sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
2370 :
2371 12938581 : if (!rel)
2372 : return rel;
2373 :
2374 12938581 : if (v->opt >= 0 && rel->opt >= v->opt) /* only once */
2375 : return rel;
2376 :
2377 12817277 : if (relations_topdown) {
2378 5380727 : if (rel->exps && (rel->exps = exps_exp_visitor(v, rel, rel->exps, 0, exp_rewriter, topdown, relations_topdown, false)) == NULL)
2379 : return NULL;
2380 5381312 : if ((is_groupby(rel->op) || is_simple_project(rel->op)) && rel->r && (rel->r = exps_exp_visitor(v, rel, rel->r, 0, exp_rewriter, topdown, relations_topdown, false)) == NULL)
2381 : return NULL;
2382 : }
2383 :
2384 12817862 : switch(rel->op){
2385 : case op_basetable:
2386 : break;
2387 48751 : case op_table:
2388 48751 : if (IS_TABLE_PROD_FUNC(rel->flag) || rel->flag == TABLE_FROM_RELATION) {
2389 48683 : bool changed = false;
2390 48683 : if (rel->l)
2391 915 : if ((rel->l = rel_exp_visitor(v, rel->l, exp_rewriter, topdown, relations_topdown)) == NULL)
2392 0 : return NULL;
2393 48683 : if (rel->r)
2394 48376 : if ((rel->r = exp_visitor(v, rel, rel->r, 0, exp_rewriter, topdown, relations_topdown, false, &changed)) == NULL)
2395 : return NULL;
2396 : }
2397 : break;
2398 2676020 : case op_ddl:
2399 2676020 : 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) {
2400 211855 : if (rel->l)
2401 209666 : if ((rel->l = rel_exp_visitor(v, rel->l, exp_rewriter, topdown, relations_topdown)) == NULL)
2402 : return NULL;
2403 : } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
2404 2668 : if (rel->l)
2405 2354 : if ((rel->l = rel_exp_visitor(v, rel->l, exp_rewriter, topdown, relations_topdown)) == NULL)
2406 : return NULL;
2407 2668 : if (rel->r)
2408 2401 : if ((rel->r = rel_exp_visitor(v, rel->r, exp_rewriter, topdown, relations_topdown)) == NULL)
2409 : return NULL;
2410 : }
2411 : break;
2412 1753233 : case op_insert:
2413 : case op_update:
2414 : case op_delete:
2415 : case op_merge:
2416 :
2417 : case op_join:
2418 : case op_left:
2419 : case op_right:
2420 : case op_full:
2421 : case op_semi:
2422 : case op_anti:
2423 :
2424 : case op_union:
2425 : case op_inter:
2426 : case op_except:
2427 1753233 : if (rel->l)
2428 1753214 : if ((rel->l = rel_exp_visitor(v, rel->l, exp_rewriter, topdown, relations_topdown)) == NULL)
2429 : return NULL;
2430 1753779 : if (rel->r)
2431 1751870 : if ((rel->r = rel_exp_visitor(v, rel->r, exp_rewriter, topdown, relations_topdown)) == NULL)
2432 : return NULL;
2433 : break;
2434 170569 : case op_munion:
2435 515675 : for (node *n = ((list*)rel->l)->h; n; n = n->next) {
2436 345106 : if ((n->data = rel_exp_visitor(v, n->data, exp_rewriter, topdown, relations_topdown)) == NULL)
2437 : return NULL;
2438 : }
2439 : break;
2440 5145392 : case op_select:
2441 : case op_topn:
2442 : case op_sample:
2443 : case op_project:
2444 : case op_groupby:
2445 : case op_truncate:
2446 5145392 : if (rel->l)
2447 4061749 : if ((rel->l = rel_exp_visitor(v, rel->l, exp_rewriter, topdown, relations_topdown)) == NULL)
2448 : return NULL;
2449 : break;
2450 : }
2451 :
2452 12818556 : if (!relations_topdown) {
2453 7436766 : if (rel->exps && (rel->exps = exps_exp_visitor(v, rel, rel->exps, 0, exp_rewriter, topdown, relations_topdown, false)) == NULL)
2454 : return NULL;
2455 7437694 : if ((is_groupby(rel->op) || is_simple_project(rel->op)) && rel->r && (rel->r = exps_exp_visitor(v, rel, rel->r, 0, exp_rewriter, topdown, relations_topdown, false)) == NULL)
2456 : return NULL;
2457 : }
2458 12819484 : if (rel && v->opt >= 0)
2459 12816594 : rel->opt = v->opt;
2460 : return rel;
2461 : }
2462 :
2463 : sql_rel *
2464 615773 : rel_exp_visitor_topdown(visitor *v, sql_rel *rel, exp_rewrite_fptr exp_rewriter, bool relations_topdown)
2465 : {
2466 615773 : if (!rel)
2467 : return rel;
2468 615773 : if (v->opt >= 0)
2469 615773 : v->opt = rel->opt+1;
2470 615773 : return rel_exp_visitor(v, rel, exp_rewriter, true, relations_topdown);
2471 : }
2472 :
2473 : sql_rel *
2474 4023979 : rel_exp_visitor_bottomup(visitor *v, sql_rel *rel, exp_rewrite_fptr exp_rewriter, bool relations_topdown)
2475 : {
2476 4023979 : if (!rel)
2477 : return rel;
2478 4023957 : if (v->opt >= 0)
2479 4023957 : v->opt = rel->opt+1;
2480 4023957 : return rel_exp_visitor(v, rel, exp_rewriter, false, relations_topdown);
2481 : }
2482 :
2483 : static list *exps_rel_visitor(visitor *v, list *exps, rel_rewrite_fptr rel_rewriter, bool topdown);
2484 : static list *exps_exps_rel_visitor(visitor *v, list *lists, rel_rewrite_fptr rel_rewriter, bool topdown);
2485 :
2486 : static sql_exp *
2487 250424150 : exp_rel_visitor(visitor *v, sql_exp *e, rel_rewrite_fptr rel_rewriter, bool topdown)
2488 : {
2489 250424150 : if (mvc_highwater(v->sql))
2490 0 : return sql_error(v->sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
2491 :
2492 250543631 : assert(e);
2493 250543631 : switch(e->type) {
2494 : case e_column:
2495 : break;
2496 5918535 : case e_convert:
2497 5918535 : if ((e->l = exp_rel_visitor(v, e->l, rel_rewriter, topdown)) == NULL)
2498 : return NULL;
2499 : break;
2500 17094982 : case e_aggr:
2501 : case e_func:
2502 17094982 : if (e->r) /* rewrite rank */
2503 106078 : if ((e->r = exps_exps_rel_visitor(v, e->r, rel_rewriter, topdown)) == NULL)
2504 : return NULL;
2505 17094982 : if (e->l)
2506 16514898 : if ((e->l = exps_rel_visitor(v, e->l, rel_rewriter, topdown)) == NULL)
2507 : return NULL;
2508 : break;
2509 10028545 : case e_cmp:
2510 10028545 : if (e->flag == cmp_or || e->flag == cmp_filter) {
2511 649951 : if ((e->l = exps_rel_visitor(v, e->l, rel_rewriter, topdown)) == NULL)
2512 : return NULL;
2513 649951 : if ((e->r = exps_rel_visitor(v, e->r, rel_rewriter, topdown)) == NULL)
2514 : return NULL;
2515 9378594 : } else if (e->flag == cmp_in || e->flag == cmp_notin) {
2516 602094 : if ((e->l = exp_rel_visitor(v, e->l, rel_rewriter, topdown)) == NULL)
2517 : return NULL;
2518 602094 : if ((e->r = exps_rel_visitor(v, e->r, rel_rewriter, topdown)) == NULL)
2519 : return NULL;
2520 : } else {
2521 8776500 : if ((e->l = exp_rel_visitor(v, e->l, rel_rewriter, topdown)) == NULL)
2522 : return NULL;
2523 8776500 : if ((e->r = exp_rel_visitor(v, e->r, rel_rewriter, topdown)) == NULL)
2524 : return NULL;
2525 8776499 : if (e->f && (e->f = exp_rel_visitor(v, e->f, rel_rewriter, topdown)) == NULL)
2526 : return NULL;
2527 : }
2528 : break;
2529 811796 : case e_psm:
2530 811796 : if (e->flag & PSM_SET || e->flag & PSM_RETURN || e->flag & PSM_EXCEPTION) {
2531 298576 : if ((e->l = exp_rel_visitor(v, e->l, rel_rewriter, topdown)) == NULL)
2532 : return NULL;
2533 513220 : } else if (e->flag & PSM_VAR) {
2534 : return e;
2535 443848 : } else if (e->flag & PSM_WHILE || e->flag & PSM_IF) {
2536 92648 : if ((e->l = exp_rel_visitor(v, e->l, rel_rewriter, topdown)) == NULL)
2537 : return NULL;
2538 92648 : if ((e->r = exps_rel_visitor(v, e->r, rel_rewriter, topdown)) == NULL)
2539 : return NULL;
2540 92648 : if (e->flag == PSM_IF && e->f && (e->f = exps_rel_visitor(v, e->f, rel_rewriter, topdown)) == NULL)
2541 : return NULL;
2542 351200 : } else if (e->flag & PSM_REL) {
2543 351200 : sql_rel *(*func)(visitor *, sql_rel *, rel_rewrite_fptr) = topdown ? rel_visitor_topdown : rel_visitor_bottomup;
2544 351200 : if ((e->l = func(v, e->l, rel_rewriter)) == NULL)
2545 : return NULL;
2546 : }
2547 : break;
2548 62977222 : case e_atom:
2549 62977222 : if (e->f)
2550 1609664 : if ((e->f = exps_rel_visitor(v, e->f, rel_rewriter, topdown)) == NULL)
2551 : return NULL;
2552 : break;
2553 : }
2554 : return e;
2555 : }
2556 :
2557 : static list *
2558 61928393 : exps_rel_visitor(visitor *v, list *exps, rel_rewrite_fptr rel_rewriter, bool topdown)
2559 : {
2560 61928393 : if (list_empty(exps))
2561 : return exps;
2562 287867613 : for (node *n = exps->h; n; n = n->next)
2563 226013926 : if (n->data && (n->data = exp_rel_visitor(v, n->data, rel_rewriter, topdown)) == NULL)
2564 : return NULL;
2565 : return exps;
2566 : }
2567 :
2568 : static list *
2569 106078 : exps_exps_rel_visitor(visitor *v, list *lists, rel_rewrite_fptr rel_rewriter, bool topdown)
2570 : {
2571 106078 : if (list_empty(lists))
2572 : return lists;
2573 223769 : for (node *n = lists->h; n; n = n->next)
2574 117691 : if (n->data && (n->data = exps_rel_visitor(v, n->data, rel_rewriter, topdown)) == NULL)
2575 : return NULL;
2576 : return lists;
2577 : }
2578 :
2579 : static inline sql_rel *
2580 42994937 : do_rel_visitor(visitor *v, sql_rel *rel, rel_rewrite_fptr rel_rewriter, bool topdown)
2581 : {
2582 42994937 : if (rel->exps && (rel->exps = exps_rel_visitor(v, rel->exps, rel_rewriter, topdown)) == NULL)
2583 : return NULL;
2584 42994717 : if ((is_groupby(rel->op) || is_simple_project(rel->op)) && rel->r && (rel->r = exps_rel_visitor(v, rel->r, rel_rewriter, topdown)) == NULL)
2585 : return NULL;
2586 42994714 : int changes = v->changes;
2587 42994714 : rel = rel_rewriter(v, rel);
2588 42993182 : if (rel && rel->exps && v->changes > changes) {
2589 334327 : list_hash_clear(rel->exps);
2590 334320 : if ((is_groupby(rel->op) || is_simple_project(rel->op)) && rel->r)
2591 13831 : list_hash_clear(rel->r);
2592 : }
2593 : return rel;
2594 : }
2595 :
2596 : static sql_rel *rel_visitor(visitor *v, sql_rel *rel, rel_rewrite_fptr rel_rewriter, bool topdown);
2597 :
2598 : static sql_rel *
2599 11794179 : rel_visitor_td(visitor *v, sql_rel *rel, rel_rewrite_fptr rel_rewriter)
2600 : {
2601 11794179 : v->depth++;
2602 11794179 : rel = rel_visitor(v, rel, rel_rewriter, true);
2603 11794671 : v->depth--;
2604 11794671 : return rel;
2605 : }
2606 :
2607 : static sql_rel *
2608 22032976 : rel_visitor_bu(visitor *v, sql_rel *rel, rel_rewrite_fptr rel_rewriter)
2609 : {
2610 22032976 : v->depth++;
2611 22032976 : rel = rel_visitor(v, rel, rel_rewriter, false);
2612 22032955 : v->depth--;
2613 22032955 : return rel;
2614 : }
2615 :
2616 : static sql_rel *
2617 43655737 : rel_visitor(visitor *v, sql_rel *rel, rel_rewrite_fptr rel_rewriter, bool topdown)
2618 : {
2619 43655737 : sql_rel *parent = v->parent;
2620 43655737 : if (mvc_highwater(v->sql))
2621 0 : return sql_error(v->sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
2622 :
2623 43668499 : if (!rel)
2624 : return NULL;
2625 :
2626 43668499 : if (v->opt >= 0 && rel->opt >= v->opt) /* only once */
2627 : return rel;
2628 :
2629 43001573 : if (topdown && !(rel = do_rel_visitor(v, rel, rel_rewriter, true)))
2630 : return NULL;
2631 :
2632 43001626 : sql_rel *(*func)(visitor *, sql_rel *, rel_rewrite_fptr) = topdown ? rel_visitor_td : rel_visitor_bu;
2633 :
2634 43001626 : v->parent = rel;
2635 43001626 : switch(rel->op){
2636 : case op_basetable:
2637 : break;
2638 150189 : case op_table:
2639 150189 : if (IS_TABLE_PROD_FUNC(rel->flag) || rel->flag == TABLE_FROM_RELATION) {
2640 149940 : if (rel->l)
2641 2894 : if ((rel->l = func(v, rel->l, rel_rewriter)) == NULL)
2642 : return NULL;
2643 : }
2644 : break;
2645 4757855 : case op_ddl:
2646 4757855 : 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) {
2647 402003 : if (rel->l)
2648 397945 : if ((rel->l = func(v, rel->l, rel_rewriter)) == NULL)
2649 : return NULL;
2650 : } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
2651 14554 : if (rel->l)
2652 10709 : if ((rel->l = func(v, rel->l, rel_rewriter)) == NULL)
2653 : return NULL;
2654 14554 : if (rel->r)
2655 13516 : if ((rel->r = func(v, rel->r, rel_rewriter)) == NULL)
2656 : return NULL;
2657 : } else if (rel->flag == ddl_psm) {
2658 435210 : if ((rel->exps = exps_rel_visitor(v, rel->exps, rel_rewriter, topdown)) == NULL)
2659 : return NULL;
2660 : }
2661 : break;
2662 6715889 : case op_insert:
2663 : case op_update:
2664 : case op_delete:
2665 : case op_merge:
2666 :
2667 : case op_join:
2668 : case op_left:
2669 : case op_right:
2670 : case op_full:
2671 : case op_semi:
2672 : case op_anti:
2673 :
2674 : case op_union:
2675 : case op_inter:
2676 : case op_except:
2677 6715889 : if (rel->l)
2678 6715889 : if ((rel->l = func(v, rel->l, rel_rewriter)) == NULL)
2679 : return NULL;
2680 6715883 : if (rel->r)
2681 6710814 : if ((rel->r = func(v, rel->r, rel_rewriter)) == NULL)
2682 : return NULL;
2683 : break;
2684 1069195 : case op_munion:
2685 3538725 : for (node *n = ((list*)rel->l)->h; n; n = n->next) {
2686 2469530 : if ((n->data = func(v, n->data, rel_rewriter)) == NULL)
2687 : return NULL;
2688 : }
2689 : break;
2690 19562934 : case op_select:
2691 : case op_topn:
2692 : case op_sample:
2693 : case op_project:
2694 : case op_groupby:
2695 : case op_truncate:
2696 19562934 : if (rel->l)
2697 17506154 : if ((rel->l = func(v, rel->l, rel_rewriter)) == NULL)
2698 : return NULL;
2699 : break;
2700 : }
2701 43002941 : v->parent = parent;
2702 :
2703 43002941 : if (!topdown)
2704 29113606 : rel = do_rel_visitor(v, rel, rel_rewriter, false);
2705 42992458 : if (rel && v->opt >= 0)
2706 42992456 : rel->opt = v->opt;
2707 : return rel;
2708 : }
2709 :
2710 : sql_rel *
2711 2355076 : rel_visitor_topdown(visitor *v, sql_rel *rel, rel_rewrite_fptr rel_rewriter)
2712 : {
2713 2355076 : if (!rel)
2714 : return rel;
2715 2355063 : if (v->opt >= 0)
2716 2355063 : v->opt = rel->opt+1;
2717 2355063 : v->depth++;
2718 2355063 : rel = rel_visitor(v, rel, rel_rewriter, true);
2719 2355858 : v->depth--;
2720 2355858 : return rel;
2721 : }
2722 :
2723 : sql_rel *
2724 7484074 : rel_visitor_bottomup(visitor *v, sql_rel *rel, rel_rewrite_fptr rel_rewriter)
2725 : {
2726 7484074 : if (!rel)
2727 : return rel;
2728 7484028 : if (v->opt >= 0)
2729 7484028 : v->opt = rel->opt+1;
2730 7484028 : v->depth++;
2731 7484028 : rel = rel_visitor(v, rel, rel_rewriter, false);
2732 7486406 : v->depth--;
2733 7486406 : return rel;
2734 : }
2735 :
2736 : list *
2737 273 : exps_exp_visitor_topdown(visitor *v, sql_rel *rel, list *exps, int depth, exp_rewrite_fptr exp_rewriter, bool relations_topdown)
2738 : {
2739 273 : return exps_exp_visitor(v, rel, exps, depth, exp_rewriter, true, relations_topdown, false);
2740 : }
2741 :
2742 : list *
2743 607079 : exps_exp_visitor_bottomup(visitor *v, sql_rel *rel, list *exps, int depth, exp_rewrite_fptr exp_rewriter, bool relations_topdown)
2744 : {
2745 607079 : return exps_exp_visitor(v, rel, exps, depth, exp_rewriter, false, relations_topdown, false);
2746 : }
2747 :
2748 : static bool
2749 73867 : exps_rebind_exp(mvc *sql, sql_rel *rel, list *exps)
2750 : {
2751 73867 : bool ok = true;
2752 :
2753 73867 : if (mvc_highwater(sql)) {
2754 0 : (void) sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
2755 0 : return false;
2756 : }
2757 :
2758 73867 : if (list_empty(exps))
2759 : return true;
2760 83984 : for (node *n = exps->h; n && ok; n = n->next)
2761 51926 : ok &= rel_rebind_exp(sql, rel, n->data);
2762 : return ok;
2763 : }
2764 :
2765 : bool
2766 1431071 : rel_rebind_exp(mvc *sql, sql_rel *rel, sql_exp *e)
2767 : {
2768 1453655 : if (mvc_highwater(sql)) {
2769 0 : (void) sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
2770 0 : return false;
2771 : }
2772 :
2773 1453655 : switch (e->type) {
2774 22584 : case e_convert:
2775 22584 : return rel_rebind_exp(sql, rel, e->l);
2776 13753 : case e_aggr:
2777 : case e_func:
2778 13753 : return exps_rebind_exp(sql, rel, e->l);
2779 566826 : case e_cmp:
2780 566826 : if (e->flag == cmp_in || e->flag == cmp_notin)
2781 8766 : return rel_rebind_exp(sql, rel, e->l) && exps_rebind_exp(sql, rel, e->r);
2782 560304 : if (e->flag == cmp_or || e->flag == cmp_filter)
2783 18047 : return exps_rebind_exp(sql, rel, e->l) && exps_rebind_exp(sql, rel, e->r);
2784 1100196 : return rel_rebind_exp(sql, rel, e->l) && rel_rebind_exp(sql, rel, e->r) && (!e->f || rel_rebind_exp(sql, rel, e->f));
2785 808452 : case e_column:
2786 808452 : if (e->freevar)
2787 : return true;
2788 808451 : return rel_find_exp(rel, e) != NULL;
2789 42035 : case e_atom:
2790 42035 : return exps_rebind_exp(sql, rel, e->f);
2791 : case e_psm:
2792 : return true;
2793 : }
2794 : return true;
2795 : }
2796 :
2797 : static sql_exp *
2798 389 : _exp_freevar_offset(visitor *v, sql_rel *rel, sql_exp *e, int depth)
2799 : {
2800 389 : (void)rel; (void)depth;
2801 : /* visitor will handle recursion, ie only need to check columns here */
2802 389 : int vf = is_freevar(e);
2803 389 : if (v->changes < vf)
2804 311 : v->changes=vf;
2805 389 : return e;
2806 : }
2807 :
2808 : int
2809 300 : exp_freevar_offset(mvc *sql, sql_exp *e)
2810 : {
2811 300 : bool changed = false;
2812 300 : visitor v = { .sql = sql };
2813 :
2814 300 : (void) changed;
2815 300 : exp_visitor(&v, NULL, e, 0, &_exp_freevar_offset, true, true, true, &changed);
2816 : /* freevar offset is passed via changes */
2817 300 : return (v.changes);
2818 : }
|
