1/*
2 * This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
5 *
6 * Copyright 1997 - July 2008 CWI, August 2008 - 2019 MonetDB B.V.
7 */
8
9#include "monetdb_config.h"
10#include "rel_rel.h"
11#include "rel_exp.h"
12#include "rel_prop.h"
13#include "rel_remote.h"
14#include "rel_unnest.h"
15#include "sql_semantic.h"
16#include "sql_mvc.h"
17
18
19/* we don't name relations directly, but sometimes we need the relation
20 name. So we look it up in the first expression
21
22 we should clean up (remove) this function.
23 */
24const char *
25rel_name( sql_rel *r )
26{
27 if (!is_project(r->op) && !is_base(r->op) && r->l)
28 return rel_name(r->l);
29 if (r->exps && list_length(r->exps)) {
30 sql_exp *e = r->exps->h->data;
31 if (exp_relname(e))
32 return exp_relname(e);
33 if (e->type == e_column)
34 return e->l;
35 }
36 return NULL;
37}
38
39sql_rel *
40rel_distinct(sql_rel *l)
41{
42#if 0
43 if (l->card >= CARD_AGGR) /* in case of CARD_AGGR, we could
44 do better, ie check the group by
45 list etc */
46#endif
47 set_distinct(l);
48 return l;
49}
50
51sql_rel *
52rel_dup(sql_rel *r)
53{
54 sql_ref_inc(&r->ref);
55 return r;
56}
57
58static void
59rel_destroy_(sql_rel *rel)
60{
61 if (!rel)
62 return;
63 if (is_join(rel->op) ||
64 is_semi(rel->op) ||
65 is_select(rel->op) ||
66 is_set(rel->op) ||
67 rel->op == op_topn ||
68 rel->op == op_sample) {
69 if (rel->l)
70 rel_destroy(rel->l);
71 if (rel->r)
72 rel_destroy(rel->r);
73 } else if (is_project(rel->op)) {
74 if (rel->l)
75 rel_destroy(rel->l);
76 } else if (is_modify(rel->op)) {
77 if (rel->r)
78 rel_destroy(rel->r);
79 }
80}
81
82void
83rel_destroy(sql_rel *rel)
84{
85 if (!rel)
86 return;
87 if (sql_ref_dec(&rel->ref) > 0)
88 return;
89 rel_destroy_(rel);
90}
91
92sql_rel*
93rel_create( sql_allocator *sa )
94{
95 sql_rel *r = SA_NEW(sa, sql_rel);
96 if(!r)
97 return NULL;
98
99 sql_ref_init(&r->ref);
100 r->l = r->r = NULL;
101 r->exps = NULL;
102 r->nrcols = 0;
103 r->flag = 0;
104 r->card = CARD_ATOM;
105 r->processed = 0;
106 r->single = 0;
107 r->dependent = 0;
108 r->subquery = 0;
109 r->p = NULL;
110 return r;
111}
112
113sql_rel *
114rel_copy( mvc *sql, sql_rel *i, int deep )
115{
116 sql_rel *rel = rel_create(sql->sa);
117 if(!rel)
118 return NULL;
119
120 rel->l = NULL;
121 rel->r = NULL;
122 rel->card = i->card;
123 rel->flag = i->flag;
124
125 switch(i->op) {
126 case op_basetable:
127 rel->l = i->l;
128 break;
129 case op_table:
130 rel->l = i->l;
131 rel->r = i->r;
132 break;
133 case op_groupby:
134 rel->l = rel_copy(sql, i->l, deep);
135 if (i->r) {
136 if (!deep) {
137 rel->r = list_dup(i->r, (fdup) NULL);
138 } else {
139 list* l = (list*)i->r;
140 rel->r = list_new(l->sa, l->destroy);
141 for(node *n = l->h ; n ; n = n->next)
142 list_append(rel->r, rel_copy(sql, (sql_rel *)n->data, deep));
143 }
144 }
145 break;
146 case op_join:
147 case op_left:
148 case op_right:
149 case op_full:
150 case op_semi:
151 case op_anti:
152 case op_project:
153 case op_select:
154 default:
155 if (i->l)
156 rel->l = rel_copy(sql, i->l, deep);
157 if (i->r)
158 rel->r = rel_copy(sql, i->r, deep);
159 break;
160 }
161 rel->op = i->op;
162 rel->exps = (!i->exps)?NULL:deep?exps_copy(sql, i->exps):list_dup(i->exps, (fdup)NULL);
163 return rel;
164}
165
166sql_rel *
167rel_select_copy(sql_allocator *sa, sql_rel *l, list *exps)
168{
169 sql_rel *rel = rel_create(sa);
170 if(!rel)
171 return NULL;
172
173 rel->l = l;
174 rel->r = NULL;
175 rel->op = op_select;
176 rel->exps = exps?list_dup(exps, (fdup)NULL):NULL;
177 rel->card = CARD_ATOM; /* no relation */
178 if (l) {
179 rel->card = l->card;
180 rel->nrcols = l->nrcols;
181 }
182 return rel;
183}
184
185static int
186rel_issubquery(sql_rel*r)
187{
188 if (!r->subquery) {
189 if (is_select(r->op))
190 return rel_issubquery(r->l);
191 }
192 return r->subquery;
193}
194
195static sql_rel *
196rel_bind_column_(mvc *sql, sql_rel **p, sql_rel *rel, const char *cname)
197{
198 int ambiguous = 0;
199 sql_rel *l = NULL, *r = NULL;
200
201 if (THRhighwater())
202 return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
203
204 switch(rel->op) {
205 case op_join:
206 case op_left:
207 case op_right:
208 case op_full: {
209 sql_rel *right = rel->r;
210
211 *p = rel;
212 r = rel_bind_column_(sql, p, rel->r, cname);
213
214 if (!r || !rel_issubquery(right)) {
215 sql_exp *e = r?exps_bind_column(r->exps, cname, &ambiguous):NULL;
216
217 if (!r || !e || !is_freevar(e)) {
218 *p = rel;
219 l = rel_bind_column_(sql, p, rel->l, cname);
220 if (l && r && !rel_issubquery(r) && !is_dependent(rel)) {
221 (void) sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s' ambiguous", cname);
222 return NULL;
223 }
224 }
225 }
226 if (sql->session->status == -ERR_AMBIGUOUS)
227 return NULL;
228 if (l && !r)
229 return l;
230 return r;
231 }
232 case op_union:
233 case op_except:
234 case op_inter:
235 case op_groupby:
236 case op_project:
237 case op_table:
238 case op_basetable:
239 if (rel->exps && exps_bind_column(rel->exps, cname, &ambiguous))
240 return rel;
241 if (rel->r && is_groupby(rel->op) && exps_bind_column(rel->r, cname, &ambiguous))
242 return rel;
243 if (ambiguous) {
244 (void) sql_error(sql, ERR_AMBIGUOUS, SQLSTATE(42000) "SELECT: identifier '%s' ambiguous", cname);
245 return NULL;
246 }
247 *p = rel;
248 if (is_processed(rel))
249 return NULL;
250 if (rel->l && !(is_base(rel->op)))
251 return rel_bind_column_(sql, p, rel->l, cname);
252 break;
253 case op_semi:
254 case op_anti:
255
256 case op_select:
257 case op_topn:
258 case op_sample:
259 *p = rel;
260 if (rel->l)
261 return rel_bind_column_(sql, p, rel->l, cname);
262 /* fall through */
263 default:
264 return NULL;
265 }
266 return NULL;
267}
268
269sql_exp *
270rel_bind_column( mvc *sql, sql_rel *rel, const char *cname, int f)
271{
272 sql_rel *p = NULL;//, *orel = rel;
273
274 if (is_sql_sel(f) && rel && is_simple_project(rel->op) && !is_processed(rel))
275 rel = rel->l;
276
277 if (!rel || (rel = rel_bind_column_(sql, &p, rel, cname)) == NULL)
278 return NULL;
279
280 if ((is_project(rel->op) || is_base(rel->op)) && rel->exps) {
281 sql_exp *e = exps_bind_column(rel->exps, cname, NULL);
282 if (e)
283 e = exp_alias_or_copy(sql, exp_relname(e), cname, rel, e);
284 if (!e && is_groupby(rel->op) && rel->r) {
285 sql_exp *e = exps_bind_column(rel->r, cname, NULL);
286 if (e)
287 e = exp_alias_or_copy(sql, exp_relname(e), cname, rel, e);
288 return e;
289 }
290 /*
291 if (p && e && is_simple_project(p->op) && !is_processed(p) && is_sql_orderby(f) && orel != rel)
292 e = rel_project_add_exp(sql, p, e);
293 */
294 return e;
295 }
296 return NULL;
297}
298
299sql_exp *
300rel_bind_column2( mvc *sql, sql_rel *rel, const char *tname, const char *cname, int f)
301{
302 if (!rel)
303 return NULL;
304
305 if ((is_project(rel->op) || is_base(rel->op))) {
306 sql_exp *e = NULL;
307
308 /* in case of orderby we should also lookup the column in group by list (and use existing references) */
309 if (!list_empty(rel->exps)) {
310 e = exps_bind_column2(rel->exps, tname, cname);
311 if (!e && is_groupby(rel->op) && rel->r) {
312 e = exps_bind_alias(rel->r, tname, cname);
313 if (e) {
314 if (exp_relname(e))
315 e = exps_bind_column2(rel->exps, exp_relname(e), exp_name(e));
316 else
317 e = exps_bind_column(rel->exps, exp_name(e), NULL);
318 if (e)
319 return e;
320 }
321 }
322 }
323 if (!e && (is_sql_sel(f) | is_sql_having(f) | !f) && is_groupby(rel->op) && rel->r) {
324 e = exps_bind_column2(rel->r, tname, cname);
325 if (e) {
326 e = exp_ref(sql->sa, e);
327 e->card = rel->card;
328 return e;
329 }
330 }
331 if (e)
332 return exp_alias_or_copy(sql, tname, cname, rel, e);
333 }
334 if ((is_simple_project(rel->op) || (is_groupby(rel->op) && is_sql_aggr(f)) ) && rel->l) {
335 if (!is_processed(rel))
336 return rel_bind_column2(sql, rel->l, tname, cname, f);
337 } else if (is_join(rel->op)) {
338 sql_exp *e = rel_bind_column2(sql, rel->l, tname, cname, f);
339 if (!e)
340 e = rel_bind_column2(sql, rel->r, tname, cname, f);
341 return e;
342 } else if (is_set(rel->op) ||
343 is_sort(rel) ||
344 is_semi(rel->op) ||
345 is_select(rel->op) ||
346 is_topn(rel->op)) {
347 if (rel->l)
348 return rel_bind_column2(sql, rel->l, tname, cname, f);
349 }
350 return NULL;
351}
352
353sql_exp *
354rel_first_column(mvc *sql, sql_rel *r)
355{
356 if (is_simple_project(r->op))
357 return r->exps->h->data;
358
359 list *exps = rel_projections(sql, r, NULL, 1, 1);
360
361 if (!list_empty(exps))
362 return exps->h->data;
363
364 return NULL;
365}
366
367sql_rel *
368rel_inplace_setop(sql_rel *rel, sql_rel *l, sql_rel *r, operator_type setop, list *exps)
369{
370 rel_destroy_(rel);
371 rel->l = l;
372 rel->r = r;
373 rel->op = setop;
374 rel->exps = NULL;
375 rel->card = CARD_MULTI;
376 rel->flag = 0;
377 if (l && r)
378 rel->nrcols = l->nrcols + r->nrcols;
379 rel->exps = exps;
380 set_processed(rel);
381 return rel;
382}
383
384sql_rel *
385rel_inplace_project(sql_allocator *sa, sql_rel *rel, sql_rel *l, list *e)
386{
387 if (!l) {
388 l = rel_create(sa);
389 if(!l)
390 return NULL;
391
392 l->op = rel->op;
393 l->l = rel->l;
394 l->r = rel->r;
395 l->exps = rel->exps;
396 l->nrcols = rel->nrcols;
397 l->flag = rel->flag;
398 l->card = rel->card;
399 } else {
400 rel_destroy_(rel);
401 }
402 set_processed(rel);
403
404 rel->l = l;
405 rel->r = NULL;
406 rel->op = op_project;
407 rel->exps = e;
408 rel->card = CARD_MULTI;
409 rel->flag = 0;
410 if (l) {
411 rel->nrcols = l->nrcols;
412 assert (exps_card(rel->exps) <= rel->card);
413 }
414 return rel;
415}
416
417sql_rel *
418rel_inplace_groupby(sql_rel *rel, sql_rel *l, list *groupbyexps, list *exps )
419{
420 rel_destroy_(rel);
421 rel->card = CARD_ATOM;
422 if (groupbyexps)
423 rel->card = CARD_AGGR;
424 rel->l = l;
425 rel->r = groupbyexps;
426 rel->exps = exps;
427 rel->nrcols = l->nrcols;
428 rel->op = op_groupby;
429 rel->flag = 0;
430 return rel;
431}
432
433sql_rel *
434rel_setop(sql_allocator *sa, sql_rel *l, sql_rel *r, operator_type setop)
435{
436 sql_rel *rel = rel_create(sa);
437 if(!rel)
438 return NULL;
439
440 rel->l = l;
441 rel->r = r;
442 rel->op = setop;
443 rel->exps = NULL;
444 if (setop == op_union) {
445 rel->card = CARD_MULTI;
446 } else {
447 rel->card = l->card;
448 }
449 if (l && r)
450 rel->nrcols = l->nrcols + r->nrcols;
451 return rel;
452}
453
454sql_rel *
455rel_setop_check_types(mvc *sql, sql_rel *l, sql_rel *r, list *ls, list *rs, operator_type op)
456{
457 list *nls = new_exp_list(sql->sa);
458 list *nrs = new_exp_list(sql->sa);
459 node *n, *m;
460
461 if(!nls || !nrs)
462 return NULL;
463
464 for (n = ls->h, m = rs->h; n && m; n = n->next, m = m->next) {
465 sql_exp *le = n->data;
466 sql_exp *re = m->data;
467
468 if ((rel_convert_types(sql, l, r, &le, &re, 1, type_set) < 0))
469 return NULL;
470 append(nls, le);
471 append(nrs, re);
472 }
473 l = rel_project(sql->sa, l, nls);
474 r = rel_project(sql->sa, r, nrs);
475 set_processed(l);
476 set_processed(r);
477 return rel_setop(sql->sa, l, r, op);
478}
479
480sql_rel *
481rel_crossproduct(sql_allocator *sa, sql_rel *l, sql_rel *r, operator_type join)
482{
483 sql_rel *rel = rel_create(sa);
484 if(!rel)
485 return NULL;
486
487 rel->l = l;
488 rel->r = r;
489 rel->op = join;
490 rel->exps = NULL;
491 rel->card = CARD_MULTI;
492 rel->nrcols = l->nrcols + r->nrcols;
493 return rel;
494}
495
496sql_exp *
497rel_is_constant(sql_rel **R, sql_exp *e)
498{
499 sql_rel *rel = *R;
500
501 if (rel && rel->op == op_project && list_length(rel->exps) == 1 &&
502 !rel->l && !rel->r && !rel_is_ref(rel) && e->type == e_column) {
503 sql_exp *ne = rel_find_exp(rel, e);
504 if (ne) {
505 rel_destroy(rel);
506 *R = NULL;
507 return ne;
508 }
509 }
510 return e;
511}
512
513sql_rel *
514rel_topn(sql_allocator *sa, sql_rel *l, list *exps )
515{
516 sql_rel *rel = rel_create(sa);
517 if(!rel)
518 return NULL;
519
520 rel->l = l;
521 rel->r = NULL;
522 rel->op = op_topn;
523 rel->exps = exps;
524 rel->card = l->card;
525 rel->nrcols = l->nrcols;
526 return rel;
527}
528
529sql_rel *
530rel_sample(sql_allocator *sa, sql_rel *l, list *exps )
531{
532 sql_rel *rel = rel_create(sa);
533 if(!rel)
534 return NULL;
535
536 rel->l = l;
537 rel->r = NULL;
538 rel->op = op_sample;
539 rel->exps = exps;
540 rel->card = l->card;
541 rel->nrcols = l->nrcols;
542 return rel;
543}
544
545sql_rel *
546rel_label( mvc *sql, sql_rel *r, int all)
547{
548 int nr = ++sql->label;
549 char tname[16], *tnme;
550 char cname[16], *cnme = NULL;
551
552 tnme = number2name(tname, sizeof(tname), nr);
553 if (!is_project(r->op)) {
554 r = rel_project(sql->sa, r, rel_projections(sql, r, NULL, 1, 1));
555 set_processed(r);
556 }
557 if (is_project(r->op) && r->exps) {
558 node *ne = r->exps->h;
559
560 r->exps->ht = NULL;
561 for (; ne; ne = ne->next) {
562 sql_exp *e = ne->data;
563
564 if (!e->freevar) {
565 if (all) {
566 nr = ++sql->label;
567 cnme = number2name(cname, sizeof(cname), nr);
568 }
569 exp_setname(sql->sa, e, tnme, cnme );
570 }
571 }
572 }
573 /* op_projects can have a order by list */
574 if (r->op == op_project && r->r) {
575 list *exps = r->r;
576 node *ne = exps->h;
577
578 exps->ht = NULL;
579 for (; ne; ne = ne->next) {
580 if (all) {
581 nr = ++sql->label;
582 cnme = number2name(cname, sizeof(cname), nr);
583 }
584 exp_setname(sql->sa, ne->data, tnme, cnme );
585 }
586 }
587 return r;
588}
589
590sql_exp *
591rel_project_add_exp( mvc *sql, sql_rel *rel, sql_exp *e)
592{
593 assert(is_project(rel->op));
594
595 /*
596 if (!exp_relname(e)) {
597 if (exp_name(e))
598 exp_setrelname(sql->sa, e, ++sql->label);
599 else
600 exp_label(sql->sa, e, ++sql->label);
601 }
602 */
603 if (!exp_name(e))
604 exp_label(sql->sa, e, ++sql->label);
605 if (rel->op == op_project) {
606 sql_rel *l = rel->l;
607 if (!rel->exps)
608 rel->exps = new_exp_list(sql->sa);
609 if (l && is_groupby(l->op) && exp_card(e) <= CARD_ATOM && list_empty(l->exps))
610 e = rel_project_add_exp(sql, l, e);
611 if (e->card > rel->card)
612 rel->card = e->card;
613 append(rel->exps, e);
614 rel->nrcols++;
615 } else if (rel->op == op_groupby) {
616 return rel_groupby_add_aggr(sql, rel, e);
617 }
618 e = exp_ref(sql->sa, e);
619 return e;
620}
621
622sql_rel *
623rel_select_add_exp(sql_allocator *sa, sql_rel *l, sql_exp *e)
624{
625 if ((l->op != op_select && !is_outerjoin(l->op)) || rel_is_ref(l))
626 return rel_select(sa, l, e);
627
628/* allow during AST->relational for bool expresssions as well
629 if (e->type != e_cmp && e->card > CARD_ATOM) {
630 sql_exp *t = exp_atom_bool(sa, 1);
631 e = exp_compare(sa, e, t, cmp_equal);
632 }
633*/
634 if (!l->exps)
635 l->exps = new_exp_list(sa);
636 append(l->exps, e);
637 return l;
638}
639
640void
641rel_join_add_exp( sql_allocator *sa, sql_rel *rel, sql_exp *e)
642{
643 assert(is_join(rel->op) || is_semi(rel->op) || is_select(rel->op));
644
645 if (!rel->exps)
646 rel->exps = new_exp_list(sa);
647 append(rel->exps, e);
648 if (e->card > rel->card)
649 rel->card = e->card;
650}
651
652static sql_exp * exps_match(sql_exp *m, sql_exp *e);
653
654static int
655explists_match(list *m, list *e)
656{
657 node *nm,*ne;
658
659 if (!m || !e)
660 return (m==e);
661 if (list_length(m) != list_length(e))
662 return 0;
663 for (nm = m->h, ne = e->h; nm && ne; nm = nm->next, ne = ne->next) {
664 if (!exps_match(nm->data, ne->data))
665 return 0;
666 }
667 return 1;
668}
669
670static sql_exp *
671exps_match(sql_exp *m, sql_exp *e)
672{
673 if (m->type != e->type)
674 return NULL;
675 switch (m->type) {
676 case e_column:
677 if (strcmp(m->r, e->r) == 0) {
678 if (m->l && e->l && (strcmp(m->l, e->l) == 0))
679 return m;
680 else if (!m->l && !e->l)
681 return m;
682 }
683 break;
684 case e_aggr:
685 if (m->f == e->f && explists_match(m->l, e->l))
686 return m;
687 break;
688 default:
689 return NULL;
690 }
691 return NULL;
692}
693
694sql_exp *
695exps_find_match_exp(list *l, sql_exp *e)
696{
697 node *n;
698 if (!l || !list_length(l))
699 return NULL;
700
701 for (n = l->h; n; n = n->next){
702 sql_exp *m = n->data;
703 if (exps_match(m,e))
704 return m;
705 }
706 return NULL;
707}
708
709sql_exp *
710rel_groupby_add_aggr(mvc *sql, sql_rel *rel, sql_exp *e)
711{
712 sql_exp *m = NULL, *ne;
713
714 if (list_empty(rel->r))
715 rel->card = e->card = CARD_ATOM;
716
717 if ((m=exps_find_match_exp(rel->exps, e)) == NULL) {
718 if (!exp_name(e))
719 exp_label(sql->sa, e, ++sql->label);
720 append(rel->exps, e);
721 rel->nrcols++;
722 m = e;
723 }
724 ne = exp_ref(sql->sa, m);
725 return ne;
726}
727
728sql_rel *
729rel_select(sql_allocator *sa, sql_rel *l, sql_exp *e)
730{
731 sql_rel *rel;
732
733 if (l && is_outerjoin(l->op) && !is_processed(l)) {
734 if (e) {
735 if (!l->exps)
736 l->exps = new_exp_list(sa);
737 append(l->exps, e);
738 }
739 return l;
740 }
741
742 if (l && l->op == op_select && !rel_is_ref(l)) { /* refine old select */
743 if (e)
744 rel_select_add_exp(sa, l, e);
745 return l;
746 }
747 rel = rel_create(sa);
748 if(!rel)
749 return NULL;
750
751 rel->l = l;
752 rel->r = NULL;
753 rel->op = op_select;
754 rel->exps = new_exp_list(sa);
755 if (e)
756 rel_select_add_exp(sa, rel, e);
757 rel->card = CARD_ATOM; /* no relation */
758 if (l) {
759 rel->card = l->card;
760 rel->nrcols = l->nrcols;
761 }
762 return rel;
763}
764
765sql_rel *
766rel_basetable(mvc *sql, sql_table *t, const char *atname)
767{
768 prop *p = NULL;
769 node *cn;
770 sql_allocator *sa = sql->sa;
771 sql_rel *rel = rel_create(sa);
772 const char *tname = t->base.name;
773 if(!rel)
774 return NULL;
775
776 assert(atname);
777 rel->l = t;
778 rel->r = NULL;
779 rel->op = op_basetable;
780 rel->exps = new_exp_list(sa);
781 if(!rel->exps) {
782 rel_destroy(rel);
783 return NULL;
784 }
785
786 if (isRemote(t))
787 tname = mapiuri_table(t->query, sql->sa, tname);
788 for (cn = t->columns.set->h; cn; cn = cn->next) {
789 sql_column *c = cn->data;
790 sql_exp *e = exp_alias(sa, atname, c->base.name, tname, c->base.name, &c->type, CARD_MULTI, c->null, 0);
791
792 if (e == NULL) {
793 rel_destroy(rel);
794 return NULL;
795 }
796 if (c->t->pkey && ((sql_kc*)c->t->pkey->k.columns->h->data)->c == c) {
797 p = e->p = prop_create(sa, PROP_HASHCOL, e->p);
798 p->value = c->t->pkey;
799 } else if (c->unique == 1) {
800 p = e->p = prop_create(sa, PROP_HASHCOL, e->p);
801 p->value = NULL;
802 }
803 set_basecol(e);
804 append(rel->exps, e);
805 }
806 append(rel->exps, exp_alias(sa, atname, TID, tname, TID, sql_bind_localtype("oid"), CARD_MULTI, 0, 1));
807
808 if (t->idxs.set) {
809 for (cn = t->idxs.set->h; cn; cn = cn->next) {
810 sql_exp *e;
811 sql_idx *i = cn->data;
812 sql_subtype *t = sql_bind_localtype("lng"); /* hash "lng" */
813 char *iname = NULL;
814
815 /* do not include empty indices in the plan */
816 if (hash_index(i->type) && list_length(i->columns) <= 1)
817 continue;
818
819 if (i->type == join_idx)
820 t = sql_bind_localtype("oid");
821
822 iname = sa_strconcat( sa, "%", i->base.name);
823 e = exp_alias(sa, atname, iname, tname, iname, t, CARD_MULTI, 0, 1);
824 /* index names are prefixed, to make them independent */
825 if (hash_index(i->type)) {
826 p = e->p = prop_create(sa, PROP_HASHIDX, e->p);
827 p->value = i;
828 }
829 if (i->type == join_idx) {
830 p = e->p = prop_create(sa, PROP_JOINIDX, e->p);
831 p->value = i;
832 }
833 append(rel->exps, e);
834 }
835 }
836
837 rel->card = CARD_MULTI;
838 rel->nrcols = list_length(t->columns.set);
839 return rel;
840}
841
842sql_rel *
843rel_groupby(mvc *sql, sql_rel *l, list *groupbyexps )
844{
845 sql_rel *rel = rel_create(sql->sa);
846 list *aggrs = new_exp_list(sql->sa);
847 node *en;
848 if(!rel || !aggrs) {
849 rel_destroy(rel);
850 return NULL;
851 }
852
853 rel->card = CARD_ATOM;
854 /* reduce duplicates in groupbyexps */
855 if (groupbyexps && list_length(groupbyexps) > 1) {
856 list *gexps = sa_list(sql->sa);
857
858 for (en = groupbyexps->h; en; en = en->next) {
859 sql_exp *e = en->data, *ne;
860
861 if ((ne=exps_find_exp(gexps, e)) == NULL ||
862 strcmp(exp_relname(e),exp_relname(ne)) != 0 ||
863 strcmp(exp_name(e),exp_name(ne)) != 0 )
864 append(gexps, e);
865 }
866 groupbyexps = gexps;
867 }
868
869 if (groupbyexps) {
870 rel->card = CARD_AGGR;
871 for (en = groupbyexps->h; en; en = en->next) {
872 sql_exp *e = en->data, *ne;
873
874 /* after the group by the cardinality reduces */
875 e->card = rel->card;
876 if (!exp_name(e))
877 exp_label(sql->sa, e, ++sql->label);
878 ne = exp_ref(sql->sa, e);
879 ne = exp_propagate(sql->sa, ne, e);
880 append(aggrs, ne);
881 }
882 }
883 rel->l = l;
884 rel->r = groupbyexps;
885 rel->exps = aggrs;
886 rel->nrcols = l->nrcols;
887 rel->op = op_groupby;
888 return rel;
889}
890
891sql_rel *
892rel_project(sql_allocator *sa, sql_rel *l, list *e)
893{
894 sql_rel *rel = rel_create(sa);
895 if(!rel)
896 return NULL;
897
898 rel->l = l;
899 rel->r = NULL;
900 rel->op = op_project;
901 rel->exps = e;
902 rel->card = exps_card(e);
903 if (l) {
904 rel->card = l->card;
905 rel->nrcols = l->nrcols;
906 }
907 if (e && !list_empty(e))
908 set_processed(rel);
909 return rel;
910}
911
912sql_rel*
913rel_project_exp(sql_allocator *sa, sql_exp *e)
914{
915 sql_rel *rel = rel_project(sa, NULL, append(new_exp_list(sa), e));
916
917 return rel;
918}
919
920sql_rel *
921rel_exception(sql_allocator *sa, sql_rel *l, sql_rel *r, list *exps)
922{
923 sql_rel *rel = rel_create(sa);
924 if(!rel)
925 return NULL;
926 rel->l = l;
927 rel->r = r;
928 rel->exps = exps;
929 rel->op = op_ddl;
930 rel->flag = ddl_exception;
931 return rel;
932}
933
934sql_rel *
935rel_relational_func(sql_allocator *sa, sql_rel *l, list *exps)
936{
937 sql_rel *rel = rel_create(sa);
938 if(!rel)
939 return NULL;
940
941 rel->flag = 1;
942 rel->l = l;
943 rel->op = op_table;
944 rel->exps = exps;
945 rel->card = CARD_MULTI;
946 rel->nrcols = list_length(exps);
947 return rel;
948}
949
950sql_rel *
951rel_table_func(sql_allocator *sa, sql_rel *l, sql_exp *f, list *exps, int kind)
952{
953 sql_rel *rel = rel_create(sa);
954 if(!rel)
955 return NULL;
956
957 rel->flag = kind;
958 rel->l = l; /* relation before call */
959 rel->r = f; /* expression (table func call) */
960 rel->op = op_table;
961 rel->exps = exps;
962 rel->card = CARD_MULTI;
963 rel->nrcols = list_length(exps);
964 return rel;
965}
966
967static void
968exps_has_nil(list *exps)
969{
970 node *m;
971
972 for (m = exps->h; m; m = m->next) {
973 sql_exp *e = m->data;
974
975 set_has_nil(e);
976 }
977}
978
979list *
980_rel_projections(mvc *sql, sql_rel *rel, const char *tname, int settname, int intern, int basecol /* basecol only */ )
981{
982 list *lexps, *rexps, *exps;
983 int include_subquery = (intern==2)?1:0;
984
985 if (THRhighwater())
986 return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
987
988 if (!rel || (!include_subquery && is_subquery(rel) && rel->op == op_project))
989 return new_exp_list(sql->sa);
990
991 switch(rel->op) {
992 case op_join:
993 case op_left:
994 case op_right:
995 case op_full:
996 exps = _rel_projections(sql, rel->l, tname, settname, intern, basecol);
997 if (rel->op == op_full || rel->op == op_right)
998 exps_has_nil(exps);
999 rexps = _rel_projections(sql, rel->r, tname, settname, intern, basecol);
1000 if (rel->op == op_full || rel->op == op_left)
1001 exps_has_nil(rexps);
1002 exps = list_merge( exps, rexps, (fdup)NULL);
1003 return exps;
1004 case op_groupby:
1005 if (list_empty(rel->exps) && rel->r) {
1006 node *en;
1007 list *r = rel->r;
1008 int label = ++sql->label;
1009
1010 exps = new_exp_list(sql->sa);
1011 for (en = r->h; en; en = en->next) {
1012 sql_exp *e = en->data;
1013
1014 if (basecol && !is_basecol(e))
1015 continue;
1016 if (intern || !is_intern(e)) {
1017 append(exps, e = exp_alias_or_copy(sql, tname, exp_name(e), rel, e));
1018 if (!settname) /* noname use alias */
1019 exp_setrelname(sql->sa, e, label);
1020
1021 }
1022 }
1023 return exps;
1024 }
1025 /* fall through */
1026 case op_project:
1027 case op_basetable:
1028 case op_table:
1029
1030 case op_union:
1031 case op_except:
1032 case op_inter:
1033 if (rel->exps) {
1034 node *en;
1035 int label = ++sql->label;
1036
1037 exps = new_exp_list(sql->sa);
1038 for (en = rel->exps->h; en; en = en->next) {
1039 sql_exp *e = en->data;
1040
1041 if (basecol && !is_basecol(e))
1042 continue;
1043 if (intern || !is_intern(e)) {
1044 append(exps, e = exp_alias_or_copy(sql, tname, exp_name(e), rel, e));
1045 if (!settname) /* noname use alias */
1046 exp_setrelname(sql->sa, e, label);
1047
1048 }
1049 }
1050 return exps;
1051 }
1052 lexps = _rel_projections(sql, rel->l, tname, settname, intern, basecol);
1053 rexps = _rel_projections(sql, rel->r, tname, settname, intern, basecol);
1054 exps = sa_list(sql->sa);
1055 if (lexps && rexps && exps) {
1056 node *en, *ren;
1057 int label = ++sql->label;
1058 for (en = lexps->h, ren = rexps->h; en && ren; en = en->next, ren = ren->next) {
1059 sql_exp *e = en->data;
1060 e->card = rel->card;
1061 if (!settname) /* noname use alias */
1062 exp_setrelname(sql->sa, e, label);
1063 append(exps, e);
1064 }
1065 }
1066 return exps;
1067 case op_ddl:
1068 case op_semi:
1069 case op_anti:
1070
1071 case op_select:
1072 case op_topn:
1073 case op_sample:
1074 return _rel_projections(sql, rel->l, tname, settname, intern, basecol);
1075 default:
1076 return NULL;
1077 }
1078}
1079
1080list *
1081rel_projections(mvc *sql, sql_rel *rel, const char *tname, int settname, int intern)
1082{
1083 return _rel_projections(sql, rel, tname, settname, intern, 0);
1084}
1085
1086/* add a project around a project where each inner expression gets a unique label */
1087sql_rel *
1088rel_safe_project(mvc *sql, sql_rel *rel)
1089{
1090 list *nexps = sa_list(sql->sa);
1091
1092 assert(!list_empty(rel->exps));
1093 for(node *n = rel->exps->h; n; n=n->next) {
1094 sql_exp *e = n->data, *ne;
1095 const char *cname = exp_name(e);
1096 const char *rname = exp_relname(e);
1097
1098 n->data = e = exp_label(sql->sa, e, ++sql->label);
1099 ne = exp_ref(sql->sa, e);
1100 exp_setname(sql->sa, ne, rname, cname);
1101 append(nexps, ne);
1102 }
1103 list_hash_clear(rel->exps);
1104 return rel_project(sql->sa, rel, nexps);
1105}
1106
1107/* find the path to the relation containing the base of the expression
1108 (e_column), in most cases this means go down the join tree and
1109 find the base column.
1110 */
1111static int
1112rel_bind_path_(mvc *sql, sql_rel *rel, sql_exp *e, list *path )
1113{
1114 int found = 0;
1115
1116 if (THRhighwater()) {
1117 sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
1118 return 0;
1119 }
1120
1121 switch (rel->op) {
1122 case op_join:
1123 case op_left:
1124 case op_right:
1125 case op_full:
1126 /* first right (possible subquery) */
1127 found = rel_bind_path_(sql, rel->r, e, path);
1128 if (!found)
1129 found = rel_bind_path_(sql, rel->l, e, path);
1130 break;
1131 case op_semi:
1132 case op_anti:
1133
1134 case op_select:
1135 case op_topn:
1136 case op_sample:
1137 found = rel_bind_path_(sql, rel->l, e, path);
1138 break;
1139
1140 case op_union:
1141 case op_inter:
1142 case op_except:
1143 if (!rel->exps) {
1144 found = rel_bind_path_(sql, rel->l, e, path);
1145 assert(0);
1146 break;
1147 }
1148 /* fall through */
1149 case op_groupby:
1150 case op_project:
1151 case op_table:
1152 case op_basetable:
1153 if (!rel->exps)
1154 break;
1155 if (!found && e->l && exps_bind_column2(rel->exps, e->l, e->r))
1156 found = 1;
1157 if (!found && !e->l && exps_bind_column(rel->exps, e->r, NULL))
1158 found = 1;
1159 break;
1160 case op_insert:
1161 case op_update:
1162 case op_delete:
1163 case op_truncate:
1164 break;
1165 case op_ddl:
1166 break;
1167 }
1168 if (found)
1169 list_prepend(path, rel);
1170 return found;
1171}
1172
1173static list *
1174rel_bind_path(mvc *sql, sql_rel *rel, sql_exp *e)
1175{
1176 list *path = new_rel_list(sql->sa);
1177 if(!path) {
1178 return NULL;
1179 }
1180
1181 if (e->type == e_convert)
1182 e = e->l;
1183 if (e->type == e_column) {
1184 if (rel) {
1185 if (!rel_bind_path_(sql, rel, e, path)) {
1186 /* something is wrong */
1187 return NULL;
1188 }
1189 }
1190 return path;
1191 }
1192 /* default the top relation */
1193 append(path, rel);
1194 return path;
1195}
1196
1197/* ls is the left expression of the select, rs is a simple atom, e is the
1198 select expression.
1199 */
1200sql_rel *
1201rel_push_select(mvc *sql, sql_rel *rel, sql_exp *ls, sql_exp *e)
1202{
1203 list *l = rel_bind_path(sql, rel, ls);
1204 node *n;
1205 sql_rel *lrel = NULL, *p = NULL;
1206
1207 if (!l || !sql->pushdown) {
1208 /* expression has no clear parent relation, so filter current
1209 with it */
1210 return rel_select(sql->sa, rel, e);
1211 }
1212
1213 for (n = l->h; n; n = n->next ) {
1214 lrel = n->data;
1215
1216 if (rel_is_ref(lrel))
1217 break;
1218
1219 /* push down as long as the operators allow this */
1220 if (!is_select(lrel->op) &&
1221 !(is_semi(lrel->op) && !rel_is_ref(lrel->l)) &&
1222 lrel->op != op_join &&
1223 lrel->op != op_left)
1224 break;
1225 /* pushing through left head of a left join is allowed */
1226 if (lrel->op == op_left && (!n->next || lrel->l != n->next->data))
1227 break;
1228 p = lrel;
1229 }
1230 if (!lrel)
1231 return NULL;
1232 if (p && p->op == op_select && !rel_is_ref(p)) { /* refine old select */
1233 rel_select_add_exp(sql->sa, p, e);
1234 } else {
1235 sql_rel *n = rel_select(sql->sa, lrel, e);
1236
1237 if (p && p != lrel) {
1238 assert(p->op == op_join || p->op == op_left || is_semi(p->op));
1239 if (p->l == lrel) {
1240 p->l = n;
1241 } else {
1242 p->r = n;
1243 }
1244 } else {
1245 if (rel != lrel)
1246 assert(0);
1247 rel = n;
1248 }
1249 }
1250 return rel;
1251}
1252
1253
1254/* ls and rs are the left and right expression of the join, e is the
1255 join expression.
1256 */
1257sql_rel *
1258rel_push_join(mvc *sql, sql_rel *rel, sql_exp *ls, sql_exp *rs, sql_exp *rs2, sql_exp *e)
1259{
1260 list *l = rel_bind_path(sql, rel, ls);
1261 list *r = rel_bind_path(sql, rel, rs);
1262 list *r2 = NULL;
1263 node *ln, *rn;
1264 sql_rel *lrel = NULL, *rrel = NULL, *rrel2 = NULL, *p = NULL;
1265
1266 if (rs2)
1267 r2 = rel_bind_path(sql, rel, rs2);
1268 if (!l || !r || (rs2 && !r2))
1269 return NULL;
1270
1271 if (!sql->pushdown)
1272 return rel_push_select(sql, rel, ls, e);
1273
1274 p = rel;
1275 if (r2) {
1276 node *rn2;
1277
1278 for (ln = l->h, rn = r->h, rn2 = r2->h; ln && rn && rn2; ln = ln->next, rn = rn->next, rn2 = rn2->next ) {
1279 lrel = ln->data;
1280 rrel = rn->data;
1281 rrel2 = rn2->data;
1282
1283 if (rel_is_ref(lrel) || rel_is_ref(rrel) || rel_is_ref(rrel2) || is_processed(lrel) || is_processed(rrel))
1284 break;
1285
1286 /* push down as long as the operators allow this
1287 and the relation is equal.
1288 */
1289 if (lrel != rrel || lrel != rrel2 ||
1290 (!is_select(lrel->op) &&
1291 !(is_semi(lrel->op) && !rel_is_ref(lrel->l)) &&
1292 lrel->op != op_join &&
1293 lrel->op != op_left))
1294 break;
1295 /* pushing through left head of a left join is allowed */
1296 if (lrel->op == op_left && (!ln->next || lrel->l != ln->next->data))
1297 break;
1298 p = lrel;
1299 }
1300 } else {
1301 for (ln = l->h, rn = r->h; ln && rn; ln = ln->next, rn = rn->next ) {
1302 lrel = ln->data;
1303 rrel = rn->data;
1304
1305 if (rel_is_ref(lrel) || rel_is_ref(rrel) || is_processed(lrel) || is_processed(rrel))
1306 break;
1307
1308 /* push down as long as the operators allow this
1309 and the relation is equal.
1310 */
1311 if (lrel != rrel ||
1312 (!is_select(lrel->op) &&
1313 !(is_semi(lrel->op) && !rel_is_ref(lrel->l)) &&
1314 lrel->op != op_join &&
1315 lrel->op != op_left))
1316 break;
1317 /* pushing through left head of a left join is allowed */
1318 if (lrel->op == op_left && (!ln->next || lrel->l != ln->next->data))
1319 break;
1320 p = lrel;
1321 }
1322 }
1323 if (!lrel || !rrel || (r2 && !rrel2))
1324 return NULL;
1325
1326 /* filter on columns of this relation */
1327 if ((lrel == rrel && (!r2 || lrel == rrel2) && lrel->op != op_join) || rel_is_ref(p)) {
1328 if (lrel->op == op_select && !rel_is_ref(lrel)) {
1329 rel_select_add_exp(sql->sa, lrel, e);
1330 } else if (p && p->op == op_select && !rel_is_ref(p)) {
1331 rel_select_add_exp(sql->sa, p, e);
1332 } else {
1333 sql_rel *n = rel_select(sql->sa, lrel, e);
1334
1335 if (p && p != lrel) {
1336 if (p->l == lrel)
1337 p->l = n;
1338 else
1339 p->r = n;
1340 } else {
1341 rel = n;
1342 }
1343 }
1344 return rel;
1345 }
1346
1347 rel_join_add_exp( sql->sa, p, e);
1348 return rel;
1349}
1350
1351sql_rel *
1352rel_or(mvc *sql, sql_rel *rel, sql_rel *l, sql_rel *r, list *oexps, list *lexps, list *rexps)
1353{
1354 sql_rel *ll = l->l, *rl = r->l;
1355 list *ls, *rs;
1356
1357 assert(!lexps || l == r);
1358 if (l == r && lexps) { /* merge both lists */
1359 sql_exp *e = exp_or(sql->sa, lexps, rexps, 0);
1360 list *nl = oexps?oexps:new_exp_list(sql->sa);
1361
1362 rel_destroy(r);
1363 append(nl, e);
1364 if (is_outerjoin(l->op) && is_processed(l))
1365 l = rel_select(sql->sa, l, NULL);
1366 l->exps = nl;
1367 return l;
1368 }
1369
1370 /* favor or expressions over union */
1371 if (l->op == r->op && l->op == op_select &&
1372 ll == rl && ll == rel && !rel_is_ref(l) && !rel_is_ref(r)) {
1373 sql_exp *e = exp_or(sql->sa, l->exps, r->exps, 0);
1374 list *nl = new_exp_list(sql->sa);
1375
1376 rel_destroy(r);
1377 append(nl, e);
1378 l->exps = nl;
1379
1380 /* merge and expressions */
1381 ll = l->l;
1382 while (ll && ll->op == op_select && !rel_is_ref(ll)) {
1383 list_merge(l->exps, ll->exps, (fdup)NULL);
1384 l->l = ll->l;
1385 ll->l = NULL;
1386 rel_destroy(ll);
1387 ll = l->l;
1388 }
1389 return l;
1390 }
1391
1392 if (rel) {
1393 ls = rel_projections(sql, rel, NULL, 1, 1);
1394 rs = rel_projections(sql, rel, NULL, 1, 1);
1395 } else {
1396 ls = rel_projections(sql, l, NULL, 1, 1);
1397 rs = rel_projections(sql, r, NULL, 1, 1);
1398 }
1399 set_processed(l);
1400 set_processed(r);
1401 rel = rel_setop_check_types(sql, l, r, ls, rs, op_union);
1402 if (!rel)
1403 return NULL;
1404 rel->exps = rel_projections(sql, rel, NULL, 1, 1);
1405 set_processed(rel);
1406 rel = rel_distinct(rel);
1407 if (!rel)
1408 return NULL;
1409 if (exps_card(l->exps) <= CARD_AGGR &&
1410 exps_card(r->exps) <= CARD_AGGR)
1411 {
1412 rel->card = exps_card(l->exps);
1413 exps_fix_card( rel->exps, rel->card);
1414 }
1415 return rel;
1416}
1417
1418sql_table *
1419rel_ddl_table_get(sql_rel *r)
1420{
1421 if (r->flag == ddl_alter_table || r->flag == ddl_create_table || r->flag == ddl_create_view) {
1422 sql_exp *e = r->exps->t->data;
1423 atom *a = e->l;
1424
1425 return a->data.val.pval;
1426 }
1427 return NULL;
1428}
1429
1430static sql_exp *
1431exps_find_identity(list *exps, sql_rel *p)
1432{
1433 node *n;
1434
1435 for (n=exps->h; n; n = n->next) {
1436 sql_exp *e = n->data;
1437
1438 if (is_identity(e, p))
1439 return e;
1440 }
1441 return NULL;
1442}
1443
1444static sql_rel *
1445_rel_add_identity(mvc *sql, sql_rel *rel, sql_exp **exp)
1446{
1447 list *exps = rel_projections(sql, rel, NULL, 1, 2);
1448 sql_exp *e;
1449
1450 if (list_length(exps) == 0) {
1451 *exp = NULL;
1452 return rel;
1453 }
1454 rel = rel_project(sql->sa, rel, exps);
1455 e = rel->exps->h->data;
1456 e = exp_column(sql->sa, exp_relname(e), exp_name(e), exp_subtype(e), rel->card, has_nil(e), is_intern(e));
1457 e = exp_unop(sql->sa, e, sql_bind_func(sql->sa, NULL, "identity", exp_subtype(e), NULL, F_FUNC));
1458 set_intern(e);
1459 e->p = prop_create(sql->sa, PROP_HASHCOL, e->p);
1460 *exp = exp_label(sql->sa, e, ++sql->label);
1461 (void) rel_project_add_exp(sql, rel, e);
1462 return rel;
1463}
1464
1465sql_rel *
1466rel_add_identity(mvc *sql, sql_rel *rel, sql_exp **exp)
1467{
1468 if (rel && is_project(rel->op) && (*exp = exps_find_identity(rel->exps, rel->l)) != NULL)
1469 return rel;
1470 return _rel_add_identity(sql, rel, exp);
1471}
1472
1473sql_rel *
1474rel_add_identity2(mvc *sql, sql_rel *rel, sql_exp **exp)
1475{
1476 sql_rel *l = rel, *p = rel;
1477
1478 if (rel && is_project(rel->op) && (*exp = exps_find_identity(rel->exps, rel->l)) != NULL)
1479 return rel;
1480 while(l && !is_set(l->op) && rel_has_freevar(sql, l) && l->l) {
1481 p = l;
1482 l = l->l;
1483 }
1484 if (l != p) {
1485 sql_rel *o = rel;
1486 sql_exp *id;
1487
1488 p->l = _rel_add_identity(sql, l, exp);
1489 l = p->l;
1490 id = exp_ref(sql->sa, *exp);
1491 while (o && o != l) {
1492 *exp = id;
1493 if (is_project(o->op))
1494 rel_project_add_exp(sql, o, id);
1495 o = o->l;
1496 }
1497 return rel;
1498 }
1499 return _rel_add_identity(sql, rel, exp);
1500}
1501
1502sql_exp *
1503rel_find_column( sql_allocator *sa, sql_rel *rel, const char *tname, const char *cname )
1504{
1505 if (!rel)
1506 return NULL;
1507
1508 if (rel->exps && (is_project(rel->op) || is_base(rel->op))) {
1509 int ambiguous = 0;
1510 sql_exp *e = exps_bind_column2(rel->exps, tname, cname);
1511 if (!e && cname[0] == '%')
1512 e = exps_bind_column(rel->exps, cname, &ambiguous);
1513 if (e && !ambiguous)
1514 return exp_alias(sa, exp_relname(e), exp_name(e), exp_relname(e), cname, exp_subtype(e), e->card, has_nil(e), is_intern(e));
1515 }
1516 if (is_project(rel->op) && rel->l && !is_processed(rel)) {
1517 return rel_find_column(sa, rel->l, tname, cname);
1518 } else if (is_join(rel->op)) {
1519 sql_exp *e = rel_find_column(sa, rel->l, tname, cname);
1520 if (!e)
1521 e = rel_find_column(sa, rel->r, tname, cname);
1522 return e;
1523 } else if (is_set(rel->op) ||
1524 is_sort(rel) ||
1525 is_semi(rel->op) ||
1526 is_select(rel->op)) {
1527 if (rel->l)
1528 return rel_find_column(sa, rel->l, tname, cname);
1529 }
1530 return NULL;
1531}
1532
1533int
1534rel_in_rel(sql_rel *super, sql_rel *sub)
1535{
1536 if (!super)
1537 return 0;
1538 if (super == sub)
1539 return 1;
1540 if (is_join(super->op) || is_semi(super->op) || is_set(super->op) || is_modify(super->op) || is_ddl(super->op))
1541 return rel_in_rel(super->l, sub) || rel_in_rel(super->r, sub);
1542 if (is_select(super->op) || is_project(super->op) || is_topn(super->op) || is_sample(super->op))
1543 return rel_in_rel(super->l, sub);
1544 return 0;
1545}
1546
1547static sql_rel *
1548refs_find_rel(list *refs, sql_rel *rel)
1549{
1550 node *n;
1551
1552 for(n=refs->h; n; n = n->next->next) {
1553 sql_rel *ref = n->data;
1554 sql_rel *s = n->next->data;
1555
1556 if (rel == ref)
1557 return s;
1558 }
1559 return NULL;
1560}
1561
1562static int exp_deps(mvc *sql, sql_exp *e, list *refs, list *l);
1563
1564static int
1565exps_deps(mvc *sql, list *exps, list *refs, list *l)
1566{
1567 node *n;
1568
1569 for(n = exps->h; n; n = n->next) {
1570 if (exp_deps(sql, n->data, refs, l) != 0)
1571 return -1;
1572 }
1573 return 0;
1574}
1575
1576static int
1577id_cmp(int *id1, int *id2)
1578{
1579 if (*id1 == *id2)
1580 return 0;
1581 return -1;
1582}
1583
1584static list *
1585cond_append(list *l, int *id)
1586{
1587 if (*id >= FUNC_OIDS && !list_find(l, id, (fcmp) &id_cmp))
1588 list_append(l, id);
1589 return l;
1590}
1591
1592static int rel_deps(mvc *sql, sql_rel *r, list *refs, list *l);
1593
1594static int
1595exp_deps(mvc *sql, sql_exp *e, list *refs, list *l)
1596{
1597 if (THRhighwater()) {
1598 (void) sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
1599 return -1;
1600 }
1601
1602 switch(e->type) {
1603 case e_psm:
1604 if (e->flag & PSM_SET || e->flag & PSM_RETURN) {
1605 return exp_deps(sql, e->l, refs, l);
1606 } else if (e->flag & PSM_VAR) {
1607 return 0;
1608 } else if (e->flag & PSM_WHILE || e->flag & PSM_IF) {
1609 if (exp_deps(sql, e->l, refs, l) != 0 ||
1610 exps_deps(sql, e->r, refs, l) != 0)
1611 return -1;
1612 if (e->flag == PSM_IF && e->f)
1613 return exps_deps(sql, e->r, refs, l);
1614 } else if (e->flag & PSM_REL) {
1615 sql_rel *rel = e->l;
1616 return rel_deps(sql, rel, refs, l);
1617 } else if (e->flag & PSM_EXCEPTION) {
1618 return exps_deps(sql, e->l, refs, l);
1619 }
1620 case e_atom:
1621 case e_column:
1622 break;
1623 case e_convert:
1624 return exp_deps(sql, e->l, refs, l);
1625 case e_func: {
1626 sql_subfunc *f = e->f;
1627
1628 if (e->l && exps_deps(sql, e->l, refs, l) != 0)
1629 return -1;
1630 cond_append(l, &f->func->base.id);
1631 if (e->l && list_length(e->l) == 2 && strcmp(f->func->base.name, "next_value_for") == 0) {
1632 /* add dependency on seq nr */
1633 list *nl = e->l;
1634 sql_exp *schname = nl->h->data;
1635 sql_exp *seqname = nl->t->data;
1636
1637 char *sch_name = ((atom*)schname->l)->data.val.sval;
1638 char *seq_name = ((atom*)seqname->l)->data.val.sval;
1639 sql_schema *sche = mvc_bind_schema(sql, sch_name);
1640 sql_sequence *seq = find_sql_sequence(sche, seq_name);
1641
1642 cond_append(l, &seq->base.id);
1643 }
1644 } break;
1645 case e_aggr: {
1646 sql_subaggr *a = e->f;
1647
1648 if (e->l &&exps_deps(sql, e->l, refs, l) != 0)
1649 return -1;
1650 cond_append(l, &a->aggr->base.id);
1651 } break;
1652 case e_cmp: {
1653 if (get_cmp(e) == cmp_or || get_cmp(e) == cmp_filter) {
1654 if (get_cmp(e) == cmp_filter) {
1655 sql_subfunc *f = e->f;
1656 cond_append(l, &f->func->base.id);
1657 }
1658 if (exps_deps(sql, e->l, refs, l) != 0 ||
1659 exps_deps(sql, e->r, refs, l) != 0)
1660 return -1;
1661 } else if (e->flag == cmp_in || e->flag == cmp_notin) {
1662 if (exp_deps(sql, e->l, refs, l) != 0 ||
1663 exps_deps(sql, e->r, refs, l) != 0)
1664 return -1;
1665 } else {
1666 if (exp_deps(sql, e->l, refs, l) != 0 ||
1667 exp_deps(sql, e->r, refs, l) != 0)
1668 return -1;
1669 if (e->f)
1670 return exp_deps(sql, e->f, refs, l);
1671 }
1672 } break;
1673 }
1674 return 0;
1675}
1676
1677static int
1678rel_deps(mvc *sql, sql_rel *r, list *refs, list *l)
1679{
1680 if (THRhighwater()) {
1681 (void) sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
1682 return -1;
1683 }
1684
1685 if (!r)
1686 return 0;
1687
1688 if (rel_is_ref(r) && refs_find_rel(refs, r)) /* allready handled */
1689 return 0;
1690 switch (r->op) {
1691 case op_basetable: {
1692 sql_table *t = r->l;
1693 sql_column *c = r->r;
1694
1695 if (!t && c)
1696 t = c->t;
1697
1698 cond_append(l, &t->base.id);
1699 /* find all used columns */
1700 for (node *en = r->exps->h; en; en = en->next) {
1701 sql_exp *exp = en->data;
1702 const char *oname = exp->r;
1703
1704 assert(!is_func(exp->type));
1705 if (oname[0] == '%' && strcmp(oname, TID) == 0) {
1706 continue;
1707 } else if (oname[0] == '%') {
1708 sql_idx *i = find_sql_idx(t, oname+1);
1709 cond_append(l, &i->base.id);
1710 } else {
1711 sql_column *c = find_sql_column(t, oname);
1712 cond_append(l, &c->base.id);
1713 }
1714 }
1715 } break;
1716 case op_table: {
1717 if ((r->flag == 0 || r->flag == 1) && r->r) { /* table producing function, excluding rel_relational_func cases */
1718 sql_exp *op = r->r;
1719 sql_subfunc *f = op->f;
1720 cond_append(l, &f->func->base.id);
1721 }
1722 } break;
1723 case op_join:
1724 case op_left:
1725 case op_right:
1726 case op_full:
1727 case op_semi:
1728 case op_anti:
1729 case op_union:
1730 case op_except:
1731 case op_inter:
1732 if (rel_deps(sql, r->l, refs, l) != 0 ||
1733 rel_deps(sql, r->r, refs, l) != 0)
1734 return -1;
1735 break;
1736 case op_project:
1737 case op_select:
1738 case op_groupby:
1739 case op_topn:
1740 case op_sample:
1741 if (rel_deps(sql, r->l, refs, l) != 0)
1742 return -1;
1743 break;
1744 case op_insert:
1745 case op_update:
1746 case op_delete:
1747 case op_truncate:
1748 if (rel_deps(sql, r->l, refs, l) != 0 ||
1749 rel_deps(sql, r->r, refs, l) != 0)
1750 return -1;
1751 break;
1752 case op_ddl:
1753 if (r->flag == ddl_output) {
1754 if (r->l)
1755 return rel_deps(sql, r->l, refs, l);
1756 } else if (r->flag == ddl_list || r->flag == ddl_exception) {
1757 if (r->l)
1758 return rel_deps(sql, r->l, refs, l);
1759 if (r->r)
1760 return rel_deps(sql, r->r, refs, l);
1761 } else if (r->flag == ddl_psm) {
1762 break;
1763 } else if (r->flag == ddl_create_seq || r->flag == ddl_alter_seq) {
1764 if (r->l)
1765 return rel_deps(sql, r->l, refs, l);
1766 }
1767 break;
1768 }
1769 if (!is_base(r->op) && r->exps) {
1770 if (exps_deps(sql, r->exps, refs, l) != 0)
1771 return -1;
1772 }
1773 if (is_groupby(r->op) && r->r) {
1774 if (exps_deps(sql, r->r, refs, l) != 0)
1775 return -1;
1776 }
1777 if (rel_is_ref(r)) {
1778 list_append(refs, r);
1779 list_append(refs, l);
1780 }
1781 return 0;
1782}
1783
1784list *
1785rel_dependencies(mvc *sql, sql_rel *r)
1786{
1787 list *refs = sa_list(sql->sa);
1788 list *l = sa_list(sql->sa);
1789
1790 if (rel_deps(sql, r, refs, l) != 0)
1791 return NULL;
1792 return l;
1793}
1794
1795
1796static list *exps_exp_visitor(mvc *sql, sql_rel *rel, list *exps, int depth, exp_rewrite_fptr exp_rewriter);
1797
1798static sql_exp *
1799exp_visitor(mvc *sql, sql_rel *rel, sql_exp *e, int depth, exp_rewrite_fptr exp_rewriter)
1800{
1801 assert(e);
1802 switch(e->type) {
1803 case e_column:
1804 break;
1805 case e_convert:
1806 if ((e->l = exp_visitor(sql, rel, e->l, depth+1, exp_rewriter)) == NULL)
1807 return NULL;
1808 break;
1809 case e_aggr:
1810 case e_func:
1811 if (e->r) /* rewrite rank */
1812 if ((e->r = exps_exp_visitor(sql, rel, e->r, depth+1, exp_rewriter)) == NULL)
1813 return NULL;
1814 if (e->l)
1815 if ((e->l = exps_exp_visitor(sql, rel, e->l, depth+1, exp_rewriter)) == NULL)
1816 return NULL;
1817 break;
1818 case e_cmp:
1819 if (get_cmp(e) == cmp_or || get_cmp(e) == cmp_filter) {
1820 if ((e->l = exps_exp_visitor(sql, rel, e->l, depth+1, exp_rewriter)) == NULL)
1821 return NULL;
1822 if ((e->r = exps_exp_visitor(sql, rel, e->r, depth+1, exp_rewriter)) == NULL)
1823 return NULL;
1824 } else if (e->flag == cmp_in || e->flag == cmp_notin) {
1825 if ((e->l = exp_visitor(sql, rel, e->l, depth+1, exp_rewriter)) == NULL)
1826 return NULL;
1827 if ((e->r = exps_exp_visitor(sql, rel, e->r, depth+1, exp_rewriter)) == NULL)
1828 return NULL;
1829 } else {
1830 if ((e->l = exp_visitor(sql, rel, e->l, depth+1, exp_rewriter)) == NULL)
1831 return NULL;
1832 if ((e->r = exp_visitor(sql, rel, e->r, depth+1, exp_rewriter)) == NULL)
1833 return NULL;
1834 if (e->f && (e->f = exp_visitor(sql, rel, e->f, depth+1, exp_rewriter)) == NULL)
1835 return NULL;
1836 }
1837 break;
1838 case e_psm:
1839 if (e->flag & PSM_SET || e->flag & PSM_RETURN) {
1840 if ((e->l = exp_visitor(sql, rel, e->l, depth+1, exp_rewriter)) == NULL)
1841 return NULL;
1842 } else if (e->flag & PSM_VAR) {
1843 return e;
1844 } else if (e->flag & PSM_WHILE || e->flag & PSM_IF) {
1845 if ((e->l = exp_visitor(sql, rel, e->l, depth+1, exp_rewriter)) == NULL)
1846 return NULL;
1847 if ((e->r = exps_exp_visitor(sql, rel, e->r, depth+1, exp_rewriter)) == NULL)
1848 return NULL;
1849 if (e->flag == PSM_IF && e->f && (e->f = exps_exp_visitor(sql, rel, e->f, depth+1, exp_rewriter)) == NULL)
1850 return NULL;
1851 } else if (e->flag & PSM_REL) {
1852 if ((e->l = rel_exp_visitor(sql, e->l, exp_rewriter)) == NULL)
1853 return NULL;
1854 } else if (e->flag & PSM_EXCEPTION) {
1855 if ((e->l = exp_visitor(sql, rel, e->l, depth+1, exp_rewriter)) == NULL)
1856 return NULL;
1857 }
1858 break;
1859 case e_atom:
1860 if (e->f)
1861 if ((e->f = exps_exp_visitor(sql, rel, e->f, depth+1, exp_rewriter)) == NULL)
1862 return NULL;
1863 break;
1864 }
1865 return exp_rewriter(sql, rel, e, depth);
1866}
1867
1868static list *
1869exps_exp_visitor(mvc *sql, sql_rel *rel, list *exps, int depth, exp_rewrite_fptr exp_rewriter)
1870{
1871 node *n;
1872
1873 if (list_empty(exps))
1874 return exps;
1875 for (n = exps->h; n; n = n->next) {
1876 if (n->data && (n->data = exp_visitor(sql, rel, n->data, depth, exp_rewriter)) == NULL)
1877 return NULL;
1878 }
1879 list_hash_clear(exps);
1880 return exps;
1881}
1882
1883sql_rel *
1884rel_exp_visitor(mvc *sql, sql_rel *rel, exp_rewrite_fptr exp_rewriter)
1885{
1886 if (!rel)
1887 return rel;
1888
1889 if (rel->exps && (rel->exps = exps_exp_visitor(sql, rel, rel->exps, 0, exp_rewriter)) == NULL)
1890 return NULL;
1891 if (is_groupby(rel->op) && rel->r && (rel->r = exps_exp_visitor(sql, rel, rel->r, 0, exp_rewriter)) == NULL)
1892 return NULL;
1893
1894 switch(rel->op){
1895 case op_basetable:
1896 case op_table:
1897 return rel;
1898 case op_ddl:
1899 if (rel->flag == ddl_output) {
1900 if (rel->l)
1901 if ((rel->l = rel_exp_visitor(sql, rel->l, exp_rewriter)) == NULL)
1902 return NULL;
1903 } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
1904 if (rel->l)
1905 if ((rel->l = rel_exp_visitor(sql, rel->l, exp_rewriter)) == NULL)
1906 return NULL;
1907 if (rel->r)
1908 if ((rel->r = rel_exp_visitor(sql, rel->r, exp_rewriter)) == NULL)
1909 return NULL;
1910 } else if (rel->flag == ddl_psm) {
1911 break;
1912 } else if (rel->flag == ddl_create_seq || rel->flag == ddl_alter_seq) {
1913 if (rel->l)
1914 if ((rel->l = rel_exp_visitor(sql, rel->l, exp_rewriter)) == NULL)
1915 return NULL;
1916 }
1917 return rel;
1918
1919 case op_insert:
1920 case op_update:
1921 case op_delete:
1922 case op_truncate:
1923
1924 case op_join:
1925 case op_left:
1926 case op_right:
1927 case op_full:
1928 case op_semi:
1929 case op_anti:
1930
1931 case op_union:
1932 case op_inter:
1933 case op_except:
1934 if (rel->l)
1935 if ((rel->l = rel_exp_visitor(sql, rel->l, exp_rewriter)) == NULL)
1936 return NULL;
1937 if (rel->r)
1938 if ((rel->r = rel_exp_visitor(sql, rel->r, exp_rewriter)) == NULL)
1939 return NULL;
1940 break;
1941 case op_select:
1942 case op_topn:
1943 case op_sample:
1944 case op_project:
1945 case op_groupby:
1946 if (rel->l)
1947 if ((rel->l = rel_exp_visitor(sql, rel->l, exp_rewriter)) == NULL)
1948 return NULL;
1949 break;
1950 }
1951 return rel;
1952}
1953
1954static list *exps_rel_visitor(mvc *sql, list *exps, rel_rewrite_fptr rel_rewriter);
1955
1956static sql_exp *
1957exp_rel_visitor(mvc *sql, sql_exp *e, rel_rewrite_fptr rel_rewriter)
1958{
1959 assert(e);
1960 switch(e->type) {
1961 case e_column:
1962 break;
1963 case e_convert:
1964 if ((e->l = exp_rel_visitor(sql, e->l, rel_rewriter)) == NULL)
1965 return NULL;
1966 break;
1967 case e_aggr:
1968 case e_func:
1969 if (e->r) /* rewrite rank */
1970 if ((e->r = exps_rel_visitor(sql, e->r, rel_rewriter)) == NULL)
1971 return NULL;
1972 if (e->l)
1973 if ((e->l = exps_rel_visitor(sql, e->l, rel_rewriter)) == NULL)
1974 return NULL;
1975 break;
1976 case e_cmp:
1977 if (get_cmp(e) == cmp_or || get_cmp(e) == cmp_filter) {
1978 if ((e->l = exps_rel_visitor(sql, e->l, rel_rewriter)) == NULL)
1979 return NULL;
1980 if ((e->r = exps_rel_visitor(sql, e->r, rel_rewriter)) == NULL)
1981 return NULL;
1982 } else if (e->flag == cmp_in || e->flag == cmp_notin) {
1983 if ((e->l = exp_rel_visitor(sql, e->l, rel_rewriter)) == NULL)
1984 return NULL;
1985 if ((e->r = exps_rel_visitor(sql, e->r, rel_rewriter)) == NULL)
1986 return NULL;
1987 } else {
1988 if ((e->l = exp_rel_visitor(sql, e->l, rel_rewriter)) == NULL)
1989 return NULL;
1990 if ((e->r = exp_rel_visitor(sql, e->r, rel_rewriter)) == NULL)
1991 return NULL;
1992 if (e->f && (e->f = exp_rel_visitor(sql, e->f, rel_rewriter)) == NULL)
1993 return NULL;
1994 }
1995 break;
1996 case e_psm:
1997 if (e->flag & PSM_SET || e->flag & PSM_RETURN) {
1998 if ((e->l = exp_rel_visitor(sql, e->l, rel_rewriter)) == NULL)
1999 return NULL;
2000 } else if (e->flag & PSM_VAR) {
2001 return e;
2002 } else if (e->flag & PSM_WHILE || e->flag & PSM_IF) {
2003 if ((e->l = exp_rel_visitor(sql, e->l, rel_rewriter)) == NULL)
2004 return NULL;
2005 if ((e->r = exps_rel_visitor(sql, e->r, rel_rewriter)) == NULL)
2006 return NULL;
2007 if (e->flag == PSM_IF && e->f && (e->f = exps_rel_visitor(sql, e->f, rel_rewriter)) == NULL)
2008 return NULL;
2009 } else if (e->flag & PSM_REL) {
2010 if ((e->l = rel_visitor(sql, e->l, rel_rewriter)) == NULL)
2011 return NULL;
2012 } else if (e->flag & PSM_EXCEPTION) {
2013 if ((e->l = exp_rel_visitor(sql, e->l, rel_rewriter)) == NULL)
2014 return NULL;
2015 }
2016 break;
2017 case e_atom:
2018 break;
2019 }
2020 return e;
2021}
2022
2023static list *
2024exps_rel_visitor(mvc *sql, list *exps, rel_rewrite_fptr rel_rewriter)
2025{
2026 node *n;
2027
2028 if (list_empty(exps))
2029 return exps;
2030 for (n = exps->h; n; n = n->next) {
2031 sql_exp *e = n->data;
2032
2033 if (e && (n->data = exp_rel_visitor(sql, e, rel_rewriter)) == NULL)
2034 return NULL;
2035 }
2036 list_hash_clear(exps);
2037 return exps;
2038}
2039
2040sql_rel *
2041rel_visitor(mvc *sql, sql_rel *rel, rel_rewrite_fptr rel_rewriter)
2042{
2043 if (!rel)
2044 return rel;
2045
2046 switch(rel->op){
2047 case op_basetable:
2048 case op_table:
2049 return rel;
2050 case op_ddl:
2051 if (rel->flag == ddl_output) {
2052 if (rel->l)
2053 if ((rel->l = rel_visitor(sql, rel->l, rel_rewriter)) == NULL)
2054 return NULL;
2055 } else if (rel->flag == ddl_list || rel->flag == ddl_exception) {
2056 if (rel->l)
2057 if ((rel->l = rel_visitor(sql, rel->l, rel_rewriter)) == NULL)
2058 return NULL;
2059 if (rel->r)
2060 if ((rel->r = rel_visitor(sql, rel->r, rel_rewriter)) == NULL)
2061 return NULL;
2062 } else if (rel->flag == ddl_psm) {
2063 if ((rel->exps = exps_rel_visitor(sql, rel->exps, rel_rewriter)) == NULL)
2064 return NULL;
2065 } else if (rel->flag == ddl_create_seq || rel->flag == ddl_alter_seq) {
2066 if (rel->l)
2067 if ((rel->l = rel_visitor(sql, rel->l, rel_rewriter)) == NULL)
2068 return NULL;
2069 }
2070 return rel;
2071
2072 case op_insert:
2073 case op_update:
2074 case op_delete:
2075 case op_truncate:
2076
2077 case op_join:
2078 case op_left:
2079 case op_right:
2080 case op_full:
2081 case op_semi:
2082 case op_anti:
2083
2084 case op_union:
2085 case op_inter:
2086 case op_except:
2087 if (rel->l)
2088 if ((rel->l = rel_visitor(sql, rel->l, rel_rewriter)) == NULL)
2089 return NULL;
2090 if (rel->r)
2091 if ((rel->r = rel_visitor(sql, rel->r, rel_rewriter)) == NULL)
2092 return NULL;
2093 break;
2094 case op_select:
2095 case op_topn:
2096 case op_sample:
2097 case op_project:
2098 case op_groupby:
2099 if (rel->l)
2100 if ((rel->l = rel_visitor(sql, rel->l, rel_rewriter)) == NULL)
2101 return NULL;
2102 if ((rel->exps = exps_rel_visitor(sql, rel->exps, rel_rewriter)) == NULL)
2103 return NULL;
2104 break;
2105 }
2106 return rel_rewriter(sql, rel);
2107}
2108