Line data Source code
1 : /*
2 : * SPDX-License-Identifier: MPL-2.0
3 : *
4 : * This Source Code Form is subject to the terms of the Mozilla Public
5 : * License, v. 2.0. If a copy of the MPL was not distributed with this
6 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7 : *
8 : * Copyright 2024 MonetDB Foundation;
9 : * Copyright August 2008 - 2023 MonetDB B.V.;
10 : * Copyright 1997 - July 2008 CWI.
11 : */
12 :
13 : #include "monetdb_config.h"
14 : #include "rel_planner.h"
15 : #include "rel_rel.h"
16 : #include "rel_exp.h"
17 : #include "rel_prop.h"
18 : #include "rel_rewriter.h"
19 : #include "sql_storage.h"
20 :
21 : typedef struct memoitem {
22 : const char *name;
23 : list *rels;
24 : list *exps;
25 : list *joins;
26 : int done;
27 : int level;
28 : lng count;
29 : lng width;
30 : dbl cost;
31 : void *data;
32 : } memoitem;
33 :
34 : #define p_pkey 1
35 : #define p_fkey 2
36 : #define p_ukey 3
37 :
38 : typedef struct memojoin {
39 : memoitem *l, *r;
40 : int rules; /* handled rules */
41 : int prop; /* pkey, fkey, ukey */
42 : dbl cost;
43 : dbl sel;
44 : sql_exp *e;
45 : } memojoin;
46 :
47 : static int
48 0 : memoitem_key( memoitem *mi )
49 : {
50 0 : return hash_key(mi->name);
51 : }
52 :
53 : static memoitem*
54 0 : memo_find(list *memo, const char *name)
55 : {
56 0 : int key = hash_key(name);
57 0 : sql_hash_e *he;
58 :
59 0 : he = memo->ht->buckets[key&(memo->ht->size-1)];
60 0 : for (; he; he = he->chain) {
61 0 : memoitem *mi = he->value;
62 :
63 0 : if (mi->name && strcmp(mi->name, name) == 0)
64 0 : return mi;
65 : }
66 : return NULL;
67 : }
68 :
69 : static char *
70 0 : merge_names( allocator *sa, const char *lname, const char *rname)
71 : {
72 0 : size_t l = strlen(lname) + strlen(rname) + 2;
73 0 : char *n = SA_NEW_ARRAY(sa, char, l);
74 0 : const char *p = lname;
75 0 : const char *c;
76 :
77 0 : while ((c = strchr(p, ',')) != NULL) {
78 0 : if (strncmp(p, rname, c - p) > 0) {
79 0 : if (p > lname)
80 0 : snprintf(n, l, "%.*s,%s,%s", (int) (c - lname),
81 : lname, rname, c + 1);
82 : else
83 0 : snprintf(n, l, "%s,%s", rname, lname);
84 0 : return n;
85 : }
86 0 : p = c + 1;
87 : }
88 0 : snprintf(n, l, "%s,%s", lname, rname);
89 0 : return n;
90 : }
91 :
92 : static memoitem *
93 0 : memoitem_create( list *memo, allocator *sa, const char *lname, const char *rname, int level)
94 : {
95 0 : const char *name = lname;
96 0 : memoitem *mi;
97 :
98 0 : if (level > 1)
99 0 : name = merge_names(sa, lname, rname);
100 0 : if (memo_find(memo, name))
101 : return NULL;
102 0 : mi = SA_NEW(sa, memoitem);
103 0 : mi->name = sa_strdup(sa, name);
104 0 : mi->joins = (rname)?sa_list(sa):NULL;
105 0 : mi->done = (rname)?0:1;
106 0 : mi->level = level;
107 0 : mi->count = 1;
108 0 : mi->cost = 0;
109 0 : mi->width = 8;
110 0 : mi->data = NULL;
111 0 : mi->rels = sa_list(sa);
112 0 : mi->exps = sa_list(sa);
113 0 : list_append(memo, mi);
114 0 : return mi;
115 : }
116 :
117 : static lng
118 0 : rel_getcount(mvc *sql, sql_rel *rel)
119 : {
120 0 : if (!sql->session->tr)
121 : return 0;
122 :
123 0 : switch(rel->op) {
124 0 : case op_basetable: {
125 0 : sql_table *t = rel->l;
126 :
127 0 : if (t && isTable(t)) {
128 0 : sqlstore *store = sql->session->tr->store;
129 0 : return (lng)store->storage_api.count_col(sql->session->tr, ol_first_node(t->columns)->data, 0);
130 : }
131 : return 0;
132 : }
133 0 : case op_select:
134 : case op_project:
135 0 : if (rel->l)
136 : return rel_getcount(sql, rel->l);
137 : return 1;
138 : default:
139 : return 0;
140 : }
141 : }
142 :
143 : static lng
144 0 : rel_getwidth(mvc *sql, sql_rel *rel)
145 : {
146 0 : if (!sql->session->tr)
147 : return 0;
148 :
149 0 : switch(rel->op) {
150 0 : case op_basetable: {
151 0 : sql_table *t = rel->l;
152 :
153 0 : if (t && isTable(t))
154 0 : return 4*list_length(rel->exps);
155 : return 0;
156 : }
157 0 : case op_select:
158 0 : if (rel->l)
159 : return rel_getwidth(sql, rel->l);
160 : return 1;
161 0 : case op_project:
162 0 : if (rel->l)
163 0 : return 4*list_length(rel->exps);
164 : return 1;
165 : default:
166 : return 0;
167 : }
168 : }
169 :
170 : static lng
171 0 : exp_getdcount( mvc *sql, sql_rel *r , sql_exp *e, lng count)
172 : {
173 0 : switch(e->type) {
174 0 : case e_column: {
175 : /* find col */
176 0 : sql_rel *bt = NULL;
177 0 : sql_column *c = name_find_column(r, e->l, e->r, -1, &bt);
178 0 : if (c) {
179 0 : lng dcount = (lng)sql_trans_dist_count(sql->session->tr, c);
180 0 : if (dcount != 0 && dcount < count)
181 : return dcount;
182 : }
183 : return count;
184 : }
185 : case e_cmp:
186 0 : assert(0);
187 :
188 :
189 : case e_convert:
190 0 : if (e->l)
191 : return exp_getdcount(sql, r, e->l, count);
192 : /* fall through */
193 : case e_func:
194 : case e_aggr:
195 : case e_atom:
196 : case e_psm:
197 : return count;
198 : }
199 : return count;
200 : }
201 :
202 : static int
203 0 : exp_getranges( mvc *sql, sql_rel *r , sql_exp *e, void **min, void **max)
204 : {
205 0 : switch(e->type) {
206 0 : case e_column: {
207 : /* find col */
208 0 : sql_rel *bt = NULL;
209 0 : sql_column *c = name_find_column(r, e->l, e->r, -1, &bt);
210 0 : if (c)
211 0 : return sql_trans_ranges(sql->session->tr, c, min, max);
212 : return 0;
213 : }
214 : case e_cmp:
215 0 : assert(0);
216 :
217 : case e_convert:
218 0 : if (e->l)
219 : return exp_getranges(sql, r, e->l, min, max);
220 : /* fall through */
221 : case e_func:
222 : case e_aggr:
223 : case e_atom:
224 : case e_psm:
225 : return 0;
226 : }
227 : return 0;
228 : }
229 :
230 : static atom *
231 0 : exp_getatom( mvc *sql, sql_exp *e, atom *m)
232 : {
233 0 : if (is_atom(e->type))
234 0 : return exp_value(sql, e);
235 0 : else if (e->type == e_convert)
236 0 : return exp_getatom(sql, e->l, m);
237 0 : else if (e->type == e_func) {
238 0 : sql_subfunc *f = e->f;
239 0 : list *l = e->l;
240 : /* handle date + x months */
241 : /* TODO add scalar -> value, ie exp->stmt-tree->exec-tree+exec */
242 0 : if (strcmp(f->func->base.name, "sql_add") == 0 && list_length(l) == 2) {
243 0 : atom *l1 = exp_getatom(sql, l->h->data, m);
244 0 : atom *l2 = exp_getatom(sql, l->h->next->data, m);
245 : /* data + months */
246 0 : (void)l2;
247 0 : (void)l1;
248 0 : return NULL;
249 : }
250 : }
251 : return m;
252 : }
253 :
254 : static dbl
255 0 : exp_getrange_sel( mvc *sql, sql_rel *r, sql_exp *e, void *min, void *max)
256 : {
257 0 : atom *amin, *amax, *emin, *emax;
258 0 : dbl sel = 1.0;
259 0 : sql_subtype *t = exp_subtype(e->l);
260 :
261 0 : (void)r;
262 0 : emin = amin = atom_general_ptr(sql->sa, t, min);
263 0 : emax = amax = atom_general_ptr(sql->sa, t, max);
264 :
265 0 : if (e->f || e->flag == cmp_gt || e->flag == cmp_gte)
266 0 : emin = exp_getatom(sql, e->r, amin);
267 0 : if (e->f || e->flag == cmp_lt || e->flag == cmp_lte)
268 0 : emax = (e->f)?exp_getatom(sql, e->f, amax):
269 0 : exp_getatom(sql, e->r, amax);
270 :
271 0 : if (!amin || !amax)
272 : return 0.1;
273 :
274 0 : if (!emin || !emax)
275 : sel = 0.125;
276 : /* 4 case, dbl and lng, date, timestamp */
277 0 : else if (t->type->eclass == EC_DATE) {
278 0 : sel = (emax->data.val.ival-emin->data.val.ival)/(dbl)(amax->data.val.ival-amin->data.val.ival);
279 0 : } else if (t->type->eclass == EC_TIMESTAMP || t->type->eclass == EC_TIMESTAMP_TZ) {
280 0 : sel = (emax->data.val.lval-emin->data.val.lval)/(dbl)(amax->data.val.lval-amin->data.val.lval);
281 0 : } else if (t->type->eclass == EC_FLT) {
282 0 : sel = (emax->data.val.dval-emin->data.val.dval)/(amax->data.val.dval-amin->data.val.dval);
283 : } else { /* lng */
284 0 : sel = (emax->data.val.lval-emin->data.val.lval)/(dbl)(amax->data.val.lval-amin->data.val.lval);
285 : }
286 : return sel;
287 : }
288 :
289 : static dbl
290 0 : rel_exp_selectivity(mvc *sql, sql_rel *r, sql_exp *e, lng count)
291 : {
292 0 : dbl sel = 1.0;
293 :
294 0 : if (!e)
295 : return 1.0;
296 0 : switch(e->type) {
297 0 : case e_cmp: {
298 0 : lng dcount = exp_getdcount( sql, r, e->l, count);
299 :
300 0 : switch (e->flag) {
301 0 : case cmp_equal: {
302 0 : sel = 1.0/dcount;
303 0 : break;
304 : }
305 0 : case cmp_notequal:
306 0 : sel = (dcount-1.0)/dcount;
307 0 : break;
308 0 : case cmp_gt:
309 : case cmp_gte:
310 : case cmp_lt:
311 : case cmp_lte: {
312 0 : void *min, *max;
313 0 : if (exp_getranges( sql, r, e->l, &min, &max )) {
314 0 : sel = (dbl)exp_getrange_sel( sql, r, e, min, max);
315 : } else {
316 0 : sel = 0.5;
317 0 : if (e->f) /* range */
318 0 : sel = 0.25;
319 : }
320 0 : } break;
321 : case cmp_filter:
322 : sel = 0.01;
323 : break;
324 0 : case cmp_in:
325 : case cmp_notin: {
326 0 : list *l = e->r;
327 0 : sel = (dbl) list_length(l) / dcount;
328 0 : break;
329 : }
330 : case cmp_or:
331 0 : sel = 0.5;
332 : break;
333 : default:
334 : return 1.0;
335 : }
336 : break;
337 : }
338 : default:
339 : break;
340 : }
341 : return sel;
342 : }
343 :
344 : static dbl
345 0 : rel_join_exp_selectivity(mvc *sql, sql_rel *l, sql_rel *r, sql_exp *e, lng lcount, lng rcount)
346 : {
347 0 : dbl sel = 1.0;
348 0 : lng ldcount, rdcount;
349 :
350 0 : if (!e)
351 : return 1.0;
352 0 : assert(lcount);
353 0 : assert(rcount);
354 0 : ldcount = exp_getdcount(sql, l, e->l, lcount);
355 0 : rdcount = exp_getdcount(sql, r, e->r, rcount);
356 0 : switch(e->type) {
357 0 : case e_cmp:
358 0 : switch (e->flag) {
359 0 : case cmp_equal:
360 0 : sel = (lcount/(dbl)ldcount)*(rcount/(dbl)rdcount);
361 0 : break;
362 0 : case cmp_notequal: {
363 0 : dbl cnt = (lcount/(dbl)ldcount)*(rcount/(dbl)rdcount);
364 0 : sel = (cnt-1)/cnt;
365 0 : } break;
366 0 : case cmp_gt:
367 : case cmp_gte:
368 : case cmp_lt:
369 : case cmp_lte:
370 : /* ugh */
371 0 : sel = 0.5;
372 0 : if (e->f) /* range */
373 : sel = 0.2;
374 : break;
375 : case cmp_filter:
376 : sel = 0.1;
377 : break;
378 0 : case cmp_in:
379 : case cmp_notin: {
380 0 : lng cnt = lcount*rcount;
381 0 : list *l = e->r;
382 0 : sel = (dbl) list_length(l) / cnt;
383 0 : break;
384 : }
385 : case cmp_or:
386 : sel = 0.5;
387 : break;
388 : default:
389 : return 1.0;
390 : }
391 : break;
392 : default:
393 : break;
394 : }
395 0 : assert(sel >= 0.000001);
396 : return sel;
397 : }
398 :
399 :
400 : static dbl
401 0 : rel_exps_selectivity(mvc *sql, sql_rel *rel, list *exps, lng count)
402 : {
403 0 : node *n;
404 0 : dbl sel = 1.0;
405 0 : if (!exps->h)
406 : return 1.0;
407 0 : for(n=exps->h; n; n = n->next) {
408 0 : dbl nsel = rel_exp_selectivity(sql, rel, n->data, count);
409 :
410 0 : sel *= nsel;
411 : }
412 : return sel;
413 : }
414 :
415 : /* need real values, ie
416 : * point select on pkey -> 1 value -> selectivity count
417 : */
418 :
419 : static dbl
420 0 : rel_getsel(mvc *sql, sql_rel *rel, lng count)
421 : {
422 0 : if (!sql->session->tr)
423 : return 1.0;
424 :
425 0 : switch(rel->op) {
426 0 : case op_select:
427 0 : return rel_exps_selectivity(sql, rel, rel->exps, count);
428 0 : case op_project:
429 0 : if (rel->l)
430 : return rel_getsel(sql, rel->l, count);
431 : /* fall through */
432 : default:
433 : return 1.0;
434 : }
435 : }
436 :
437 : static list*
438 0 : memo_create(mvc *sql, list *rels )
439 : {
440 0 : int len = list_length(rels);
441 0 : list *memo = sa_list(sql->sa);
442 0 : node *n;
443 :
444 0 : memo->ht = hash_new(sql->sa, len*len, (fkeyvalue)&memoitem_key);
445 0 : for(n = rels->h; n; n = n->next) {
446 0 : sql_rel *r = n->data;
447 0 : memoitem *mi = memoitem_create(memo, sql->sa, rel_name(r), NULL, 1);
448 0 : dbl sel = 1;
449 :
450 0 : mi->count = rel_getcount(sql, r);
451 0 : sel = rel_getsel(sql, r, mi->count);
452 0 : mi->count = MAX( (lng) (mi->count*sel), 1);
453 0 : assert(mi->count);
454 0 : mi->width = rel_getwidth(sql, r);
455 0 : mi->cost = (dbl)(mi->count*mi->width);
456 0 : mi->data = r;
457 0 : append(mi->rels, r);
458 : }
459 0 : return memo;
460 : }
461 :
462 : static void
463 0 : memo_add_exps(list *memo, mvc *sql, list *rels, list *jes)
464 : {
465 0 : node *n;
466 0 : memoitem *mi;
467 :
468 0 : for(n = jes->h; n; n = n->next) {
469 0 : sql_exp *e = n->data;
470 0 : if (e->type != e_cmp || !is_complex_exp(e->flag)){
471 0 : sql_rel *l = find_one_rel(rels, e->l);
472 0 : sql_rel *r = find_one_rel(rels, e->r);
473 0 : memojoin *mj = SA_ZNEW(sql->sa, memojoin);
474 :
475 0 : mj->l = memo_find( memo, rel_name(l));
476 0 : mj->r = memo_find( memo, rel_name(r));
477 0 : mj->rules = 0;
478 0 : mj->cost = 0;
479 0 : mj->e = e;
480 0 : mj->sel = rel_join_exp_selectivity(sql, l, r, e, mj->l->count, mj->r->count);
481 :
482 0 : mi = memoitem_create(memo, sql->sa, mj->l->name, mj->r->name, 2);
483 0 : mi->width = (rel_getwidth(sql, l) + rel_getwidth(sql, r))/2;
484 0 : mi->data = e;
485 0 : mi->count = (lng)(mj->sel * MIN(mj->l->count, mj->r->count));
486 0 : append(mi->rels, l);
487 0 : append(mi->rels, r);
488 0 : append(mi->exps, e);
489 0 : list_append(mi->joins, mj);
490 : }
491 : }
492 0 : }
493 :
494 : static int
495 0 : memoitem_has( memoitem *mi, const char *name)
496 : {
497 0 : if (mi->level > 1) {
498 0 : memojoin *mj = mi->joins->h->data;
499 :
500 0 : return (memoitem_has(mj->l, name) ||
501 0 : memoitem_has(mj->r, name));
502 : } else {
503 0 : return strcmp(mi->name, name) == 0;
504 : }
505 : }
506 :
507 : static void
508 0 : memoitem_add_attr(list *memo, mvc *sql, memoitem *mi, list *rels, list *jes, int level)
509 : {
510 0 : node *n;
511 :
512 0 : for( n = jes->h; n; n = n->next) {
513 0 : sql_exp *e = n->data;
514 :
515 0 : if (e->type != e_cmp || !is_complex_exp(e->flag)){
516 0 : int hasl = 0, hasr = 0;
517 0 : sql_rel *l = find_one_rel(rels, e->l);
518 0 : sql_rel *r = find_one_rel(rels, e->r);
519 :
520 : /* check if exactly one rel is in mi */
521 0 : hasl = memoitem_has(mi, rel_name(l));
522 0 : hasr = memoitem_has(mi, rel_name(r));
523 0 : if (hasl != hasr) {
524 0 : memoitem *nmi;
525 0 : sql_rel *rr = r;
526 :
527 0 : if (!hasl)
528 0 : rr = l;
529 0 : nmi = memoitem_create(memo, sql->sa, mi->name, rel_name(rr), level);
530 0 : if (nmi) {
531 0 : memojoin *mj = SA_ZNEW(sql->sa, memojoin);
532 0 : lng mincnt = 0;
533 :
534 0 : list_merge(nmi->rels, mi->rels, (fdup)NULL);
535 0 : append(nmi->rels, rr);
536 0 : append(nmi->exps, e);
537 :
538 0 : mj->l = mi;
539 0 : mj->r = memo_find( memo, rel_name(rr));
540 0 : mincnt = MIN(mj->l->count, mj->r->count);
541 0 : nmi->width = mi->width + mj->r->width;
542 0 : mj->rules = 0;
543 0 : mj->cost = 0;
544 0 : mj->sel = rel_join_exp_selectivity(sql, l, r, e, mj->l->count, mj->r->count);
545 0 : list_append(nmi->joins, mj);
546 :
547 0 : if (!nmi->count)
548 0 : nmi->count = (lng)(mincnt*mj->sel);
549 0 : nmi->count = MIN((lng) (mincnt*mj->sel), nmi->count);
550 0 : assert(nmi->count >= 0);
551 : }
552 : }
553 : }
554 : }
555 0 : }
556 :
557 : static void
558 0 : memo_add_attr(list *memo, mvc *sql, list *rels, list *jes)
559 : {
560 0 : node *n;
561 0 : int l, len = list_length(rels);
562 :
563 0 : for(l=2; l<len; l++) {
564 0 : for (n = memo->h; n; n = n->next) {
565 0 : memoitem *mi = n->data;
566 :
567 0 : if (mi->level == l)
568 0 : memoitem_add_attr( memo, sql, mi, rels, jes, l+1);
569 : }
570 : }
571 0 : }
572 :
573 : /* Rule 1: Commutativity A join B -> B join A */
574 : static int
575 0 : memoitem_apply_r1(memoitem *mi, allocator *sa)
576 : {
577 0 : int changes = 0;
578 0 : node *n;
579 :
580 0 : if (!mi->joins)
581 : return 0;
582 0 : for ( n = mi->joins->h; n; n = n->next) {
583 0 : memojoin *mj = n->data;
584 :
585 0 : if (mj->rules == 0 || mj->rules == 2) {
586 0 : memojoin *mjn = SA_ZNEW(sa, memojoin);
587 :
588 0 : mjn->l = mj->r;
589 0 : mjn->r = mj->l;
590 :
591 0 : if (mj->rules)
592 0 : mj->rules = 4;
593 : else
594 0 : mj->rules = 1;
595 0 : mjn->rules = 4;
596 0 : mjn->cost = 0;
597 0 : mjn->sel = mj->sel;
598 0 : list_append(mi->joins, mjn);
599 0 : changes ++;
600 : }
601 : }
602 : return changes;
603 : }
604 :
605 : /* Rule 2: Right Associativity (A join B) join C -> A join (B join C) */
606 : static int
607 0 : memoitem_apply_r2(memoitem *mi, allocator *sa, list *memo)
608 : {
609 0 : int changes = 0;
610 0 : node *n;
611 :
612 0 : if (!mi->joins || mi->level <= 2)
613 : return 0;
614 0 : for ( n = mi->joins->h; n; n = n->next) {
615 0 : memojoin *mj = n->data;
616 :
617 0 : if (mj->rules <= 1 && mj->l->level >= 2) {
618 0 : node *m;
619 :
620 0 : for( m = mj->l->joins->h; m; m = m->next) {
621 0 : memoitem *r = NULL;
622 0 : memojoin *mjl = m->data;
623 : /* combine mjl->r and mj->r */
624 0 : char *name = merge_names(sa, mjl->r->name, mj->r->name);
625 :
626 0 : if ((r = memo_find(memo, name))) {
627 0 : memojoin *mjn = SA_ZNEW(sa, memojoin);
628 :
629 0 : mjn->l = mjl->l;
630 0 : mjn->r = r;
631 0 : mjn->rules = 2;
632 0 : mjn->cost = 0;
633 0 : mjn->sel = 1;
634 0 : list_append(mi->joins, mjn);
635 0 : changes ++;
636 : }
637 : }
638 0 : if (mj->rules)
639 0 : mj->rules = 4;
640 : else
641 0 : mj->rules = 2;
642 : }
643 : }
644 : return changes;
645 : }
646 :
647 : /* Rule 4: Exchange (A join B) join (C join D) -> (A join C) join (B join D)
648 : static int
649 : memoitem_apply_r4(memoitem *mi, allocator *sa, list *memo)
650 : {
651 : int changes = 0;
652 : node *n;
653 :
654 : if (!mi->joins || mi->level <= 2)
655 : return 0;
656 : for ( n = mi->joins->h; n; n = n->next) {
657 : memojoin *mj = n->data;
658 :
659 : if (mj->rules <= 1 && mj->l->level >= 2) {
660 : node *m;
661 :
662 : for( m = mj->l->joins->h; m; m = m->next) {
663 : memoitem *r = NULL;
664 : memojoin *mjl = m->data;
665 : char *name = merge_names(sa, mjl->r->name, mj->r->name);
666 :
667 : if ((r = memo_find(memo, name))) {
668 : memojoin *mjn = SA_ZNEW(sa, memojoin);
669 :
670 : mjn->l = mjl->l;
671 : mjn->r = r;
672 : mjn->rules = 2;
673 : mjn->cost = 0;
674 : list_append(mi->joins, mjn);
675 : changes ++;
676 : }
677 : }
678 : if (mj->rules)
679 : mj->rules = 4;
680 : else
681 : mj->rules = 2;
682 : }
683 : }
684 : return changes;
685 : }
686 : * */
687 :
688 : static void
689 0 : memo_apply_rules(list *memo, allocator *sa, int len)
690 : {
691 0 : int level;
692 0 : node *n;
693 :
694 0 : for (level = 2; level<=len; level++) {
695 : int gchanges = 1;
696 :
697 0 : while(gchanges) {
698 0 : gchanges = 0;
699 0 : for ( n = memo->h; n; n = n->next) {
700 0 : int changes = 0;
701 0 : memoitem *mi = n->data;
702 :
703 0 : if (!mi->done && mi->level == level) {
704 0 : changes += memoitem_apply_r1(mi, sa);
705 0 : changes += memoitem_apply_r2(mi, sa, memo);
706 : //changes += memoitem_apply_r4(mi, sa, memo);
707 :
708 0 : if (!changes)
709 0 : mi->done = 1;
710 : }
711 0 : gchanges |= changes;
712 : }
713 : }
714 : }
715 0 : }
716 :
717 : static void
718 0 : memo_locate_exps( list *memo )
719 : {
720 0 : node *n, *m, *o;
721 :
722 0 : for(n = memo->h; n; n = n->next) {
723 0 : memoitem *mi = n->data;
724 0 : int prop = 0;
725 :
726 0 : if (mi->level == 2) {
727 0 : sql_exp *e = mi->data;
728 :
729 0 : if (find_prop(e->p, PROP_HASHIDX))
730 0 : prop = p_pkey;
731 0 : if (find_prop(e->p, PROP_JOINIDX))
732 : prop = p_fkey;
733 :
734 0 : if (prop) {
735 0 : for (m = mi->joins->h; m; m = m->next) {
736 0 : memojoin *mj = m->data;
737 0 : sql_exp *e = mj->e;
738 :
739 0 : mj->prop = prop;
740 0 : if (prop == p_fkey) {
741 0 : sql_rel *l = mj->l->data, *f = NULL;
742 0 : if (!l)
743 0 : continue;
744 0 : if (e)
745 0 : f = find_one_rel(mi->rels, e->l);
746 0 : if (f != l) /* we dislike swapped pkey/fkey joins */
747 0 : mj->prop = 0;
748 : }
749 : }
750 : }
751 0 : } else if (mi->level > 2) {
752 : /* find exp which isn't in the mj->l/r->exps lists */
753 0 : for( o = mi->exps->h; o; o = o->next) {
754 0 : sql_exp *e = o->data;
755 :
756 0 : for (m = mi->joins->h; m; m = m->next) {
757 0 : memojoin *mj = m->data;
758 :
759 0 : if (list_find(mj->l->exps, e, NULL) == NULL &&
760 0 : list_find(mj->r->exps, e, NULL) == NULL) {
761 0 : if (find_prop(e->p, PROP_HASHIDX))
762 0 : prop = p_pkey;
763 0 : if (find_prop(e->p, PROP_JOINIDX))
764 0 : prop = p_fkey;
765 0 : mj->prop = prop;
766 0 : if (prop == p_fkey) {
767 0 : sql_rel *l = find_one_rel(mi->rels, e->l);
768 0 : sql_rel *f = find_one_rel(mj->l->rels, e->l);
769 0 : if (!l)
770 0 : continue;
771 0 : if (f != l) /* we dislike swapped pkey/fkey joins */
772 0 : mj->prop = 0;
773 : }
774 : }
775 : }
776 : }
777 : }
778 : }
779 0 : }
780 :
781 : static void
782 0 : memo_compute_cost(list *memo)
783 : {
784 0 : node *n, *m;
785 :
786 0 : for ( n = memo->h; n; n = n->next) {
787 0 : memoitem *mi = n->data;
788 :
789 0 : if (mi->joins) {
790 0 : lng cnt = 0, width = 1;
791 0 : dbl cost = 0;
792 :
793 : /* cost minimum of join costs */
794 0 : for ( m = mi->joins->h; m; m = m->next ) {
795 0 : memojoin *mj = m->data;
796 :
797 0 : lng mincnt = MIN(mj->l->count, mj->r->count);
798 0 : dbl nsel = mj->sel;
799 0 : lng ocnt = MAX((lng) (mincnt*nsel), 1);
800 0 : dbl ncost = 0;
801 :
802 : /* mincnt*mincnt_size_width*hash_const_cost + mincnt * output_width(for now just sum of width) * memaccess const */
803 : /* current consts are 1 and 1 */
804 : //ncost += ocnt * MIN(mj->l->width, mj->r->width);
805 0 : width = (mj->l->count < mj->r->count)?mj->l->width:mj->r->width;
806 0 : ncost += (mincnt * width * 1 ) + ocnt * (mj->l->width + mj->r->width) * 1;
807 0 : assert(mj->l->cost > 0 && mj->r->cost > 0);
808 0 : ncost += mj->l->cost; /* add cost of left */
809 0 : ncost += mj->r->cost; /* add cost of right */
810 :
811 0 : width = mj->l->width + mj->r->width;
812 0 : mj->cost = ncost;
813 :
814 0 : if (cnt == 0)
815 0 : cnt = ocnt;
816 0 : cnt = MIN(cnt,ocnt);
817 :
818 0 : if (cost == 0)
819 0 : cost = ncost;
820 0 : cost = MIN(cost,ncost);
821 : }
822 0 : assert(cnt > 0);
823 0 : mi->count = cnt;
824 0 : mi->cost = cost;
825 0 : mi->width = width;
826 : }
827 : }
828 0 : }
829 :
830 : static void
831 0 : memojoin_print( memojoin *mj )
832 : {
833 0 : printf("%s join-%s%d(cost=%f) %s", mj->l->name, mj->prop==p_pkey?"pkey":mj->prop==p_fkey?"fkey":"", mj->rules, mj->cost, mj->r->name);
834 0 : }
835 :
836 : static void
837 0 : memojoins_print( list *joins )
838 : {
839 0 : node *n;
840 :
841 0 : if (!joins)
842 : return;
843 0 : for(n=joins->h; n; n = n->next) {
844 0 : memojoin *mj = n->data;
845 :
846 0 : memojoin_print( mj );
847 0 : if (n->next)
848 0 : printf(" | ");
849 : }
850 : }
851 :
852 : static void
853 0 : memoitem_print( memoitem *mi )
854 : {
855 0 : printf("# %s(count="LLFMT",width="LLFMT",cost=%f): ", mi->name, mi->count, mi->width, mi->cost);
856 0 : memojoins_print(mi->joins);
857 0 : }
858 :
859 : static void
860 0 : memo_print( list *memo )
861 : {
862 0 : node *n;
863 0 : int level = 0;
864 :
865 0 : for(n=memo->h; n; n = n->next) {
866 0 : memoitem *mi = n->data;
867 :
868 0 : if (mi->level > level){
869 0 : level = mi->level;
870 0 : printf("\n");
871 : }
872 0 : memoitem_print( mi );
873 0 : printf("\n");
874 : }
875 0 : fflush(stdout);
876 0 : }
877 :
878 : static memojoin *
879 0 : find_cheapest( list *joins )
880 : {
881 0 : node *n;
882 0 : memojoin *cur = NULL;
883 :
884 0 : if (!joins)
885 : return NULL;
886 0 : cur = joins->h->data;
887 0 : for ( n = joins->h; n; n = n->next) {
888 0 : memojoin *mj = n->data;
889 :
890 0 : if (cur->cost > mj->cost)
891 0 : cur = mj;
892 : }
893 : return cur;
894 : }
895 :
896 : static sql_rel *
897 0 : memo_select_plan( mvc *sql, list *memo, memoitem *mi, list *sdje, list *exps)
898 : {
899 0 : if (mi->level >= 2) {
900 0 : memojoin *mj = find_cheapest(mi->joins);
901 0 : sql_rel *top;
902 :
903 0 : top = rel_crossproduct(sql->sa,
904 : memo_select_plan(sql, memo, mj->l, sdje, exps),
905 : memo_select_plan(sql, memo, mj->r, sdje, exps),
906 : op_join);
907 0 : if (mi->level == 2) {
908 0 : rel_join_add_exp(sql->sa, top, mi->data);
909 0 : list_remove_data(sdje, NULL, mi->data);
910 : } else {
911 : node *djn;
912 :
913 : /* all other join expressions on these 2 relations */
914 0 : while((djn = list_find(sdje, mi->rels, (fcmp)&exp_joins_rels)) != NULL) {
915 0 : sql_exp *e = djn->data;
916 :
917 0 : rel_join_add_exp(sql->sa, top, e);
918 0 : list_remove_data(sdje, NULL, e);
919 : }
920 :
921 : /* all other join expressions on these 2 relations */
922 0 : while((djn = list_find(exps, mi->rels, (fcmp)&exp_joins_rels)) != NULL) {
923 0 : sql_exp *e = djn->data;
924 :
925 0 : rel_join_add_exp(sql->sa, top, e);
926 0 : list_remove_data(exps, NULL, e);
927 : }
928 : }
929 0 : set_processed(top);
930 0 : return top;
931 : } else {
932 0 : return mi->data;
933 : }
934 : }
935 :
936 : sql_rel *
937 0 : rel_planner(mvc *sql, list *rels, list *sdje, list *exps)
938 : {
939 0 : list *memo = memo_create(sql, rels);
940 0 : memoitem *mi;
941 0 : sql_rel *top;
942 :
943 : /* extend one attribute at a time */
944 0 : memo_add_exps(memo, sql, rels, sdje);
945 0 : memo_add_attr(memo, sql, rels, sdje);
946 :
947 0 : memo_apply_rules(memo, sql->sa, list_length(rels));
948 0 : memo_locate_exps(memo);
949 0 : memo_compute_cost(memo);
950 : //if (0)
951 0 : memo_print(memo);
952 0 : mi = memo->t->data;
953 0 : top = memo_select_plan(sql, memo, mi, sdje, exps);
954 0 : if (list_length(sdje) != 0)
955 0 : list_merge (top->exps, sdje, (fdup)NULL);
956 0 : return top;
957 : }
|
