Changeset: 9e6a391a3840 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=9e6a391a3840
Added Files:
sql/server/rel_planner.c
sql/server/rel_planner.h
Modified Files:
sql/server/Makefile.ag
sql/server/rel_optimizer.c
sql/server/rel_optimizer.h
Branch: default
Log Message:
MonetDB goes classic....
Added first version of a query planner, just for the join tree/order.
Will need lots more work.., statistics, cost models etc...
Therefor its disabled by default, it can be enabled using --set sql_debug=256
This work started because we would like a better join index storage (which
is less or not dependend on the tuple ids). Disabling the single column
join indices can therefor be switched on also using --set sql_debug=512.
diffs (truncated from 1021 to 300 lines):
diff --git a/sql/server/Makefile.ag b/sql/server/Makefile.ag
--- a/sql/server/Makefile.ag
+++ b/sql/server/Makefile.ag
@@ -49,6 +49,7 @@ lib_sqlserver = {
rel_prop.c \
rel_exp.c \
rel_optimizer.c \
+ rel_planner.c \
rel_distribute.c \
rel_psm.c \
rel_xml.c \
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
@@ -27,6 +27,7 @@
#include "rel_dump.h"
#include "rel_select.h"
#include "rel_updates.h"
+#include "rel_planner.h"
#include "sql_env.h"
#define new_func_list(sa) sa_list(sa)
@@ -415,14 +416,6 @@ exp_keyvalue(sql_exp *e)
return cnt;
}
-static int
-rel_has_exp(sql_rel *rel, sql_exp *e)
-{
- if (rel_find_exp(rel, e) != NULL)
- return 0;
- return -1;
-}
-
static sql_rel *
find_rel(list *rels, sql_exp *e)
{
@@ -432,22 +425,6 @@ find_rel(list *rels, sql_exp *e)
return NULL;
}
-static sql_rel *
-find_one_rel(list *rels, sql_exp *e)
-{
- node *n;
- sql_rel *fnd = NULL;
-
- for(n = rels->h; n; n = n->next) {
- if (rel_has_exp(n->data, e) == 0) {
- if (fnd)
- return NULL;
- fnd = n->data;
- }
- }
- return fnd;
-}
-
static int
joinexp_cmp(list *rels, sql_exp *h, sql_exp *key)
{
@@ -510,7 +487,7 @@ table_colexp(sql_exp *e, sql_rel *r)
return NULL;
}
-static int
+int
exp_joins_rels(sql_exp *e, list *rels)
{
sql_rel *l = NULL, *r = NULL;
@@ -668,7 +645,7 @@ rel_find_column( sql_allocator *sa, sql_
}
static list *
-find_fk( sql_allocator *sa, list *rels, list *exps)
+find_fk( mvc *sql, list *rels, list *exps)
{
node *djn;
list *sdje, *aje, *dje;
@@ -685,7 +662,7 @@ find_fk( sql_allocator *sa, list *rels,
break;
if (!find_prop(je->p, PROP_JOINIDX)) {
int swapped = 0;
- list *aaje = matching_joins(sa, rels, aje, je);
+ list *aaje = matching_joins(sql->sa, rels, aje, je);
list *eje = list_select(aaje, (void*)1, (fcmp)
&exp_is_eqjoin, (fdup)NULL);
sql_rel *lr = find_rel(rels, le), *olr = lr;
sql_rel *rr = find_rel(rels, re), *orr = rr;
@@ -717,7 +694,7 @@ find_fk( sql_allocator *sa, list *rels,
swapped = 1;
}
- if (idx && (iname = sa_strconcat( sa, "%",
idx->base.name)) != NULL &&
+ if (idx && (iname = sa_strconcat( sql->sa, "%",
idx->base.name)) != NULL &&
((!swapped && name_find_column(olr, NULL,
iname, -2, &bt) == NULL) ||
( swapped && name_find_column(orr, NULL,
iname, -2, &bt) == NULL)))
idx = NULL;
@@ -727,28 +704,39 @@ find_fk( sql_allocator *sa, list *rels,
node *n;
sql_exp *t = NULL, *i = NULL;
- /* Add join between idx and TID */
- if (swapped) {
- sql_exp *s = je->l, *l = je->r;
-
- t = rel_find_column(sa, lr, s->l, TID);
- i = rel_find_column(sa, rr, l->l,
iname);
- assert(t && i);
- je = exp_compare(sa, i, t, cmp_equal);
- } else {
- sql_exp *s = je->r, *l = je->l;
-
- t = rel_find_column(sa, rr, s->l, TID);
- i = rel_find_column(sa, lr, l->l,
iname);
- assert(t && i);
- je = exp_compare(sa, i, t, cmp_equal);
+ if (list_length(lcols) > 1 ||
!mvc_debug_on(sql, 512)) {
+
+ /* Add join between idx and TID */
+ if (swapped) {
+ sql_exp *s = je->l, *l = je->r;
+
+ t = rel_find_column(sql->sa,
lr, s->l, TID);
+ i = rel_find_column(sql->sa,
rr, l->l, iname);
+ assert(t && i);
+ je = exp_compare(sql->sa, i, t,
cmp_equal);
+ } else {
+ sql_exp *s = je->r, *l = je->l;
+
+ t = rel_find_column(sql->sa,
rr, s->l, TID);
+ i = rel_find_column(sql->sa,
lr, l->l, iname);
+ assert(t && i);
+ je = exp_compare(sql->sa, i, t,
cmp_equal);
+ }
+
+ /* Remove all join expressions */
+ for (n = eje->h; n; n = n->next)
+ list_remove_data(exps, n->data);
+ append(exps, je);
+ djn->data = je;
+ } else if (swapped) { /* else keep je for
single column expressions */
+ je = exp_compare(sql->sa, je->r, je->l,
cmp_equal);
+ /* Remove all join expressions */
+ for (n = eje->h; n; n = n->next)
+ list_remove_data(exps, n->data);
+ append(exps, je);
+ djn->data = je;
}
- /* Remove all join expressions */
- for (n = eje->h; n; n = n->next)
- list_remove_data(exps, n->data);
- append(exps, je);
- djn->data = je;
- je->p = p = prop_create(sa, PROP_JOINIDX,
je->p);
+ je->p = p = prop_create(sql->sa, PROP_JOINIDX,
je->p);
p->value = idx;
}
lcols->destroy = NULL;
@@ -757,7 +745,7 @@ find_fk( sql_allocator *sa, list *rels,
}
/* sort expressions on weighted number of reducing operators */
- sdje = order_join_expressions(sa, dje, rels);
+ sdje = order_join_expressions(sql->sa, dje, rels);
return sdje;
}
@@ -771,7 +759,10 @@ order_joins(mvc *sql, list *rels, list *
int fnd = 0;
/* find foreign keys and reorder the expressions on reducing quality */
- sdje = find_fk(sql->sa, rels, exps);
+ sdje = find_fk(sql, rels, exps);
+
+ if (list_length(rels) > 2 && mvc_debug_on(sql, 256))
+ return rel_planner(sql, rels, sdje);
/* open problem, some expressions use more than 2 relations */
/* For example a.x = b.y * c.z; */
@@ -990,7 +981,7 @@ reorder_join(mvc *sql, sql_rel *rel)
list_append(rels, rel->l);
list_append(rels, rel->r);
cnt = list_length(exps);
- rel->exps = find_fk(sql->sa, rels, exps);
+ rel->exps = find_fk(sql, rels, exps);
if (list_length(rel->exps) != cnt)
rel->exps = order_join_expressions(sql->sa, exps, rels);
} else {
@@ -5323,7 +5314,7 @@ rel_semijoin_use_fk(int *changes, mvc *s
append(rels, rel->l);
append(rels, rel->r);
- (void) find_fk( sql->sa, rels, exps);
+ (void) find_fk( sql, rels, exps);
rel->exps = exps;
}
return rel;
diff --git a/sql/server/rel_optimizer.h b/sql/server/rel_optimizer.h
--- a/sql/server/rel_optimizer.h
+++ b/sql/server/rel_optimizer.h
@@ -24,4 +24,7 @@
extern sql_rel * rel_optimizer(mvc *sql, sql_rel *rel);
+extern int exp_joins_rels(sql_exp *e, list *rels);
+
+
#endif /*_REL_OPTIMIZER_H_*/
diff --git a/sql/server/rel_planner.c b/sql/server/rel_planner.c
new file mode 100644
--- /dev/null
+++ b/sql/server/rel_planner.c
@@ -0,0 +1,774 @@
+/*
+ * The contents of this file are subject to the MonetDB Public License
+ * Version 1.1 (the "License"); you may not use this file except in
+ * compliance with the License. You may obtain a copy of the License at
+ * http://www.monetdb.org/Legal/MonetDBLicense
+ *
+ * Software distributed under the License is distributed on an "AS IS"
+ * basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
+ * License for the specific language governing rights and limitations
+ * under the License.
+ *
+ * The Original Code is the MonetDB Database System.
+ *
+ * The Initial Developer of the Original Code is CWI.
+ * Portions created by CWI are Copyright (C) 1997-July 2008 CWI.
+ * Copyright August 2008-2013 MonetDB B.V.
+ * All Rights Reserved.
+ */
+
+#include "monetdb_config.h"
+#include "rel_planner.h"
+#include "rel_exp.h"
+#include "rel_prop.h"
+#include "rel_select.h"
+#include "rel_optimizer.h"
+
+typedef struct memoitem {
+ char *name;
+ list *rels;
+ list *exps;
+ list *joins;
+ int done;
+ int level;
+ lng count;
+ dbl sel;
+ lng cost;
+ void *data;
+} memoitem;
+
+#define p_pkey 1
+#define p_fkey 2
+#define p_ukey 3
+
+typedef struct memojoin {
+ memoitem *l, *r;
+ int rules; /* handled rules */
+ int prop; /* pkey, fkey, ukey */
+ lng cost;
+ sql_exp *e;
+} memojoin;
+
+static int
+memoitem_key( memoitem *mi )
+{
+ return hash_key(mi->name);
+}
+
+static memoitem*
+memo_find(list *memo, char *name)
+{
+ int key = hash_key(name);
+ sql_hash_e *he = memo->ht->buckets[key&(memo->ht->size-1)];
+
+ for (; he; he = he->chain) {
+ memoitem *mi = he->value;
+
+ if (mi->name && strcmp(mi->name, name) == 0)
+ return mi;
+ }
+ return NULL;
+}
+
+static char *
+merge_names( sql_allocator *sa, char *lname, char *rname)
+{
+ int llen = strlen(lname);
+ int rlen = strlen(rname);
+ char *n = SA_NEW_ARRAY(sa, char, llen+rlen+2), *p = n;
+ char *c = lname;
+
+ while (*c) {
+ int i = 0;
+ for ( ; c[i] && c[i] != ','; i++)
+ p[i] = c[i];
+ p[i] = 0;
+ if (strcmp(p, rname) > 0) {
+ strncpy(p, rname, rlen);
+ p+=rlen;
_______________________________________________
checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
