Update of /cvsroot/monetdb/pathfinder/compiler/algebra
In directory sc8-pr-cvs16.sourceforge.net:/tmp/cvs-serv11089/algebra
Modified Files:
algebra.c algopt.c planner.c
Log Message:
-- First steps to get rid of bit-encoded column names:
o The planner and the MIL generation do not rely
on bit-encoded columns anymore.
o A global counter allows to assign new column names
without the need to analyze the plan before.
o Operator la_eqjoin_unq is only introduced in the
join pushdown phase and a normal eqjoin is available
for all other phases working on unique column names.
o Changed the required node optimization phase to cope
with unique column names.
U algopt.c
Index: algopt.c
===================================================================
RCS file: /cvsroot/monetdb/pathfinder/compiler/algebra/algopt.c,v
retrieving revision 1.36
retrieving revision 1.37
diff -u -d -r1.36 -r1.37
--- algopt.c 30 May 2008 09:40:48 -0000 1.36
+++ algopt.c 18 Jun 2008 11:24:16 -0000 1.37
@@ -228,7 +228,6 @@
break;
case 'K':
- MAP_ORI_NAMES("key optimization")
REMOVE_PROXIES("key optimization")
tm = PFtimer_start ();
@@ -257,8 +256,6 @@
break;
case 'N':
- MAP_ORI_NAMES("required nodes optimization")
-
tm = PFtimer_start ();
root = PFalgopt_req_node (root);
@@ -345,8 +342,8 @@
true /* icol */,
false /* composite key */,
true /* key */,
- false /* ocols */,
- false /* req_node */,
+ true /* ocols */,
+ true /* req_node */,
false /* reqval */,
true /* level */,
true /* refctr */,
@@ -462,12 +459,6 @@
if (debug_opt)
fputc ('\n', stderr);
- if (unq_names)
- PFinfo (OOPS_WARNING,
- "Physical algebra requires original names. "
- "Add ']' optimization option (at the end) to "
- "ensure correct attribute name usage.");
-
if (proxies_involved)
PFinfo (OOPS_WARNING,
"Physical algebra does not cope with proxies. "
U algebra.c
Index: algebra.c
===================================================================
RCS file: /cvsroot/monetdb/pathfinder/compiler/algebra/algebra.c,v
retrieving revision 1.87
retrieving revision 1.88
diff -u -d -r1.87 -r1.88
--- algebra.c 13 Jun 2008 12:50:43 -0000 1.87
+++ algebra.c 18 Jun 2008 11:24:15 -0000 1.88
@@ -782,6 +782,17 @@
return NULL;
}
+static unsigned int highest_col_name_id;
+
+/**
+ * Initialize the column name counter.
+ */
+void
+PFalg_init (void)
+{
+ highest_col_name_id = 1;
+}
+
/**
* Checks whether a name is unique or not.
*/
@@ -792,16 +803,16 @@
}
/**
- * Return the id of a unique name
+ * Return a new unique column name
*/
-unsigned int
-PFalg_unq_name_id (PFalg_att_t att)
+PFalg_att_t
+PFalg_new_name (PFalg_att_t att)
{
if (!PFalg_is_unq_name(att))
PFoops (OOPS_FATAL,
"unique column name expected");
- return att >> 4;
+ return (highest_col_name_id++ << 4) | (1 << 3) | (att & 7);
}
/**
@@ -809,14 +820,14 @@
* an original name @a ori that retains the usage information
* of the new variable (iter, pos or item).
*/
-PFalg_att_t
-PFalg_unq_name (PFalg_att_t ori, unsigned int id)
+static PFalg_att_t
+unq_name (PFalg_att_t ori, unsigned int id)
{
+ PFalg_att_t unq = att_NULL;
-// printf("id:%i\n", id);
-// printf("name:%s\n", PFatt_str(ori));
-
- PFalg_att_t unq;
+ if (PFalg_is_unq_name(ori))
+ PFoops (OOPS_FATAL,
+ "bit-encoded column name expected");
switch (ori) {
case att_iter:
@@ -863,11 +874,36 @@
default:
PFoops (OOPS_FATAL,
"Mapping variable to an unique name failed. "
- "(original name: %s, id: %u)",
+ "(bit-encoded name: %s, id: %u)",
PFatt_str (ori), id);
}
- return unq | 1 << 3 | id << 4;
+ return (id << 4) | (1 << 3) | unq;
+}
+
+/**
+ * Create a unique name based on an original bit-encoded name @a ori
+ * that retains the usage information of the new variable (iter, pos
+ * or item).
+ */
+PFalg_att_t
+PFalg_unq_name (PFalg_att_t ori)
+{
+ return unq_name (ori, highest_col_name_id++);
+}
+
+/**
+ * Create an unique name based on an id @a id and
+ * an original name @a ori that retains the usage information
+ * of the new variable (iter, pos or item).
+ */
+PFalg_att_t
+PFalg_unq_fixed_name (PFalg_att_t ori, unsigned int id)
+{
+ if (id > highest_col_name_id)
+ highest_col_name_id = id;
+
+ return unq_name (ori, id);
}
/**
@@ -995,11 +1031,16 @@
case att_isdec: return "item8";
default:
if (att & (1 << 3)) {
- unsigned int id = att >> 4;
- size_t len = sizeof ("iter0000");
- char *res = PFmalloc (len+1);
+ unsigned int id = att >> 4,
+ tmp_id = id;
+ size_t len = sizeof ("iter");
+ char *res;
- assert (id < 10000);
+ while (tmp_id > 0) {
+ tmp_id /= 10;
+ len++;
+ }
+ res = PFmalloc (len+1);
if (att & att_iter)
snprintf (res, len, "%s%u", "iter", id);
U planner.c
Index: planner.c
===================================================================
RCS file: /cvsroot/monetdb/pathfinder/compiler/algebra/planner.c,v
retrieving revision 1.66
retrieving revision 1.67
diff -u -d -r1.66 -r1.67
--- planner.c 5 Jun 2008 09:18:50 -0000 1.66
+++ planner.c 18 Jun 2008 11:24:17 -0000 1.67
@@ -124,6 +124,12 @@
/* Function call kind indicator */
static PFalg_fun_call_t fun_call_kind;
+/* Information if we have unique or bit-encoded column names */
+static unsigned int unq_column_names;
+#define new_name(p,l) (unq_column_names \
+ ? PFalg_unq_name (p) \
+ : PFalg_ori_name (PFalg_unq_name (p), ~l))
+
/* ensure some ordering on a given plan */
static PFplanlist_t *ensure_ordering (const plan_t *unordered,
PFord_ordering_t required);
@@ -896,9 +902,8 @@
for (unsigned int i = 0; i < n->schema.count; i++)
used_cols |= n->schema.items[i].name;
- num = PFalg_ori_name (PFalg_unq_name (att_pos, 0), ~used_cols);
- used_cols |= num;
- cast = PFalg_ori_name (PFalg_unq_name (att_pos, 0), ~used_cols);
+ num = new_name (att_pos, used_cols);
+ cast = new_name (att_pos, (used_cols|num));
for (unsigned int i = 0; i < count; i++)
proj[i] = PFalg_proj (n->schema.items[i].name,
@@ -1540,12 +1545,11 @@
static PFplanlist_t *
plan_step (const PFla_op_t *n)
{
- PFplanlist_t *ret = new_planlist ();
+ PFplanlist_t *ret = new_planlist ();
+ PFalg_proj_t *proj = PFmalloc (2 * sizeof (PFalg_proj_t));
-#ifndef NDEBUG
- /* ensure that input and output columns have the same name */
- assert (n->sem.step.item == n->sem.step.item_res);
-#endif
+ proj[0] = PFalg_proj (n->sem.step.iter, n->sem.step.iter);
+ proj[1] = PFalg_proj (n->sem.step.item_res, n->sem.step.item);
/*
* Loop-lifted staircase join can handle two different orderings
@@ -1579,13 +1583,15 @@
for (unsigned short o = 0; o < 2; o++)
add_plan (
ret,
- llscjoin (
- *(plan_t **) PFarray_at (ordered, k),
- n->sem.step.spec,
- in[i],
- out[o],
- n->sem.step.iter,
- n->sem.step.item));
+ project (
+ llscjoin (
+ *(plan_t **) PFarray_at (ordered, k),
+ n->sem.step.spec,
+ in[i],
+ out[o],
+ n->sem.step.iter,
+ n->sem.step.item),
+ 2, proj));
}
return ret;
@@ -1641,9 +1647,8 @@
for (unsigned int i = 0; i < n->schema.count; i++)
used_cols |= n->schema.items[i].name;
- iter = PFalg_ori_name (PFalg_unq_name (att_iter, 0), ~used_cols);
- used_cols |= iter;
- iter2 = PFalg_ori_name (PFalg_unq_name (att_iter, 0), ~used_cols);
+ iter = new_name (att_iter, used_cols);
+ iter2 = new_name (att_iter, (used_cols|iter));
/* create the inner projection list */
proj_in[0] = PFalg_proj (iter2, iter);
@@ -1712,7 +1717,7 @@
/* find a free iter value */
item = L(n)->sem.step.item;
used_cols = item_res | item;
- iter = PFalg_ori_name (PFalg_unq_name (att_iter, 0), ~used_cols);
+ iter = new_name (att_iter, used_cols);
proj_out[0].new = item_out;
proj_out[0].old = item;
@@ -2192,10 +2197,11 @@
static PFplanlist_t *
plan_content (const PFla_op_t *n)
{
- PFplanlist_t *ret = new_planlist ();
- PFplanlist_t *ordered_in = new_planlist ();
- PFalg_att_t iter = n->sem.iter_pos_item.iter;
- PFalg_att_t pos = n->sem.iter_pos_item.pos;
+ PFplanlist_t *ret = new_planlist (),
+ *ordered_in = new_planlist ();
+ PFalg_att_t iter = n->sem.iter_pos_item.iter,
+ pos = n->sem.iter_pos_item.pos,
+ item = n->sem.iter_pos_item.item;
for (unsigned int i = 0; i < PFarray_last (R(n)->plans); i++)
add_plans (ordered_in,
@@ -2203,21 +2209,19 @@
*(plan_t **) PFarray_at (R(n)->plans, i),
sortby (iter, pos)));
- if (PFprop_node_property (n->prop, att_item) &&
- !PFprop_node_content_queried (n->prop, att_item))
+ if (PFprop_node_property (R(n)->prop, item) &&
+ !PFprop_node_content_queried (R(n)->prop, item))
/* for each plan, generate a constructor */
for (unsigned int i = 0; i < PFarray_last (ordered_in); i++)
add_plan (ret,
slim_content (*(plan_t **) PFarray_at (ordered_in, i),
- iter,
- n->sem.iter_pos_item.item));
+ iter, item));
else
/* for each plan, generate a constructor */
for (unsigned int i = 0; i < PFarray_last (ordered_in); i++)
add_plan (ret,
content (*(plan_t **) PFarray_at (ordered_in, i),
- iter,
- n->sem.iter_pos_item.item));
+ iter, item));
return ret;
}
@@ -2229,23 +2233,24 @@
static PFplanlist_t *
plan_merge_texts (const PFla_op_t *n)
{
- PFplanlist_t *ret = new_planlist ();
- PFplanlist_t *sorted = new_planlist ();
- plan_t *cheapest_sorted = NULL;
- PFalg_att_t iter = n->sem.merge_adjacent.iter_in;
- PFalg_att_t pos = n->sem.merge_adjacent.pos_in;
- PFalg_att_t item = n->sem.merge_adjacent.item_in;
-
-#ifndef NDEBUG
- /* ensure that matching columns (iter, pos, item) have the same name */
- assert (iter == n->sem.merge_adjacent.iter_res);
- assert (pos == n->sem.merge_adjacent.pos_res);
- assert (item == n->sem.merge_adjacent.item_res);
-#endif
-
assert (n); assert (n->kind == la_merge_adjacent);
assert (R(n)); assert (R(n)->plans);
+ PFplanlist_t *ret = new_planlist ();
+ PFplanlist_t *sorted = new_planlist ();
+ plan_t *cheapest_sorted = NULL;
+ PFalg_att_t iter = n->sem.merge_adjacent.iter_in,
+ pos = n->sem.merge_adjacent.pos_in,
+ item = n->sem.merge_adjacent.item_in,
+ iter_res = n->sem.merge_adjacent.iter_res,
+ pos_res = n->sem.merge_adjacent.pos_res,
+ item_res = n->sem.merge_adjacent.item_res;
+ PFalg_proj_t *proj = PFmalloc (3 * sizeof (PFalg_proj_t));
+
+ proj[0] = PFalg_proj (iter_res, iter);
+ proj[1] = PFalg_proj (pos_res, pos);
+ proj[2] = PFalg_proj (item_res, item);
+
/* The merge_adjacent_text_node operator requires
its inputs to be properly sorted. */
for (unsigned int i = 0; i < PFarray_last (R(n)->plans); i++)
@@ -2263,9 +2268,11 @@
/* generate a merge_adjacent_text_node operator for
the single remaining plan */
add_plan (ret,
- merge_adjacent (
- cheapest_sorted,
- iter, pos, item));
+ project (
+ merge_adjacent (
+ cheapest_sorted,
+ iter, pos, item),
+ 3, proj));
return ret;
}
@@ -2471,25 +2478,29 @@
static PFplanlist_t *
plan_string_join (const PFla_op_t *n)
{
+ assert (n); assert (n->kind == la_string_join);
+ assert (L(n)); assert (L(n)->plans);
+ assert (R(n)); assert (R(n)->plans);
+
PFplanlist_t *ret = new_planlist ();
PFplanlist_t *sorted_n1 = new_planlist ();
PFplanlist_t *sorted_n2 = new_planlist ();
- PFalg_att_t iter = n->sem.string_join.iter;
- PFalg_att_t pos = n->sem.string_join.pos;
- PFalg_att_t item = n->sem.string_join.item;
-
-#ifndef NDEBUG
- /* ensure that matching columns (iter, pos, item) have the same name */
- assert (iter == n->sem.string_join.iter_sep &&
- iter == n->sem.string_join.iter_res);
- assert (item == n->sem.string_join.item_sep &&
- item == n->sem.string_join.item_res);
-#endif
+ PFalg_att_t iter = n->sem.string_join.iter,
+ pos = n->sem.string_join.pos,
+ item = n->sem.string_join.item,
+ iter_res = n->sem.string_join.iter_res,
+ item_res = n->sem.string_join.item_res,
+ iter_sep = n->sem.string_join.iter_sep,
+ item_sep = n->sem.string_join.item_sep;
- assert (n); assert (n->kind == la_string_join);
- assert (L(n)); assert (L(n)->plans);
- assert (R(n)); assert (R(n)->plans);
+ PFalg_proj_t *lproj = PFmalloc (2 * sizeof (PFalg_proj_t)),
+ *rproj = PFmalloc (1 * sizeof (PFalg_proj_t));
+ lproj[0] = PFalg_proj (iter_res, iter);
+ lproj[1] = PFalg_proj (item_res, item);
+ rproj[0] = PFalg_proj (iter_res, iter_sep);
+ rproj[1] = PFalg_proj (item_res, item_sep);
+
/* The string_join operator requires its inputs to be properly sorted. */
for (unsigned int i = 0; i < PFarray_last (L(n)->plans); i++)
add_plans (sorted_n1,
@@ -2501,16 +2512,22 @@
add_plans (sorted_n2,
ensure_ordering (
*(plan_t **) PFarray_at (R(n)->plans, i),
- sortby (iter)));
+ sortby (iter_sep)));
/* for each remaining plan, generate a string_join operator */
for (unsigned int i = 0; i < PFarray_last (sorted_n1); i++)
for (unsigned int j = 0; j < PFarray_last (sorted_n2); j++)
add_plan (ret,
string_join (
- *(plan_t **) PFarray_at (sorted_n1, i),
- *(plan_t **) PFarray_at (sorted_n2, j),
- iter, item));
+ project (
+ *(plan_t **) PFarray_at (sorted_n1, i),
+ 2,
+ lproj),
+ project (
+ *(plan_t **) PFarray_at (sorted_n2, j),
+ 2,
+ rproj),
+ iter_res, item_res));
return ret;
}
@@ -2676,9 +2693,8 @@
for (unsigned int i = 0; i < n->schema.count; i++)
used_cols |= n->schema.items[i].name;
- iter = PFalg_ori_name (PFalg_unq_name (att_iter, 0), ~used_cols);
- used_cols |= iter;
- iter2 = PFalg_ori_name (PFalg_unq_name (att_iter, 0), ~used_cols);
+ iter = new_name (att_iter, used_cols);
+ iter2 = new_name (att_iter, (used_cols|iter));
/* create the inner projection list */
proj_in[0] = PFalg_proj (iter2, iter);
@@ -3439,13 +3455,19 @@
plan_t *p = (*(plan_t **) PFarray_at (plans, 0));
unsigned int plan_count = PFarray_last (plans);
unsigned int i, j, plan;
+ PFalg_att_t att;
- for (i = 0; i < p->schema.count; i++)
+ for (i = 0; i < p->schema.count; i++) {
+ att = p->schema.items[i].name;
/* 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))
+ if ((unq_column_names &&
+ PFalg_ori_name (att, ~att_NULL) == att_iter) ||
+ (!unq_column_names &&
+ PFalg_unq_fixed_name (p->schema.items[i].name, 1) ==
+ PFalg_unq_fixed_name (att_iter, 1)))
ord = PFord_refine (ord, p->schema.items[i].name, DIR_ASC);
+ }
/* collect all possible orderings of length 1 and 2 */
for (i = 0; i < PFord_count (ord); i++) {
@@ -3517,6 +3539,10 @@
{
PFpa_op_t *ret = NULL;
+ assert (root->kind == la_serialize_seq);
+
+ unq_column_names = PFalg_is_unq_name (root->sem.ser_seq.item);
+
/* compute all interesting plans for root */
plan_subexpression (root);
-------------------------------------------------------------------------
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://sourceforge.net/services/buy/index.php
_______________________________________________
Monetdb-pf-checkins mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/monetdb-pf-checkins
