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