Update of /cvsroot/monetdb/sql/src/server
In directory 23jxhf1.ch3.sourceforge.com:/tmp/cvs-serv21211/src/server
Modified Files:
rel_exp.mx rel_optimizer.mx
Log Message:
detect related expressions in or lists. The detect expressions are then
merged (as much as possible) and added as filters before the or's
are handled.
fixed problem with join orders. Sofar the join order was only based
on join expressions. Now we also make sure the selections expressions
are weigth too.
U rel_exp.mx
Index: rel_exp.mx
===================================================================
RCS file: /cvsroot/monetdb/sql/src/server/rel_exp.mx,v
retrieving revision 1.34
retrieving revision 1.35
diff -u -d -r1.34 -r1.35
--- rel_exp.mx 7 Aug 2009 21:24:39 -0000 1.34
+++ rel_exp.mx 19 Aug 2009 19:53:27 -0000 1.35
@@ -76,6 +76,9 @@
extern int exp_cmp( sql_exp *e1, sql_exp *e2);
extern int exp_match( sql_exp *e1, sql_exp *e2);
extern int exp_match_exp( sql_exp *e1, sql_exp *e2);
+/* match just the column (cmp equality) expressions */
+extern int exp_match_col_exps( sql_exp *e, list *l);
+extern int exps_match_col_exps( sql_exp *e1, sql_exp *e2);
extern int exp_is_join(sql_exp *e);
extern int exp_is_eqjoin(sql_exp *e);
extern int exp_is_correlation(sql_exp *e, sql_rel *r );
@@ -514,6 +517,60 @@
return 0;
}
+int
+exp_match_col_exps( sql_exp *e, list *l)
+{
+ node *n;
+
+ for(n=l->h; n; n = n->next) {
+ sql_exp *re = n->data;
+ sql_exp *re_r = re->r;
+
+ if (re->type == e_cmp && re->flag == cmp_or)
+ return exp_match_col_exps(e, re->l) &&
+ exp_match_col_exps(e, re->r);
+
+ if (re->type != e_cmp || /*re->flag != cmp_equal ||*/ !re_r ||
re_r->card != 1 || !exp_match_exp(e, re->l))
+ return 0;
+ }
+ return 1;
+}
+
+int
+exps_match_col_exps( sql_exp *e1, sql_exp *e2)
+{
+ sql_exp *e1_r = e1->r;
+ sql_exp *e2_r = e2->r;
+
+ if (e1->type != e_cmp || e2->type != e_cmp)
+ return 0;
+
+ if (e1->flag != cmp_or && e1_r && e1_r->card == 1 &&
+ e2->flag != cmp_or && e2_r && e2_r->card == 1)
+ return exp_match_exp(e1->l, e2->l);
+
+ if (e1->flag != cmp_or && e1_r && e1_r->card == 1 &&
+ e2->flag == cmp_or)
+ return exp_match_col_exps(e1->l, e2->l) &&
+ exp_match_col_exps(e1->l, e2->r);
+
+ if (e1->flag == cmp_or &&
+ e2->flag != cmp_or && e2_r && e2_r->card == 1)
+ return exp_match_col_exps(e2->l, e1->l) &&
+ exp_match_col_exps(e2->l, e1->r);
+
+ if (e1->flag == cmp_or && e2->flag == cmp_or) {
+ list *l = e1->l, *r = e1->r;
+ sql_exp *el = l->h->data;
+ sql_exp *er = r->h->data;
+
+ return list_length(l) == 1 && list_length(r) == 1 &&
+ exps_match_col_exps(el, e2) &&
+ exps_match_col_exps(er, e2);
+ }
+ return 0;
+}
+
int
exp_match_list( list *l, list *r)
{
@@ -560,14 +617,13 @@
if (e1->flag == e2->flag && e1->flag != cmp_or &&
exp_match_exp(e1->l, e2->l) &&
exp_match_exp(e1->r, e2->r) &&
- ((!e1->f && !e1->f) || exp_match_exp(e1->f, e2->f)))
+ ((!e1->f && !e2->f) || exp_match_exp(e1->f, e2->f)))
return 1;
else if (e1->flag == e2->flag && e1->flag == cmp_or &&
exp_match_list(e1->l, e2->l) &&
exp_match_list(e1->r, e2->r))
return 1;
break;
- break;
case e_convert:
if (!subtype_cmp(exp_totype(e1), exp_totype(e2)) &&
!subtype_cmp(exp_fromtype(e1), exp_fromtype(e2)) &&
U rel_optimizer.mx
Index: rel_optimizer.mx
===================================================================
RCS file: /cvsroot/monetdb/sql/src/server/rel_optimizer.mx,v
retrieving revision 1.68
retrieving revision 1.69
diff -u -d -r1.68 -r1.69
--- rel_optimizer.mx 7 Aug 2009 21:24:43 -0000 1.68
+++ rel_optimizer.mx 19 Aug 2009 19:53:27 -0000 1.69
@@ -479,6 +479,41 @@
}
}
+list *
+order_join_expressions(list *dje, list *rels)
+{
+ list *res = list_create(dje->destroy);
+ node *n = NULL;
+ int i, j, *keys, *pos, cnt = list_length(dje);
+
+ keys = (int*)alloca(cnt*sizeof(int));
+ pos = (int*)alloca(cnt*sizeof(int));
+ for (n = dje->h, i = 0; n; n = n->next, i++) {
+ sql_exp *e = n->data;
+
+ keys[i] = exp_keyvalue(e);
+ /* add some weigth for the selections */
+ if (e->type == e_cmp) {
+ sql_rel *l = find_rel(rels, e->l);
+ sql_rel *r = find_rel(rels, e->r);
+
+ if (l && is_select(l->op))
+ keys[i] += list_length(l->exps)*10;
+ if (r && is_select(r->op))
+ keys[i] += list_length(r->exps)*10;
+ }
+ pos[i] = i;
+ }
+ /* sort descending */
+ GDKqsort_rev(keys, pos, NULL, cnt, sizeof(int), sizeof(int), TYPE_int);
+ for(j=0; j<cnt; j++) {
+ for(n = dje->h, i = 0; n && i != pos[j]; n = n->next, i++)
+ ;
+ list_append(res, exp_dup(n->data));
+ }
+ return res;
+}
+
static list *
find_fk(list *rels, list *exps)
{
@@ -565,7 +600,7 @@
list_destroy(aje);
/* sort expressions on weighted number of reducing operators */
- sdje = list_sort(dje, (fkeyvalue)&exp_keyvalue, (fdup)&exp_dup);
+ sdje = order_join_expressions(dje, rels);
list_destroy(dje);
return sdje;
@@ -1400,6 +1435,7 @@
append(oexps, exp_or(list_dup(l, (fdup)&exp_dup),
list_dup(r, (fdup)&exp_dup)));
}
+
if (l != ol)
list_destroy(l);
if (r != or)
@@ -1433,6 +1469,143 @@
return rel;
}
+static list *
+exps_merge_rse( list *l, list *r )
+{
+ node *n, *m, *o;
+ list *nexps = NULL, *lexps, *rexps;
+
+ lexps = new_exp_list();
+ for (n = l->h; n; n = n->next) {
+ sql_exp *e = n->data;
+
+ if (e->type == e_cmp && e->flag == cmp_or) {
+ list *nexps = exps_merge_rse(e->l, e->r);
+ if (nexps) {
+ for (o = nexps->h; o; o = o->next)
+ append(lexps, exp_dup(o->data));
+ list_destroy(nexps);
+ nexps = NULL;
+ }
+ }
+ }
+ rexps = new_exp_list();
+ for (n = r->h; n; n = n->next) {
+ sql_exp *e = n->data;
+
+ if (e->type == e_cmp && e->flag == cmp_or) {
+ list *nexps = exps_merge_rse(e->l, e->r);
+ if (nexps) {
+ for (o = nexps->h; o; o = o->next)
+ append(rexps, exp_dup(o->data));
+ list_destroy(nexps);
+ nexps = NULL;
+ }
+ }
+ }
+
+ /* merge merged lists first ? */
+ nexps = new_exp_list();
+
+ for (n = lexps->h; n; n = n->next) {
+ sql_exp *le = n->data, *re, *fnd = NULL;
+
+ if (le->type != e_cmp || le->flag != cmp_or)
+ continue;
+ for (m = rexps->h; m; m = m->next) {
+ re = m->data;
+ if (exps_match_col_exps(le, re))
+ fnd = re;
+ }
+ for (m = r->h; !fnd && m; m = m->next) {
+ re = m->data;
+ if (exps_match_col_exps(le, re))
+ fnd = re;
+ }
+ if (fnd) {
+ le = exp_dup(le);
+ re = exp_dup(fnd);
+ fnd = exp_or(append(new_exp_list(),le),
+ append(new_exp_list(),re));
+ append(nexps, fnd);
+ }
+ }
+ for (n = l->h; n; n = n->next) {
+ sql_exp *le = n->data, *re, *fnd = NULL;
+
+ if (le->type != e_cmp /*||
+ (le->flag != cmp_or && le->flag != cmp_equal)*/)
+ continue;
+
+ for (m = lexps->h; !fnd && m; m = m->next) {
+ re = m->data;
+ if (exps_match_col_exps(le, re))
+ fnd = re;
+ }
+ if (fnd)
+ continue;
+ for (m = rexps->h; m; m = m->next) {
+ re = m->data;
+ if (exps_match_col_exps(le, re))
+ fnd = re;
+ }
+ for (m = r->h; !fnd && m; m = m->next) {
+ re = m->data;
+ if (exps_match_col_exps(le, re))
+ fnd = re;
+ }
+ if (fnd) {
+ le = exp_dup(le);
+ re = exp_dup(fnd);
+ fnd = exp_or(append(new_exp_list(),le),
+ append(new_exp_list(),re));
+ append(nexps, fnd);
+ }
+ }
+ return nexps;
+}
+
+
+/* merge related sub expressions */
+static sql_rel *
+rel_merge_rse(int *changes, mvc *sql, sql_rel *rel)
+{
+ /* only execute once per select, ie don't return changes */
+
+ (void)sql;
+ *changes = 0;
+ if (rel->op == op_select && !rel_is_ref(rel) && rel->exps) {
+ node *n, *o;
+ list *nexps = NULL;
+
+ for (n=rel->exps->h; n; n = n->next) {
+ sql_exp *e = n->data;
+
+ if (e->type == e_cmp && e->flag == cmp_or) {
+ /* possibly merge related expressions */
+ list *lexps = exps_merge_rse(e->l, e->r);
+ if (lexps) {
+ if (!nexps) {
+ nexps = lexps;
+ } else {
+ for (o = lexps->h; o; o =
o->next)
+ append(nexps,
exp_dup(o->data));
+ list_destroy(lexps);
+ lexps = NULL;
+ }
+ }
+ }
+ }
+ if (nexps) {
+ for (o = nexps->h; o; o = o->next)
+ append(rel->exps, exp_dup(o->data));
+ list_destroy(nexps);
+ nexps = NULL;
+ }
+ }
+ return rel;
+}
+
/*
* Push select down, pushes the selects through (simple) projections. Also
* it cleans up the projections which become useless.
@@ -2630,13 +2803,18 @@
exp_merge_range(list *exps)
{
node *n, *m;
- for (n=exps->h; n && n->next; n = n->next) {
+ for (n=exps->h; n; n = n->next) {
sql_exp *e = n->data;
sql_exp *le = e->l;
sql_exp *re = e->r;
+ /* handle the and's in the or lists */
+ if (e->type == e_cmp && e->flag == cmp_or) {
+ e->l = exp_merge_range(e->l);
+ e->r = exp_merge_range(e->r);
/* only look for gt, gte, lte, lt */
- if (e->type == e_cmp && e->flag < cmp_equal &&
+ } else if (n->next &&
+ e->type == e_cmp && e->flag < cmp_equal &&
re->card == CARD_ATOM) {
for (m=n->next; m; m = m->next) {
sql_exp *f = m->data;
@@ -2672,7 +2850,8 @@
return exp_merge_range(exps);
}
}
- } else if (e->type == e_cmp && e->flag < cmp_equal &&
+ } else if (n->next &&
+ e->type == e_cmp && e->flag < cmp_equal &&
re->card > CARD_ATOM) {
for (m=n->next; m; m = m->next) {
sql_exp *f = m->data;
@@ -2888,9 +3067,15 @@
if (gp.cnt[op_project])
rel = rewrite(sql, rel, &rel_merge_projects);
+ if (gp.cnt[op_join] ||
+ gp.cnt[op_left] || gp.cnt[op_right] || gp.cnt[op_full] ||
+ gp.cnt[op_select])
+ rel = rewrite(sql, rel, &rel_find_range);
+
if (gp.cnt[op_union]) {
rel = rewrite(sql, rel, &rel_merge_union);
rel = rewrite(sql, rel, &rel_cse);
+ rel = rewrite(sql, rel, &rel_merge_rse);
}
/* Remove unused expressions */
@@ -2935,11 +3120,6 @@
if (gp.cnt[op_select])
rel = rewrite(sql, rel, &rel_select_order);
- if (gp.cnt[op_join] ||
- gp.cnt[op_left] || gp.cnt[op_right] || gp.cnt[op_full] ||
- gp.cnt[op_select])
- rel = rewrite(sql, rel, &rel_find_range);
-
if (gp.cnt[op_select])
rel = rewrite(sql, rel, &rel_select_use_index);
------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now. http://p.sf.net/sfu/bobj-july
_______________________________________________
Monetdb-sql-checkins mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/monetdb-sql-checkins
