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/*#define DEBUG*/
10
11#include "monetdb_config.h"
12#include "rel_unnest.h"
13#include "rel_optimizer.h"
14#include "rel_prop.h"
15#include "rel_rel.h"
16#include "rel_exp.h"
17#include "rel_select.h"
18#include "mal_errors.h" /* for SQLSTATE() */
19
20static void
21exp_set_freevar(mvc *sql, sql_exp *e, sql_rel *r)
22{
23 switch(e->type) {
24 case e_cmp:
25 if (get_cmp(e) == cmp_or || get_cmp(e) == cmp_filter) {
26 exps_set_freevar(sql, e->l, r);
27 exps_set_freevar(sql, e->r, r);
28 } else if (e->flag == cmp_in || e->flag == cmp_notin) {
29 exp_set_freevar(sql, e->l, r);
30 exps_set_freevar(sql, e->r, r);
31 } else {
32 exp_set_freevar(sql, e->l, r);
33 exp_set_freevar(sql, e->r, r);
34 if (e->f)
35 exp_set_freevar(sql, e->f, r);
36 }
37 break;
38 case e_convert:
39 exp_set_freevar(sql, e->l, r);
40 break;
41 case e_func:
42 case e_aggr:
43 if (e->l)
44 exps_set_freevar(sql, e->l, r);
45 break;
46 case e_column:
47 if ((e->l && rel_bind_column2(sql, r, e->l, e->r, 0)) ||
48 (!e->l && rel_bind_column(sql, r, e->r, 0)))
49 return;
50 set_freevar(e, 0);
51 break;
52 case e_atom:
53 case e_psm:
54 break;
55 }
56}
57
58void
59exps_set_freevar(mvc *sql, list *exps, sql_rel *r)
60{
61 node *n;
62
63 if (list_empty(exps))
64 return;
65 for(n = exps->h; n; n = n->next)
66 exp_set_freevar(sql, n->data, r);
67}
68
69static int exps_have_freevar(mvc *sql, list *exps);
70
71/* check if the set is distinct for the set of free variables */
72static int
73is_distinct_set(mvc *sql, sql_rel *rel, list *ad)
74{
75 int distinct = 0;
76 if (ad && exps_unique(sql, rel, ad ))
77 return 1;
78 if (ad && is_groupby(rel->op) && exp_match_list(rel->r, ad))
79 return 1;
80 distinct = need_distinct(rel);
81 if (is_project(rel->op) && rel->l && !distinct)
82 distinct = is_distinct_set(sql, rel->l, ad);
83 return distinct;
84}
85
86int
87exp_has_freevar(mvc *sql, sql_exp *e)
88{
89 if (THRhighwater()) {
90 (void) sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
91 return 0;
92 }
93
94 if (is_freevar(e))
95 return 1;
96 switch(e->type) {
97 case e_cmp:
98 if (get_cmp(e) == cmp_or || get_cmp(e) == cmp_filter) {
99 return (exps_have_freevar(sql, e->l) || exps_have_freevar(sql, e->r));
100 } else if (e->flag == cmp_in || e->flag == cmp_notin) {
101 return (exp_has_freevar(sql, e->l) || exps_have_freevar(sql, e->r));
102 } else {
103 return (exp_has_freevar(sql, e->l) || exp_has_freevar(sql, e->r) ||
104 (e->f && exp_has_freevar(sql, e->f)));
105 }
106 break;
107 case e_convert:
108 return exp_has_freevar(sql, e->l);
109 case e_func:
110 case e_aggr:
111 if (e->l)
112 return exps_have_freevar(sql, e->l);
113 /* fall through */
114 case e_psm:
115 if (exp_is_rel(e))
116 return rel_has_freevar(sql, e->l);
117 break;
118 case e_column:
119 case e_atom:
120 default:
121 return 0;
122 }
123 return 0;
124}
125
126static int
127exps_have_freevar(mvc *sql, list *exps)
128{
129 node *n;
130
131 if (THRhighwater()) {
132 (void) sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
133 return 0;
134 }
135 if (!exps)
136 return 0;
137 for(n = exps->h; n; n = n->next) {
138 sql_exp *e = n->data;
139 if (exp_has_freevar(sql, e))
140 return 1;
141 }
142 return 0;
143}
144
145int
146rel_has_freevar(mvc *sql, sql_rel *rel)
147{
148 if (THRhighwater()) {
149 (void) sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
150 return 0;
151 }
152
153 if (is_basetable(rel->op)) {
154 return 0;
155 } else if (is_base(rel->op)) {
156 return exps_have_freevar(sql, rel->exps) ||
157 (rel->l && rel_has_freevar(sql, rel->l));
158 } else if (is_simple_project(rel->op) || is_groupby(rel->op) || is_select(rel->op) || is_topn(rel->op) || is_sample(rel->op)) {
159 if ((is_simple_project(rel->op) || is_groupby(rel->op)) && rel->r && exps_have_freevar(sql, rel->r))
160 return 1;
161 return exps_have_freevar(sql, rel->exps) ||
162 (rel->l && rel_has_freevar(sql, rel->l));
163 } else if (is_join(rel->op) || is_set(rel->op) || is_semi(rel->op) || is_modify(rel->op)) {
164 return exps_have_freevar(sql, rel->exps) ||
165 rel_has_freevar(sql, rel->l) || rel_has_freevar(sql, rel->r);
166 }
167 return 0;
168}
169
170static list *
171merge_freevar(list *l, list *r)
172{
173 if (!l)
174 return r;
175 if (!r)
176 return l;
177 return list_distinct(list_merge(l, r, (fdup)NULL), (fcmp)exp_equal, (fdup)NULL);
178}
179
180static list * exps_freevar(mvc *sql, list *exps);
181static list * rel_freevar(mvc *sql, sql_rel *rel);
182
183static list *
184exp_freevar(mvc *sql, sql_exp *e)
185{
186 if (THRhighwater())
187 return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
188
189 switch(e->type) {
190 case e_column:
191 if (e->freevar)
192 return append(sa_list(sql->sa), e);
193 break;
194 case e_convert:
195 return exp_freevar(sql, e->l);
196 case e_aggr:
197 case e_func:
198 if (e->l)
199 return exps_freevar(sql, e->l);
200 break;
201 case e_cmp:
202 if (get_cmp(e) == cmp_or || get_cmp(e) == cmp_filter) {
203 list *l = exps_freevar(sql, e->l);
204 list *r = exps_freevar(sql, e->r);
205 return merge_freevar(l, r);
206 } else if (e->flag == cmp_in || e->flag == cmp_notin) {
207 list *l = exp_freevar(sql, e->l);
208 list *r = exps_freevar(sql, e->r);
209 return merge_freevar(l, r);
210 } else {
211 list *l = exp_freevar(sql, e->l);
212 list *r = exp_freevar(sql, e->r);
213 l = merge_freevar(l, r);
214 if (e->f) {
215 r = exp_freevar(sql, e->f);
216 return merge_freevar(l, r);
217 }
218 return l;
219 }
220 break;
221 case e_psm:
222 if (exp_is_rel(e))
223 if (rel_has_freevar(sql, e->l))
224 return rel_freevar(sql, e->l);
225 return NULL;
226 case e_atom:
227 default:
228 return NULL;
229 }
230 return NULL;
231}
232
233static list *
234exps_freevar(mvc *sql, list *exps)
235{
236 node *n;
237 list *c = NULL;
238
239 if (THRhighwater())
240 return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
241 if (!exps)
242 return NULL;
243 for (n = exps->h; n; n = n->next) {
244 sql_exp *e = n->data;
245 list *var = exp_freevar(sql, e);
246
247 c = merge_freevar(c,var);
248 }
249 return c;
250}
251
252static list *
253rel_freevar(mvc *sql, sql_rel *rel)
254{
255 list *lexps = NULL, *rexps = NULL, *exps = NULL;
256
257 if (THRhighwater())
258 return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
259 if (!rel)
260 return NULL;
261 switch(rel->op) {
262 case op_join:
263 case op_left:
264 case op_right:
265 case op_full:
266 exps = exps_freevar(sql, rel->exps);
267 lexps = rel_freevar(sql, rel->l);
268 rexps = rel_freevar(sql, rel->r);
269 lexps = merge_freevar(lexps, rexps);
270 exps = merge_freevar(exps, lexps);
271 return exps;
272
273 case op_basetable:
274 return NULL;
275 case op_table: {
276 sql_exp *call = rel->r;
277 if (rel->flag != 2 && rel->l)
278 lexps = rel_freevar(sql, rel->l);
279 exps = (rel->flag != 2 && call)?exps_freevar(sql, call->l):NULL;
280 return merge_freevar(exps, lexps);
281 }
282 case op_union:
283 case op_except:
284 case op_inter:
285 exps = exps_freevar(sql, rel->exps);
286 lexps = rel_freevar(sql, rel->l);
287 rexps = rel_freevar(sql, rel->r);
288 lexps = merge_freevar(lexps, rexps);
289 exps = merge_freevar(exps, lexps);
290 return exps;
291 case op_ddl:
292 case op_semi:
293 case op_anti:
294
295 case op_select:
296 case op_topn:
297 case op_sample:
298
299 case op_groupby:
300 case op_project:
301 exps = exps_freevar(sql, rel->exps);
302 lexps = rel_freevar(sql, rel->l);
303 if (rel->r) {
304 if (is_groupby(rel->op))
305 rexps = exps_freevar(sql, rel->r);
306 else
307 rexps = rel_freevar(sql, rel->r);
308 lexps = merge_freevar(lexps, rexps);
309 }
310 exps = merge_freevar(exps, lexps);
311 return exps;
312 default:
313 return NULL;
314 }
315
316}
317
318static list *
319rel_dependent_var(mvc *sql, sql_rel *l, sql_rel *r)
320{
321 list *res = NULL;
322
323 if (rel_has_freevar(sql, r)){
324 list *freevar = rel_freevar(sql, r);
325 if (freevar) {
326 node *n;
327 list *boundvar = rel_projections(sql, l, NULL, 1, 0);
328
329 for(n = freevar->h; n; n = n->next) {
330 sql_exp *e = n->data, *ne = NULL;
331 /* each freevar should be an e_column */
332 if (e->l) {
333 ne = exps_bind_column2(boundvar, e->l, e->r );
334 } else {
335 ne = exps_bind_column(boundvar, e->r, NULL);
336 }
337 if (ne) {
338 if (!res)
339 res = sa_list(sql->sa);
340 append(res, ne);
341 }
342 }
343 }
344 }
345 return res;
346}
347
348/*
349 * try to bind any freevar in the expression e
350 */
351static void
352rel_bind_var(mvc *sql, sql_rel *rel, sql_exp *e)
353{
354 list *fvs = exp_freevar(sql, e);
355
356 if (fvs) {
357 node *n;
358
359 for(n = fvs->h; n; n=n->next) {
360 sql_exp *e = n->data;
361
362 if (e->freevar && (exp_is_atom(e) || rel_find_exp(rel,e)))
363 reset_freevar(e);
364 }
365 }
366}
367
368static sql_exp * push_up_project_exp(mvc *sql, sql_rel *rel, sql_exp *e);
369
370static list *
371push_up_project_exps(mvc *sql, sql_rel *rel, list *exps)
372{
373 node *n;
374
375 if (!exps)
376 return exps;
377
378 for(n=exps->h; n; n=n->next) {
379 sql_exp *e = n->data;
380
381 n->data = push_up_project_exp(sql, rel, e);
382 }
383 list_hash_clear(exps);
384 return exps;
385}
386
387static sql_exp *
388push_up_project_exp(mvc *sql, sql_rel *rel, sql_exp *e)
389{
390 if (THRhighwater())
391 return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
392
393 switch(e->type) {
394 case e_cmp:
395 if (get_cmp(e) == cmp_or || get_cmp(e) == cmp_filter) {
396 e->l = push_up_project_exps(sql, rel, e->l);
397 e->r = push_up_project_exps(sql, rel, e->r);
398 return e;
399 } else if (e->flag == cmp_in || e->flag == cmp_notin) {
400 e->l = push_up_project_exp(sql, rel, e->l);
401 e->r = push_up_project_exps(sql, rel, e->r);
402 return e;
403 } else {
404 e->l = push_up_project_exp(sql, rel, e->l);
405 e->r = push_up_project_exp(sql, rel, e->r);
406 if (e->f)
407 e->f = push_up_project_exp(sql, rel, e->f);
408 }
409 break;
410 case e_convert:
411 e->l = push_up_project_exp(sql, rel, e->l);
412 break;
413 case e_func:
414 case e_aggr:
415 if (e->l)
416 e->l = push_up_project_exps(sql, rel, e->l);
417 break;
418 case e_column:
419 {
420 sql_exp *ne;
421
422 /* include project or just lookup */
423 if (e->l) {
424 ne = exps_bind_column2(rel->exps, e->l, e->r );
425 } else {
426 ne = exps_bind_column(rel->exps, e->r, NULL);
427 }
428 if (ne) {
429 if (ne->type == e_column) {
430 /* deref alias */
431 e->l = ne->l;
432 e->r = ne->r;
433 } else {
434 return push_up_project_exp(sql, rel, ne);
435 }
436 }
437 } break;
438 case e_atom:
439 case e_psm:
440 break;
441 }
442 return e;
443}
444
445static sql_exp *exp_rewrite(mvc *sql, sql_rel *rel, sql_exp *e, list *ad);
446
447static list *
448exps_rewrite(mvc *sql, sql_rel *rel, list *exps, list *ad)
449{
450 list *nexps;
451 node *n;
452
453 if (list_empty(exps))
454 return exps;
455 nexps = sa_list(sql->sa);
456 for(n=exps->h; n; n = n->next)
457 append(nexps, exp_rewrite(sql, rel, n->data, ad));
458 return nexps;
459}
460
461/* recursively rewrite some functions */
462static sql_exp *
463exp_rewrite(mvc *sql, sql_rel *rel, sql_exp *e, list *ad)
464{
465 sql_subfunc *sf;
466
467 if (e->type == e_convert) {
468 e->l = exp_rewrite(sql, rel, e->l, ad);
469 return e;
470 }
471 if (e->type != e_func)
472 return e;
473 e->l = exps_rewrite(sql, rel, e->l, ad);
474 sf = e->f;
475 /* window functions need to be run per freevars */
476 if (sf->func->type == F_ANALYTIC && list_length(sf->func->ops) > 2) {
477 sql_subtype *bt = sql_bind_localtype("bit");
478 node *d;
479 list *rankopargs = e->l;
480 /* window_bound has partition/orderby as first argument (before normal expressions), others as second (and have a boolean placeholder) */
481 int is_wb = (strcmp(sf->func->base.name, "window_bound") == 0);
482 node *n = (is_wb)?rankopargs->h:rankopargs->h->next;
483 sql_exp *pe = n->data;
484
485 /* if pe is window_bound function skip */
486 if (pe->type == e_func) {
487 sf = pe->f;
488 if (strcmp(sf->func->base.name, "window_bound") == 0)
489 return e;
490 }
491 /* find partition expression in rankfunc */
492 /* diff function */
493 if (exp_is_atom(pe) || (is_wb && (pe->type != e_func || strcmp(sf->func->base.name, "diff") != 0)))
494 pe = NULL;
495 else
496 is_wb = 0;
497 for(d=ad->h; d; d=d->next) {
498 sql_subfunc *df;
499 sql_exp *e = d->data;
500 list *args = sa_list(sql->sa);
501 if (pe) {
502 df = sql_bind_func(sql->sa, NULL, "diff", bt, exp_subtype(e), F_ANALYTIC);
503 append(args, pe);
504 } else {
505 df = sql_bind_func(sql->sa, NULL, "diff", exp_subtype(e), NULL, F_ANALYTIC);
506 }
507 assert(df);
508 append(args, e);
509 pe = exp_op(sql->sa, args, df);
510 }
511 if (is_wb)
512 e->l = list_prepend(rankopargs, pe);
513 else
514 n->data = pe;
515 }
516 return e;
517}
518
519static sql_exp *
520rel_reduce2one_exp(mvc *sql, sql_rel *sq)
521{
522 sql_exp *e = NULL;
523
524 if (list_empty(sq->exps))
525 return NULL;
526 if (list_length(sq->exps) == 1)
527 return sq->exps->t->data;
528 for(node *n = sq->exps->h; n && !e; n = n->next) {
529 sql_exp *t = n->data;
530
531 if (!is_freevar(t))
532 e = t;
533 }
534 if (!e)
535 e = sq->exps->t->data;
536 sq->exps = append(sa_list(sql->sa), e);
537 return e;
538}
539
540static sql_exp *
541rel_bound_exp(mvc *sql, sql_rel *rel )
542{
543 while (rel->l) {
544 rel = rel->l;
545 if (is_base(rel->op) || is_project(rel->op))
546 break;
547 }
548
549 if (rel) {
550 node *n;
551 for(n = rel->exps->h; n; n = n->next){
552 sql_exp *e = n->data;
553
554 if (exp_is_atom(e))
555 return e;
556 if (!is_freevar(e))
557 return exp_ref(sql->sa, e);
558 }
559 }
560 if (rel && is_project(rel->op)) /* add dummy expression */
561 return rel_project_add_exp(sql, rel, exp_atom_bool(sql->sa, 1));
562 return NULL;
563}
564
565/*
566 * join j was just rewriten, but some join expressions may now
567 * be too low in de relation rel. These need to move up.
568 * */
569static void
570move_join_exps(mvc *sql, sql_rel *j, sql_rel *rel)
571{
572 node *n;
573 list *exps = rel->exps;
574
575 if (!exps)
576 return;
577 rel->exps = sa_list(sql->sa);
578 if (!j->exps)
579 j->exps = sa_list(sql->sa);
580 for(n = exps->h; n; n = n->next){
581 sql_exp *e = n->data;
582
583 if (rel_find_exp(rel, e)) {
584 if (exp_has_freevar(sql, e))
585 rel_bind_var(sql, rel->l, e);
586 append(rel->exps, e);
587 } else {
588 if (exp_has_freevar(sql, e))
589 rel_bind_var(sql, j->l, e);
590 append(j->exps, e);
591 }
592 }
593}
594
595static sql_rel *
596rel_general_unnest(mvc *sql, sql_rel *rel, list *ad)
597{
598 /* current unnest only possible for equality joins, <, <> etc needs more work */
599 if (rel && (is_join(rel->op) || is_semi(rel->op)) && is_dependent(rel) && ad) {
600 list *fd;
601 node *n, *m;
602 int nr;
603
604 sql_rel *l = rel->l, *r = rel->r, *inner_r;
605 /* rewrite T1 dependent join T2 -> T1 join D dependent join T2, where the T1/D join adds (equality) predicates (for the Domain (ad)) and D is are the distinct(projected(ad) from T1) */
606 sql_rel *D = rel_project(sql->sa, rel_dup(l), exps_copy(sql, ad));
607 set_distinct(D);
608
609 r = rel_crossproduct(sql->sa, D, r, rel->op);
610 r->op = /*is_semi(rel->op)?op_left:*/op_join;
611 move_join_exps(sql, rel, r);
612 set_dependent(r);
613 inner_r = r;
614 r = rel_project(sql->sa, r, (is_semi(inner_r->op))?sa_list(sql->sa):rel_projections(sql, r->r, NULL, 1, 1));
615
616 if (!is_semi(inner_r->op)) { /* skip the free vars */
617 list *exps = sa_list(sql->sa);
618
619 for(node *n=r->exps->h; n; n = n->next) {
620 sql_exp *e = n->data, *ne = NULL;
621
622 if (e->l) {
623 ne = exps_bind_column2(ad, e->l, e->r );
624 } else {
625 ne = exps_bind_column(ad, e->r, NULL);
626 }
627 if (!ne)
628 append(exps,e);
629 }
630 r->exps = exps;
631 }
632
633 /* append ad + rename */
634 nr = sql->label+1;
635 sql->label += list_length(ad);
636 fd = exps_label(sql->sa, exps_copy(sql, ad), nr);
637 for (n = ad->h, m = fd->h; n && m; n = n->next, m = m->next) {
638 sql_exp *l = n->data, *r = m->data, *e;
639
640 l = exp_ref(sql->sa, l);
641 r = exp_ref(sql->sa, r);
642 e = exp_compare(sql->sa, l, r, (is_outerjoin(rel->op)|is_semi(rel->op))?cmp_equal_nil:cmp_equal);
643 if (!rel->exps)
644 rel->exps = sa_list(sql->sa);
645 append(rel->exps, e);
646 }
647 list_merge(r->exps, fd, (fdup)NULL);
648 rel->r = r;
649 reset_dependent(rel);
650 return rel;
651 }
652 return rel;
653}
654
655static sql_rel *
656push_up_project(mvc *sql, sql_rel *rel, list *ad)
657{
658 /* input rel is dependent outerjoin with on the right a project, we first try to push inner side expressions down (because these cannot be pushed up) */
659 if (rel && is_outerjoin(rel->op) && is_dependent(rel)) {
660 sql_rel *r = rel->r;
661
662 assert(!rel_is_ref(r));
663 /* find constant expressions and move these down */
664 if (r && r->op == op_project) {
665 node *n;
666 list *nexps = NULL;
667 list *cexps = NULL;
668 sql_rel *l = r->l;
669
670 if (l && is_select(l->op)) {
671 for(n=r->exps->h; n; n=n->next) {
672 sql_exp *e = n->data;
673
674 if (exp_is_atom(e) || rel_find_exp(l,e)) { /* move down */
675 if (!cexps)
676 cexps = sa_list(sql->sa);
677 append(cexps, e);
678 } else {
679 if (!nexps)
680 nexps = sa_list(sql->sa);
681 append(nexps, e);
682 }
683 }
684 if (cexps) {
685 sql_rel *p = l->l = rel_project( sql->sa, l->l,
686 rel_projections(sql, l->l, NULL, 1, 1));
687 p->exps = list_merge(p->exps, cexps, (fdup)NULL);
688 if (list_empty(nexps)) {
689 rel->r = l; /* remove empty project */
690 } else {
691 for (n = cexps->h; n; n = n->next) { /* add pushed down renamed expressions */
692 sql_exp *e = n->data;
693 append(nexps, exp_ref(sql->sa, e));
694 }
695 r->exps = nexps;
696 }
697 }
698 }
699 }
700 }
701 /* input rel is dependent join with on the right a project */
702 if (rel && is_join(rel->op) && is_dependent(rel)) {
703 sql_rel *r = rel->r;
704
705 assert(!rel_is_ref(r));
706 if (r && r->op == op_project /*&& r->l*/) {
707 sql_exp *id = NULL;
708 node *m;
709 /* move project up, ie all attributes of left + the old expression list */
710 sql_rel *n = rel_project( sql->sa, (r->l)?rel:rel->l,
711 rel_projections(sql, rel->l, NULL, 1, 1));
712
713 /* only pass bound variables */
714 if (is_left(rel->op) && exps_have_freevar(sql, r->exps)) {
715 id = rel_bound_exp(sql, r);
716 id = rel_project_add_exp(sql, n, id);
717 }
718 for (m=r->exps->h; m; m = m->next) {
719 sql_exp *e = m->data;
720
721 if (!e->freevar || exp_name(e)) { /* only skip full freevars */
722 if (exp_has_freevar(sql, e)) {
723 rel_bind_var(sql, rel->l, e);
724 if (is_left(rel->op)) { /* add ifthenelse */
725 /* need bound var from r */
726 /* if id is NULL then NULL else e */
727 sql_exp *ne = rel_unop_(sql, NULL, exp_copy(sql, id), NULL, "isnull", card_value);
728 set_has_no_nil(ne);
729 ne = rel_nop_(sql, NULL, ne, exp_null(sql->sa, exp_subtype(e)), e, NULL, NULL, "ifthenelse", card_value);
730 exp_prop_alias(sql->sa, ne, e);
731 e = ne;
732 }
733 }
734 }
735 if (r->l)
736 e = exp_rewrite(sql, r->l, e, ad);
737 append(n->exps, e);
738 }
739 if (r->r) {
740 list *exps = r->r, *oexps = n->r = sa_list(sql->sa);
741
742 for (m=exps->h; m; m = m->next) {
743 sql_exp *e = m->data;
744
745 if (!e->freevar || exp_name(e)) { /* only skip full freevars */
746 if (exp_has_freevar(sql, e))
747 rel_bind_var(sql, rel->l, e);
748 }
749 append(oexps, e);
750 }
751 }
752 /* remove old project */
753 rel->r = r->l;
754 r->l = NULL;
755 rel_destroy(r);
756 r = rel->r;
757 return n;
758 /*
759 } else if (r && r->op == op_project && !r->l) {
760 sql_rel *l = rel->l;
761
762 rel->l = NULL;
763 rel_destroy(rel);
764 return l;
765 */
766 }
767 }
768 /* a dependent semi/anti join with a project on the right side, could be removed */
769 if (rel && is_semi(rel->op) && is_dependent(rel)) {
770 sql_rel *r = rel->r;
771
772 assert(!rel_is_ref(r));
773 /* merge project expressions into the join expressions */
774 rel->exps = push_up_project_exps(sql, r, rel->exps);
775
776 if (r && r->op == op_project && r->l) {
777 /* remove old project */
778 rel->r = r->l;
779 r->l = NULL;
780 rel_destroy(r);
781 return rel;
782 } else if (r && r->op == op_project) {
783 /* remove freevars from projection */
784 list *exps = r->exps, *nexps = sa_list(sql->sa);
785 node *m;
786
787 for (m=exps->h; m; m = m->next) {
788 sql_exp *e = m->data;
789
790 if (!exp_has_freevar(sql, e))
791 append(nexps, e);
792 }
793 if (list_empty(nexps)) {
794 /* remove old project and change outer into select */
795 rel->r = r->l;
796 r->l = NULL;
797 rel_destroy(r);
798 rel->op = op_select;
799 return rel;
800 }
801 r->exps = nexps;
802 }
803 }
804 return rel;
805}
806
807static sql_rel *
808push_up_topn(mvc *sql, sql_rel *rel)
809{
810 /* a dependent semi/anti join with a project on the right side, could be removed */
811 if (rel && (is_semi(rel->op) || is_join(rel->op)) && is_dependent(rel)) {
812 sql_rel *r = rel->r;
813
814 if (r && r->op == op_topn) {
815 /* remove old topn */
816 rel->r = r->l;
817 rel = rel_topn(sql->sa, rel, r->exps);
818 r->l = NULL;
819 rel_destroy(r);
820 return rel;
821 }
822 }
823 return rel;
824}
825
826static sql_rel *
827push_up_select(mvc *sql, sql_rel *rel, list *ad)
828{
829 sql_rel *d = rel->l;
830 sql_rel *r = rel->r;
831 int inner = 0;
832
833 if (rel && is_dependent(rel) && r && r->op == op_select) {
834 sql_rel *rl = r->l;
835
836 if (rl && rel_has_freevar(sql, rl)) {
837 list *inner_ad = rel_dependent_var(sql, d, rl);
838
839 inner = !list_empty(inner_ad);
840 }
841 }
842 if (inner && is_left(rel->op) && !need_distinct(d))
843 return rel_general_unnest(sql, rel, ad);
844 /* input rel is dependent join with on the right a select */
845 if ((!inner || is_semi(rel->op)) && rel && is_dependent(rel)) {
846 sql_rel *r = rel->r;
847
848 if (r && r->op == op_select) { /* move into join */
849 node *n;
850
851 for (n=r->exps->h; n; n = n->next) {
852 sql_exp *e = n->data;
853
854 e = exp_copy(sql, e);
855 if (exp_has_freevar(sql, e))
856 rel_bind_var(sql, rel->l, e);
857 rel_join_add_exp(sql->sa, rel, e);
858 }
859 /* remove select */
860 rel->r = rel_dup(r->l);
861 rel_destroy(r);
862 if (!inner)
863 reset_dependent(rel);
864 }
865 } else if (rel && is_join(rel->op) && is_dependent(rel)) {
866 sql_rel *r = rel->r;
867 list *exps = r->exps;
868
869 /* remove select */
870 rel->r = rel_dup(r->l);
871 rel_destroy(r);
872 rel = rel_select(sql->sa, rel, NULL);
873 rel->exps = exps;
874 }
875 return rel;
876}
877
878static int
879exps_is_constant( list *exps )
880{
881 sql_exp *e;
882
883 if (!exps || list_empty(exps))
884 return 1;
885 if (list_length(exps) > 1)
886 return 0;
887 e = exps->h->data;
888 return exp_is_atom(e);
889}
890
891static int
892exp_is_count(sql_exp *e, sql_rel *rel)
893{
894 if (!e || !rel)
895 return 0;
896 if (is_alias(e->type) && is_project(rel->op)) {
897 sql_exp *ne = rel_find_exp(rel->l, e);
898 return exp_is_count(ne, rel->l);
899 }
900 if (is_convert(e->type))
901 return exp_is_count(e->l, rel);
902 if (is_aggr(e->type) && exp_aggr_is_count(e))
903 return 1;
904 return 0;
905}
906
907static sql_rel *
908push_up_groupby(mvc *sql, sql_rel *rel, list *ad)
909{
910 /* input rel is dependent join with on the right a groupby */
911 if (rel && (is_join(rel->op) || is_semi(rel->op)) && is_dependent(rel)) {
912 sql_rel *l = rel->l, *r = rel->r;
913
914 /* left of rel should be a set */
915 if (l && is_distinct_set(sql, l, ad) && r && r->op == op_groupby) {
916 list *sexps, *jexps, *a = rel_projections(sql, rel->l, NULL, 1, 1);
917 node *n;
918 sql_exp *id = NULL;
919
920 /* move groupby up, ie add attributes of left + the old expression list */
921
922 if (l && list_length(a) > 1 && !need_distinct(l)) { /* add identity call only if there's more than one column in the groupby */
923 rel->l = rel_add_identity(sql, l, &id); /* add identity call for group by */
924 assert(id);
925 }
926
927 assert(rel->op != op_anti);
928 if (rel->op == op_semi && !need_distinct(l))
929 rel->op = op_join;
930
931 for (n = r->exps->h; n; n = n->next ) {
932 sql_exp *e = n->data;
933
934 /* count_nil(* or constant) -> count(t.TID) */
935 if (exp_is_count(e, r) && (!e->l || exps_is_constant(e->l))) {
936 sql_exp *col;
937 sql_rel *p = r->l; /* ugh */
938
939 if (!is_project(p->op))
940 r->l = p = rel_project(sql->sa, p, rel_projections(sql, p, NULL, 1, 1));
941 col = p->exps->t->data;
942 if (strcmp(exp_name(col), TID) != 0) {
943 col = exp_ref(sql->sa, col);
944 col = exp_unop(sql->sa, col, sql_bind_func(sql->sa, NULL, "identity", exp_subtype(col), NULL, F_FUNC));
945 col = exp_label(sql->sa, col, ++sql->label);
946 append(p->exps, col);
947 }
948 col = exp_ref(sql->sa, col);
949 append(e->l=sa_list(sql->sa), col);
950 set_no_nil(e);
951 }
952 if (exp_has_freevar(sql, e))
953 rel_bind_var(sql, rel->l, e);
954 }
955 r->exps = list_merge(r->exps, a, (fdup)NULL);
956 if (!r->r) {
957 if (id)
958 r->r = list_append(sa_list(sql->sa), exp_ref(sql->sa, id));
959 else
960 r->r = exps_copy(sql, a);
961 } else {
962 if (id)
963 list_append(r->r, exp_ref(sql->sa, id));
964 else
965 r->r = list_distinct(list_merge(r->r, exps_copy(sql, a), (fdup)NULL), (fcmp)exp_equal, (fdup)NULL);
966 }
967
968 if (!r->l) {
969 r->l = rel->l;
970 rel->l = NULL;
971 rel->r = NULL;
972 rel_destroy(rel);
973 /* merge (distinct) projects / group by (over the same group by cols) */
974 while (r->l && exps_have_freevar(sql, r->exps)) {
975 sql_rel *l = r->l;
976
977 if (!is_project(l->op))
978 break;
979 if (l->op == op_project && need_distinct(l)) { /* TODO: check if group by exps and distinct list are equal */
980 r->l = rel_dup(l->l);
981 rel_destroy(l);
982 }
983 if (l->op == op_groupby) { /* TODO: check if group by exps and distinct list are equal */
984 /* add aggr exps of r too l, replace r by l */
985 node *n;
986 for(n = r->exps->h; n; n = n->next) {
987 sql_exp *e = n->data;
988
989 if (e->type == e_aggr)
990 append(l->exps, e);
991 if (exp_has_freevar(sql, e))
992 rel_bind_var(sql, l, e);
993 }
994 r->l = NULL;
995 rel_destroy(r);
996 r = l;
997 }
998 }
999 return r;
1000 } else {
1001 rel->r = r->l;
1002 r->l = rel;
1003 }
1004 /* check if a join expression needs to be moved above the group by (into a select) */
1005 sexps = sa_list(sql->sa);
1006 jexps = sa_list(sql->sa);
1007 if (rel->exps) {
1008 for (n = rel->exps->h; n; n = n->next ) {
1009 sql_exp *e = n->data;
1010
1011 if (rel_find_exp(rel, e)) {
1012 append(jexps, e);
1013 } else {
1014 append(sexps, e);
1015 }
1016 }
1017 }
1018 rel->exps = jexps;
1019 if (list_length(sexps)) {
1020 r = rel_select(sql->sa, r, NULL);
1021 r->exps = sexps;
1022 }
1023 return r;
1024 }
1025 }
1026 return rel;
1027}
1028
1029static sql_rel *
1030push_up_select_l(mvc *sql, sql_rel *rel)
1031{
1032 (void)sql;
1033 /* input rel is dependent join with on the right a project */
1034 if (rel && (is_join(rel->op) || is_semi(rel->op))) {
1035 sql_rel *l = rel->l;
1036
1037 if (is_select(l->op) && rel_has_freevar(sql, l) && !rel_is_ref(l) ) {
1038 /* push up select (above join) */
1039 rel->l = l->l;
1040 l->l = rel;
1041 return l;
1042 }
1043 }
1044 return rel;
1045}
1046
1047static sql_rel *
1048push_up_join(mvc *sql, sql_rel *rel, list *ad)
1049{
1050 /* input rel is dependent join with on the right a project */
1051 if (rel && (is_join(rel->op) || is_semi(rel->op)) && is_dependent(rel)) {
1052 sql_rel *d = rel->l, *j = rel->r;
1053
1054 /* left of rel should be a set */
1055 if (d && is_distinct_set(sql, d, ad) && j && (is_join(j->op) || is_semi(j->op))) {
1056 int crossproduct = 0;
1057 sql_rel *jl = j->l, *jr = j->r;
1058 /* op_join if F(jl) intersect A(D) = empty -> jl join (D djoin jr)
1059 * F(jr) intersect A(D) = empty -> (D djoin jl) join jr
1060 * else (D djoin jl) natural join (D djoin jr)
1061 *
1062 * */
1063 list *rd = NULL, *ld = NULL;
1064
1065 if (is_semi(j->op) && is_select(jl->op) && rel_has_freevar(sql, jl) && !rel_is_ref(jl)) {
1066 rel->r = j = push_up_select_l(sql, j);
1067 return rel; /* ie try again */
1068 }
1069 crossproduct = list_empty(j->exps);
1070 rd = (j->op != op_full)?rel_dependent_var(sql, d, jr):(list*)1;
1071 ld = (((j->op == op_join && rd) || j->op == op_right))?rel_dependent_var(sql, d, jl):(list*)1;
1072
1073 if (ld && rd) {
1074 node *m;
1075 sql_rel *n, *nr;
1076
1077 rel->r = jl;
1078 j->l = rel_dup(d);
1079 j->r = jr;
1080 set_dependent(j);
1081 n = rel_crossproduct(sql->sa, rel, j, j->op);
1082 j->op = rel->op;
1083 if (is_semi(n->op))
1084 j->op = op_left;
1085 n->l = rel_project(sql->sa, n->l, rel_projections(sql, n->l, NULL, 1, 1));
1086 nr = n->r;
1087 nr = n->r = rel_project(sql->sa, n->r, rel_projections(sql, nr->r, NULL, 1, 1));
1088 move_join_exps(sql, n, j);
1089 /* add nr->l exps with labels */
1090 /* create jexps */
1091 if (!n->exps)
1092 n->exps = sa_list(sql->sa);
1093 for (m = d->exps->h; m; m = m->next) {
1094 sql_exp *e = m->data, *pe, *je;
1095
1096 pe = exp_ref(sql->sa, e);
1097 pe = exp_label(sql->sa, pe, ++sql->label);
1098 append(nr->exps, pe);
1099 pe = exp_ref(sql->sa, pe);
1100 e = exp_ref(sql->sa, e);
1101 je = exp_compare(sql->sa, e, pe, cmp_equal_nil);
1102 append(n->exps, je);
1103 }
1104 return n;
1105 }
1106
1107 if (!rd) {
1108 rel->r = jl;
1109 j->l = rel;
1110 j->r = jr;
1111 move_join_exps(sql, j, rel);
1112 return j;
1113 }
1114 if (!ld && is_left(rel->op) && crossproduct) {
1115 sql_exp *l = exp_atom_int(sql->sa, 1);
1116 sql_exp *r = exp_atom_int(sql->sa, 1);
1117 rel->r = jr;
1118 j->l = rel;
1119 j->r = jl;
1120
1121 if (!is_simple_project(jr->op))
1122 rel->r = jr = rel_project(sql->sa, jr, rel_projections(sql, jr, NULL, 1, 1));
1123 if (!is_simple_project(jl->op))
1124 j->r = jl = rel_project(sql->sa, jl, rel_projections(sql, jl, NULL, 1, 1));
1125 l = exp_label(sql->sa, l, ++sql->label);
1126 r = exp_label(sql->sa, r, ++sql->label);
1127 append(jl->exps, l);
1128 append(jr->exps, r);
1129 l = exp_ref(sql->sa, l);
1130 r = exp_ref(sql->sa, r);
1131 l = exp_compare(sql->sa, r, l, cmp_equal_nil);
1132 j->op = rel->op;
1133 move_join_exps(sql, j, rel);
1134 if (!j->exps)
1135 j->exps = sa_list(sql->sa);
1136 append(j->exps, l);
1137 return j;
1138 } else if (!ld) {
1139 rel->r = jr;
1140 j->l = jl;
1141 j->r = rel;
1142 move_join_exps(sql, j, rel);
1143 return j;
1144 }
1145 assert(0);
1146 return rel;
1147 }
1148 }
1149 return rel;
1150}
1151
1152static sql_rel *
1153push_up_set(mvc *sql, sql_rel *rel, list *ad)
1154{
1155 if (rel && (is_join(rel->op) || is_semi(rel->op)) && is_dependent(rel)) {
1156 sql_rel *d = rel->l, *s = rel->r;
1157
1158 /* left of rel should be a set */
1159 if (d && is_distinct_set(sql, d, ad) && s && is_set(s->op)) {
1160 list *sexps;
1161 node *m;
1162 sql_rel *sl = s->l, *sr = s->r, *n;
1163
1164 /* D djoin (sl setop sr) -> (D djoin sl) setop (D djoin sr) */
1165 rel->r = sl;
1166 n = rel_crossproduct(sql->sa, rel_dup(d), sr, rel->op);
1167 set_dependent(n);
1168 s->l = rel;
1169 s->r = n;
1170 sexps = sa_list(sql->sa);
1171 for (m = d->exps->h; m; m = m->next) {
1172 sql_exp *e = m->data, *pe;
1173
1174 pe = exp_ref(sql->sa, e);
1175 append(sexps, pe);
1176 }
1177 s->exps = list_merge(sexps, s->exps, (fdup)NULL);
1178 /* add projections to inner parts of the union */
1179 s->l = rel_project(sql->sa, s->l, rel_projections(sql, s->l, NULL, 1, 1));
1180 s->r = rel_project(sql->sa, s->r, rel_projections(sql, s->r, NULL, 1, 1));
1181 return s;
1182 }
1183 }
1184 return rel;
1185}
1186
1187static sql_rel *
1188push_up_table(mvc *sql, sql_rel *rel, list *ad)
1189{
1190 (void)sql;
1191 if (rel && (is_join(rel->op) || is_semi(rel->op)) && is_dependent(rel)) {
1192 sql_rel *d = rel->l, *tf = rel->r;
1193
1194 /* for now just push d into function */
1195 if (d && is_distinct_set(sql, d, ad) && tf && is_base(tf->op)) {
1196 if (tf->l) {
1197 sql_rel *l = tf->l;
1198
1199 assert(!l->l);
1200 l->l = rel_dup(d);
1201 } else {
1202 tf->l = rel_dup(d);
1203 }
1204 return rel;
1205 }
1206 }
1207 return rel;
1208}
1209
1210/* reintroduce selects, for freevar's of other dependent joins */
1211static sql_rel *
1212push_down_select(mvc *sql, sql_rel *rel)
1213{
1214 if (!list_empty(rel->exps)) {
1215 node *n;
1216 list *jexps = sa_list(sql->sa);
1217 list *sexps = sa_list(sql->sa);
1218 sql_rel *d = rel->l;
1219
1220 for(n=rel->exps->h; n; n=n->next) {
1221 sql_exp *e = n->data;
1222 list *v = exp_freevar(sql, e);
1223 int found = 1;
1224
1225 if (v) {
1226 node *m;
1227 for(m=v->h; m && found; m=m->next) {
1228 sql_exp *fv = m->data;
1229
1230 found = (rel_find_exp(d, fv) != NULL);
1231 }
1232 }
1233 if (found) {
1234 append(jexps, e);
1235 } else {
1236 append(sexps, e);
1237 }
1238 }
1239 if (!list_empty(sexps)) {
1240 sql_rel *r;
1241
1242 rel->exps = jexps;
1243 r = rel->r = rel_select(sql->sa, rel->r, NULL);
1244 r->exps = sexps;
1245 }
1246 }
1247 return rel;
1248}
1249
1250static sql_rel *
1251rel_unnest_dependent(mvc *sql, sql_rel *rel)
1252{
1253 sql_rel *nrel = rel;
1254
1255 if (THRhighwater())
1256 return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
1257
1258 /* current unnest only possible for equality joins, <, <> etc needs more work */
1259 if (rel && (is_join(rel->op) || is_semi(rel->op)) && is_dependent(rel)) {
1260 /* howto find out the left is a set */
1261 sql_rel *l, *r;
1262
1263 l = rel->l;
1264 r = rel->r;
1265
1266 if (rel_has_freevar(sql, l))
1267 rel->l = rel_unnest_dependent(sql, rel->l);
1268
1269 if (!rel_has_freevar(sql, r)) {
1270 reset_dependent(rel);
1271 /* reintroduce selects, for freevar's of other dependent joins */
1272 return push_down_select(sql, rel);
1273 }
1274
1275 /* try to push dependent join down */
1276 if (rel_has_freevar(sql, r)) {
1277 list *ad = rel_dependent_var(sql, rel->l, rel->r);
1278
1279 if (r && is_simple_project(r->op) && (!exps_have_freevar(sql, r->exps) || is_distinct_set(sql, l, ad))) {
1280 rel = push_up_project(sql, rel, ad);
1281 return rel_unnest_dependent(sql, rel);
1282 }
1283
1284 if (r && is_topn(r->op)) {
1285 rel = push_up_topn(sql, rel);
1286 return rel_unnest_dependent(sql, rel);
1287 }
1288
1289 if (r && is_select(r->op) && ad) {
1290 rel = push_up_select(sql, rel, ad);
1291 return rel_unnest_dependent(sql, rel);
1292 }
1293
1294 if (r && is_groupby(r->op) && need_distinct(l) /*&& is_distinct_set(sql, l, ad)*/) {
1295 rel = push_up_groupby(sql, rel, ad);
1296 return rel_unnest_dependent(sql, rel);
1297 }
1298
1299 if (r && (is_join(r->op) || is_semi(r->op)) && is_distinct_set(sql, l, ad)) {
1300 rel = push_up_join(sql, rel, ad);
1301 return rel_unnest_dependent(sql, rel);
1302 }
1303
1304 if (r && is_set(r->op) && (!is_left(rel->op) && is_distinct_set(sql, l, ad))) {
1305 rel = push_up_set(sql, rel, ad);
1306 return rel_unnest_dependent(sql, rel);
1307 }
1308
1309 if (r && is_base(r->op) && is_distinct_set(sql, l, ad)) { /* TODO table functions need dependent implementation */
1310 rel = push_up_table(sql, rel, ad);
1311 return rel;
1312 }
1313
1314 /* fallback */
1315 if (ad != NULL)
1316 rel = rel_general_unnest(sql, rel, ad);
1317
1318 /* no dependent variables */
1319 reset_dependent(rel);
1320 rel->r = rel_unnest_dependent(sql, rel->r);
1321 } else {
1322 rel->l = rel_unnest_dependent(sql, rel->l);
1323 rel->r = rel_unnest_dependent(sql, rel->r);
1324 }
1325 } else {
1326 if (rel && (is_simple_project(rel->op) || is_groupby(rel->op) || is_select(rel->op) || is_topn(rel->op) || is_sample(rel->op)))
1327 rel->l = rel_unnest_dependent(sql, rel->l);
1328 else if (rel && (is_join(rel->op) || is_semi(rel->op) || is_set(rel->op) || is_modify(rel->op) || is_ddl(rel->op))) {
1329 rel->l = rel_unnest_dependent(sql, rel->l);
1330 rel->r = rel_unnest_dependent(sql, rel->r);
1331 }
1332 }
1333 return nrel;
1334}
1335
1336static sql_rel *
1337_rel_unnest(mvc *sql, sql_rel *rel)
1338{
1339 if (THRhighwater())
1340 return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
1341 if (!rel)
1342 return rel;
1343
1344 switch (rel->op) {
1345 case op_basetable:
1346 case op_table:
1347 break;
1348 case op_join:
1349 case op_left:
1350 case op_right:
1351 case op_full:
1352
1353 case op_semi:
1354 case op_anti:
1355
1356 case op_union:
1357 case op_inter:
1358 case op_except:
1359 rel->l = _rel_unnest(sql, rel->l);
1360 rel->r = _rel_unnest(sql, rel->r);
1361 break;
1362 case op_project:
1363 case op_select:
1364 case op_groupby:
1365 case op_topn:
1366 case op_sample:
1367 rel->l = _rel_unnest(sql, rel->l);
1368 break;
1369 case op_ddl:
1370 rel->l = _rel_unnest(sql, rel->l);
1371 if (rel->r)
1372 rel->r = _rel_unnest(sql, rel->r);
1373 break;
1374 case op_insert:
1375 case op_update:
1376 case op_delete:
1377 case op_truncate:
1378 rel->l = _rel_unnest(sql, rel->l);
1379 rel->r = _rel_unnest(sql, rel->r);
1380 break;
1381 }
1382 if (is_dependent(rel))
1383 rel = rel_unnest_dependent(sql, rel);
1384 return rel;
1385}
1386
1387static void
1388rel_reset_subquery(sql_rel *rel)
1389{
1390 if (!rel)
1391 return;
1392
1393 rel->subquery = 0;
1394 switch(rel->op){
1395 case op_basetable:
1396 case op_table:
1397 break;
1398 case op_ddl:
1399 rel_reset_subquery(rel->l);
1400 if (rel->r)
1401 rel_reset_subquery(rel->r);
1402 break;
1403 case op_insert:
1404 case op_update:
1405 case op_delete:
1406 case op_truncate:
1407 if (rel->l)
1408 rel_reset_subquery(rel->l);
1409 if (rel->r)
1410 rel_reset_subquery(rel->r);
1411 break;
1412 case op_select:
1413 case op_topn:
1414 case op_sample:
1415
1416 case op_project:
1417 case op_groupby:
1418 if (rel->l)
1419 rel_reset_subquery(rel->l);
1420 break;
1421 case op_join:
1422 case op_left:
1423 case op_right:
1424 case op_full:
1425 case op_semi:
1426 case op_anti:
1427
1428 case op_union:
1429 case op_inter:
1430 case op_except:
1431 if (rel->l)
1432 rel_reset_subquery(rel->l);
1433 if (rel->r)
1434 rel_reset_subquery(rel->r);
1435 }
1436
1437}
1438
1439static sql_exp *
1440rewrite_inner(mvc *sql, sql_rel *rel, sql_rel *inner, operator_type op)
1441{
1442 sql_rel *d = NULL;
1443
1444 if (!is_project(inner->op))
1445 inner = rel_project(sql->sa, inner, rel_projections(sql, inner, NULL, 1, 1));
1446
1447 if (is_join(rel->op)){ /* TODO handle set operators etc */
1448 d = rel->r = rel_crossproduct(sql->sa, rel->r, inner, op);
1449 } else if (is_project(rel->op)){ /* projection -> op_left */
1450 if (rel->l) {
1451 d = rel->l = rel_crossproduct(sql->sa, rel->l, inner, op_left);
1452 } else {
1453 d = rel->l = inner;
1454 }
1455 } else {
1456 d = rel->l = rel_crossproduct(sql->sa, rel->l, inner, op);
1457 }
1458 if (d && rel_has_freevar(sql, inner)) {
1459 /* check if the inner depends on the new join (d) or one leve up */
1460 if (!list_empty(rel_dependent_var(sql, d, inner)))
1461 set_dependent(d);
1462 else
1463 set_dependent(rel);
1464 }
1465 return inner->exps->t->data;
1466}
1467
1468static sql_exp *
1469rewrite_exp_rel(mvc *sql, sql_rel *rel, sql_exp *e, int depth)
1470{
1471 (void)depth;
1472 if (exp_has_rel(e) && !is_ddl(rel->op)) {
1473 sql_exp *ne = rewrite_inner(sql, rel, exp_rel_get_rel(sql->sa, e), op_join);
1474
1475 if (!ne)
1476 return ne;
1477 if (exp_is_rel(e)) {
1478 ne = exp_ref(sql->sa, ne);
1479 if (exp_name(e))
1480 exp_prop_alias(sql->sa, ne, e);
1481 if (!exp_name(ne))
1482 ne = exp_label(sql->sa, ne, ++sql->label);
1483 e = ne;
1484 } else {
1485 e = exp_rel_update_exp(sql->sa, e);
1486 }
1487 }
1488 if (exp_is_rel(e) && is_ddl(rel->op))
1489 e->l = rel_exp_visitor(sql, e->l, &rewrite_exp_rel);
1490 return e;
1491}
1492
1493#define is_not_func(sf) (strcmp(sf->func->base.name, "not") == 0)
1494#define is_not_anyequal(sf) (strcmp(sf->func->base.name, "sql_not_anyequal") == 0)
1495
1496/* simplify expressions, such as not(not(x)) */
1497/* exp visitor */
1498static sql_exp *
1499rewrite_simplify_exp(mvc *sql, sql_rel *rel, sql_exp *e, int depth)
1500{
1501 if (!e)
1502 return e;
1503
1504 (void)sql; (void)rel; (void)depth;
1505
1506 sql_subfunc *sf = e->f;
1507 if (is_func(e->type) && list_length(e->l) == 1 && is_not_func(sf)) {
1508 list *args = e->l;
1509 sql_exp *ie = args->h->data;
1510
1511 if (!ie)
1512 return e;
1513
1514 sql_subfunc *sf = ie->f;
1515 if (is_func(ie->type) && list_length(ie->l) == 1 && is_not_func(sf)) {
1516 args = ie->l;
1517
1518 ie = args->h->data;
1519 if (exp_name(e))
1520 exp_prop_alias(sql->sa, ie, e);
1521 return ie;
1522 }
1523 if (is_func(ie->type) && list_length(ie->l) == 2 && is_not_anyequal(sf)) {
1524 args = ie->l;
1525
1526 sql_exp *l = args->h->data;
1527 sql_exp *vals = args->h->next->data;
1528
1529 ie = exp_in_func(sql, l, vals, 1, 0);
1530 if (exp_name(e))
1531 exp_prop_alias(sql->sa, ie, e);
1532 return ie;
1533 }
1534 }
1535 return e;
1536}
1537
1538/* add an dummy true projection column */
1539static sql_rel *
1540rewrite_empty_project(mvc *sql, sql_rel *rel)
1541{
1542 if (is_simple_project(rel->op) && list_empty(rel->exps))
1543 append(rel->exps, exp_atom_bool(sql->sa, 1));
1544 if (is_groupby(rel->op) && list_empty(rel->exps))
1545 append(rel->exps, exp_atom_bool(sql->sa, 1));
1546 return rel;
1547}
1548
1549static list*
1550aggrs_split_args(mvc *sql, list *aggrs, list *exps, int is_groupby_list)
1551{
1552 if (list_empty(aggrs))
1553 return aggrs;
1554 for (node *n=aggrs->h; n; n = n->next) {
1555 sql_exp *a = n->data;
1556
1557 if (is_func(a->type) && !is_groupby_list)
1558 continue;
1559 if (!is_aggr(a->type)) {
1560 sql_exp *e1 = a, *found = NULL;
1561
1562 for (node *nn = exps->h; nn && !found; nn = nn->next) {
1563 sql_exp *e2 = nn->data;
1564
1565 if (!exp_equal(e1, e2))
1566 found = e2;
1567 }
1568 if (!found) {
1569 if (!exp_name(e1))
1570 e1 = exp_label(sql->sa, e1, ++sql->label);
1571 append(exps, e1);
1572 } else {
1573 e1 = found;
1574 }
1575 e1 = exp_ref(sql->sa, e1);
1576 n->data = e1; /* replace by reference */
1577 continue;
1578 }
1579 list *args = a->l;
1580
1581 if (!list_empty(args)) {
1582 for (node *an = args->h; an; an = an->next) {
1583 sql_exp *e1 = an->data, *found = NULL, *eo = e1;
1584 /* we keep converts as they reuse names of inner columns */
1585 int convert = is_convert(e1->type);
1586
1587 if (convert)
1588 e1 = e1->l;
1589 for (node *nn = exps->h; nn && !found; nn = nn->next) {
1590 sql_exp *e2 = nn->data;
1591
1592 if (!exp_equal(e1, e2))
1593 found = e2;
1594 }
1595 if (!found) {
1596 if (!exp_name(e1))
1597 e1 = exp_label(sql->sa, e1, ++sql->label);
1598 append(exps, e1);
1599 } else {
1600 e1 = found;
1601 }
1602 e1 = exp_ref(sql->sa, e1);
1603 /* replace by reference */
1604 if (convert)
1605 eo->l = e1;
1606 else
1607 an->data = e1;
1608 }
1609 }
1610 }
1611 return aggrs;
1612}
1613
1614static int
1615exps_complex(list *exps)
1616{
1617 if (list_empty(exps))
1618 return 0;
1619 for(node *n = exps->h; n; n = n->next) {
1620 sql_exp *e = n->data;
1621
1622 if (e->type != e_column && e->type != e_atom)
1623 return 1;
1624 }
1625 return 0;
1626}
1627
1628static int
1629aggrs_complex(list *exps)
1630{
1631 if (list_empty(exps))
1632 return 0;
1633 for(node *n = exps->h; n; n = n->next) {
1634 sql_exp *e = n->data;
1635
1636 if (e->type != e_column) {
1637 if (e->type == e_aggr) {
1638 if (exps_complex(e->l))
1639 return 1;
1640 }
1641 }
1642 }
1643 return 0;
1644}
1645
1646/* simplify aggregates, ie push functions under the groupby relation */
1647/* rel visitor */
1648static sql_rel *
1649rewrite_aggregates(mvc *sql, sql_rel *rel)
1650{
1651 if (is_groupby(rel->op) && (exps_complex(rel->r) || aggrs_complex(rel->exps))) {
1652 list *exps = sa_list(sql->sa);
1653
1654 rel->r = aggrs_split_args(sql, rel->r, exps, 1);
1655 rel->exps = aggrs_split_args(sql, rel->exps, exps, 0);
1656 rel->l = rel_project(sql->sa, rel->l, exps);
1657 return rel;
1658 }
1659 return rel;
1660}
1661
1662/* remove or expressions with subqueries */
1663static sql_rel *
1664rewrite_or_exp(mvc *sql, sql_rel *rel)
1665{
1666 if ((is_select(rel->op) || is_join(rel->op)) && !list_empty(rel->exps)) {
1667 for(node *n=rel->exps->h; n; n=n->next) {
1668 sql_exp *e = n->data;
1669
1670 if (is_compare(e->type) && e->flag == cmp_or) {
1671 /* check for exp_is_rel */
1672 if (exps_have_rel_exp(e->l) || exps_have_rel_exp(e->r)) {
1673 /* rewrite into setop */
1674 sql_rel *l = rel;
1675 sql_rel *r = rel_dup(rel);
1676 list *exps = rel_projections(sql, rel, NULL, 1, 1);
1677
1678 l = rel_select(sql->sa, l, NULL);
1679 l->exps = e->l;
1680 r = rel_select(sql->sa, r, NULL);
1681 r->exps = e->r;
1682
1683 list_remove_node(rel->exps, n); /* remove or expression */
1684 list *ls = rel_projections(sql, rel, NULL, 1, 1);
1685 list *rs = rel_projections(sql, rel, NULL, 1, 1);
1686 rel = rel_setop_check_types(sql, l, r, ls, rs, op_union);
1687 rel = rel_distinct(rel);
1688 rel->exps = exps;
1689 return rewrite_or_exp(sql, rel);
1690 }
1691 }
1692 }
1693 }
1694 return rel;
1695}
1696
1697/* exp visitor */
1698static sql_exp *
1699rewrite_rank(mvc *sql, sql_rel *rel, sql_exp *e, int depth)
1700{
1701 if (e->type != e_func || !e->r /* e->r means window function */)
1702 return e;
1703
1704 (void)depth;
1705 /* ranks/window functions only exist in the projection */
1706 assert(is_simple_project(rel->op));
1707 list *r = e->r, *gbe = r->h->data, *obe = r->h->next->data;
1708
1709 if (gbe || obe) {
1710 sql_rel *r = rel_project(sql->sa, rel->l, rel_projections(sql, rel->l, NULL, 1, 1));
1711 if (gbe && obe) {
1712 gbe = list_merge(sa_list(sql->sa), gbe, (fdup)NULL); /* make sure the p->r is a different list than the gbe list */
1713 for(node *n = obe->h ; n ; n = n->next) {
1714 sql_exp *e1 = n->data;
1715 bool found = false;
1716
1717 for(node *nn = gbe->h ; nn && !found ; nn = nn->next) {
1718 sql_exp *e2 = nn->data;
1719 //the partition expression order should be the same as the one in the order by clause (if it's in there as well)
1720 if(!exp_equal(e1, e2)) {
1721 if(is_ascending(e1))
1722 e2->flag |= ASCENDING;
1723 else
1724 e2->flag &= ~ASCENDING;
1725 found = true;
1726 }
1727 }
1728 if(!found)
1729 append(gbe, e1);
1730 }
1731 } else if (obe) {
1732 gbe = obe;
1733 }
1734 r->r = gbe;
1735 rel->l = r;
1736
1737 /* mark as normal (analytic) function now */
1738 e->r = NULL;
1739
1740 /* add project with rank */
1741 r = rel->l = rel_project(sql->sa, rel->l, rel_projections(sql, rel->l, NULL, 1, 1));
1742 /* move rank down add ref */
1743 if (!exp_name(e))
1744 e = exp_label(sql->sa, e, ++sql->label);
1745 append(r->exps, e);
1746 e = exp_ref(sql->sa, e);
1747 } else {
1748 /* mark as normal (analytic) function now */
1749 e->r = NULL;
1750 }
1751 return e;
1752}
1753
1754#define is_anyequal_func(sf) (strcmp(sf->func->base.name, "sql_anyequal") == 0 || strcmp(sf->func->base.name, "sql_not_anyequal") == 0)
1755#define is_anyequal(sf) (strcmp(sf->func->base.name, "sql_anyequal") == 0)
1756
1757static sql_rel *
1758rel_union_exps(mvc *sql, sql_exp **l, list *vals, int is_tuple)
1759{
1760 sql_rel *u = NULL;
1761 list *exps = NULL;
1762
1763 for(node *n=vals->h; n; n = n->next) {
1764 sql_exp *ve = n->data, *r;
1765 sql_rel *sq = NULL;
1766
1767 if (exp_has_rel(ve))
1768 sq = exp_rel_get_rel(sql->sa, ve); /* get subquery */
1769 else
1770 sq = rel_project(sql->sa, NULL, append(sa_list(sql->sa), ve));
1771 /* TODO merge expressions (could x+ cast(y) where y is result of a sub query) */
1772 r = sq->exps->t->data;
1773 if (!is_tuple && rel_convert_types(sql, NULL, NULL, l, &r, 1, type_equal) < 0)
1774 return NULL;
1775 sq->exps->t->data = r;
1776 if (!u) {
1777 u = sq;
1778 exps = rel_projections(sql, sq, NULL, 1/*keep names */, 1);
1779 } else {
1780 u = rel_setop(sql->sa, u, sq, op_union);
1781 u->exps = exps;
1782 exps = rel_projections(sql, sq, NULL, 1/*keep names */, 1);
1783 }
1784 }
1785 return u;
1786}
1787
1788static sql_exp *
1789exp_in_project(mvc *sql, sql_exp **l, list *vals, int anyequal)
1790{
1791 sql_exp *e = NULL;
1792
1793 for(node *n=vals->h; n; n = n->next) {
1794 sql_exp *r = n->data, *ne;
1795
1796 if (rel_convert_types(sql, NULL, NULL, l, &r, 1, type_equal_no_any) < 0)
1797 return NULL;
1798 if (anyequal)
1799 ne = rel_binop_(sql, NULL, *l, r, NULL, "=", card_value);
1800 else
1801 ne = rel_binop_(sql, NULL, *l, r, NULL, "<>", card_value);
1802 if (!e) {
1803 e = ne;
1804 } else if (anyequal) {
1805 e = rel_binop_(sql, NULL, e, ne, NULL, "or", card_value);
1806 } else {
1807 e = rel_binop_(sql, NULL, e, ne, NULL, "and", card_value);
1808 }
1809 }
1810 return e;
1811}
1812
1813static sql_exp *
1814exp_in_compare(mvc *sql, sql_exp **l, list *vals, int anyequal)
1815{
1816 int vals_only = 1;
1817
1818 for(node *n=vals->h; n; n = n->next) {
1819 sql_exp *r = n->data;
1820
1821 if (rel_convert_types(sql, NULL, NULL, l, &r, 1, type_equal_no_any) < 0)
1822 return NULL;
1823 n->data = r;
1824 if (!exp_is_atom(r))
1825 vals_only = 0;
1826 }
1827 if (vals_only)
1828 return exp_in(sql->sa, *l, vals, anyequal?cmp_in:cmp_notin);
1829
1830 *l = exp_in_project(sql, l, vals, anyequal);
1831 return exp_compare(sql->sa, *l, exp_atom_bool(sql->sa, 1), cmp_equal);
1832}
1833
1834/* exp visitor */
1835static sql_exp *
1836rewrite_anyequal(mvc *sql, sql_rel *rel, sql_exp *e, int depth)
1837{
1838 sql_subfunc *sf;
1839 if (e->type != e_func)
1840 return e;
1841
1842 sf = e->f;
1843 if (is_anyequal_func(sf) && !list_empty(e->l)) {
1844 list *l = e->l;
1845
1846 if (list_length(l) == 2) { /* input is a set */
1847
1848 sql_exp *ile = l->h->data, *le, *re = l->h->next->data;
1849 sql_rel *lsq = NULL, *rsq = NULL;
1850 int is_tuple = 0;
1851
1852 /* possibly this is already done ? */
1853 if (exp_has_rel(ile))
1854 lsq = exp_rel_get_rel(sql->sa, ile); /* get subquery */
1855
1856 if (lsq)
1857 le = lsq->exps->t->data;
1858 else
1859 le = ile;
1860
1861 if (is_values(le)) /* exp_values */
1862 is_tuple = 1;
1863
1864 /* re should be a values list */
1865 if (!is_tuple && is_values(re) && !exps_have_rel_exp(re->f)) { /* exp_values */
1866 list *vals = re->f;
1867
1868 if (depth == 0 && is_select(rel->op))
1869 return exp_in_compare(sql, &le, vals, is_anyequal(sf));
1870 else
1871 return exp_in_project(sql, &le, vals, is_anyequal(sf));
1872 }
1873
1874 if (is_atom(re->type) && re->f) { /* exp_values */
1875 /* flatten using unions */
1876 rsq = rel_union_exps(sql, &le, re->f, is_tuple);
1877 re = rsq->exps->t->data;
1878
1879 if (!is_tuple && !is_freevar(re)) {
1880 re = exp_label(sql->sa, re, ++sql->label); /* unique name */
1881 list_hash_clear(rsq->exps);
1882 re = exp_ref(sql->sa, re);
1883 } else if (has_label(re)) {
1884 re = exp_ref(sql->sa, re);
1885 }
1886 }
1887
1888 if (is_project(rel->op) || depth > 0) {
1889 list *exps = NULL;
1890 sql_exp *rid, *lid;
1891 sql_rel *sq = lsq;
1892
1893 assert(!is_tuple);
1894 rsq = rel_add_identity2(sql, rsq, &rid);
1895 rid = exp_ref(sql->sa, rid);
1896
1897 if (!lsq)
1898 lsq = rel->l;
1899 if (!lsq) { /* single row */
1900 lid = exp_atom_lng(sql->sa, 1);
1901 } else {
1902 exps = rel_projections(sql, lsq, NULL, 1/*keep names */, 1);
1903 lsq = rel_add_identity(sql, lsq, &lid);
1904 if (!sq)
1905 rel->l = lsq;
1906 lid = exp_ref(sql->sa, lid);
1907 }
1908
1909 if (sq)
1910 (void)rewrite_inner(sql, rel, lsq, op_join);
1911 if (rsq)
1912 (void)rewrite_inner(sql, rel, rsq, op_join);
1913
1914 lsq = rel->l = rel_groupby(sql, rel->l, exp2list(sql->sa, lid));
1915 if (exps)
1916 lsq->exps = exps;
1917
1918 sql_subaggr *ea = sql_bind_aggr(sql->sa, sql->session->schema, is_anyequal(sf)?"anyequal":"allnotequal", exp_subtype(re));
1919 sql_exp *a = exp_aggr1(sql->sa, le, ea, 0, 0, CARD_AGGR, has_nil(le));
1920 append(a->l, re);
1921 append(a->l, rid);
1922 le = rel_groupby_add_aggr(sql, lsq, a);
1923 if (exp_name(e))
1924 exp_prop_alias(sql->sa, le, e);
1925 return le;
1926 } else {
1927 if (lsq)
1928 (void)rewrite_inner(sql, rel, lsq, op_join);
1929 if (rsq)
1930 (void)rewrite_inner(sql, rel, rsq, !is_tuple?op_join:is_anyequal(sf)?op_semi:op_anti);
1931 if (is_tuple) {
1932 list *t = le->f;
1933 list *l = sa_list(sql->sa);
1934 list *r = sa_list(sql->sa);
1935
1936 /* find out list of right expression */
1937 if (list_length(t) != list_length(rsq->exps))
1938 return NULL;
1939 for (node *n = t->h, *m = rsq->exps->h; n && m; n = n->next, m = m->next ) {
1940 sql_exp *le = n->data;
1941 sql_exp *re = m->data;
1942
1943 append(l, le);
1944 re = exp_ref(sql->sa, re);
1945 append(r, re);
1946 }
1947 return exp_in_func(sql, exp_values(sql->sa, l), exp_values(sql->sa, r), is_anyequal(sf), 1);
1948 } else {
1949 if (exp_has_freevar(sql, le))
1950 rel_bind_var(sql, rel, le);
1951 return exp_in_func(sql, le, re, is_anyequal(sf), 0);
1952 }
1953 }
1954 }
1955 }
1956 return e;
1957}
1958
1959static const char *
1960compare_aggr_op( char *compare, int quantifier)
1961{
1962 if (quantifier == 0)
1963 return "zero_or_one";
1964 switch(compare[0]) {
1965 case '<':
1966 if (compare[1] == '>')
1967 return "all";
1968 return "min";
1969 case '>':
1970 return "max";
1971 default:
1972 return "all";
1973 }
1974}
1975/* exp visitor */
1976/* rewrite compare expressions including quantifiers any and all */
1977static sql_exp *
1978rewrite_compare(mvc *sql, sql_rel *rel, sql_exp *e, int depth)
1979{
1980 sql_subfunc *sf;
1981 if (e->type != e_func || is_ddl(rel->op))
1982 return e;
1983
1984 sf = e->f;
1985 if (is_compare_func(sf) && !list_empty(e->l)) {
1986 list *l = e->l;
1987
1988 /* TODO handle range expressions */
1989 if (list_length(l) == 2) { /* input is a set */
1990 char *op = sf->func->base.name;
1991
1992 sql_exp *ile = l->h->data, *le, *re = l->h->next->data, *rnull = NULL;
1993 sql_rel *lsq = NULL, *rsq = NULL;
1994 int is_tuple = 0; /* TODO add this feature, ie select (1,2) = (1,2) etc */
1995 /* cleanup tuple handling by introducing an expression for tuples */
1996 int quantifier = e->flag;
1997
1998 /* possibly this is already done ? */
1999 if (exp_has_rel(ile))
2000 lsq = exp_rel_get_rel(sql->sa, ile); /* get subquery */
2001
2002 if (lsq)
2003 le = exp_rel_update_exp(sql->sa, ile);
2004 else
2005 le = ile;
2006
2007 if (exp_has_rel(re))
2008 rsq = exp_rel_get_rel(sql->sa, re); /* get subquery */
2009 if (rsq) {
2010 re = rsq->exps->t->data;
2011 re = exp_ref(sql->sa, re);
2012 }
2013
2014 if (is_values(le)) /* exp_values */
2015 is_tuple = 1;
2016
2017 /* re should be a values list */
2018 if (!is_tuple && exp_is_atom(le) && exp_is_atom(re)) {
2019 e->flag = 0; /* remove quantifier */
2020
2021 if (rel_convert_types(sql, NULL, NULL, &le, &re, 1, type_equal_no_any) < 0)
2022 return NULL;
2023 le = exp_compare_func(sql, le, re, NULL, op, 0);
2024 if (exp_name(e))
2025 exp_prop_alias(sql->sa, le, e);
2026 return le;
2027 }
2028 if (!is_tuple && is_values(re) && !exps_have_rel_exp(re->f)) { /* exp_values */
2029 list *vals = re->f;
2030
2031 assert(0);
2032 if (depth == 0 && is_select(rel->op))
2033 return exp_in_compare(sql, &le, vals, is_anyequal(sf));
2034 else
2035 return exp_in_project(sql, &le, vals, is_anyequal(sf));
2036 }
2037
2038 if (is_values(re)) { /* exp_values */
2039 /* flatten using unions */
2040 rsq = rel_union_exps(sql, &le, re->f, is_tuple);
2041 re = rsq->exps->t->data;
2042
2043 if (!is_tuple) {
2044 re = exp_label(sql->sa, re, ++sql->label); /* unique name */
2045 list_hash_clear(rsq->exps);
2046 re = exp_ref(sql->sa, re);
2047 }
2048 }
2049
2050 int is_cnt = 0;
2051 if (rsq)
2052 is_cnt = exp_is_count(re, rsq);
2053 if (is_project(rel->op) || depth > 0 || quantifier || is_cnt) {
2054 sql_rel *sq = lsq;
2055
2056 assert(!is_tuple);
2057
2058 if (!lsq)
2059 lsq = rel->l;
2060 if (sq)
2061 (void)rewrite_inner(sql, rel, sq, op_join);
2062
2063 if (quantifier) {
2064 sql_subaggr *a;
2065
2066 rsq = rel_groupby(sql, rsq, NULL);
2067 a = sql_bind_aggr(sql->sa, NULL, "null", exp_subtype(re));
2068 rnull = exp_aggr1(sql->sa, re, a, 0, 1, CARD_AGGR, 0);
2069 rnull = rel_groupby_add_aggr(sql, rsq, rnull);
2070
2071 if (is_notequal_func(sf))
2072 op = "=";
2073 if (op[0] == '<') {
2074 a = sql_bind_aggr(sql->sa, sql->session->schema, (quantifier==1)?"max":"min", exp_subtype(re));
2075 } else if (op[0] == '>') {
2076 a = sql_bind_aggr(sql->sa, sql->session->schema, (quantifier==1)?"min":"max", exp_subtype(re));
2077 } else /* (op[0] == '=')*/ /* only = ALL */ {
2078 a = sql_bind_aggr(sql->sa, sql->session->schema, "all", exp_subtype(re));
2079 is_cnt = 1;
2080 }
2081 re = exp_aggr1(sql->sa, re, a, 0, 1, CARD_AGGR, has_nil(re));
2082 re = rel_groupby_add_aggr(sql, rsq, re);
2083 } else if (rsq && exp_card(re) > CARD_ATOM) {
2084 sql_subaggr *zero_or_one = sql_bind_aggr(sql->sa, NULL, compare_aggr_op(op, quantifier), exp_subtype(re));
2085
2086 rsq = rel_groupby(sql, rsq, NULL);
2087
2088 re = exp_aggr1(sql->sa, re, zero_or_one, 0, 0, CARD_AGGR, has_nil(re));
2089 re = rel_groupby_add_aggr(sql, rsq, re);
2090 }
2091 if (rsq)
2092 (void)rewrite_inner(sql, rel, rsq, is_cnt?op_left:op_join);
2093
2094 if (rel_convert_types(sql, NULL, NULL, &le, &re, 1, type_equal) < 0)
2095 return NULL;
2096 if (rnull) { /* complex compare operator */
2097 sql_exp *lnull = rel_unop_(sql, rel, le, NULL, "isnull", card_value);
2098 set_has_no_nil(lnull);
2099 le = exp_compare_func(sql, le, re, NULL, op, 0);
2100 le = rel_nop_(sql, rel, le, lnull, rnull, NULL, NULL, (quantifier==1)?"any":"all", card_value);
2101 if (is_notequal_func(sf))
2102 le = rel_unop_(sql, rel, le, NULL, "not", card_value);
2103 } else if (is_project(rel->op) || depth) {
2104 le = exp_compare_func(sql, le, re, NULL, op, 0);
2105 } else {
2106 return exp_compare(sql->sa, le, re, compare_str2type(op));
2107 }
2108 if (exp_name(e))
2109 exp_prop_alias(sql->sa, le, e);
2110 return le;
2111 } else {
2112 if (lsq)
2113 (void)rewrite_inner(sql, rel, lsq, op_join);
2114 if (rsq)
2115 (void)rewrite_inner(sql, rel, rsq, !is_tuple?op_join:is_anyequal(sf)?op_semi:op_anti);
2116 if (is_tuple) {
2117 list *t = le->f;
2118 list *l = sa_list(sql->sa);
2119 list *r = sa_list(sql->sa);
2120
2121 /* find out list of right expression */
2122 if (list_length(t) != list_length(rsq->exps))
2123 return NULL;
2124 for (node *n = t->h, *m = rsq->exps->h; n && m; n = n->next, m = m->next ) {
2125 sql_exp *le = n->data;
2126 sql_exp *re = m->data;
2127
2128 append(l, le);
2129 append(r, re);
2130 }
2131 return exp_compare(sql->sa, exp_values(sql->sa, l), exp_values(sql->sa, r), compare_str2type(op));
2132 } else {
2133 if (exp_has_freevar(sql, le))
2134 rel_bind_var(sql, rel, le);
2135 if (rel_convert_types(sql, NULL, NULL, &le, &re, 1, type_equal) < 0)
2136 return NULL;
2137 return exp_compare(sql->sa, le, re, compare_str2type(op));
2138 }
2139 }
2140 }
2141 }
2142 return e;
2143}
2144
2145
2146static sql_rel *
2147rewrite_join2semi(mvc *sql, sql_rel *rel)
2148{
2149 if (is_select(rel->op) && !list_empty(rel->exps)) {
2150 sql_rel *j = rel->l;
2151 int needed=0;
2152
2153 if (!j || (!is_join(j->op) && !is_semi(j->op)) || !list_empty(j->exps))
2154 return rel;
2155 /* if needed first push select exps down under the join */
2156 for(node *n = rel->exps->h; n && !needed; n = n->next) {
2157 sql_exp *e = n->data;
2158 sql_subfunc *sf = e->f;
2159
2160 if (is_func(e->type) && exp_card(e) > CARD_ATOM && is_anyequal_func(sf) && rel_has_all_exps(j->l, e->l))
2161 needed = 1;
2162 }
2163 if (needed) {
2164 list *exps = sa_list(sql->sa), *jexps = sa_list(sql->sa);
2165 sql_rel *l = j->l = rel_select(sql->sa, j->l, NULL);
2166
2167 for(node *n = rel->exps->h; n; n = n->next) {
2168 sql_exp *e = n->data;
2169 sql_subfunc *sf = e->f;
2170
2171 if (is_func(e->type) && exp_card(e) > CARD_ATOM && is_anyequal_func(sf) && rel_has_all_exps(j->l, e->l))
2172 append(exps, e);
2173 else
2174 append(jexps, e);
2175 }
2176 rel->exps = jexps;
2177 l->exps = exps;
2178 j->l = rewrite_join2semi(sql, j->l);
2179 }
2180
2181 needed = 0;
2182 for(node *n = rel->exps->h; n && !needed; n = n->next) {
2183 sql_exp *e = n->data;
2184 sql_subfunc *sf = e->f;
2185
2186 if (is_func(e->type) && is_anyequal_func(sf))
2187 needed = 1;
2188 }
2189 if (!needed)
2190 return rel;
2191 list *exps = sa_list(sql->sa);
2192 if (!j->exps)
2193 j->exps = sa_list(sql->sa);
2194 for(node *n = rel->exps->h; n; n = n->next) {
2195 sql_exp *e = n->data;
2196 sql_subfunc *sf = e->f;
2197
2198 if (is_func(e->type) && is_anyequal_func(sf)) {
2199 list *args = e->l;
2200 sql_exp *l, *r;
2201
2202 assert(list_length(args)==2);
2203 l = args->h->data;
2204 r = args->h->next->data;
2205 j->op = (is_anyequal(sf))?op_semi:op_anti;
2206
2207 if (is_values(l)) {
2208 assert(is_values(r));
2209 list *ll = l->f, *rl = r->f;
2210 for(node *n=ll->h, *m=rl->h; n && m; n=n->next, m=m->next) {
2211 e = exp_compare(sql->sa, n->data, m->data, j->op == op_semi?mark_in:mark_notin);
2212 append(j->exps, e);
2213 }
2214 } else {
2215 e = exp_compare(sql->sa, l, r, j->op == op_semi?mark_in:mark_notin);
2216 append(j->exps, e);
2217 }
2218 } else {
2219 append(exps, e);
2220 }
2221 }
2222 rel->exps = exps;
2223 }
2224 return rel;
2225}
2226
2227#define is_exists_func(sf) (strcmp(sf->func->base.name, "sql_exists") == 0 || strcmp(sf->func->base.name, "sql_not_exists") == 0)
2228#define is_exists(sf) (strcmp(sf->func->base.name, "sql_exists") == 0)
2229
2230static sql_exp *
2231exp_exist(mvc *sql, sql_exp *le, sql_exp *ne, int exists)
2232{
2233 sql_subfunc *exists_func = NULL;
2234
2235 if (exists)
2236 exists_func = sql_bind_func(sql->sa, sql->session->schema, "sql_exists", exp_subtype(le), NULL, F_FUNC);
2237 else
2238 exists_func = sql_bind_func(sql->sa, sql->session->schema, "sql_not_exists", exp_subtype(le), NULL, F_FUNC);
2239
2240 if (!exists_func)
2241 return sql_error(sql, 02, SQLSTATE(42000) "exist operator on type %s missing", exp_subtype(le)->type->sqlname);
2242 if (ne) { /* correlated case */
2243 ne = rel_unop_(sql, NULL, ne, NULL, "isnull", card_value);
2244 set_has_no_nil(ne);
2245 le = rel_nop_(sql, NULL, ne, exp_atom_bool(sql->sa, !exists), exp_atom_bool(sql->sa, exists), NULL, NULL, "ifthenelse", card_value);
2246 return le;
2247 } else {
2248 return exp_unop(sql->sa, le, exists_func);
2249 }
2250}
2251
2252/* exp visitor */
2253static sql_exp *
2254rewrite_exists(mvc *sql, sql_rel *rel, sql_exp *e, int depth)
2255{
2256 sql_subfunc *sf;
2257 if (e->type != e_func)
2258 return e;
2259
2260 sf = e->f;
2261 if (is_exists_func(sf) && !list_empty(e->l)) {
2262 list *l = e->l;
2263
2264 if (list_length(l) == 1) { /* exp_values */
2265 sql_exp *ne = NULL, *ie = l->h->data, *le;
2266 sql_rel *sq = NULL;
2267
2268 if (!exp_is_rel(ie)) /* already fine */
2269 return e;
2270
2271 sq = exp_rel_get_rel(sql->sa, ie); /* get subquery */
2272
2273 le = rel_reduce2one_exp(sql, sq);
2274 if (!exp_name(le))
2275 le = exp_label(sql->sa, le, ++sql->label);
2276 le = exp_ref(sql->sa, le);
2277 if (is_project(rel->op) && is_freevar(le)) {
2278 sql_exp *re, *jc, *null;
2279
2280 re = rel_bound_exp(sql, sq);
2281 re = rel_project_add_exp(sql, sq, re);
2282 jc = rel_unop_(sql, NULL, re, NULL, "isnull", card_value);
2283 set_has_no_nil(jc);
2284 null = exp_null(sql->sa, exp_subtype(le));
2285 le = rel_nop_(sql, NULL, jc, null, le, NULL, NULL, "ifthenelse", card_value);
2286 }
2287
2288 sql_subaggr *ea = NULL;
2289 sq = rel_groupby(sql, sq, NULL);
2290
2291 if (exp_is_rel(ie)) /* TODO add set rel function */
2292 ie->l = sq;
2293 ea = sql_bind_aggr(sql->sa, sql->session->schema, is_exists(sf)?"exist":"not_exist", exp_subtype(le));
2294 le = exp_aggr1(sql->sa, le, ea, 0, 0, CARD_AGGR, has_nil(le));
2295 le = rel_groupby_add_aggr(sql, sq, le);
2296 if (rel_has_freevar(sql, sq))
2297 ne = le;
2298
2299 if (exp_has_rel(ie))
2300 (void)rewrite_exp_rel(sql, rel, ie, depth);
2301
2302 if (is_project(rel->op) && rel_has_freevar(sql, sq))
2303 le = exp_exist(sql, le, ne, is_exists(sf));
2304 if (exp_name(e))
2305 exp_prop_alias(sql->sa, le, e);
2306 return le;
2307 }
2308 }
2309 return e;
2310}
2311
2312#define is_ifthenelse_func(sf) (strcmp(sf->func->base.name, "ifthenelse") == 0)
2313#define is_isnull_func(sf) (strcmp(sf->func->base.name, "isnull") == 0)
2314
2315/* exp visitor */
2316static sql_exp *
2317rewrite_ifthenelse(mvc *sql, sql_rel *rel, sql_exp *e, int depth)
2318{
2319 sql_subfunc *sf;
2320 if (e->type != e_func)
2321 return e;
2322
2323 (void)depth;
2324 sf = e->f;
2325 if (is_ifthenelse_func(sf) && !list_empty(e->l)) {
2326 list *l = e->l;
2327 sql_exp *cond = l->h->data;
2328 sql_subfunc *nf = cond->f;
2329
2330 if (has_nil(cond) && (cond->type != e_func || !is_isnull_func(nf))) {
2331 /* add is null */
2332 sql_exp *condnil = rel_unop_(sql, rel, cond, NULL, "isnull", card_value);
2333
2334 set_has_no_nil(condnil);
2335 cond = exp_copy(sql, cond);
2336 cond = rel_nop_(sql, rel, condnil, exp_atom_bool(sql->sa, 0), cond, NULL, NULL, "ifthenelse", card_value);
2337 l->h->data = cond;
2338 }
2339 }
2340 return e;
2341}
2342
2343static list *
2344rewrite_compare_exps(mvc *sql, list *exps)
2345{
2346 if (list_empty(exps))
2347 return exps;
2348 for(node *n = exps->h; n; n = n->next) {
2349 sql_exp *e = n->data;
2350
2351 if (!is_compare(e->type)) {
2352 n->data = e = exp_compare(sql->sa, e, exp_atom_bool(sql->sa, 1), cmp_equal);
2353 }
2354 if (is_compare(e->type) && e->flag == cmp_or) {
2355 e->l = rewrite_compare_exps(sql, e->l);
2356 e->r = rewrite_compare_exps(sql, e->r);
2357 }
2358 }
2359 list_hash_clear(exps);
2360 return exps;
2361}
2362
2363/* add an dummy true projection column */
2364static sql_rel *
2365rewrite_compare_exp(mvc *sql, sql_rel *rel)
2366{
2367 if ((is_select(rel->op) || is_join(rel->op)) && !list_empty(rel->exps))
2368 rel->exps = rewrite_compare_exps(sql, rel->exps);
2369 return rel;
2370}
2371
2372static sql_rel *
2373rewrite_remove_xp(mvc *sql, sql_rel *rel)
2374{
2375 (void)sql;
2376 if (rel->op == op_join && list_empty(rel->exps)) {
2377 sql_rel *r = rel->r;
2378
2379 if (is_simple_project(r->op) && !r->l && list_length(r->exps) == 1) {
2380 sql_exp *t = r->exps->h->data;
2381
2382 if (is_atom(t->type) && !exp_name(t)) /* atom with out alias cannot be used later */
2383 return rel->l;
2384 }
2385 }
2386 return rel;
2387}
2388
2389/* rel visitor */
2390static sql_rel *
2391rewrite_fix_count(mvc *sql, sql_rel *rel)
2392{
2393 if (rel->op == op_left) {
2394 int changes = 0;
2395 sql_rel *r = rel->r;
2396 /* TODO create an exp iterator */
2397 list *rexps = rel_projections(sql, r, NULL, 1, 1), *exps;
2398
2399 for(node *n = rexps->h; n; n=n->next) {
2400 sql_exp *e = n->data, *ne;
2401
2402 if (exp_is_count(e, r)) {
2403 const char *rname = exp_relname(e), *name = exp_name(e);
2404 /* rewrite count in subquery */
2405 list *args, *targs;
2406 sql_subfunc *isnil = sql_bind_func(sql->sa, NULL, "isnull", exp_subtype(e), NULL, F_FUNC), *ifthen;
2407
2408 changes = 1;
2409 ne = exp_unop(sql->sa, e, isnil);
2410 set_has_no_nil(ne);
2411 targs = sa_list(sql->sa);
2412 append(targs, sql_bind_localtype("bit"));
2413 append(targs, exp_subtype(e));
2414 append(targs, exp_subtype(e));
2415 ifthen = sql_bind_func_(sql->sa, NULL, "ifthenelse", targs, F_FUNC);
2416 args = sa_list(sql->sa);
2417 append(args, ne);
2418 append(args, exp_atom(sql->sa, atom_zero_value(sql->sa, exp_subtype(e))));
2419 append(args, e);
2420 e = exp_op(sql->sa, args, ifthen);
2421 exp_setname(sql->sa, e, rname, name);
2422 n->data = e;
2423 }
2424 }
2425 if (changes) { /* add project */
2426 exps = list_merge(rel_projections(sql, rel->l, NULL, 1, 1), rexps, (fdup)NULL);
2427 rel = rel_project(sql->sa, rel, exps);
2428 }
2429 }
2430 return rel;
2431}
2432
2433sql_rel *
2434rel_unnest(mvc *sql, sql_rel *rel)
2435{
2436 rel_reset_subquery(rel);
2437 rel = rel_exp_visitor(sql, rel, &rewrite_simplify_exp);
2438 rel = rel_visitor(sql, rel, &rewrite_aggregates);
2439 rel = rel_visitor(sql, rel, &rewrite_or_exp);
2440 rel = rel_exp_visitor(sql, rel, &rewrite_rank);
2441 rel = rel_exp_visitor(sql, rel, &rewrite_anyequal);
2442 rel = rel_visitor(sql, rel, &rewrite_join2semi); /* where possible convert anyequal functions into marks */
2443 rel = rel_exp_visitor(sql, rel, &rewrite_compare);
2444 rel = rel_exp_visitor(sql, rel, &rewrite_exists);
2445 rel = rel_exp_visitor(sql, rel, &rewrite_ifthenelse); /* add isnull handling */
2446 rel = rel_exp_visitor(sql, rel, &rewrite_exp_rel);
2447 rel = rel_visitor(sql, rel, &rewrite_compare_exp); /* only allow for e_cmp in selects and handling */
2448 rel = rel_visitor(sql, rel, &rewrite_empty_project);
2449 rel = _rel_unnest(sql, rel);
2450 rel = rel_visitor(sql, rel, &rewrite_fix_count); /* fix count inside a left join (adds a project (if (cnt IS null) then (0) else (cnt)) */
2451 rel = rel_visitor(sql, rel, &rewrite_remove_xp); /* remove crossproducts with project [ atom ] */
2452 return rel;
2453}
2454