Changeset: 1a557e468767 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=1a557e468767
Modified Files:
sql/include/sql_relation.h
sql/server/rel_optimizer.c
Branch: graph0
Log Message:
Join reordering
diffs (truncated from 663 to 300 lines):
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
@@ -231,6 +231,10 @@ typedef enum operator_type {
(op == op_sample)
#define is_graph(op) \
(op == op_graph_join || op == op_graph_select)
+#define is_extended_select(op) \
+ (is_select(op) || op == op_graph_select)
+#define is_extended_join(op) \
+ (is_join(op) || op == op_graph_join)
/* NO NIL semantics of aggr operations */
#define need_no_nil(e) \
diff --git a/sql/server/rel_optimizer.c b/sql/server/rel_optimizer.c
--- a/sql/server/rel_optimizer.c
+++ b/sql/server/rel_optimizer.c
@@ -34,6 +34,8 @@ typedef int (*find_prop_fptr)(mvc *sql,
static sql_rel * rewrite_topdown(mvc *sql, sql_rel *rel, rewrite_fptr
rewriter, int *has_changes);
static sql_rel * rewrite(mvc *sql, sql_rel *rel, rewrite_fptr rewriter, int
*has_changes) ;
+static sql_rel * rel_graph_pda(int *changes, mvc *sql, sql_rel *rel);
+static sql_rel * rel_push_select_down(int *changes, mvc *sql, sql_rel *rel);
static sql_rel * rel_remove_empty_select(int *changes, mvc *sql, sql_rel *rel);
static sql_subfunc *find_func( mvc *sql, char *name, list *exps );
@@ -321,19 +323,25 @@ static sql_rel * rel_join_order(mvc *sql
// graph related stuff
typedef struct {
- sql_exp* join;
+ sql_exp* exp;
sql_rel* graph;
} graph_association;
static int
graph_association_cmp(graph_association* a, sql_exp* e){
- return (e == a->join) ? 0 : -1;
+ return (e == a->exp) ? 0 : -1;
}
static void
get_relations(mvc *sql, sql_rel *rel, list *rels)
{
- if (!rel_is_ref(rel) && (rel->op == op_join || rel->op ==
op_graph_join) && rel->exps == NULL) {
+ bool domain_op;
+
+ if(!rel) return; // stop the recursion
+
+ domain_op = rel->op == op_join || rel->op == op_graph_join || rel->op
== op_select || rel->op == op_graph_select;
+
+ if (domain_op && !rel_is_ref(rel) && rel->exps == NULL) {
sql_rel *l = rel->l;
sql_rel *r = rel->r;
@@ -608,6 +616,7 @@ find_basetable( sql_rel *r)
return r;
case op_project:
case op_select:
+ case op_graph_select:
return find_basetable(r->l);
default:
return NULL;
@@ -646,10 +655,18 @@ order_join_expressions(mvc *sql, list *d
sql_rel *l = find_rel(rels, e->l);
sql_rel *r = find_rel(rels, e->r);
- if (l && (is_select(l->op) || l->op == op_graph_select)
&& l->exps)
- keys[i] += list_length(l->exps)*10 +
exps_count(l->exps)*debug;
- if (r && (is_select(r->op) || r->op == op_graph_select)
&& r->exps)
- keys[i] += list_length(r->exps)*10 +
exps_count(r->exps)*debug;
+ if(l != NULL){
+ while (is_extended_select(l->op)){
+ keys[i] += list_length(l->exps)*10 +
exps_count(l->exps)*debug;
+ l = l->l;
+ }
+ }
+ if(r != NULL){
+ while (is_extended_select(r->op)) {
+ keys[i] += list_length(r->exps)*10 +
exps_count(r->exps)*debug;
+ r = r->l;
+ }
+ }
}
pos[i] = i;
}
@@ -721,7 +738,7 @@ distinct_join_exps(list *aje, list *lrel
return res;
}
-static list *
+static list*
find_fk( mvc *sql, list *rels, list *exps)
{
node *djn;
@@ -740,6 +757,9 @@ find_fk( mvc *sql, list *rels, list *exp
sql_idx *idx = NULL;
sql_exp *je = djn->data, *le = je->l, *re = je->r;
+ if (je->type == e_graph)
+ continue;
+
if (je->type != e_cmp || is_complex_exp(je->flag))
break;
if (!find_prop(je->p, PROP_JOINIDX)) {
@@ -832,20 +852,7 @@ find_fk( mvc *sql, list *rels, list *exp
static sql_rel *
-reset_graph_join(mvc *sql, list* graphs, sql_rel *l, sql_rel *r, sql_exp *e){
- node* n = NULL;
- sql_rel* graph = NULL;
-
- n = list_find(graphs, e, (fcmp) graph_association_cmp);
- assert(n != NULL);
- graph = rel_graph_move2rel(sql, ((graph_association*) n->data)->graph,
l, r, e);
- list_remove_node(graphs, n);
-
- return graph;
-}
-
-static sql_rel *
-order_joins(mvc *sql, list *rels, list *exps, list *graphs)
+order_joins(mvc *sql, list *rels, list *exps)
{
sql_rel *top = NULL, *l = NULL, *r = NULL;
sql_exp *cje;
@@ -873,79 +880,56 @@ order_joins(mvc *sql, list *rels, list *
/* find the involved relations */
- /* complex expressions may touch multiple base tables
+ /* complex expressions may touch multiple base tables
* Should be pushed up to extra selection.
* */
if (cje->type != e_cmp || !is_complex_exp(cje->flag) ||
!find_prop(cje->p, PROP_HASHCOL) /*||
(cje->type == e_cmp && cje->f == NULL)*/) {
- sql_exp *le, *re;
- if(cje->type == e_graph){
- assert(list_length(cje->l) == 1 &&
list_length(cje->r) == 1);
- le = ((list*) cje->l)->h->data;
- re = ((list*) cje->r)->h->data;
- } else {
- le = cje->l;
- re = cje->r;
- }
-
- l = find_one_rel(rels, le);
- r = find_one_rel(rels, re);
+ l = find_one_rel(rels, cje->l);
+ r = find_one_rel(rels, cje->r);
}
if (l && r && l != r) {
list_remove_data(sdje, cje);
list_remove_data(exps, cje);
- 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.
- */
- if(cje->type != e_graph){
- top = rel_crossproduct(sql->sa, l, r, op_join);
- rel_join_add_exp(sql->sa, top, cje);
- } else { // bring back to life the graph join
- top = reset_graph_join(sql, graphs, l, r, 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;
- assert(e->type != e_graph && "Mixing regular
and graph joins");
-
- rel_join_add_exp(sql->sa, top, 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;
- }
- }
-
+ }
+ }
+ if (l && r && 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(sql->sa, l, r, op_join);
+ rel_join_add_exp(sql->sa, top, 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;
+
+ rel_join_add_exp(sql->sa, top, 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;
+ }
/* build join tree using the ordered list */
while(list_length(exps) && fnd) {
fnd = 0;
/* find the first expression which could be added */
for(djn = sdje->h; djn && !fnd && rels->h; djn =
(!fnd)?djn->next:NULL) {
node *ln, *rn, *en;
- sql_exp *le, *re;
-
+
cje = djn->data;
- if(cje->type == e_graph){
- assert(list_length(cje->l) == 1 &&
list_length(cje->r) == 1);
- le = ((list*) cje->l)->h->data;
- re = ((list*) cje->r)->h->data;
- } else {
- le = cje->l;
- re = cje->r;
- }
- ln = list_find(n_rels, le, (fcmp)&rel_has_exp);
- rn = list_find(n_rels, re, (fcmp)&rel_has_exp);
+ ln = list_find(n_rels, cje->l, (fcmp)&rel_has_exp);
+ rn = list_find(n_rels, cje->r, (fcmp)&rel_has_exp);
if (ln || rn) {
/* remove the expression from the lists */
@@ -962,32 +946,27 @@ order_joins(mvc *sql, list *rels, list *
} else if (ln || rn) {
if (ln) {
l = ln->data;
- r = find_rel(rels, re);
+ r = find_rel(rels, cje->r);
} else {
l = rn->data;
- r = find_rel(rels, le);
+ r = find_rel(rels, cje->l);
}
list_remove_data(rels, r);
append(n_rels, r);
/* create a join using the current expression */
- if(cje->type != e_graph){
- top = rel_crossproduct(sql->sa, top, r,
op_join);
- rel_join_add_exp(sql->sa, top, cje);
- } else {
- top = reset_graph_join(sql, graphs, l,
r, cje);
- }
+ top = rel_crossproduct(sql->sa, top, r,
op_join);
+ rel_join_add_exp(sql->sa, top, cje);
/* all join expressions on these tables */
while((en = list_find(exps, n_rels,
(fcmp)&exp_joins_rels)) != NULL) {
sql_exp *e = en->data;
- assert(e->type != e_graph && "Mixing
regular and graph joins");
rel_join_add_exp(sql->sa, top, e);
list_remove_data(exps, e);
}
- /* Remove other joins on the current 'n_rels'
+ /* Remove other joins on the current 'n_rels'
set in the distinct list too */
- while((en = list_find(sdje, n_rels,
(fcmp)&exp_joins_rels)) != NULL)
+ while((en = list_find(sdje, n_rels,
(fcmp)&exp_joins_rels)) != NULL)
list_remove_data(sdje, en->data);
fnd = 1;
}
@@ -998,7 +977,7 @@ order_joins(mvc *sql, list *rels, list *
for(n=rels->h; n; n = n->next) {
if (top)
top = rel_crossproduct(sql->sa, top, n->data,
op_join);
- else
+ else
top = n->data;
}
}
@@ -1011,13 +990,13 @@ order_joins(mvc *sql, list *rels, list *
/* find the involved relations */
- /* complex expressions may touch multiple base tables
+ /* complex expressions may touch multiple base tables
* Should be push up to extra selection. */
/*
l = find_one_rel(rels, e->l);
r = find_one_rel(rels, e->r);
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
https://www.monetdb.org/mailman/listinfo/checkin-list
