Update of /cvsroot/monetdb/sql/src/server
In directory sc8-pr-cvs16.sourceforge.net:/tmp/cvs-serv9668/src/server
Modified Files:
rel_bin.mx rel_dump.mx rel_exp.mx rel_optimizer.mx
rel_select.mx sql_optimize.mx
Log Message:
handle range joins efficiently in the algebra version
U rel_select.mx
Index: rel_select.mx
===================================================================
RCS file: /cvsroot/monetdb/sql/src/server/rel_select.mx,v
retrieving revision 1.73
retrieving revision 1.74
diff -u -d -r1.73 -r1.74
--- rel_select.mx 1 Apr 2008 17:04:56 -0000 1.73
+++ rel_select.mx 9 Apr 2008 09:56:23 -0000 1.74
@@ -1652,47 +1652,18 @@
}
static sql_rel *
-rel_compare_exp(mvc *sql, sql_rel *rel, sql_exp *ls, sql_exp *rs, char
*compare_op, sql_exp *esc, int f )
+rel_compare_exp_(mvc *sql, sql_rel *rel, sql_exp *ls, sql_exp *rs, sql_exp
*rs2, int type, int anti )
{
sql_exp *L = ls, *R = rs, *e = NULL;
- comp_type type = cmp_equal;
-
- if (!ls || !rs)
- return NULL;
- if (rel_convert_types(sql, &ls, &rs, 1, type_equal) < 0) {
- if (ls)
- exp_destroy(ls);
- if (rs)
- exp_destroy(rs);
+ if (rel_convert_types(sql, &ls, &rs, 1, type_equal) < 0 ||
+ (rs2 && rel_convert_types(sql, &ls, &rs2, 1, type_equal) < 0)) {
+ exp_destroy(ls);
+ exp_destroy(rs);
+ exp_destroy(rs2);
return NULL;
}
- if (!rel || f == sql_sel || (ls->card <= CARD_ATOM && rs->card <=
CARD_ATOM)) {
- sql_exp *e;
-
- if (compare_op[0] == 'l')
- compare_op = "like";
- if (compare_op[0] == 'n')
- compare_op = "not_like";
- e = rel_binop_(sql, ls, rs, NULL, compare_op);
-
- if (!e)
- return NULL;
- if (f == sql_sel) {
- if (rel->op == op_project) {
- append(rel->exps, e);
- } else {
- list *exps = new_exp_list();
-
- append(exps, e);
- return rel_project(rel, exps);
- }
- } else {
- return rel_select(rel, e);
- }
- }
- type = compare_str2type(compare_op);
- if (type != cmp_like && type != cmp_notlike) {
+ if (!rs2 && type != cmp_like && type != cmp_notlike) {
if (ls->card < rs->card) {
sql_exp *swap = ls;
@@ -1707,8 +1678,10 @@
}
e = exp_compare( ls, rs, type );
} else {
- e = exp_compare2( ls, rs, esc, type );
+ e = exp_compare2( ls, rs, rs2, type );
}
+ if (anti)
+ set_anti(e);
/* atom or row => select */
if (ls->card > rel->card)
@@ -1728,6 +1701,47 @@
}
static sql_rel *
+rel_compare_exp(mvc *sql, sql_rel *rel, sql_exp *ls, sql_exp *rs, char
*compare_op, sql_exp *esc, int f )
+{
+ comp_type type = cmp_equal;
+
+ if (!ls || !rs)
+ return NULL;
+
+ if (!rel || f == sql_sel || (ls->card <= CARD_ATOM && rs->card <=
CARD_ATOM)) {
+ sql_exp *e;
+
+ if (compare_op[0] == 'l')
+ compare_op = "like";
+ if (compare_op[0] == 'n')
+ compare_op = "not_like";
+ if (rel_convert_types(sql, &ls, &rs, 1, type_equal) < 0) {
+ exp_destroy(ls);
+ exp_destroy(rs);
+ return NULL;
+ }
+ e = rel_binop_(sql, ls, rs, NULL, compare_op);
+
+ if (!e)
+ return NULL;
+ if (f == sql_sel) {
+ if (rel->op == op_project) {
+ append(rel->exps, e);
+ } else {
+ list *exps = new_exp_list();
+
+ append(exps, e);
+ return rel_project(rel, exps);
+ }
+ } else {
+ return rel_select(rel, e);
+ }
+ }
+ type = compare_str2type(compare_op);
+ return rel_compare_exp_(sql, rel, ls, rs, esc, type, 0);
+}
+
+static sql_rel *
rel_compare(mvc *sql, sql_rel *rel, symbol *lo, symbol *ro, char *compare_op,
int f )
{
sql_exp *rs = 0, *ls;
@@ -2397,12 +2411,9 @@
}
if (sc->token == SQL_NOT_BETWEEN) {
- /* TODO should be 'or' */
- rel = rel_compare_exp(sql, rel, le, re1, "<", NULL, f);
- rel = rel_compare_exp(sql, rel, exp_dup(le), re2, ">",
NULL, f);
+ rel = rel_compare_exp_(sql, rel, le, re1, re2, 3, 1);
} else {
- rel = rel_compare_exp(sql, rel, le, re1, ">=", NULL, f);
- rel = rel_compare_exp(sql, rel, exp_dup(le), re2, "<=",
NULL, f);
+ rel = rel_compare_exp_(sql, rel, le, re1, re2, 3, 0);
}
return rel;
}
U rel_dump.mx
Index: rel_dump.mx
===================================================================
RCS file: /cvsroot/monetdb/sql/src/server/rel_dump.mx,v
retrieving revision 1.25
retrieving revision 1.26
diff -u -d -r1.25 -r1.26
--- rel_dump.mx 8 Mar 2008 07:27:00 -0000 1.25
+++ rel_dump.mx 9 Apr 2008 09:56:23 -0000 1.26
@@ -131,6 +131,8 @@
break;
case e_cmp:
exp_print(sql, e->l, depth+1, 0, 0);
+ if (is_anti(e))
+ printf(" ! ");
cmp_print(sql, e->flag );
exp_print(sql, e->r, depth+1, 0, 0);
if (e->f) {
U rel_optimizer.mx
Index: rel_optimizer.mx
===================================================================
RCS file: /cvsroot/monetdb/sql/src/server/rel_optimizer.mx,v
retrieving revision 1.14
retrieving revision 1.15
diff -u -d -r1.14 -r1.15
--- rel_optimizer.mx 21 Mar 2008 14:47:57 -0000 1.14
+++ rel_optimizer.mx 9 Apr 2008 09:56:23 -0000 1.15
@@ -299,17 +299,21 @@
case e_cmp:
switch (e->flag) {
case cmp_equal:
- *cnt += 20;
- return 20;
- case cmp_notequal:
*cnt += 10;
return 10;
+ case cmp_notequal:
+ *cnt += 7;
+ return 7;
case cmp_gt:
case cmp_gte:
case cmp_lt:
case cmp_lte:
- *cnt += 4;
- return 4;
+ *cnt += 6;
+ if (e->f){ /* range */
+ *cnt += 6;
+ return 12;
+ }
+ return 6;
case cmp_like:
case cmp_notlike:
*cnt += 2;
@@ -491,7 +495,7 @@
sql_exp *cje;
node *djn;
list *sdje, *n_rels = list_create(NULL);
- int fnd;
+ int fnd = 0;
/* first find the distinct join expressions */
list *aje = list_select(exps, (void*)1, (fcmp) &exp_is_join,
(fdup)exp_dup);
@@ -591,33 +595,33 @@
/* find the involved relations */
l = find_rel(rels, cje->l);
r = find_rel(rels, cje->r);
- list_remove_data(rels, l);
- list_remove_data(rels, r);
- list_append(n_rels, l);
- list_append(n_rels, r);
+ if (l && r) {
+ list_remove_data(rels, l);
+ list_remove_data(rels, r);
+ list_append(n_rels, l);
+ list_append(n_rels, r);
- /* Create a relation between l and r. Since the calling
- functions rewrote the join tree, into a list of expressions
- and a list of (simple) relations, there are no outer joins
- involved, we can simply do a crossproduct here.
- */
- top = rel_crossproduct(l, r, op_join);
- rel_join_add_exp(top, exp_dup(cje));
+ /* Create a relation between l and r. Since the calling
+ functions rewrote the join tree, into a list of expressions
+ and a list of (simple) relations, there are no outer joins
+ involved, we can simply do a crossproduct here.
+ */
+ top = rel_crossproduct(l, r, op_join);
+ rel_join_add_exp(top, exp_dup(cje));
- /* all other join expressions on these 2 relations */
- while((djn = list_find(exps, n_rels, (fcmp)&exp_joins_rels)) != NULL) {
- sql_exp *e = djn->data;
+ /* all other join expressions on these 2 relations */
+ while((djn = list_find(exps, n_rels, (fcmp)&exp_joins_rels)) !=
NULL) {
+ sql_exp *e = djn->data;
- rel_join_add_exp(top, exp_dup(e));
- list_remove_data(exps, e);
+ rel_join_add_exp(top, exp_dup(e));
+ list_remove_data(exps, e);
+ }
+ /* Remove other joins on the current 'n_rels' set in the
distinct list too */
+ while((djn = list_find(sdje, n_rels, (fcmp)&exp_joins_rels)) !=
NULL)
+ list_remove_data(sdje, djn->data);
+ fnd = 1;
}
- /* Remove other joins on the current 'n_rels'
- set in the distinct list too */
- while((djn = list_find(sdje, n_rels, (fcmp)&exp_joins_rels)) != NULL)
- list_remove_data(sdje, djn->data);
-
/* build join tree using the ordered list */
- fnd = 1;
while(list_length(exps) && fnd) {
fnd = 0;
/* find the first expression which could be added */
@@ -671,8 +675,12 @@
}
if (list_length(rels)) { /* more relations */
node *n;
- for(n=rels->h; n; n = n->next)
- top = rel_crossproduct(top, n->data, op_join);
+ for(n=rels->h; n; n = n->next) {
+ if (top)
+ top = rel_crossproduct(top, n->data, op_join);
+ else
+ top = n->data;
+ }
}
if (list_length(exps)) { /* more expressions */
node *n;
U sql_optimize.mx
Index: sql_optimize.mx
===================================================================
RCS file: /cvsroot/monetdb/sql/src/server/sql_optimize.mx,v
retrieving revision 1.91
retrieving revision 1.92
diff -u -d -r1.91 -r1.92
--- sql_optimize.mx 14 Mar 2008 12:55:18 -0000 1.91
+++ sql_optimize.mx 9 Apr 2008 09:56:23 -0000 1.92
@@ -377,11 +377,11 @@
* without unique head identifiers + semijoin is wrong
*/
if (!reverse) {
+ stmt *ml = stmt_mark(stmt_reverse(stmt_dup(op1)), 50);
+ stmt *mr = stmt_mark(stmt_dup(op1), 50);
+ stmt *l = stmt_join(stmt_dup(ml),
+ stmt_dup(op2->op1.stval), cmp_equal);
if (op2->type == st_join2) {
- stmt *ml = stmt_mark(stmt_reverse(stmt_dup(op1)), 50);
- stmt *mr = stmt_mark(stmt_dup(op1), 50);
- stmt *l = stmt_join(stmt_dup(ml),
- stmt_dup(op2->op1.stval), cmp_equal);
stmt *r1 = stmt_join(stmt_dup(mr),
stmt_dup(op2->op2.stval), cmp_equal);
stmt *r2 = stmt_join(stmt_dup(mr),
@@ -395,10 +395,6 @@
ml = stmt_semijoin(ml, v2);
res = stmt_join(stmt_reverse(ml), mr, cmp_equal);
} else {
- stmt *ml = stmt_mark(stmt_reverse(stmt_dup(op1)), 50);
- stmt *mr = stmt_mark(stmt_dup(op1), 50);
- stmt *l = stmt_join(stmt_dup(ml),
- stmt_dup(op2->op1.stval), cmp_equal);
stmt *r = stmt_join(stmt_dup(mr),
stmt_reverse(stmt_dup(op2->op2.stval)),
cmp_equal);
stmt *v = stmt_uselect(l, r, (comp_type) op2->flag);
U rel_exp.mx
Index: rel_exp.mx
===================================================================
RCS file: /cvsroot/monetdb/sql/src/server/rel_exp.mx,v
retrieving revision 1.9
retrieving revision 1.10
diff -u -d -r1.9 -r1.10
--- rel_exp.mx 14 Mar 2008 12:55:15 -0000 1.9
+++ rel_exp.mx 9 Apr 2008 09:56:23 -0000 1.10
@@ -545,7 +545,7 @@
sql_exp *
exps_bind_column( list *exps, char *cname )
{
- if (exps) {
+ if (exps && cname) {
node *en;
for (en = exps->h; en; en = en->next ) {
U rel_bin.mx
Index: rel_bin.mx
===================================================================
RCS file: /cvsroot/monetdb/sql/src/server/rel_bin.mx,v
retrieving revision 1.38
retrieving revision 1.39
diff -u -d -r1.38 -r1.39
--- rel_bin.mx 21 Mar 2008 08:41:28 -0000 1.38
+++ rel_bin.mx 9 Apr 2008 09:56:23 -0000 1.39
@@ -277,9 +277,9 @@
}
} break;
case e_cmp: {
- stmt *l = NULL, *r = NULL;
+ stmt *l = NULL, *r = NULL, *r2 = NULL;
int swapped = 0, sel = 0;
- sql_exp *re = e->r;
+ sql_exp *re = e->r, *re2 = e->f;
prop *p;
/* here we handle join indices */
@@ -319,25 +319,6 @@
l = exp_bin(sql, e->l, right, NULL, grp);
swapped = 1;
}
- /* the escape charachter of like is in the right expression */
- if (e->flag == cmp_notlike || e->flag == cmp_like) {
- stmt *escape = NULL;
-
- r = exp_bin(sql, e->r, left, right, grp);
- if (e->f) {
- escape = exp_bin(sql, e->f, left, right, grp);
- } else {
- escape = stmt_atom_string(_strdup(""));
- }
- if (!l || !r || !escape) {
- assert(0);
- if (l) stmt_destroy(l);
- if (r) stmt_destroy(r);
- if (escape) stmt_destroy(escape);
- return NULL;
- }
- return stmt_likeselect(l, r, escape,
(comp_type)e->flag);
- }
if (swapped || !right)
r = exp_bin(sql, e->r, left, NULL, grp);
else
@@ -346,12 +327,29 @@
r = exp_bin(sql, e->r, left, NULL, grp);
sel = 1;
}
- if (!l || !r) {
+ if (re2)
+ r2 = exp_bin(sql, e->f, left, right, grp);
+ if (!l || !r || (re2 && !r2)) {
assert(0);
if (l) stmt_destroy(l);
if (r) stmt_destroy(r);
+ if (r2) stmt_destroy(r2);
return NULL;
}
+
+ /* the escape charachter of like is in the right expression */
+ if (e->flag == cmp_notlike || e->flag == cmp_like) {
+ if (!e->f)
+ r2 = stmt_atom_string(_strdup(""));
+ if (!l || !r || !r2) {
+ assert(0);
+ if (l) stmt_destroy(l);
+ if (r) stmt_destroy(r);
+ if (r2) stmt_destroy(r2);
+ return NULL;
+ }
+ return stmt_likeselect(l, r, r2, (comp_type)e->flag);
+ }
if (left && right && re->card > CARD_ATOM && !sel) {
if (l->nrcols == 0)
l =
stmt_const(bin_first_column(swapped?right:left), l);
@@ -359,12 +357,20 @@
r =
stmt_const(bin_first_column(swapped?left:right), r);
if (swapped) {
s = stmt_join(r, stmt_reverse(l),
swap_compare((comp_type)e->flag));
+ } else if (r2) {
+ s = stmt_join2(l, r, r2, (comp_type)e->flag);
} else {
s = stmt_join(l, stmt_reverse(r),
(comp_type)e->flag);
}
} else {
- s = stmt_uselect(l, r, (comp_type)e->flag);
+ if (r2) {
+ s = stmt_uselect2(l, r, r2, (comp_type)e->flag);
+ } else {
+ s = stmt_uselect(l, r, (comp_type)e->flag);
+ }
}
+ if (is_anti(e))
+ s->flag |= ANTI;
} break;
default:
;
@@ -541,7 +547,7 @@
}
if (!join) {
join = s;
- } else if (s->type != st_join) {
+ } else if (s->type != st_join && s->type != st_join2) {
/* handle select expressions */
if (s->h == join->h) {
join = stmt_semijoin(join,s);
@@ -555,24 +561,38 @@
stmt *l = stmt_mark(stmt_reverse(join), 100);
stmt *r = stmt_mark(stmt_dup(join), 100);
stmt *ld = stmt_dup(s->op1.stval);
- stmt *rd = stmt_reverse(stmt_dup(s->op2.stval));
stmt *le = stmt_join(l, ld, cmp_equal);
- stmt *re = stmt_join(r, rd, cmp_equal);
-
- sql_subfunc *f =
sql_bind_func(sql->session->schema, compare_func((comp_type)s->flag),
tail_type(le), tail_type(le));
- stmt * cmp;
-
- assert(f);
-
-
- cmp = stmt_binop(le, re, f);
+ if (s->type == st_join2) {
+ stmt *rd = stmt_dup(s->op2.stval);
+ stmt *re = stmt_join(r, rd, cmp_equal);
+ stmt *r2 = stmt_dup(s->op3.stval);
+ stmt *re2 = stmt_join(stmt_dup(r), r2,
cmp_equal);
+ comp_type c1 = s->flag&2?cmp_gte:cmp_gt;
+ comp_type c2 = s->flag&1?cmp_lte:cmp_lt;
+ stmt *v1 = stmt_uselect(le, re, c1);
+ stmt *v2 = stmt_uselect(stmt_dup(le),
re2, c2);
+ l = stmt_semijoin(stmt_dup(l),
stmt_dup(v1));
+ l = stmt_semijoin(l, stmt_dup(v2));
+ r = stmt_semijoin(stmt_dup(r), v1);
+ r = stmt_semijoin(r, v2);
+ join = stmt_join(stmt_reverse(l), r,
cmp_equal);
+ stmt_destroy(s);
+ } else {
+ stmt *rd =
stmt_reverse(stmt_dup(s->op2.stval));
+ stmt *re = stmt_join(r, rd, cmp_equal);
+ sql_subfunc *f =
sql_bind_func(sql->session->schema, compare_func((comp_type)s->flag),
tail_type(le), tail_type(le));
+ stmt * cmp;
+
+ assert(f);
- cmp = stmt_uselect(cmp, stmt_bool(1),
cmp_equal);
+ cmp = stmt_binop(le, re, f);
+ cmp = stmt_uselect(cmp, stmt_bool(1),
cmp_equal);
- l = stmt_semijoin(stmt_dup(l), stmt_dup(cmp));
- r = stmt_semijoin(stmt_dup(r), cmp);
- join = stmt_join(stmt_reverse(l), r, cmp_equal);
- stmt_destroy(s);
+ l = stmt_semijoin(stmt_dup(l),
stmt_dup(cmp));
+ r = stmt_semijoin(stmt_dup(r), cmp);
+ join = stmt_join(stmt_reverse(l), r,
cmp_equal);
+ stmt_destroy(s);
+ }
}
}
} else {
-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
Monetdb-sql-checkins mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/monetdb-sql-checkins
