LCOV - code coverage report
Current view: top level - sql/server - rel_planner.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 0 419 0.0 %
Date: 2021-10-13 02:24:04 Functions: 0 31 0.0 %

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

Generated by: LCOV version 1.14