Changeset: 45dc2b932ce7 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/45dc2b932ce7
Modified Files:
sql/server/rel_optimize_join.c
Branch: default
Log Message:
simplified join reordering
diffs (truncated from 363 to 300 lines):
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
@@ -407,6 +407,41 @@ exp_keyvalue(sql_exp *e)
extern void _exp_print(mvc *sql, sql_exp *e);
extern void _exps_print(mvc *sql, list *l);
+extern void _rel_print(mvc *sql, sql_rel *rel);
+
+static sql_exp *
+find_unique(sql_exp *e, sql_rel *rel)
+{
+ if (is_select(rel->op) || is_basetable(rel->op) ||
is_simple_project(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 prop *
exp_selectivity(visitor *v, sql_exp *e, sql_rel *l, sql_rel *r, prop *p)
@@ -418,11 +453,16 @@ exp_selectivity(visitor *v, sql_exp *e,
bool runique = true;
if (jip) {
- sql_exp *tid = e->r;
+ //sql_exp *tid = e->r;
/* check if TID isn't just in join already */
/* single list (doesn't work for bushy, needs to be in the
relational tree or in the call ! */
- list *tids = v->data;
- if (exps_bind_nid(tids, tid->nid)) {
+ //list *tids = v->data;
+ //if (exps_bind_nid(tids, tid->nid)) {
+ // jip = NULL;
+ // runique = false;
+ //}
+ sql_exp *be = find_unique(e->r, r);
+ if (!be || !is_unique(be)) {
jip = NULL;
runique = false;
}
@@ -483,39 +523,6 @@ 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
@@ -827,7 +834,6 @@ order_joins_bushy( visitor *v, list *rel
mark_join_sides(ta, rels, exps, &max, &rels_a, &r1, &r2, &r3);
-
/* find number of unique pairs */
int *useda = SA_ZNEW_ARRAY(ta, int, nr_exps);
int nr_pairs = unique_pairs(r1, r2, nr_exps, useda);
@@ -856,7 +862,7 @@ order_joins_bushy( visitor *v, list *rel
/* open problem, some expressions use more than 2 relations */
/* For example a.x = b.y * c.z; */
void *data = v->data;
- list *tids_used = v->data = sa_list(v->sql->sa);
+ //list *tids_used = v->data = sa_list(v->sql->sa);
while(list_length(rels) >= 2) {
sql_rel *l = NULL, *r = NULL;
sql_exp *cje;
@@ -901,7 +907,7 @@ order_joins_bushy( visitor *v, list *rel
rel_join_add_exp(v->sql->sa, top, cje);
if (find_prop(cje->p, PROP_JOINIDX) != NULL) {
sql_exp *cjer = cje->r;
- append(tids_used, cjer);
+ //append(tids_used, cjer);
if (is_unique(cjer)) {
if (rel_find_exp(l, cjer))
top->runique =
is_basetable(r->op) || is_select(r->op) || (r->lunique || r->runique);
@@ -922,8 +928,8 @@ order_joins_bushy( visitor *v, list *rel
if (rel_rebind_exp(v->sql, top, e)) {
rel_join_add_exp(v->sql->sa, top, e);
list_remove_data(exps, NULL, e);
- if (find_prop(e->p, PROP_JOINIDX) !=
NULL)
- append(tids_used, e->r);
+ //if (find_prop(e->p, PROP_JOINIDX) !=
NULL)
+ //append(tids_used, e->r);
}
en = next;
}
@@ -966,8 +972,8 @@ order_joins_bushy( visitor *v, list *rel
if (rel_rebind_exp(v->sql, l, e)) {
rel_join_add_exp(v->sql->sa, l,
e);
list_remove_data(exps, NULL, e);
- if (find_prop(e->p,
PROP_JOINIDX) != NULL)
- append(tids_used, e->r);
+ //if (find_prop(e->p,
PROP_JOINIDX) != NULL)
+ //append(tids_used,
e->r);
}
en = next;
}
@@ -1029,200 +1035,6 @@ order_joins_bushy( visitor *v, list *rel
return top;
}
-static bool
-exp_allready_checked(sql_rel *r, sql_exp *e, list *exps)
- /* r is join tree,
- * e is equality join expression, which may overlap with earlier join
expressions in some transitive way
- * exps list of all join expressions in the tree r
- */
-{
- (void)r;
- sql_exp *el = e->l, *er = e->r;
- if (e->type != e_cmp || e->flag != cmp_equal || is_anti(e) ||
is_semantics(e) ||
- el->type != e_column || er->type != e_column ||
- list_length(exps) < 2)
- return false;
- for (node *n = exps->h; n; n = n->next) {
- sql_exp *je1 = n->data, *je1l = je1->l, *je1r = je1->r;
- if (je1->type != e_cmp || je1->flag != cmp_equal ||
is_anti(je1) || is_semantics(je1) ||
- je1l->type != e_column || je1r->type != e_column)
- continue;
-
- bool c1 = el->nid == je1l->nid, c2 = el->nid == je1r->nid, c3 =
er->nid == je1l->nid, c4 = er->nid == je1r->nid;
- if (c1 || c2 || c3 || c4) {
- for (node *m = n->next; m; m = m->next) {
- sql_exp *je2 = n->data, *je2l = je2->l, *je2r =
je2->r;
- if (je2->type != e_cmp || je2->flag !=
cmp_equal || is_anti(je2) || is_semantics(je2) ||
- je2l->type != e_column || je2r->type !=
e_column)
- continue;
- bool c1 = el->nid == je2l->nid, c2 = el->nid ==
je2r->nid, c3 = er->nid == je2l->nid, c4 = er->nid == je2r->nid;
- if (c1 || c2 || c3 || c4) {
- /* todo check if we have some order of
el == je1l, je1r == je2l, je2r == er */
- return true;
- }
- }
- }
- }
- return false;
-}
-
-static void
-je_append(list *exps, sql_exp *je)
-{
- prop *p = find_prop(je->p, PROP_JOINIDX);
- if (p && p->exps) {
- list_merge(exps, p->exps, NULL);
- } else {
- append(exps, je);
- }
-}
-
-extern void _rel_print(mvc *sql, sql_rel *rel);
-
-static sql_rel *
-order_joins_bushy2( visitor *v, list *rels, list *exps)
-{
- /* rels is set of filters relations
- * exps is set of join expressions
- * returns join tree
- */
-
- int nr_exps = list_length(exps), nr_rels = list_length(rels);
- /* split joins into n_m joins and filters (ie others with 1 side
unique's (pkey/ukey etc) */
- //sql_rel *T = NULL;
- //for( node *n = rels->h; n; n = n->next) {
- //_rel_print(v->sql, n->data);
- //}
- int nr = 0;
- for (node *n = exps->h; n; n = n->next) {
- sql_exp *je = n->data;
- if (find_prop(je->p, PROP_JOINIDX)) {
- //printf("joinidx ");
- nr++;
- }
- if (je->type == e_cmp && je->flag == cmp_equal) {
- sql_exp *le = je->l;
- sql_exp *re = je->r;
- if (find_prop(le->p, PROP_HASHCOL)) {
- //printf("hashcol ");
- nr++;
- } else if (find_prop(re->p, PROP_HASHCOL)) {
- //printf("hashcol ");
- nr++;
- }
- }
- //_exp_print(v->sql, je);
- }
- if (nr == list_length(exps)) { /* all pk-fk */
- allocator *ta = MT_thread_getallocator();
- ulng max = 0;
- sql_rel **rels_a = NULL;
- uint16_t *r1, *r2;
- int *r3, ci = 1, cur_nr = 1;
-
- mark_join_sides(ta, rels, exps, &max, &rels_a, &r1, &r2, &r3);
-
- //printf("all pk fk\n");
- BUN min = get_rel_count(rels->h->data);
- sql_rel *cur = rels->h->data;
- for(node *n = rels->h; n; n = n->next, ci++) {
- sql_rel *r = n->data;
- BUN cnt = get_rel_count(r);
-
- if (cnt < min) {
- cur = r;
- min = cnt;
- cur_nr = ci;
- }
- }
- //printf("min %lu ", min);
- //_rel_print(v->sql, cur);
- list_remove_data(rels, NULL, cur);
- list *used_exps = sa_list(ta);
- while(!list_empty(rels)) {
- min = BUN_MAX;
- sql_exp *cje = NULL;
- for(node *n = exps->h; n; n = n->next) { /* find join
expr */
- sql_exp *je = n->data;
- if (r1[je->tmp] == cur_nr || r2[je->tmp] ==
cur_nr) {
- int oside = (r1[je->tmp] == cur_nr) ?
r2[je->tmp] : r1[je->tmp];
- sql_rel *r = rels_a[oside];
- BUN cnt = get_rel_count(r);
- if (cnt < min) {
- cje = je;
- min = cnt;
- }
- }
- }
- if (cje) {
- int oside = (r1[cje->tmp] == cur_nr) ?
r2[cje->tmp] : r1[cje->tmp];
- sql_rel *r = rels_a[oside], *l = cur;
- if (rel_rebind_exp(v->sql, l, cje->l))
- cur = rel_crossproduct(v->sql->sa, l,
r, op_join);
- else
- cur = rel_crossproduct(v->sql->sa, r,
l, op_join);
- rel_join_add_exp(v->sql->sa, cur, cje);
- je_append(used_exps, cje);
- for(int i = 0; i<nr_rels+1; i++) {
- if (rels_a[i] == l || rels_a[i] == r)
- rels_a[i] = cur;
- }
- for(int i = 0; i<nr_exps; i++) {
- if (r1[i] == oside)
- r1[i] = cur_nr;
- if (r2[i] == oside)
- r2[i] = cur_nr;
_______________________________________________
checkin-list mailing list -- [email protected]
To unsubscribe send an email to [email protected]
