Changeset: 2b0a6451e0d6 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=2b0a6451e0d6
Modified Files:
sql/common/sql_hash.c
sql/include/sql_hash.h
sql/server/rel_exp.c
sql/server/rel_graph.c
sql/server/rel_graph.h
sql/server/rel_optimizer.c
sql/server/rel_rel.c
sql/server/rel_rel.h
Branch: graph0
Log Message:
QRW: join reordering (WIP)
Still need to ensure that join predicates are not moved upward
when they depend on a graph operator
diffs (truncated from 507 to 300 lines):
diff --git a/sql/common/sql_hash.c b/sql/common/sql_hash.c
--- a/sql/common/sql_hash.c
+++ b/sql/common/sql_hash.c
@@ -5,6 +5,8 @@
*
* Copyright 1997 - July 2008 CWI, August 2008 - 2017 MonetDB B.V.
*/
+#include <inttypes.h> // uint64_t
+#include <stdlib.h> // rand
#include "monetdb_config.h"
#include "sql_mem.h"
@@ -81,3 +83,18 @@ hash_key(const char *k)
h += (h << 15);
return h;
}
+
+//unsigned int
+//hash_key_ptr(void* ptr)
+//{
+// static uint64_t a = 0;
+// static uint64_t b = 0;
+// const uint64_t p = 2386660291; // prime number
+// if(a == 0 && b == 0){
+// srand(time(NULL));
+// a = rand() +1;
+// b = rand() +1;
+// }
+//
+// return (unsigned int) (( a * ((uint64_t) ptr) + b ) % p);
+//}
diff --git a/sql/include/sql_hash.h b/sql/include/sql_hash.h
--- a/sql/include/sql_hash.h
+++ b/sql/include/sql_hash.h
@@ -37,5 +37,6 @@ extern sql_hash_e *hash_add(sql_hash *ht
extern void hash_del(sql_hash *ht, int key, void *value);
extern unsigned int hash_key(const char *n);
+//extern unsigned int hash_key_ptr(void* pointer);
#endif /* SQL_STACK_H */
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
@@ -1262,7 +1262,6 @@ rel_find_exp( sql_rel *rel, sql_exp *e)
case op_full:
case op_join:
case op_apply:
- case op_graph_join:
ne = rel_find_exp(rel->l, e);
if (!ne)
ne = rel_find_exp(rel->r, e);
@@ -1287,6 +1286,20 @@ rel_find_exp( sql_rel *rel, sql_exp *e)
if (rel->exps && e->type == e_column && e->l)
ne = exps_bind_column2(rel->exps, e->l, e->r);
break;
+ case op_graph_join:
+ case op_graph_select: {
+ assert(ne == NULL && "Expression already assigned?");
+ // check whether this is some kind of shortest path
+ if(e->type == e_column){
+ sql_graph* graph_ptr = (sql_graph*) rel;
+ ne = exps_bind_column2(graph_ptr->spfw, e->l,
e->r);
+ }
+
+ // try with the lhs
+ if(!ne) { ne = rel_find_exp(rel->l, e); }
+ // and then with the rhs (ok for selects as well)
+ if(!ne) { ne = rel_find_exp(rel->r, e); }
+ } break;
default:
if (!is_project(rel->op) && rel->l)
ne = rel_find_exp(rel->l, e);
diff --git a/sql/server/rel_graph.c b/sql/server/rel_graph.c
--- a/sql/server/rel_graph.c
+++ b/sql/server/rel_graph.c
@@ -15,8 +15,51 @@
#include "rel_exp.h"
#include "rel_rel.h"
#include "rel_select.h"
+#include "sql_mem.h" // sql_ref_init
#include "sql_relation.h" // rel_graph
+/*****************************************************************************
+ * *
+ * Create the graph operator *
+ * *
+ *****************************************************************************/
+
+sql_graph* rel_graph_create(sql_allocator *sa) {
+ sql_graph *r = SA_NEW(sa, sql_graph);
+ if(!r) return NULL;
+ memset(r, 0, sizeof(sql_graph));
+ sql_ref_init(&(r->relation.ref));
+ return r;
+}
+
+sql_graph* rel_graph_move(mvc* sql, sql_rel* rel, sql_rel* l, sql_rel* r,
sql_exp* e){
+ sql_graph* graph_old = NULL;
+ sql_graph* graph_new = NULL;
+ sql_rel* graph_rel = NULL;
+
+ assert(rel && is_graph(rel->op));
+ graph_old = (sql_graph*) rel;
+ graph_new = rel_graph_create(sql->sa);
+ if(!graph_new) return NULL;
+ memcpy(graph_new + sizeof(sql_ref), graph_old + sizeof(sql_ref),
sizeof(sql_graph) - sizeof(sql_ref));
+ graph_rel = &(graph_new->relation);
+ graph_rel->l = l;
+ graph_rel->r = r;
+ graph_rel->exps = new_exp_list(sql->sa);
+ list_append(graph_rel->exps, e);
+
+ return graph_new;
+}
+
+sql_rel* rel_graph_move2rel(mvc* sql, sql_rel* rel, sql_rel* l, sql_rel* r,
sql_exp* e){
+ return (sql_rel*) rel_graph_move(sql, rel, l, r, e);
+}
+
+/*****************************************************************************
+ * *
+ * Parse the REACHES clause *
+ * *
+ *****************************************************************************/
sql_rel* rel_graph_reaches(mvc *sql, sql_rel *rel, symbol *sq, int context){
// TODO handle edge components defined with multiple attributes
// this needs changes in the parser to accept list of columns & scalars
diff --git a/sql/server/rel_graph.h b/sql/server/rel_graph.h
--- a/sql/server/rel_graph.h
+++ b/sql/server/rel_graph.h
@@ -15,4 +15,8 @@
sql_rel* rel_graph_reaches(mvc *sql, sql_rel *rel, symbol *sq, int context);
sql_exp* rel_graph_cheapest_sum(mvc *sql, sql_rel **rel, symbol *sq, int
context);
+sql_graph* rel_graph_create(sql_allocator *sa);
+sql_graph* rel_graph_move(mvc* sql, sql_rel* graph_old, sql_rel* l, sql_rel*
r, sql_exp* e);
+sql_rel* rel_graph_move2rel(mvc* sql, sql_rel* graph_old, sql_rel* l, sql_rel*
r, sql_exp* e);
+
#endif /* _REL_GRAPH_H_ */
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
@@ -319,10 +319,21 @@ rel_properties(mvc *sql, global_props *g
static sql_rel * rel_join_order(mvc *sql, sql_rel *rel) ;
+// graph related stuff
+typedef struct {
+ sql_exp* join;
+ sql_rel* graph;
+} graph_association;
+
+static int
+graph_association_cmp(graph_association* a, sql_exp* e){
+ return (e == a->join) ? 0 : -1;
+}
+
static void
get_relations(mvc *sql, sql_rel *rel, list *rels)
{
- if (!rel_is_ref(rel) && rel->op == op_join && rel->exps == NULL) {
+ if (!rel_is_ref(rel) && (rel->op == op_join || rel->op ==
op_graph_join) && rel->exps == NULL) {
sql_rel *l = rel->l;
sql_rel *r = rel->r;
@@ -484,29 +495,54 @@ exp_joins_rels(sql_exp *e, list *rels)
{
sql_rel *l = NULL, *r = NULL;
- assert (e->type == e_cmp);
-
- if (e->flag == cmp_or) {
- l = NULL;
- } else if (get_cmp(e) == cmp_filter) {
+ switch(e->type){
+ case e_cmp:
+ if (e->flag == cmp_or) {
+ l = NULL;
+ } else if (get_cmp(e) == cmp_filter) {
+ list *ll = e->l;
+ list *lr = e->r;
+
+ l = find_rel(rels, ll->h->data);
+ r = find_rel(rels, lr->h->data);
+ } else if (e->flag == cmp_in || e->flag == cmp_notin) {
+ list *lr = e->r;
+
+ l = find_rel(rels, e->l);
+ if (lr && lr->h)
+ r = find_rel(rels, lr->h->data);
+ } else {
+ l = find_rel(rels, e->l);
+ r = find_rel(rels, e->r);
+ }
+
+ if (l && r)
+ return 0;
+ break;
+ case e_graph: {
+ // same as cmp_filter
list *ll = e->l;
list *lr = e->r;
-
- l = find_rel(rels, ll->h->data);
- r = find_rel(rels, lr->h->data);
- } else if (e->flag == cmp_in || e->flag == cmp_notin) {
- list *lr = e->r;
-
- l = find_rel(rels, e->l);
- if (lr && lr->h)
- r = find_rel(rels, lr->h->data);
- } else {
- l = find_rel(rels, e->l);
- r = find_rel(rels, e->r);
- }
-
- if (l && r)
+ assert(list_length(ll) >= 1 && list_length(lr) >= 1);
+
+ for(node *n = ll->h; n; n = n->next){
+ sql_rel* tmp = find_rel(rels, n->data);
+ if(tmp == NULL || (l != NULL && l != tmp)) return -1;
+ l = tmp;
+ }
+ for(node *n = lr->h; n; n = n->next){
+ sql_rel* tmp = find_rel(rels, n->data);
+ if(tmp == NULL || (r != NULL && r != tmp)) return -1;
+ r = tmp;
+ }
+
return 0;
+ } break;
+ default:
+ assert (0 && "Invalid expression type");
+ }
+
+
return -1;
}
@@ -794,8 +830,22 @@ find_fk( mvc *sql, list *rels, list *exp
return sdje;
}
+
static sql_rel *
-order_joins(mvc *sql, list *rels, list *exps)
+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)
{
sql_rel *top = NULL, *l = NULL, *r = NULL;
sql_exp *cje;
@@ -828,51 +878,74 @@ order_joins(mvc *sql, list *rels, list *
* */
if (cje->type != e_cmp || !is_complex_exp(cje->flag) ||
!find_prop(cje->p, PROP_HASHCOL) /*||
(cje->type == e_cmp && cje->f == NULL)*/) {
- l = find_one_rel(rels, cje->l);
- r = find_one_rel(rels, cje->r);
+ 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);
}
if (l && r && l != r) {
list_remove_data(sdje, cje);
list_remove_data(exps, cje);
- }
- }
- 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.
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
https://www.monetdb.org/mailman/listinfo/checkin-list
