Update of /cvsroot/monetdb/pathfinder/compiler/algebra
In directory sc8-pr-cvs16:/tmp/cvs-serv26652/algebra
Modified Files:
algebra.c algebra_cse.c algopt.c logical.c physical.c
planner.c
Log Message:
Thetajoin operator:
Introduced a thetajoin operator in the logical algebra (and the physical
algebra and the MIL generation). This new thetajoin can handle a list of
conjunctive predicates where each predicate represents an (in-)equality
condition.
Thetajoin introduction:
A thetajoin operator is introduced either by a small pattern
(select-comparison-cross) in opt_general.brg or by a new introduction
phase in intro_thetajoin.c. The latter introduction phase uses a
selection as a basis to find the *correct* equi-join and transforms
this equi-join into a thetajoin (for more details please look into
the code).
Thetajoin optimization:
Similar to the MVD optimization phase that pushes cross product
operators up in the DAG structure this checkin provides a new
optimization phase that pushes thetajoin operators up in the DAG
(opt_thetajoin.c). These rewrites result in thetajoin operators
that contain multiple predicates. (E.g. the transformed equi-joins
eventually hit the selection that triggered the rewrite and thus form
a new scope-dependent value-based join -- see XMark Q3 and Q4.)
Additional changes:
opt_general.brg
* Extended thetajoin pattern to cope with inequality comparisons
* Rewrite the pattern: semijoin (distinct (Rel), Rel) into
distinct (semijoin (Rel, Rel) as the semijoin hopefully reduces
the cardinality more than the distinct operator. (This speeds
up XMark Q12 by a factor of 2.5.)
intro_proxy.c
* Added a preceding phase that removes all semijoin operators.
(Using only simply checks more proxies are now detected.)
* Removed unnest optimization phase (thetajoin optimization
does the same in a more general scenario).
physical.c
* Toyed around with the cost model
* Fixed 'PFord_order_dir_at' bug
planner.c
* Generated more ordered alternatives (even if an ordering is
not required) after an operator is mapped to physical algebra.
In some situations this avoids in a later step planning the same
sort operator multiple times. (We only introduce orderings for
iter-like columns and sort at most two columns. Otherwise the
plan space explodes for some sample queries.)
* Extended list of possible orderings for the rownum operator
Index: algopt.c
===================================================================
RCS file: /cvsroot/monetdb/pathfinder/compiler/algebra/algopt.c,v
retrieving revision 1.15
retrieving revision 1.16
diff -u -d -r1.15 -r1.16
--- algopt.c 28 Mar 2007 15:06:49 -0000 1.15
+++ algopt.c 7 May 2007 10:17:05 -0000 1.16
@@ -34,6 +34,7 @@
/* always include pathfinder.h first! */
#include "pathfinder.h"
#include <assert.h>
+#include <stdio.h>
#include "algopt.h"
#include "map_names.h"
@@ -41,6 +42,7 @@
#include "timer.h"
#include "algebra_cse.h"
#include "la_proxy.h"
+#include "la_thetajoin.h"
#define MAP_ORI_NAMES(phase) \
if (unq_names) { \
@@ -94,7 +96,14 @@
bool proxies_involved = false;
char *args = PFstate.opt_alg;
+#define DEBUG_OPT_STR 0
+#if DEBUG_OPT_STR
+ fprintf (stderr, "-o");
+#endif
while (*args) {
+#if DEBUG_OPT_STR
+ fputc (*args, stderr);
+#endif
switch (*args) {
case 'A': /* disabled */
/*
@@ -242,6 +251,20 @@
PFtimer_str (tm));
break;
+ case 'T':
+ MAP_ORI_NAMES("thetajoin optimization")
+
+ tm = PFtimer_start ();
+
+ root = PFintro_thetajoins (root);
+ root = PFalgopt_thetajoin (root);
+
+ tm = PFtimer_stop (tm);
+ if (timing)
+ PFlog (" thetajoin optimization:\t %s",
+ PFtimer_str (tm));
+ break;
+
case 'V':
MAP_ORI_NAMES("required value optimization")
REMOVE_PROXIES("required value optimization")
@@ -374,6 +397,9 @@
args++;
root = PFla_cse (root);
}
+#if DEBUG_OPT_STR
+ fputc ('\n', stderr);
+#endif
if (unq_names)
PFinfo (OOPS_WARNING,
Index: algebra.c
===================================================================
RCS file: /cvsroot/monetdb/pathfinder/compiler/algebra/algebra.c,v
retrieving revision 1.51
retrieving revision 1.52
diff -u -d -r1.51 -r1.52
--- algebra.c 11 Apr 2007 14:17:42 -0000 1.51
+++ algebra.c 7 May 2007 10:17:04 -0000 1.52
@@ -899,4 +899,13 @@
return NULL;
}
+/**
+ * Construct a predicate.
+ */
+PFalg_sel_t PFalg_sel (PFalg_comp_t comp,
+ PFalg_att_t left,
+ PFalg_att_t right) {
+ return (PFalg_sel_t) { .comp = comp, .left = left, .right = right };
+}
+
/* vim:set shiftwidth=4 expandtab: */
Index: physical.c
===================================================================
RCS file: /cvsroot/monetdb/pathfinder/compiler/algebra/physical.c,v
retrieving revision 1.32
retrieving revision 1.33
diff -u -d -r1.32 -r1.33
--- physical.c 15 Mar 2007 14:12:55 -0000 1.32
+++ physical.c 7 May 2007 10:17:06 -0000 1.33
@@ -57,7 +57,7 @@
#define DEFAULT_COST INIT_COST
#define AGGR_COST 50
#define JOIN_COST 100
-#define SORT_COST 100
+#define SORT_COST 700
/**
* Create an algebra operator (leaf) node.
@@ -650,7 +650,7 @@
ret->orderings = PFord_set ();
/* ---- EqJoin: costs ---- */
- ret->cost = 1.5 * JOIN_COST + n1->cost + n2->cost;
+ ret->cost = 2.5 * JOIN_COST + n1->cost + n2->cost;
return ret;
}
@@ -700,6 +700,160 @@
}
/**
+ * ThetaJoin: Theta-Join. Does not provide any ordering guarantees.
+ */
+PFpa_op_t *
+PFpa_thetajoin (const PFpa_op_t *n1, const PFpa_op_t *n2,
+ unsigned int count, PFalg_sel_t *pred)
+{
+ unsigned int i;
+ PFpa_op_t *ret;
+
+ /* verify that the join attributes are all available */
+ for (i = 0; i < count; i++)
+ if (!contains_att (n1->schema, pred[i].left) ||
+ !contains_att (n2->schema, pred[i].right))
+ break;
+
+ /* did we find all attributes? */
+ if (i < count)
+ PFoops (OOPS_FATAL,
+ "attribute `%s' referenced in theta-join not found",
+ contains_att (n2->schema, pred[i].right)
+ ? PFatt_str(pred[i].left) : PFatt_str(pred[i].right));
+
+ ret = wire2 (pa_thetajoin, n1, n2);
+
+ ret->sem.thetajoin.count = count;
+ ret->sem.thetajoin.pred = PFmalloc (count * sizeof (PFalg_sel_t));
+ for (i = 0; i < count; i++)
+ ret->sem.thetajoin.pred[i] = pred[i];
+
+ /* allocate memory for the result schema */
+ ret->schema.count = n1->schema.count + n2->schema.count;
+ ret->schema.items
+ = PFmalloc (ret->schema.count * sizeof (*(ret->schema.items)));
+
+ /* copy schema from n1 */
+ for (unsigned int i = 0; i < n1->schema.count; i++)
+ ret->schema.items[i] = n1->schema.items[i];
+
+ /* copy schema from n2 */
+ for (unsigned int i = 0; i < n2->schema.count; i++)
+ ret->schema.items[n1->schema.count + i] = n2->schema.items[i];
+
+ /* ---- ThetaJoin: orderings ---- */
+ ret->orderings = PFord_set ();
+
+ /* ---- ThetaJoin: costs ---- */
+
+ /* make it a little bit more expensive than the normal equi-join
+ and more expensive than the specialized variant that require
+ two sorted columns up front. */
+ ret->cost = 4 * JOIN_COST + 2 * SORT_COST + n1->cost + n2->cost;
+
+ return ret;
+}
+
+/**
+ * ThetaJoin: Theta-Join. Returns two columns (from n1 and n2)
+ * with duplicates eliminated. Preserves the order
+ * of the left argument.
+ */
+PFpa_op_t *
+PFpa_unq2_thetajoin (PFalg_comp_t comp, PFalg_att_t left, PFalg_att_t right,
+ PFalg_att_t ldist, PFalg_att_t rdist,
+ const PFpa_op_t *n1, const PFpa_op_t *n2)
+{
+ PFpa_op_t *ret = wire2 (pa_unq2_thetajoin, n1, n2);
+
+ assert (contains_att (n1->schema, left) &&
+ contains_att (n2->schema, right) &&
+ contains_att (n1->schema, ldist) &&
+ contains_att (n2->schema, rdist));
+
+ ret->sem.unq_thetajoin.comp = comp;
+ ret->sem.unq_thetajoin.left = left;
+ ret->sem.unq_thetajoin.right = right;
+ ret->sem.unq_thetajoin.ldist = ldist;
+ ret->sem.unq_thetajoin.rdist = rdist;
+
+ /* allocate memory for the result schema */
+ ret->schema.count = 2;
+ ret->schema.items = PFmalloc (2 * sizeof (*(ret->schema.items)));
+ ret->schema.items[0].name = ldist;
+ ret->schema.items[0].type = aat_nat;
+ ret->schema.items[1].name = rdist;
+ ret->schema.items[1].type = aat_nat;
+
+ /* ---- ThetaJoin: orderings ---- */
+
+ /* The result is ordered by first the left distinct column
+ and then by the right distinct column. */
+
+ ret->orderings = PFord_set ();
+ PFord_set_add (ret->orderings,
+ PFord_refine (PFordering (),
+ ldist,
+ DIR_ASC));
+ PFord_set_add (ret->orderings,
+ PFord_refine (PFord_refine (PFordering (),
+ ldist,
+ DIR_ASC),
+ rdist,
+ DIR_ASC));
+
+ /* ---- ThetaJoin: costs ---- */
+ ret->cost = 3 * JOIN_COST + n1->cost + n2->cost;
+
+ return ret;
+}
+
+/**
+ * ThetaJoin: Theta-Join. Returns a single column with duplicates
+ * eliminated. Preserves the order of the left argument.
+ */
+PFpa_op_t *
+PFpa_unq1_thetajoin (PFalg_comp_t comp, PFalg_att_t left, PFalg_att_t right,
+ PFalg_att_t ldist, PFalg_att_t rdist,
+ const PFpa_op_t *n1, const PFpa_op_t *n2)
+{
+ PFpa_op_t *ret = wire2 (pa_unq1_thetajoin, n1, n2);
+
+ assert (contains_att (n1->schema, left) &&
+ contains_att (n2->schema, right) &&
+ contains_att (n1->schema, ldist) &&
+ contains_att (n2->schema, rdist));
+
+ ret->sem.unq_thetajoin.comp = comp;
+ ret->sem.unq_thetajoin.left = left;
+ ret->sem.unq_thetajoin.right = right;
+ ret->sem.unq_thetajoin.ldist = ldist;
+ ret->sem.unq_thetajoin.rdist = rdist;
+
+ /* allocate memory for the result schema */
+ ret->schema.count = 1;
+ ret->schema.items = PFmalloc (sizeof (*(ret->schema.items)));
+ ret->schema.items[0].name = ldist;
+ ret->schema.items[0].type = aat_nat;
+
+ /* ---- ThetaJoin: orderings ---- */
+
+ /* The result is ordered by the left distinct column */
+
+ ret->orderings = PFord_set ();
+ PFord_set_add (ret->orderings,
+ PFord_refine (PFordering (),
+ ldist,
+ DIR_ASC));
+
+ /* ---- ThetaJoin: costs ---- */
+ ret->cost = 3 * JOIN_COST + n1->cost + n2->cost;
+
+ return ret;
+}
+
+/**
* Project: Column selection and renaming.
*
* Note that projection does @b not eliminate duplicates. If you
@@ -1224,7 +1378,12 @@
PFord_set_add (ret->orderings, required);
/* ---- StandardSort: costs ---- */
- ret->cost = PFord_count (required) * SORT_COST + n->cost;
+ ret->cost = 3 * SORT_COST /* (1) */
+ + PFord_count (required) * SORT_COST
+ + n->cost;
+ /* (1): make sorting more expensive as all path steps.
+ This ensures that path steps sort internally
+ which is probably more efficient. */
for (unsigned int i = 0; i < PFord_count (required); i++)
if (PFord_order_dir_at (required, i) == DIR_DESC)
@@ -1261,9 +1420,13 @@
PFord_set_add (ret->orderings, required);
/* ---- StandardSort: costs ---- */
- ret->cost = PFord_count (required) * SORT_COST
+ ret->cost = 3 * SORT_COST /* (1) */
+ + PFord_count (required) * SORT_COST
- PFord_count (existing) * SORT_COST
+ n->cost;
+ /* (1): make sorting more expensive as all path steps.
+ This ensures that path steps sort internally
+ which is probably more efficient. */
for (unsigned int i = 0; i < PFord_count (required); i++)
if (PFord_order_dir_at (required, i) == DIR_DESC)
@@ -1785,11 +1948,19 @@
/* ---- MergeRowNum: orderings ---- */
for (unsigned int i = 0; i < PFord_set_count (n->orderings); i++) {
PFord_set_add (ret->orderings, PFord_set_at (n->orderings, i));
+
+ /* if we have already an ordering we can also add the new
+ generated column at the end. It won't break the ordering. */
+ PFord_set_add (ret->orderings,
+ PFord_refine (
+ PFord_set_at (n->orderings, i),
+ new_att, DIR_ASC));
+
/* get the direction of the partitioning column */
if (part &&
PFord_order_col_at (PFord_set_at (n->orderings, i), 0)
== part) {
- if (PFord_order_col_at (PFord_set_at (n->orderings, i), 0)
+ if (PFord_order_dir_at (PFord_set_at (n->orderings, i), 0)
== DIR_ASC)
dir_asc = true;
else
@@ -2019,11 +2190,11 @@
if (PFord_implies (n->sem.scjoin.out, iter_item)) {
/* output has iter|item ordering */
- n->cost = 3 * SORT_COST + ctx_cost;
+ n->cost = 3 * SORT_COST;
}
else {
/* output has item|iter ordering */
- n->cost = 2 * SORT_COST + ctx_cost;
+ n->cost = 2 * SORT_COST;
}
}
@@ -2032,13 +2203,13 @@
if (PFord_implies (n->sem.scjoin.out, iter_item)) {
/* output has iter|item ordering */
- n->cost = 1 * SORT_COST + ctx_cost;
+ n->cost = 1 * SORT_COST;
}
else {
/* output has item|iter ordering */
/* should be cheapest */
- n->cost = 0 * SORT_COST + ctx_cost;
+ n->cost = 0 * SORT_COST;
}
}
Index: planner.c
===================================================================
RCS file: /cvsroot/monetdb/pathfinder/compiler/algebra/planner.c,v
retrieving revision 1.34
retrieving revision 1.35
diff -u -d -r1.34 -r1.35
--- planner.c 15 Mar 2007 14:12:55 -0000 1.34
+++ planner.c 7 May 2007 10:17:07 -0000 1.35
@@ -173,7 +173,22 @@
PFarray_concat (list, plans);
}
+/**
+ * Helper function: Determine type of attribute @a att in schema
+ * @a schema. Used by plan_disjunion() and plan_thetajoin().
+ */
+static PFalg_simple_type_t
+type_of (PFalg_schema_t schema, PFalg_att_t att)
+{
+ for (unsigned int i = 0; i < schema.count; i++)
+ if (schema.items[i].name == att)
+ return schema.items[i].type;
+ PFoops (OOPS_FATAL, "unable to find attribute %s in schema",
+ PFatt_str (att));
+
+ return 0; /* pacify compilers */
+}
/**
@@ -379,8 +394,8 @@
* LeftJoin may be more expensive, but gives us some ordering
* guarantees.
*/
- add_plan (ret, leftjoin (att1, att2, a, b));
add_plan (ret, leftjoin (att2, att1, b, a));
+ add_plan (ret, leftjoin (att1, att2, a, b));
#if 0
PFalg_att_t att_a = NULL;
@@ -449,9 +464,6 @@
join_worker (ret, n->sem.eqjoin.att1, n->sem.eqjoin.att2,
*(plan_t **) PFarray_at (L(n)->plans, r),
*(plan_t **) PFarray_at (R(n)->plans, s));
- join_worker (ret, n->sem.eqjoin.att2, n->sem.eqjoin.att1,
- *(plan_t **) PFarray_at (R(n)->plans, s),
- *(plan_t **) PFarray_at (L(n)->plans, r));
}
return ret;
@@ -463,7 +475,7 @@
static PFplanlist_t *
plan_semijoin (const PFla_op_t *n)
{
- PFplanlist_t *ret = new_planlist ();
+ PFplanlist_t *ret = new_planlist ();
assert (n); assert (n->kind == la_semijoin);
assert (L(n)); assert (L(n)->plans);
@@ -483,6 +495,220 @@
}
/**
+ * Generate physical plans for theta-join.
+ */
+static PFplanlist_t *
+plan_thetajoin (const PFla_op_t *n)
+{
+ PFplanlist_t *ret = new_planlist ();
+
+ PFalg_simple_type_t cur_type;
+
+ assert (n); assert (n->kind == la_thetajoin);
+ assert (L(n)); assert (L(n)->plans);
+ assert (R(n)); assert (R(n)->plans);
+
+ /* combine each plan in R with each plan in S */
+ for (unsigned int r = 0; r < PFarray_last (L(n)->plans); r++)
+ for (unsigned int s = 0; s < PFarray_last (R(n)->plans); s++) {
+ add_plan (ret,
+ thetajoin (*(plan_t **) PFarray_at (L(n)->plans, r),
+ *(plan_t **) PFarray_at (R(n)->plans, s),
+ n->sem.thetajoin.count,
+ n->sem.thetajoin.pred));
+ }
+
+ cur_type = type_of (n->schema, n->sem.thetajoin.pred[0].left);
+ /* If we have only a single equi-join predicate we can also plan
+ an equi-join in addition. */
+ if (n->sem.thetajoin.count == 1 &&
+ n->sem.thetajoin.pred[0].comp == alg_comp_eq &&
+ monomorphic (cur_type) &&
+ cur_type != aat_anode &&
+ cur_type != aat_pnode)
+ /* combine each plan in R with each plan in S */
+ for (unsigned int r = 0; r < PFarray_last (L(n)->plans); r++)
+ for (unsigned int s = 0; s < PFarray_last (R(n)->plans); s++)
+ join_worker (ret,
+ n->sem.thetajoin.pred[0].left,
+ n->sem.thetajoin.pred[0].right,
+ *(plan_t **) PFarray_at (L(n)->plans, r),
+ *(plan_t **) PFarray_at (R(n)->plans, s));
+
+ return ret;
+}
+
+/**
+ * Generate physical plans for dependent
+ * theta-join that additionally removes duplicates.
+ */
+static PFplanlist_t *
+plan_dep_unique_thetajoin (const PFla_op_t *n)
+{
+ PFplanlist_t *ret = new_planlist (),
+ *lsorted = new_planlist (),
+ *rsorted = new_planlist ();
+
+ PFalg_simple_type_t cur_type;
+
+ /* check all conditions again */
+ assert (n); assert (n->kind == la_distinct);
+ assert (L(n)); assert (L(n)->kind == la_project);
+ assert (LL(n)); assert (LL(n)->kind == la_thetajoin);
+ assert (L(LL(n))); assert (L(LL(n))->plans);
+ assert (R(LL(n))); assert (R(LL(n))->plans);
+ assert (L(n)->schema.count == 1);
+ assert (LL(n)->sem.thetajoin.count == 2);
+ assert (LL(n)->sem.thetajoin.pred[0].comp == alg_comp_eq);
+ assert (L(n)->sem.proj.items[0].old ==
+ LL(n)->sem.thetajoin.pred[0].left ||
+ L(n)->sem.proj.items[0].old ==
+ LL(n)->sem.thetajoin.pred[0].right);
+
+ /* check for nat type in the first predicate */
+ if (type_of (LL(n)->schema,
+ LL(n)->sem.thetajoin.pred[0].left) != aat_nat ||
+ type_of (LL(n)->schema,
+ LL(n)->sem.thetajoin.pred[0].right) != aat_nat)
+ return ret;
+
+ if ((cur_type = type_of (LL(n)->schema,
+ LL(n)->sem.thetajoin.pred[1].left)) !=
+ type_of (LL(n)->schema,
+ LL(n)->sem.thetajoin.pred[1].right) ||
+ !monomorphic (cur_type) ||
+ cur_type & aat_node)
+ return ret;
+
+ /* make sure the left input is sorted by the left sort criterion */
+ for (unsigned int i = 0; i < PFarray_last (L(LL(n))->plans); i++)
+ add_plans (lsorted,
+ ensure_ordering (
+ *(plan_t **) PFarray_at (L(LL(n))->plans, i),
+ sortby (LL(n)->sem.thetajoin.pred[0].left)));
+
+ /* make sure the right input is sorted by the right sort criterion */
+ for (unsigned int i = 0; i < PFarray_last (R(LL(n))->plans); i++)
+ add_plans (rsorted,
+ ensure_ordering (
+ *(plan_t **) PFarray_at (R(LL(n))->plans, i),
+ sortby (LL(n)->sem.thetajoin.pred[0].right)));
+
+ /* combine each plan in R with each plan in S */
+ for (unsigned int l = 0; l < PFarray_last (lsorted); l++)
+ for (unsigned int r = 0; r < PFarray_last (rsorted); r++) {
+ add_plan (ret,
+ /* add the renaming projection afterwards */
+ project (
+ unq1_tjoin (
+ /* from our compilation we know that
+ the first predicate is the dependent
+ one which is also used for removing
+ duplicate tuples. */
+ LL(n)->sem.thetajoin.pred[1].comp,
+ LL(n)->sem.thetajoin.pred[1].left,
+ LL(n)->sem.thetajoin.pred[1].right,
+ LL(n)->sem.thetajoin.pred[0].left,
+ LL(n)->sem.thetajoin.pred[0].right,
+ *(plan_t **) PFarray_at (lsorted, l),
+ *(plan_t **) PFarray_at (rsorted, r)),
+ 1,
+ L(n)->sem.proj.items));
+ }
+
+ return ret;
+}
+
+/**
+ * Generate physical plans for theta-join
+ * that additionally removes duplicates.
+ */
+static PFplanlist_t *
+plan_unique_thetajoin (const PFla_op_t *n)
+{
+ PFplanlist_t *ret = new_planlist ();
+ PFalg_att_t ldist, rdist;
+
+ PFalg_simple_type_t cur_type;
+
+ /* check all conditions again */
+ assert (n); assert (n->kind == la_distinct);
+ assert (L(n)); assert (L(n)->kind == la_project);
+ assert (LL(n)); assert (LL(n)->kind == la_thetajoin);
+ assert (L(LL(n))); assert (L(LL(n))->plans);
+ assert (R(LL(n))); assert (R(LL(n))->plans);
+ assert (L(n)->schema.count == 2);
+ assert (LL(n)->sem.thetajoin.count == 1);
+ assert ((PFprop_ocol (L(LL(n)), L(n)->sem.proj.items[0].old) &&
+ PFprop_ocol (R(LL(n)), L(n)->sem.proj.items[1].old)) ^
+ (PFprop_ocol (L(LL(n)), L(n)->sem.proj.items[1].old) &&
+ PFprop_ocol (R(LL(n)), L(n)->sem.proj.items[0].old)));
+
+ if (PFprop_ocol (L(LL(n)), L(n)->sem.proj.items[0].old)) {
+ ldist = L(n)->sem.proj.items[0].old;
+ rdist = L(n)->sem.proj.items[1].old;
+ } else {
+ ldist = L(n)->sem.proj.items[1].old;
+ rdist = L(n)->sem.proj.items[0].old;
+ }
+ /* check for nat type in the distinct check */
+ if (type_of (LL(n)->schema, ldist) != aat_nat ||
+ type_of (LL(n)->schema, rdist) != aat_nat)
+ return ret;
+
+ if ((cur_type = type_of (LL(n)->schema,
+ LL(n)->sem.thetajoin.pred[0].left)) !=
+ type_of (LL(n)->schema,
+ LL(n)->sem.thetajoin.pred[0].right) ||
+ !monomorphic (cur_type) ||
+ cur_type & aat_node)
+ return ret;
+
+ for (unsigned int l = 0; l < PFarray_last (L(LL(n))->plans); l++)
+ for (unsigned int r = 0; r < PFarray_last (R(LL(n))->plans); r++) {
+ add_plan (ret,
+ /* add the renaming projection afterwards */
+ project (
+ unq2_tjoin (
+ /* from our compilation we know that
+ the first predicate is the dependent
+ one which is also used for removing
+ duplicate tuples. */
+ LL(n)->sem.thetajoin.pred[0].comp,
+ LL(n)->sem.thetajoin.pred[0].left,
+ LL(n)->sem.thetajoin.pred[0].right,
+ ldist,
+ rdist,
+ *(plan_t **) PFarray_at (L(LL(n))->plans, l),
+ *(plan_t **) PFarray_at (R(LL(n))->plans, r)),
+ 2,
+ L(n)->sem.proj.items));
+
+ /* for an equi-join we can also plan with switched sides */
+ if (LL(n)->sem.thetajoin.pred[0].comp == alg_comp_eq)
+ add_plan (ret,
+ /* add the renaming projection afterwards */
+ project (
+ unq2_tjoin (
+ /* from our compilation we know that
+ the first predicate is the dependent
+ one which is also used for removing
+ duplicate tuples. */
+ alg_comp_eq,
+ LL(n)->sem.thetajoin.pred[0].right,
+ LL(n)->sem.thetajoin.pred[0].left,
+ rdist,
+ ldist,
+ *(plan_t **) PFarray_at (R(LL(n))->plans, r),
+ *(plan_t **) PFarray_at (L(LL(n))->plans,
l)),
+ 2,
+ L(n)->sem.proj.items));
+ }
+
+ return ret;
+}
+
+/**
* Generate physical plan for the logical `project' operator.
*
* There's just one physical operator for `project' that we
@@ -532,23 +758,6 @@
}
/**
- * Helper function: Determine type of attribute @a att in schema
- * @a schema. Used by plan_disjunion().
- */
-static PFalg_simple_type_t
-type_of (PFalg_schema_t schema, PFalg_att_t att)
-{
- for (unsigned int i = 0; i < schema.count; i++)
- if (schema.items[i].name == att)
- return schema.items[i].type;
-
- PFoops (OOPS_FATAL, "unable to find attribute %s in schema",
- PFatt_str (att));
-
- return 0; /* pacify compilers */
-}
-
-/**
* Generate physical plans for disjoint union.
*
* Available implementations are MergeUnion and AppendUnion.
@@ -954,7 +1163,7 @@
{
PFplanlist_t *ret = new_planlist ();
PFplanlist_t *sorted = new_planlist ();
- PFord_ordering_t ord_asc, ord_desc;
+ PFord_ordering_t ord_asc, ord_desc, ord_wo_part;
assert (n); assert (n->kind == la_rownum);
assert (L(n)); assert (L(n)->plans);
@@ -962,8 +1171,9 @@
/*
* Build up the ordering that we require for MergeRowNumber
*/
- ord_asc = PFordering ();
- ord_desc = PFordering ();
+ ord_asc = PFordering ();
+ ord_desc = PFordering ();
+ ord_wo_part = PFordering ();
/* the partitioning attribute must be the primary ordering */
if (n->sem.rownum.part) {
@@ -975,14 +1185,18 @@
for (unsigned int i = 0;
i < PFord_count (n->sem.rownum.sortby);
i++) {
- ord_asc = PFord_refine (
- ord_asc,
- PFord_order_col_at (n->sem.rownum.sortby, i),
- PFord_order_dir_at (n->sem.rownum.sortby, i));
- ord_desc = PFord_refine (
- ord_desc,
- PFord_order_col_at (n->sem.rownum.sortby, i),
- PFord_order_dir_at (n->sem.rownum.sortby, i));
+ ord_asc = PFord_refine (
+ ord_asc,
+ PFord_order_col_at (n->sem.rownum.sortby, i),
+ PFord_order_dir_at (n->sem.rownum.sortby, i));
+ ord_desc = PFord_refine (
+ ord_desc,
+ PFord_order_col_at (n->sem.rownum.sortby, i),
+ PFord_order_dir_at (n->sem.rownum.sortby, i));
+ ord_wo_part = PFord_refine (
+ ord_wo_part,
+ PFord_order_col_at (n->sem.rownum.sortby, i),
+ PFord_order_dir_at (n->sem.rownum.sortby, i));
}
/* ensure correct input ordering for MergeRowNumber */
@@ -993,6 +1207,9 @@
add_plans (sorted,
ensure_ordering (
*(plan_t **) PFarray_at (L(n)->plans, i), ord_desc));
+ add_plans (sorted,
+ ensure_ordering (
+ *(plan_t **) PFarray_at (L(n)->plans, i), ord_wo_part));
}
/* throw out those plans that are too expensive */
@@ -1000,10 +1217,10 @@
/* for each remaining plan, generate a MergeRowNumber operator */
for (unsigned int i = 0; i < PFarray_last (sorted); i++)
- for (unsigned int j = 0; j < PFarray_last (L(n)->plans); j++)
- add_plan (ret,
- number (*(plan_t **) PFarray_at (sorted, i),
- n->sem.rownum.attname, n->sem.rownum.part));
+ add_plan (ret,
+ number (*(plan_t **) PFarray_at (sorted, i),
+ n->sem.rownum.attname,
+ n->sem.rownum.part));
return ret;
}
@@ -2183,12 +2400,74 @@
case la_cross: plans = plan_cross (n); break;
case la_eqjoin: plans = plan_eqjoin (n); break;
case la_semijoin: plans = plan_semijoin (n); break;
- case la_project: plans = plan_project (n); break;
+ case la_thetajoin: plans = plan_thetajoin (n); break;
+ case la_project:
+ plans = plan_project (n);
+
+ /* in addition try to implement the combination
+ of thetajoin and distinct more efficiently */
+ if (L(n)->kind == la_thetajoin &&
+ PFprop_set (n->prop)) {
+ /* check for dependent thetajoins where the
+ distinct column is also a join column */
+ if (n->schema.count == 1 &&
+ L(n)->sem.thetajoin.count == 2 &&
+ L(n)->sem.thetajoin.pred[0].comp == alg_comp_eq &&
+ (n->sem.proj.items[0].old ==
+ L(n)->sem.thetajoin.pred[0].left ||
+ n->sem.proj.items[0].old ==
+ L(n)->sem.thetajoin.pred[0].right)) {
+ add_plans (plans, plan_dep_unique_thetajoin (
+ PFla_distinct (n)));
+ /* check for independent thetajoins where the
+ two distinct column come from both the left
+ and the right children of the thetajoin */
+ } else if (n->schema.count == 2 &&
+ L(n)->sem.thetajoin.count == 1 &&
+ (PFprop_ocol (L(L(n)), n->sem.proj.items[0].old) &&
+ PFprop_ocol (R(L(n)), n->sem.proj.items[1].old)) ^
+ (PFprop_ocol (L(L(n)), n->sem.proj.items[1].old) &&
+ PFprop_ocol (R(L(n)), n->sem.proj.items[0].old))) {
+ add_plans (plans, plan_unique_thetajoin (
+ PFla_distinct (n)));
+ }
+ }
+ break;
+
case la_select: plans = plan_select (n); break;
case la_disjunion: plans = plan_disjunion (n); break;
case la_intersect: plans = plan_intersect (n); break;
case la_difference: plans = plan_difference (n); break;
- case la_distinct: plans = plan_distinct (n); break;
+ case la_distinct:
+ plans = plan_distinct (n);
+
+ /* in addition try to implement the combination
+ of thetajoin and distinct more efficiently */
+ if (L(n)->kind == la_project &&
+ LL(n)->kind == la_thetajoin) {
+ /* check for dependent thetajoins where the
+ distinct column is also a join column */
+ if (n->schema.count == 1 &&
+ LL(n)->sem.thetajoin.count == 2 &&
+ LL(n)->sem.thetajoin.pred[0].comp == alg_comp_eq &&
+ (L(n)->sem.proj.items[0].old ==
+ LL(n)->sem.thetajoin.pred[0].left ||
+ L(n)->sem.proj.items[0].old ==
+ LL(n)->sem.thetajoin.pred[0].right)) {
+ add_plans (plans, plan_dep_unique_thetajoin (n));
+ /* check for independent thetajoins where the
+ two distinct column come from both the left
+ and the right children of the thetajoin */
+ } else if (n->schema.count == 2 &&
+ LL(n)->sem.thetajoin.count == 1 &&
+ (PFprop_ocol (L(LL(n)), L(n)->sem.proj.items[0].old) &&
+ PFprop_ocol (R(LL(n)), L(n)->sem.proj.items[1].old)) ^
+ (PFprop_ocol (L(LL(n)), L(n)->sem.proj.items[1].old) &&
+ PFprop_ocol (R(LL(n)), L(n)->sem.proj.items[0].old))) {
+ add_plans (plans, plan_unique_thetajoin (n));
+ }
+ }
+ break;
case la_fun_1to1: plans = plan_fun_1to1 (n); break;
case la_num_eq:
@@ -2349,6 +2628,68 @@
assert (plans);
assert (PFarray_last (plans) > 0);
+ /* Introduce some more orders (on iter columns of length 1 or 2)
+ in the hope to share more sort operations. */
+ switch (n->kind) {
+ case la_element:
+ case la_attribute:
+ case la_textnode:
+ case la_docnode:
+ case la_comment:
+ case la_processi:
+ case la_merge_adjacent:
+ case la_fragment:
+ case la_frag_union:
+ case la_empty_frag:
+ case la_nil:
+ case la_trace_msg:
+ case la_trace_map:
+ break;
+
+ default:
+ {
+ PFord_ordering_t ord = PFordering ();
+ PFord_set_t orderings = PFord_set ();
+ plan_t *p = (*(plan_t **) PFarray_at (plans, 0));
+ unsigned int plan_count = PFarray_last (plans);
+
+ for (unsigned int i = 0; i < p->schema.count; i++)
+ /* check for an iter-like column (to avoid generating
+ a large amount of plans) */
+ if (PFalg_unq_name (p->schema.items[i].name, 0) ==
+ PFalg_unq_name (att_iter, 0))
+ ord = PFord_refine (ord, p->schema.items[i].name, DIR_ASC);
+
+ /* collect all possible orderings of length 1 and 2 */
+ for (unsigned int i = 0; i < PFord_count (ord); i++) {
+ PFord_ordering_t ordering = PFordering ();
+
+ ordering = PFord_refine (ordering,
+ PFord_order_col_at (ord, i),
+ DIR_ASC);
+ PFord_set_add (orderings, ordering);
+
+ for (unsigned int j = 0; j < PFord_count (ord); j++)
+ if (j != i)
+ PFord_set_add (orderings,
+ PFord_refine (
+ ordering,
+ PFord_order_col_at (ord, j),
+ DIR_ASC));
+ }
+
+ /* add all plans satisfying the generated ordering
+ to the list of plans */
+ for (unsigned int plan = 0; plan < plan_count; plan++) {
+ p = (*(plan_t **) PFarray_at (plans, plan));
+ for (unsigned int i = 0; i < PFord_set_count (orderings); i++)
{
+ ord = PFord_set_at (orderings, i);
+ add_plans (plans, ensure_ordering (p, ord));
+ }
+ }
+ }
+ }
+
/* Prune un-interesting plans. */
plans = prune_plans (plans);
Index: algebra_cse.c
===================================================================
RCS file: /cvsroot/monetdb/pathfinder/compiler/algebra/algebra_cse.c,v
retrieving revision 1.49
retrieving revision 1.50
diff -u -d -r1.49 -r1.50
--- algebra_cse.c 15 Mar 2007 14:12:55 -0000 1.49
+++ algebra_cse.c 7 May 2007 10:17:05 -0000 1.50
@@ -192,6 +192,22 @@
&& a->sem.eqjoin.att2 == b->sem.eqjoin.att2);
break;
+ case la_thetajoin:
+ if (a->sem.thetajoin.count != b->sem.thetajoin.count)
+ return false;
+
+ for (unsigned int i = 0; i < a->sem.thetajoin.count; i++)
+ if ((a->sem.thetajoin.pred[i].comp !=
+ b->sem.thetajoin.pred[i].comp) ||
+ (a->sem.thetajoin.pred[i].left !=
+ b->sem.thetajoin.pred[i].left) ||
+ (a->sem.thetajoin.pred[i].right !=
+ b->sem.thetajoin.pred[i].right))
+ return false;
+
+ return true;
+ break;
+
case la_eqjoin_unq:
return (a->sem.eqjoin_unq.att1 == b->sem.eqjoin_unq.att1
&& a->sem.eqjoin_unq.att2 == b->sem.eqjoin_unq.att2
Index: logical.c
===================================================================
RCS file: /cvsroot/monetdb/pathfinder/compiler/algebra/logical.c,v
retrieving revision 1.45
retrieving revision 1.46
diff -u -d -r1.45 -r1.46
--- logical.c 16 Apr 2007 12:06:31 -0000 1.45
+++ logical.c 7 May 2007 10:17:06 -0000 1.46
@@ -712,6 +712,98 @@
}
/**
+ * Theta-join between two operator nodes.
+ *
+ * Assert that all columns listed in the predicate list are
+ * available. @a n1 and @a n2 must not have duplicate attribute names.
+ * The schema of the result is (schema(@a n1) + schema(@a n2)).
+ */
+PFla_op_t *
+PFla_thetajoin (const PFla_op_t *n1, const PFla_op_t *n2,
+ unsigned int count, PFalg_sel_t *pred)
+{
+ PFla_op_t *ret;
+ unsigned int i, j;
+
+ assert (n1); assert (n2);
+
+ /* verify that the join attributes are all available */
+ for (i = 0; i < count; i++)
+ if (!PFprop_ocol (n1, pred[i].left) ||
+ !PFprop_ocol (n2, pred[i].right))
+ break;
+
+ /* did we find all attributes? */
+ if (i < count)
+ PFoops (OOPS_FATAL,
+ "attribute `%s' referenced in theta-join not found",
+ PFprop_ocol (n2, pred[i].right)
+ ? PFatt_str(pred[i].left) : PFatt_str(pred[i].right));
+
+ /* build new theta-join node */
+ ret = la_op_wire2 (la_thetajoin, n1, n2);
+
+ /* insert semantic value (predicates) into the result */
+ ret->sem.thetajoin.count = count;
+ ret->sem.thetajoin.pred = PFmalloc (count * sizeof (PFalg_sel_t));
+ for (i = 0; i < count; i++)
+ ret->sem.thetajoin.pred[i] = pred[i];
+
+ /* allocate memory for the result schema (schema(n1) + schema(n2)) */
+ ret->schema.count = n1->schema.count + n2->schema.count;
+ ret->schema.items
+ = PFmalloc (ret->schema.count * sizeof (*(ret->schema.items)));
+
+ /* copy schema from argument 'n1' */
+ for (i = 0; i < n1->schema.count; i++)
+ ret->schema.items[i] = n1->schema.items[i];
+
+ /* copy schema from argument 'n2', check for duplicate attribute names */
+ for (j = 0; j < n2->schema.count; j++) {
+
+ ret->schema.items[n1->schema.count + j] = n2->schema.items[j];
+
+#ifndef NDEBUG
+ for (i = 0; i < n1->schema.count; i++)
+ if (n1->schema.items[i].name == n2->schema.items[j].name)
+ PFoops (OOPS_FATAL,
+ "duplicate attribute `%s' in theta-join",
+ PFatt_str (n2->schema.items[j].name));
+#endif
+ }
+
+ return ret;
+}
+
+/**
+ * Theta-join between two operator nodes.
+ * Special internal variant used during thetajoin optimization.
+ *
+ * The optimizer will fill check for consistency and
+ * fill in the correct schema (which requires internal knowledge
+ * of @a data).
+ */
+PFla_op_t *
+PFla_thetajoin_opt_internal (const PFla_op_t *n1,
+ const PFla_op_t *n2,
+ PFarray_t *data)
+{
+ PFla_op_t *ret;
+
+ assert (n1); assert (n2);
+
+ /* build new theta-join node */
+ ret = la_op_wire2 (la_thetajoin, n1, n2);
+
+ /* insert semantic value (predicates) into the result */
+ ret->sem.thetajoin_opt.pred = PFarray_copy (data);
+
+ /* allocate no schema -- this will be done by the optimization */
+
+ return ret;
+}
+
+/**
* Logical algebra projection/renaming.
*
* @param n Argument for the projection operator.
-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/
_______________________________________________
Monetdb-pf-checkins mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/monetdb-pf-checkins
