Changeset: 757554481335 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/757554481335
Added Files:
sql/server/rel_optimize_join.c
Modified Files:
sql/server/CMakeLists.txt
sql/server/rel_optimize_sel.c
sql/server/rel_rel.c
sql/server/rel_statistics.c
sql/server/rel_statistics.h
Branch: default
Log Message:
split some of the join optimization code into rel_optimize_join.c
diffs (truncated from 4424 to 300 lines):
diff --git a/sql/server/CMakeLists.txt b/sql/server/CMakeLists.txt
--- a/sql/server/CMakeLists.txt
+++ b/sql/server/CMakeLists.txt
@@ -51,6 +51,7 @@ target_sources(sqlserver
rel_optimize_others.c
rel_optimize_proj.c
rel_optimize_sel.c
+ rel_optimize_join.c
rel_distribute.c
rel_remote.c rel_remote.h
rel_propagate.c rel_propagate.h
diff --git a/sql/server/rel_optimize_join.c b/sql/server/rel_optimize_join.c
new file mode 100644
--- /dev/null
+++ b/sql/server/rel_optimize_join.c
@@ -0,0 +1,2177 @@
+
+#include "monetdb_config.h"
+#include "rel_optimizer_private.h"
+#include "rel_statistics.h"
+//#include "rel_basetable.h"
+#include "rel_rewriter.h"
+//#include "sql_storage.h"
+
+static int
+find_join_rels(list **L, list **R, list *exps, list *rels)
+{
+ node *n;
+
+ *L = sa_list(exps->sa);
+ *R = sa_list(exps->sa);
+ if (!exps || list_length(exps) <= 1)
+ return -1;
+ for(n = exps->h; n; n = n->next) {
+ sql_exp *e = n->data;
+ sql_rel *l = NULL, *r = NULL;
+
+ if (!is_complex_exp(e->flag)){
+ l = find_rel(rels, e->l);
+ r = find_rel(rels, e->r);
+ }
+ if (l<r) {
+ list_append(*L, l);
+ list_append(*R, r);
+ } else {
+ list_append(*L, r);
+ list_append(*R, l);
+ }
+ }
+ return 0;
+}
+
+static list *
+distinct_join_exps(list *aje, list *lrels, list *rrels)
+{
+ node *n, *m, *o, *p;
+ int len = list_length(aje), i, j;
+ char *used = SA_ZNEW_ARRAY(aje->sa, char, len);
+ list *res = sa_list(aje->sa);
+
+ assert(len == list_length(lrels));
+ for(n = lrels->h, m = rrels->h, j = 0; n && m;
+ n = n->next, m = m->next, j++) {
+ if (n->data && m->data)
+ for(o = n->next, p = m->next, i = j+1; o && p;
+ o = o->next, p = p->next, i++) {
+ if (o->data == n->data && p->data == m->data)
+ used[i] = 1;
+ }
+ }
+ for (i = 0, n = aje->h; i < len; n = n->next, i++) {
+ if (!used[i])
+ list_append(res, n->data);
+ }
+ return res;
+}
+
+static sql_rel *
+remove_blocking_selects( mvc *sql, sql_rel *p, sql_rel *rel)
+{
+ if (rel_is_ref(rel))
+ return rel;
+
+ switch(rel->op) {
+ case op_select:
+ if (p) {
+ sql_rel *l = rel->l;
+ if (is_single(rel) || l->op != op_join)
+ return rel;
+ if (!list_empty(rel->exps)) {
+ p->exps = list_join(p->exps, rel->exps);
+ rel->exps = NULL;
+ }
+ if (list_empty(rel->exps)) {
+ sql_rel *l = rel->l;
+ rel->l = NULL;
+ rel_destroy(sql, rel);
+ return remove_blocking_selects( sql, p, l);
+ }
+ }
+ return rel;
+ case op_join:
+ rel->l = remove_blocking_selects(sql, rel, rel->l);
+ rel->r = remove_blocking_selects(sql, rel, rel->r);
+ return rel;
+ default:
+ return rel;
+ }
+}
+
+static void
+get_relations(visitor *v, sql_rel *rel, list *rels)
+{
+ if (list_empty(rel->attr) && !rel_is_ref(rel) && rel->op == op_join &&
rel->exps == NULL && !is_single(rel)) {
+ sql_rel *l = rel->l;
+ sql_rel *r = rel->r;
+
+ get_relations(v, l, rels);
+ get_relations(v, r, rels);
+ rel->l = NULL;
+ rel->r = NULL;
+ rel_destroy(v->sql, rel);
+ } else {
+ append(rels, rel);
+ }
+}
+
+static sql_rel *
+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:
+ case op_left:
+ case op_right:
+ case op_full:
+ {
+ /* propagate row count */
+ BUN lv = get_rel_count(l), rv = get_rel_count(r),
r_uniques_estimate = BUN_MAX, join_idx_estimate = BUN_MAX;
+
+ //assert (lv < 1000000000 && rv < 1000000000);
+ if (!list_empty(rel->exps) && !is_single(rel) && rel->op ==
op_join) {
+ for (node *n = rel->exps->h ; n ; n = n->next) {
+ sql_exp *e = n->data, *el = e->l, *er = e->r;
+ BUN uniques_estimate = BUN_MAX;
+
+ 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;
+ join_idx_estimate = lv>rv?lv:rv;
+ join_idx_estimate =
(BUN)(join_idx_estimate * ls * rs);
+ if (join_idx_estimate < 1)
+ join_idx_estimate = 1;
+ dbl s =
((dbl)join_idx_estimate/(lv*rv));
+ prop *sp = prop_create(v->sql->sa,
PROP_SELECTIVITY, (prop *) e->p);
+ sp->value.dval = s;
+ e->p = sp;
+ } 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;
+ prop *p = NULL;
+ if ((p = find_prop(el->p,
PROP_NUNIQUES)))
+ lu = (BUN)
p->value.dval;
+ if ((p = find_prop(er->p,
PROP_NUNIQUES)))
+ ru = (BUN)
p->value.dval;
+ if (is_unique(el) || lu > lv) {
+ BUN ncount =
(is_right(rel->op) || is_full(rel->op) || !lv || lu < lv) ? MAX(lv, rv) :
rv/(lu/lv);
+ if (ncount == 0)
+ ncount =
MAX(lv, rv);
+ uniques_estimate =
MIN(uniques_estimate, ncount);
+ } else if (is_unique(er) || ru
> rv) {
+ BUN ncount =
(is_left(rel->op) || is_full(rel->op) || !rv || ru < rv) ? MAX(lv, rv) :
lv/(ru/rv);
+ if (ncount == 0)
+ ncount =
MAX(lv, rv);
+ uniques_estimate =
MIN(uniques_estimate, ncount);
+ }
+ if (uniques_estimate < BUN_MAX)
{
+ if (uniques_estimate <
r_uniques_estimate)
+
r_uniques_estimate = uniques_estimate;
+ dbl s =
((dbl)uniques_estimate/(lv*rv));
+ prop *sp =
prop_create(v->sql->sa, PROP_SELECTIVITY, (prop *) e->p);
+ sp->value.dval = s;
+ e->p = sp;
+ } else {
+ dbl u = (dbl)MAX(lu,
ru);
+ 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;
+ }
+ }
+ }
+ }
+ }
+ if (is_single(rel) || is_left(rel->op)) {
+ set_count_prop(v->sql->sa, rel, lv);
+ } else if (is_right(rel->op)) {
+ set_count_prop(v->sql->sa, rel, rv);
+ } else if (is_full(rel->op)) {
+ set_count_prop(v->sql->sa, rel, MAX(lv,rv));
+ } else if (join_idx_estimate < BUN_MAX) {
+ set_count_prop(v->sql->sa, rel, join_idx_estimate);
+ } else if (r_uniques_estimate < BUN_MAX) {
+ set_count_prop(v->sql->sa, rel, r_uniques_estimate);
+ } else if (list_length(rel->exps) == 1 &&
(exp_is_false(rel->exps->h->data) || exp_is_null(rel->exps->h->data))) {
+ /* corner cases for outer joins */
+ if (is_left(rel->op)) {
+ set_count_prop(v->sql->sa, rel, lv);
+ } else if (is_right(rel->op)) {
+ set_count_prop(v->sql->sa, rel, rv);
+ } else if (is_full(rel->op) && lv != BUN_NONE && rv !=
BUN_NONE) {
+ set_count_prop(v->sql->sa, rel, (rv > (BUN_MAX
- lv)) ? BUN_MAX : (lv + rv)); /* overflow check */
+ } else if (lv != BUN_NONE && rv != BUN_NONE) {
+ set_count_prop(v->sql->sa, rel, 0);
+ }
+ } else if (lv == 0) {
+ set_count_prop(v->sql->sa, rel, (is_right(rel->op) ||
is_full(rel->op)) ? rv : 0);
+ } else if (rv == 0) {
+ set_count_prop(v->sql->sa, rel, (is_left(rel->op) ||
is_full(rel->op)) ? lv : 0);
+ } else if (lv != BUN_NONE && rv != BUN_NONE) {
+ dbl sel = 1.0;
+ if (!list_empty(rel->exps)) {
+ for (node *n = rel->exps->h ; n ; n = n->next) {
+ sql_exp *e = n->data;
+ prop *sp = NULL;
+ if ((sp = find_prop(e->p,
PROP_SELECTIVITY)) == NULL) {
+ dbl s =
exp_estimate_selectivity(v->sql, e, rel);
+ /* store selectivity on
predicate for later use */
+ sp = prop_create(v->sql->sa,
PROP_SELECTIVITY, e->p);
+ sp->value.dval = s;
+ e->p = sp;
+ }
+ sel *= sp->value.dval;
+ }
+ }
+ dbl est = (dbl)lv * (dbl)rv * sel;
+ if (est <= 1)
+ est = 2;
+ set_count_prop(v->sql->sa, rel, est > (dbl)BUN_MAX ?
BUN_MAX : (BUN)est);
+ prop *sp = NULL;
+ if ((sp = find_prop(rel->p, PROP_SELECTIVITY)) == NULL)
{
+ /* store selectivity on predicate for later use
*/
+ rel->p = sp = prop_create(v->sql->sa,
PROP_SELECTIVITY, rel->p);
+ sp->value.dval = sel;
+ }
+ }
+ } break;
+ case op_anti:
+ set_count_prop(v->sql->sa, rel, get_rel_count(l));
+ break;
+ case op_semi:
+ if (list_length(rel->exps) == 1 &&
(exp_is_false(rel->exps->h->data) || exp_is_null(rel->exps->h->data))) {
+ set_count_prop(v->sql->sa, rel, 0);
+ } else {
+ if (!list_empty(rel->exps) && !is_single(rel)) {
+ BUN cnt = get_rel_count(l);
+ dbl sel = 1.0;
+ for (node *n = rel->exps->h ; n ; n = n->next) {
+ sql_exp *e = n->data;
+ dbl s =
exp_estimate_selectivity(v->sql, e, rel);
+ /* store selectivity on predicate for
later use */
+ prop *sp = prop_create(v->sql->sa,
PROP_SELECTIVITY, (prop *) e->p);
+ sp->value.dval = s;
+ e->p = sp;
+ sel *= s;
+ }
+ BUN est = cnt == 0 ? 0 : (BUN)((dbl)cnt * sel);
+ if (est > cnt)
+ est = cnt;
+ if (est <= 1 && cnt > 0)
+ est = 2;
+ set_count_prop(v->sql->sa, rel, est);
+ prop *sp = NULL;
+ if ((sp = find_prop(rel->p, PROP_SELECTIVITY))
== NULL) {
+ /* store selectivity on predicate for
later use */
+ rel->p = sp = prop_create(v->sql->sa,
PROP_SELECTIVITY, rel->p);
+ sp->value.dval = sel;
+ }
+ } else {
+ set_count_prop(v->sql->sa, rel,
get_rel_count(l));
+ }
+ }
+ break;
+ default:
+ break;
+ }
+ return rel;
+}
_______________________________________________
checkin-list mailing list -- [email protected]
To unsubscribe send an email to [email protected]
