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 "sql_query.h"
13#include "rel_partition.h"
14#include "rel_optimizer.h"
15#include "rel_exp.h"
16#include "rel_prop.h"
17#include "rel_dump.h"
18#include "rel_select.h"
19#include "rel_updates.h"
20#include "sql_env.h"
21
22static lng
23rel_getcount(mvc *sql, sql_rel *rel)
24{
25 if (!sql->session->tr)
26 return 0;
27
28 switch(rel->op) {
29 case op_basetable: {
30 sql_table *t = rel->l;
31
32 if (t && isTable(t))
33 return (lng)store_funcs.count_col(sql->session->tr, t->columns.set->h->data, 1);
34 if (!t && rel->r) /* dict */
35 return (lng)sql_trans_dist_count(sql->session->tr, rel->r);
36 return 0;
37 }
38 default:
39 assert(0);
40 return 0;
41 }
42}
43
44static void
45find_basetables(mvc *sql, sql_rel *rel, list *tables )
46{
47 if (THRhighwater()) {
48 (void) sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
49 return;
50 }
51
52 if (!rel)
53 return;
54 switch (rel->op) {
55 case op_basetable: {
56 sql_table *t = rel->l;
57
58 if (t && isTable(t))
59 append(tables, rel);
60 break;
61 }
62 case op_table:
63 break;
64 case op_join:
65 case op_left:
66 case op_right:
67 case op_full:
68 case op_union:
69 case op_inter:
70 case op_except:
71 if (rel->l)
72 find_basetables(sql, rel->l, tables);
73 if (rel->r)
74 find_basetables(sql, rel->r, tables);
75 break;
76 case op_semi:
77 case op_anti:
78 case op_groupby:
79 case op_project:
80 case op_select:
81 case op_topn:
82 case op_sample:
83 if (rel->l)
84 find_basetables(sql, rel->l, tables);
85 break;
86 case op_ddl:
87 break;
88 case op_insert:
89 case op_update:
90 case op_delete:
91 case op_truncate:
92 if (rel->r)
93 find_basetables(sql, rel->r, tables);
94 break;
95 }
96}
97
98static sql_rel *
99_rel_partition(mvc *sql, sql_rel *rel)
100{
101 list *tables = sa_list(sql->sa);
102 /* find basetable relations */
103 /* mark one (largest) with REL_PARTITION */
104 find_basetables(sql, rel, tables);
105 if (list_length(tables)) {
106 sql_rel *r;
107 node *n;
108 int i, mi = 0;
109 lng *sizes = SA_NEW_ARRAY(sql->sa, lng, list_length(tables)), m = 0;
110
111 for(i=0, n = tables->h; n; i++, n = n->next) {
112 r = n->data;
113 sizes[i] = rel_getcount(sql, r);
114 if (sizes[i] > m) {
115 m = sizes[i];
116 mi = i;
117 }
118 }
119 for(i=0, n = tables->h; i<mi; i++, n = n->next)
120 ;
121 r = n->data;
122 /* TODO, we now pick first (okay?)! In case of self joins we need to pick the correct table */
123 r->flag = REL_PARTITION;
124 }
125 return rel;
126}
127
128static int
129has_groupby(sql_rel *rel)
130{
131 if (rel->op == op_groupby)
132 return 1;
133 if (is_join(rel->op))
134 return has_groupby(rel->l) || has_groupby(rel->r);
135 if ((is_select(rel->op) || is_project(rel->op)) && rel->l)
136 return has_groupby(rel->l);
137 return 0;
138}
139
140sql_rel *
141rel_partition(mvc *sql, sql_rel *rel)
142{
143 if (THRhighwater())
144 return sql_error(sql, 10, SQLSTATE(42000) "Query too complex: running out of stack space");
145 (void)sql;
146 if (rel->op == op_basetable) {
147 rel->flag = REL_PARTITION;
148 } else if ((rel->op == op_topn || rel->op == op_sample || rel->op == op_select) && rel->l) {
149 rel_partition(sql, rel->l);
150 } else if (is_modify(rel->op) && rel->card <= CARD_AGGR) {
151 if (rel->r)
152 rel_partition(sql, rel->r);
153 } else if (is_project(rel->op) && rel->l) {
154 rel_partition(sql, rel->l);
155 } else if (rel->op == op_semi && rel->l && rel->r) {
156 rel_partition(sql, rel->l);
157 rel_partition(sql, rel->r);
158 } else if (rel->op == op_anti && rel->l && rel->r) {
159 rel_partition(sql, rel->l);
160 rel_partition(sql, rel->r);
161 } else if (is_join(rel->op)) {
162 if (has_groupby(rel->l) || has_groupby(rel->r)) {
163 rel_partition(sql, rel->l);
164 rel_partition(sql, rel->r);
165 }
166 else
167 _rel_partition(sql, rel);
168 }
169 return rel;
170}
171