Changeset: 36e282f14df5 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/36e282f14df5
Modified Files:
sql/backends/monet5/rel_bin.c
sql/backends/monet5/rel_physical.c
sql/backends/monet5/rel_util.c
sql/backends/monet5/sql_pp_statement.c
sql/include/sql_relation.h
sql/server/rel_dump.c
sql/server/rel_exp.c
sql/server/rel_optimize_join.c
sql/server/rel_statistics.c
Branch: default
Log Message:
improved computation of join-costs and cardinality estimation
diffs (truncated from 434 to 300 lines):
diff --git a/sql/backends/monet5/rel_bin.c b/sql/backends/monet5/rel_bin.c
--- a/sql/backends/monet5/rel_bin.c
+++ b/sql/backends/monet5/rel_bin.c
@@ -8279,7 +8279,7 @@ exp_remap(sql_exp *le, sql_exp *re, list
case e_column:
if (exp_pair_match(remapped, le->nid, re->nid))
return 0;
- break;
+ return -1;
case e_convert:
ll = le->r;
rl = re->r;
@@ -8385,8 +8385,7 @@ deduplicate_refs(mvc *sql, allocator *ta
for(node *n = refs->h; n; n = n->next) {
sql_rel *or = n->data, *nr = or;
prop *op = find_prop(or->p, PROP_HASH);
- if (or->op == op_buildhash &&
- op && op->value.lval) {
+ if (or->op == op_buildhash && op && op->value.lval) {
BUN h = op->value.lval;
for(node *m = prefs->h; m; m = m->next->next) {
sql_rel *ir = m->data;
diff --git a/sql/backends/monet5/rel_physical.c
b/sql/backends/monet5/rel_physical.c
--- a/sql/backends/monet5/rel_physical.c
+++ b/sql/backends/monet5/rel_physical.c
@@ -504,8 +504,10 @@ find_cmp_exps(list **exps_hsh, list **ex
sql_exp *ne = NULL;
if ((ne = rel_find_exp(rel_hsh, e->r)) != NULL) {
sql_exp *er = e->r;
+ /*
if (is_unique(ne))
set_unique(er);
+ */
if (any)
set_any(er);
if (semantic)
@@ -516,8 +518,10 @@ find_cmp_exps(list **exps_hsh, list **ex
ne = rel_find_exp(rel_hsh, e->l);
assert(ne);
sql_exp *el = e->l;
+ /*
if (is_unique(ne))
set_unique(el);
+ */
if (any)
set_any(el);
if (semantic)
diff --git a/sql/backends/monet5/rel_util.c b/sql/backends/monet5/rel_util.c
--- a/sql/backends/monet5/rel_util.c
+++ b/sql/backends/monet5/rel_util.c
@@ -89,14 +89,18 @@ void
split_join_exps(sql_rel *rel, list *joinable, list *not_joinable, bool anti,
bool eqonly)
{
if (!list_empty(rel->exps)) {
+ bool done = false;
for (node *n = rel->exps->h; n; n = n->next) {
sql_exp *e = n->data;
/* eqonly -
* TRUE: only handle equi-join expressions, e.g. in
case of pipeline hash join
* FALSE: we can (also) handle thetajoins, rangejoins
and filter joins (like) */
- if (can_join_exp(rel, e, anti) && (!eqonly ||
(is_equi_exp_(e) && !exp_is_atom(e->r) && !exp_is_atom(e->l)))) {
+ if (!done && (can_join_exp(rel, e, anti) && (!eqonly ||
(is_equi_exp_(e) && !exp_is_atom(e->r) && !exp_is_atom(e->l))))) {
append(joinable, e);
+ sql_exp *el = e->l, *er = e->r;
+ if (eqonly && is_innerjoin(rel->op) &&
(is_unique(el) || is_unique(er)))
+ done = true;
} else {
append(not_joinable, e);
}
diff --git a/sql/backends/monet5/sql_pp_statement.c
b/sql/backends/monet5/sql_pp_statement.c
--- a/sql/backends/monet5/sql_pp_statement.c
+++ b/sql/backends/monet5/sql_pp_statement.c
@@ -565,6 +565,11 @@ stmt_oahash_probe(backend *be, stmt *key
q = pushArgument(be->mb, q, getArg(prev->q, 0));
q = pushArgument(be->mb, q, getArg(prev->q, 1));
}
+ /*
+ sql_subtype *htype = tail_type(rhs_ht);
+ sql_subtype *ptype = tail_type(key);
+ assert(subtype_cmp(htype, ptype) == 0);
+ */
q = pushArgument(be->mb, q, rhs_ht->nr);
if (single) {
assert(freq);
diff --git a/sql/include/sql_relation.h b/sql/include/sql_relation.h
--- a/sql/include/sql_relation.h
+++ b/sql/include/sql_relation.h
@@ -351,11 +351,12 @@ typedef struct relation {
*/
int nrcols; /* nr of cols */
unsigned int
- flag:16,
card:2, /* 0, 1 (row), 2 aggr, 3 */
dependent:1, /* dependent join */
distinct:1,
fv_distinct:1, /* set during general unnest */
+ lunique:1, /* left side of join unique */
+ runique:1, /* right side of join unique */
processed:1, /* fully processed or still in the process of building
*/
outer:1, /* used as outer (ungrouped) */
grouped:1, /* groupby processed all the group by exps */
@@ -374,6 +375,7 @@ typedef struct relation {
* Used by rewriters at rel_unnest, rel_optimizer and rel_distribute so
a relation is not modified twice
* The list is kept at rel_optimizer_private.h Please update it
accordingly
*/
+ uint16_t flag;
uint16_t used;
uint16_t nr_outers;
int opt;
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
@@ -381,7 +381,7 @@ exp_print(mvc *sql, stream *fout, sql_ex
mnstr_printf(fout, " NULLS LAST");
if (e->type != e_atom && e->type != e_cmp && !has_nil(e))
mnstr_printf(fout, " NOT NULL");
- if (e->type != e_atom && e->type != e_cmp && is_unique(e))
+ if (e->type != e_atom && (sql->show_all_details || e->type !=
e_cmp) && is_unique(e))
mnstr_printf(fout, " UNIQUE");
/* don't show properties on value lists */
if (decorate && e->p && e->type != e_atom && !exp_is_atom(e)) {
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
@@ -176,7 +176,7 @@ exp_compare(allocator *sa, sql_exp *l, s
e->l = l;
e->r = r;
e->flag = cmptype;
- if (cmptype == cmp_equal) {
+ if (cmptype == cmp_equal && r->card <= CARD_AGGR) {
prop *p = e->p = prop_create(sa, PROP_NUNIQUES, (prop *) e->p);
p->value.dval = 1;
}
@@ -197,7 +197,7 @@ exp_compare2(allocator *sa, sql_exp *l,
e->r = r;
e->f = f;
e->flag = cmptype;
- if (cmptype == cmp_equal) {
+ if (cmptype == cmp_equal && r->card <= CARD_AGGR) {
prop *p = e->p = prop_create(sa, PROP_NUNIQUES, (prop *) e->p);
p->value.dval = 1;
}
@@ -4419,6 +4419,10 @@ exp_estimate_selectivity(mvc *sql, sql_e
case cmp_lt:
case cmp_lte:
sel = 0.50;
+ /*
+ if (e->f)
+ sel = 0.10;
+ */
break;
case cmp_in:
case cmp_notin: {
diff --git a/sql/server/rel_optimize_join.c b/sql/server/rel_optimize_join.c
--- a/sql/server/rel_optimize_join.c
+++ b/sql/server/rel_optimize_join.c
@@ -115,12 +115,14 @@ rel_estimate(visitor *v, sql_rel *rel)
/* Don't prune updates as pruning will possibly result in removing the
joins which therefore cannot be used for constraint checking */
sql_rel *l = rel->l, *r = rel->r;
+ /*
if (is_join(rel->op) || is_semi(rel->op)) {
rel->l = rel_estimate(v, rel->l);
rel->r = rel_estimate(v, rel->r);
}
if (is_join(rel->op))
rel->exps = exps_exp_visitor_bottomup(v, rel, rel->exps, 0,
&rel_propagate_statistics, false);
+ */
switch (rel->op) {
case op_join:
@@ -139,8 +141,8 @@ rel_estimate(visitor *v, sql_rel *rel)
if (find_prop(e->p, PROP_JOINIDX)) {
prop *lsp = find_prop(l->p,
PROP_SELECTIVITY), *rsp = find_prop(r->p, PROP_SELECTIVITY);
- dbl ls = lsp && is_join(l->op) ?
lsp->value.dval : 1.0;
- dbl rs = rsp && is_join(r->op) ?
rsp->value.dval : 1.0;
+ dbl ls = lsp /*&& is_join(l->op)*/ ?
lsp->value.dval : 1.0;
+ dbl rs = rsp /*&& is_join(r->op)*/ ?
rsp->value.dval : 1.0;
join_idx_estimate = lv>rv?lv:rv;
join_idx_estimate =
(BUN)(join_idx_estimate * ls * rs);
if (join_idx_estimate < 1)
@@ -152,7 +154,7 @@ rel_estimate(visitor *v, sql_rel *rel)
} else if (e->type == e_cmp && e->flag ==
cmp_equal) {
/* if one of the sides is unique, the
cardinality will be at most the cardinality of the other side */
if (!is_semantics(e) || !has_nil(el) ||
!has_nil(er)) {
- BUN lu = lv, ru = rv;
+ BUN lu = 1, ru = 1; /*
initialize with worst case */
prop *p = NULL;
if ((p = find_prop(el->p,
PROP_NUNIQUES)))
lu = (BUN)
p->value.dval;
@@ -177,9 +179,11 @@ rel_estimate(visitor *v, sql_rel *rel)
sp->value.dval = s;
e->p = sp;
} else {
- dbl u = (dbl)MAX(lu,
ru);
+ dbl mfl = (dbl)lv/lu;
+ dbl mfr = (dbl)rv/ru;
+ dbl mf = MIN(lv/mfl,
rv/mfr);
+ dbl u = mf * mfl * mfr;
dbl s = u/(lv*rv);
- //dbl s = 1/u;
prop *sp =
prop_create(v->sql->sa, PROP_SELECTIVITY, (prop *) e->p);
sp->value.dval = s;
e->p = sp;
@@ -407,7 +411,7 @@ extern void _exps_print(mvc *sql, list *
static prop *
exp_selectivity(visitor *v, sql_exp *e, sql_rel *l, sql_rel *r, prop *p)
{
- BUN lv = get_rel_count(l), rv = get_rel_count(r), r_uniques_estimate =
BUN_MAX, join_idx_estimate = BUN_MAX;
+ BUN lv = get_rel_count(l), rv = get_rel_count(r), join_idx_estimate =
BUN_MAX;
sql_exp *el = e->l, *er = e->r;
BUN uniques_estimate = BUN_MAX;
prop *jip = find_prop(e->p, PROP_JOINIDX);
@@ -436,30 +440,32 @@ exp_selectivity(visitor *v, sql_exp *e,
} else if (e->type == e_cmp && e->flag == cmp_equal) {
/* if one of the sides is unique, the cardinality will be at
most the cardinality of the other side */
if (!is_semantics(e) || !has_nil(el) || !has_nil(er)) {
- BUN lu = lv, ru = rv, nlv = lv, nrv = rv;
+ BUN lu = 1, ru = 1; /* initialize with worst case */
prop *up = NULL;
if (el->type == e_column && (is_select(l->op) ||
is_basetable(l->op)))
el = rel_find_exp(l, el);
if ((up = find_prop(el->p, PROP_NUNIQUES)))
- lu = (BUN) up->value.dval;
+ lu = MIN((BUN) up->value.dval, lv);
if (er->type == e_column && (is_select(r->op) ||
is_basetable(r->op)))
er = rel_find_exp(r, er);
if ((up = find_prop(er->p, PROP_NUNIQUES)))
- ru = (BUN) up->value.dval;
- if (is_unique(el) || (is_unique(er) && runique)) {
+ ru = MIN((BUN) up->value.dval, rv);
+ if (is_unique(el) || (is_unique(er) && runique))
uniques_estimate = MIN(uniques_estimate,
MAX(lv, rv));
- }
+ if (is_unique(el) && is_unique(er) && runique)
+ uniques_estimate = MIN(lu, ru);
if (uniques_estimate != BUN_MAX) {
- if (uniques_estimate < r_uniques_estimate)
- r_uniques_estimate = uniques_estimate;
dbl s = ((dbl)uniques_estimate/(lv*rv));
if (!p)
p = prop_create(v->sql->sa,
PROP_SELECTIVITY, (prop *) e->p);
p->value.dval = s;
e->p = p;
} else {
- dbl u = ((dbl)lu*ru) / (nlv*nrv);
- dbl s = 1/u;
+ dbl mfl = (dbl)lv/lu;
+ dbl mfr = (dbl)rv/ru;
+ dbl mf = MIN(lv/mfl, rv/mfr);
+ dbl u = mf * mfl * mfr;
+ dbl s = u/(lv*rv);
if (!p)
p = prop_create(v->sql->sa,
PROP_SELECTIVITY, (prop *) e->p);
p->value.dval = s;
@@ -477,6 +483,39 @@ exp_selectivity(visitor *v, sql_exp *e,
return p;
}
+static sql_exp *
+find_unique(sql_exp *e, sql_rel *rel)
+{
+ if (is_select(rel->op) || is_basetable(rel->op))
+ return rel_find_exp(rel, e);
+ if (is_join(rel->op)) {
+ if (rel->lunique)
+ return find_unique(e, rel->l);
+ if (rel->runique)
+ return find_unique(e, rel->r);
+ }
+ return NULL;
+}
+
+static void
+exp_set_uniques(sql_exp *e, sql_rel *l, sql_rel *r)
+{
+ if (e->type == e_cmp) {
+ if (e->flag == cmp_equal || e->flag == cmp_notequal) {
+ exp_set_uniques(e->l, l, r);
+ exp_set_uniques(e->r, l, r);
+ }
+ } else if (e->type == e_column) {
+ sql_exp *be = find_unique(e, l);
+ if (!be)
+ be = find_unique(e, r);
+ if (be && is_unique(be))
+ set_unique(e);
+ else
+ set_not_unique(e);
+ }
+}
+
static int VERBOSE = 0;
static dbl
@@ -487,6 +526,7 @@ exp_cost(visitor *v, sql_exp *e, ulng ma
if (!l || !r)
_______________________________________________
checkin-list mailing list -- [email protected]
To unsubscribe send an email to [email protected]
