Changeset: 00fb7a4501c0 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/00fb7a4501c0
Modified Files:
monetdb5/modules/mal/pp_hash.c
sql/backends/monet5/rel_pphash.c
sql/rel.txt
sql/server/rel_dump.c
sql/server/rel_exp.c
sql/server/rel_exp.h
sql/server/rel_optimize_proj.c
sql/server/rel_optimize_sel.c
sql/server/rel_optimizer.c
sql/server/rel_optimizer_private.h
sql/server/rel_prop.c
sql/server/rel_prop.h
sql/server/rel_statistics.c
sql/server/rel_statistics.h
sql/server/rel_unnest.c
Branch: pp_hashjoin
Log Message:
add join reorders based on selectivity and cost calculation for pipelines
diffs (truncated from 2387 to 300 lines):
diff --git a/monetdb5/modules/mal/pp_hash.c b/monetdb5/modules/mal/pp_hash.c
--- a/monetdb5/modules/mal/pp_hash.c
+++ b/monetdb5/modules/mal/pp_hash.c
@@ -1144,7 +1144,7 @@ error:
if (slots == 0) { \
slots = ht_preclaim(private); \
slot = ATOMIC_ADD(&h->last,
slots); \
- if (((slot*100)/100) >=
(gid)h->size) { \
+ if (((slot*100)/70) >=
(gid)h->size) { \
hash_rehash(h, p, err);
\
vals = h->vals; \
pgids = h->pgids; \
@@ -1192,7 +1192,7 @@ error:
if (slots == 0) { \
slots =
ht_preclaim(private); \
slot =
ATOMIC_ADD(&h->last, slots); \
- if (((slot*100)/100) >=
(gid)h->size) { \
+ if (((slot*100)/70) >=
(gid)h->size) { \
hash_rehash(h,
p, err); \
vals = h->vals;
\
pgids =
h->pgids; \
diff --git a/sql/backends/monet5/rel_pphash.c b/sql/backends/monet5/rel_pphash.c
--- a/sql/backends/monet5/rel_pphash.c
+++ b/sql/backends/monet5/rel_pphash.c
@@ -295,7 +295,7 @@ rel2bin_oahash_build(backend *be, sql_re
bool need_freq = (rel->flag != (int)op_semi || rel->ref.refcnt > 2 ||
!list_empty(exps_prj_hsh));
if (need_freq && list_length(exps_cmp_hsh) == 1 && !is_single(rel)) {
sql_exp *e = exps_cmp_hsh->h->data;
- if (e->unique)
+ if (0 && e->unique)
need_freq = false;
}
lng bld_sz = _estimate(be->mvc, rel); /* TODO: change into dynamic
where possible ?? */
diff --git a/sql/rel.txt b/sql/rel.txt
--- a/sql/rel.txt
+++ b/sql/rel.txt
@@ -99,15 +99,15 @@ INSERT|DELETE|UPDATE|TRUNCATE (card ATO
-> flag (if set don't insert (is done already))
only (UPDATE)
- -> exps
- UPDATE: Named columns to update
+ -> exps
+ UPDATE: Named columns to update
DELETE: deleted rows (for returning return all columns
(the deleted content))
INSERT: inserted values
TRUNCATE: The first expression is a e_atom integer
indicating to restart sequences, and the second is another e_atom integer
telling to cascade the truncate if the table has fk dependents
- -> attr UPDATE: for returning all columns of updated rows
+ -> attr UPDATE: for returning all columns of updated rows
TODO cleanup
-UPDATE have a special case
+UPDATE have a special case
for inserts/updates with indices a double
relation is used as we need to keep access to
@@ -121,7 +121,7 @@ PROBEHASH
-> attr hash-expressions
-> exps payload
-PARTITION
+PARTITION
-> l relation
-> attr hash-expressions
-> exps payload
@@ -144,15 +144,15 @@ e_convert
e_cmp
-> l left sub expression
-> r right sub expression (f second arg (->f) for range expressions)
- -> flag compare type
+ -> flag compare type
(
- cmp_gt = 0, or [ v > l && v < h ]
+ cmp_gt = 0, or [ v > l && v < h ]
cmp_gte = 1, or [ v >= l && v < h ]
cmp_lte = 2, or [ v > l && v <= h ]
cmp_lt = 3, or [ v >= l && v <= h ]
- uses flag&CMP_BETWEEN bit for
handling nil
+ uses flag&CMP_BETWEEN bit for
handling nil
open ranges and isNull
vs NULL
- uses flag&CMP_SYMMETRIC bit
for symmetric
+ uses flag&CMP_SYMMETRIC bit
for symmetric
cmp_equal = 4,
cmp_notequal = 5,
@@ -191,9 +191,11 @@ e_column
-> rname alias for the relation (i.e., alias of ->l, used by higher
expressions)
-> name alias for the expression (i.e., alias of ->r, used by higher
expressions)
l,r names of referred expression
- -> l optional relation name
+ -> l optional relation name
-> r expression name
- -> type
+ -> f pointer to relation, if expression is part of base table
+ -> nid == label of referenced expression (down the tree)
+ -> type
e_psm
-> flag
diff --git a/sql/server/rel_dump.c b/sql/server/rel_dump.c
--- a/sql/server/rel_dump.c
+++ b/sql/server/rel_dump.c
@@ -386,7 +386,7 @@ exp_print(mvc *sql, stream *fout, sql_ex
/* don't show properties on value lists */
if (decorate && e->p && e->type != e_atom && !exp_is_atom(e)) {
for (prop *p = e->p; p; p = p->p) {
- if (p->kind != PROP_MIN && p->kind != PROP_MAX
&& p->kind != PROP_NUNIQUES) {
+ if (p->kind != PROP_MIN && p->kind != PROP_MAX
&& p->kind != PROP_NUNIQUES && p->kind != PROP_SELECTIVITY) {
char *pv = propvalue2string(ta, p);
mnstr_printf(fout, " %s %s",
propkind2string(p), pv);
}
@@ -776,7 +776,7 @@ rel_print_rel(mvc *sql, stream *fout, s
if ((ATOMIC_GET(&GDKdebug) & TESTINGMASK) == 0 &&
rel->partition)
mnstr_printf(fout, " %c PARTITION",
rel->partition==1?'L':rel->partition == 2?'R':' ');
for (prop *p = rel->p; p; p = p->p) {
- if ((p->kind != PROP_COUNT && p->kind != PROP_UKEY &&
p->kind != PROP_UNNESTING) || (ATOMIC_GET(&GDKdebug) & TESTINGMASK) == 0) {
+ if ((p->kind != PROP_COUNT && p->kind != PROP_UKEY &&
p->kind != PROP_UNNESTING && p->kind != PROP_SELECTIVITY) ||
(ATOMIC_GET(&GDKdebug) & TESTINGMASK) == 0) {
char *pv = propvalue2string(ta, p);
mnstr_printf(fout, " %s %s",
propkind2string(p), pv);
}
diff --git a/sql/server/rel_exp.c b/sql/server/rel_exp.c
--- a/sql/server/rel_exp.c
+++ b/sql/server/rel_exp.c
@@ -1473,7 +1473,11 @@ exp_match_exp_semantics( sql_exp *e1, sq
if (e1->type == e2->type) {
switch(e1->type) {
case e_cmp:
- if (e1->flag == e2->flag && !is_complex_exp(e1->flag) &&
+ if (e1->flag == e2->flag && e1->flag == cmp_equal &&
!is_anti(e1) && !is_anti(e2) &&
+ ((exp_match_exp(e1->l, e2->l) &&
exp_match_exp(e1->r, e2->r)) ||
+ (exp_match_exp(e1->l, e2->r) &&
exp_match_exp(e1->r, e2->l))))
+ return 1;
+ else if (e1->flag == e2->flag &&
!is_complex_exp(e1->flag) &&
exp_match_exp(e1->l, e2->l) && exp_match_exp(e1->r,
e2->r) &&
((!e1->f && !e2->f) || (e1->f && e2->f &&
exp_match_exp(e1->f, e2->f))))
return 1;
@@ -1539,6 +1543,12 @@ exp_match_exp( sql_exp *e1, sql_exp *e2)
return exp_match_exp_semantics( e1, e2, true);
}
+int
+exp_match_exp_cmp( sql_exp *e1, sql_exp *e2)
+{
+ return !exp_match_exp_semantics( e1, e2, true);
+}
+
sql_exp *
exps_any_match(list *l, sql_exp *e)
{
@@ -4324,6 +4334,137 @@ free_exp(allocator *sa, sql_exp *e)
_free_exp_internal(sa, e);
}
+dbl
+exp_estimate_selectivity(mvc *sql, sql_exp *e)
+{
+ dbl sel = 0.1;
+ (void)sql;
+ if (!e)
+ return 1.0;
+ switch (e->type) {
+ case e_atom:
+ if (exp_is_true(e))
+ return 1.0;
+ if (exp_is_false(e))
+ return 0.0;
+ return 0.5;
+ case e_column:
+ return 0.1;
+ case e_convert:
+ return exp_estimate_selectivity(sql, (sql_exp *) e->l);
+ case e_func:
+ return 0.1;
+ case e_aggr:
+ return 0.1;
+ case e_cmp: {
+ sql_exp *l = (sql_exp *) e->l, *r = (sql_exp *) e->r;
+ if (e->flag <= cmp_lte && e->f) {
+ sel = 0.50;
+ } else {
+ switch (e->flag) {
+ case cmp_equal:
+ if (exp_is_atom(r) && !exp_is_atom(l)) {
+ prop *p = find_prop(l->p,
PROP_NUNIQUES);
+ if (p && p->value.dval > 1)
+ sel = 1.0 / p->value.dval;
+ else
+ sel = 0.1;
+ } else if (exp_is_atom(l) && !exp_is_atom(r)) {
+ prop *p = find_prop(r->p,
PROP_NUNIQUES);
+ if (p && p->value.dval > 1)
+ sel = 1.0 / p->value.dval;
+ else
+ sel = 0.1;
+ } else if (!exp_is_atom(l) && !exp_is_atom(r)) {
+ prop *pl = find_prop(l->p,
PROP_NUNIQUES), *pr = find_prop(r->p, PROP_NUNIQUES);
+ if (pl && pr && pl->value.dval > 0 &&
pr->value.dval > 0)
+ sel = 1.0 / MAX(pl->value.dval,
pr->value.dval);
+ else if (pl && pl->value.dval > 0)
+ sel = 1.0 / pl->value.dval;
+ else if (pr && pr->value.dval > 0)
+ sel = 1.0 / pr->value.dval;
+ else
+ sel = 0.1;
+ } else {
+ sel = 0.5;
+ }
+ break;
+ case cmp_notequal:
+ if (exp_is_atom(r) && !exp_is_atom(l)) {
+ prop *p = find_prop(l->p,
PROP_NUNIQUES);
+ if (p && p->value.dval > 1)
+ sel = 1.0 - 1.0 / p->value.dval;
+ else
+ sel = 0.9;
+ } else if (exp_is_atom(l) && !exp_is_atom(r)) {
+ prop *p = find_prop(r->p,
PROP_NUNIQUES);
+ if (p && p->value.dval > 1)
+ sel = 1.0 - 1.0 / p->value.dval;
+ else
+ sel = 0.9;
+ } else {
+ sel = 0.9;
+ }
+ break;
+ case cmp_gt:
+ case cmp_gte:
+ case cmp_lt:
+ case cmp_lte:
+ sel = 0.50;
+ break;
+ case cmp_in:
+ case cmp_notin: {
+ list *vals = (list *) e->r;
+ int nvals = list_length(vals);
+ prop *p = find_prop(l->p, PROP_NUNIQUES);
+ if (p && p->value.dval > 0) {
+ sel = (dbl) nvals / p->value.dval;
+ } else {
+ sel = (dbl) nvals * 0.05;
+ }
+ if (sel > 0.5)
+ sel = 0.5;
+ if (e->flag == cmp_notin)
+ sel = 1.0 - sel;
+ break;
+ }
+ case cmp_con: {
+ list *lst = (list *) e->l;
+ sel = 1.0;
+ for (node *n = lst->h; n; n = n->next)
+ sel *= exp_estimate_selectivity(sql,
(sql_exp *) n->data);
+ break;
+ }
+ case cmp_dis: {
+ list *lst = (list *) e->l;
+ sel = 0.0;
+ for (node *n = lst->h; n; n = n->next)
+ sel += exp_estimate_selectivity(sql, (sql_exp
*) n->data);
+ if (sel > 1.0)
+ sel = 1.0;
+ break;
+ }
+ case cmp_filter:
+ sel = 0.01;
+ break;
+ default:
+ sel = 0.1;
+ break;
+ }
+ }
+ break;
+ }
+ case e_psm:
+ sel = 0.5;
+ break;
+ }
+ if (sel < 0.0)
+ sel = 0.0;
+ if (sel > 1.0)
+ sel = 1.0;
+ return sel;
+}
+
bool
exps_has_group_filter(list *exps)
{
diff --git a/sql/server/rel_exp.h b/sql/server/rel_exp.h
--- a/sql/server/rel_exp.h
+++ b/sql/server/rel_exp.h
@@ -153,6 +153,7 @@ extern int exp_match( sql_exp *e1, sql_e
extern sql_exp* exps_find_exp( list *l, sql_exp *e);
extern int exp_match_exp( sql_exp *e1, sql_exp *e2);
extern int exp_match_exp_semantics( sql_exp *e1, sql_exp *e2, bool semantics);
+extern int exp_match_exp_cmp( sql_exp *e1, sql_exp *e2 ); /* return 0 on match
else !0 */
extern sql_exp* exps_any_match(list *l, sql_exp *e);
/* match just the column (cmp equality) expressions */
extern int exp_match_col_exps( sql_exp *e, list *l);
@@ -211,6 +212,7 @@ extern sql_exp *exps_bind_column2(list *
extern sql_exp * list_find_exp(const list *exps, sql_exp *e);
_______________________________________________
checkin-list mailing list -- [email protected]
To unsubscribe send an email to [email protected]
