Update of /cvsroot/monetdb/pathfinder/compiler/algebra/opt
In directory sc8-pr-cvs7.sourceforge.net:/tmp/cvs-serv21716/algebra/opt
Modified Files:
opt_complex.c opt_const.c opt_dom.c opt_reqval.c
Log Message:
-- Fixed bug in opt/opt_const.c
-- Extended domain based optimization with a case for semijoin operators
(Copied the two rules in opt_dom.c to opt_complex.c to save some phases.)
-- Extended pattern for equi-join rewrites: If the cardinality does not matter
we may even forget self-joins.
-- Extended optimization based on required values: We now look one operator
ahead thus trying to bridge union operators if both input relations generate
constant required value columns with different values.
Index: opt_complex.c
===================================================================
RCS file: /cvsroot/monetdb/pathfinder/compiler/algebra/opt/opt_complex.c,v
retrieving revision 1.18
retrieving revision 1.19
diff -u -d -r1.18 -r1.19
--- opt_complex.c 3 Jan 2007 12:32:35 -0000 1.18
+++ opt_complex.c 21 Feb 2007 14:25:01 -0000 1.19
@@ -198,7 +198,8 @@
p->prop,
L(p)->schema.items[i].name));
}
- if (PFprop_key_left (p->prop, p->sem.eqjoin.att1) &&
+ if ((PFprop_key_left (p->prop, p->sem.eqjoin.att1) ||
+ PFprop_set (p->prop)) &&
PFprop_subdom (p->prop,
PFprop_dom_right (p->prop,
p->sem.eqjoin.att2),
@@ -241,7 +242,8 @@
p->prop,
R(p)->schema.items[i].name));
}
- if (PFprop_key_right (p->prop, p->sem.eqjoin.att2) &&
+ if ((PFprop_key_right (p->prop, p->sem.eqjoin.att2) ||
+ PFprop_set (p->prop)) &&
PFprop_subdom (p->prop,
PFprop_dom_left (p->prop,
p->sem.eqjoin.att1),
@@ -341,6 +343,26 @@
} break;
case la_semijoin:
+ /* the following if statement is a copy of code in opt_dom.c */
+ /* if the semijoin operator does not prune a row
+ because the domains are identical we can safely
+ remove it. */
+ if (PFprop_subdom (
+ p->prop,
+ PFprop_dom_left (p->prop,
+ p->sem.eqjoin.att1),
+ PFprop_dom_right (p->prop,
+ p->sem.eqjoin.att2)) &&
+ PFprop_subdom (
+ p->prop,
+ PFprop_dom_right (p->prop,
+ p->sem.eqjoin.att2),
+ PFprop_dom_left (p->prop,
+ p->sem.eqjoin.att1))) {
+ *p = *L(p);
+ break;
+ }
+
if (!PFprop_key_left (p->prop, p->sem.eqjoin.att1) ||
!PFprop_subdom (p->prop,
PFprop_dom_right (p->prop,
@@ -511,6 +533,34 @@
2, top_proj);
} break;
+ case la_difference: /* this case is a copy of code in opt_dom.c */
+ { /**
+ * If the domains of the first relation are all subdomains
+ * of the corresponding domains in the second argument
+ * the result of the difference operation will be empty.
+ */
+ unsigned int all_subdom = 0;
+ for (unsigned int i = 0; i < L(p)->schema.count; i++)
+ for (unsigned int j = 0; j < R(p)->schema.count; j++)
+ if (L(p)->schema.items[i].name ==
+ R(p)->schema.items[j].name &&
+ PFprop_subdom (
+ p->prop,
+ PFprop_dom_left (p->prop,
+ L(p)->schema.items[i].name),
+ PFprop_dom_right (p->prop,
+ R(p)->schema.items[j].name))) {
+ all_subdom++;
+ break;
+ }
+
+ if (all_subdom == p->schema.count) {
+ *p = *PFla_empty_tbl_ (p->schema);
+ SEEN(p) = true;
+ break;
+ }
+ } break;
+
case la_rownum:
/* match the pattern rownum - (project -) rownum and
try to merge both row number operators if the nested
Index: opt_reqval.c
===================================================================
RCS file: /cvsroot/monetdb/pathfinder/compiler/algebra/opt/opt_reqval.c,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -d -r1.7 -r1.8
--- opt_reqval.c 3 Jan 2007 12:32:36 -0000 1.7
+++ opt_reqval.c 21 Feb 2007 14:25:02 -0000 1.8
@@ -43,10 +43,26 @@
#include "alg_dag.h"
#include "mem.h" /* PFmalloc() */
+/*
+ * Easily access subtree-parts.
+ */
+/** starting from p, make a step left */
+#define L(p) ((p)->child[0])
+/** starting from p, make a step right */
+#define R(p) ((p)->child[1])
+#define LL(p) (L(L(p)))
+#define RL(p) (L(R(p)))
+#define LR(p) (R(L(p)))
+#define RR(p) (R(R(p)))
+
/* worker for PFalgopt_reqval */
static void
opt_reqvals (PFla_op_t *p)
{
+ unsigned int count = 0;
+ PFalg_att_t att = 0;
+ bool val = false;
+
assert (p);
/* nothing to do if we already visited that node */
@@ -58,15 +74,54 @@
column has a constant value that differs its required value,
by an empty table. */
for (unsigned int i = 0; i < p->schema.count; i++) {
- PFalg_att_t att = p->schema.items[i].name;
+ PFalg_att_t cur_att = p->schema.items[i].name;
- if (PFprop_reqval (p->prop, att) && PFprop_const (p->prop, att) &&
- (PFprop_const_val (p->prop, att)).val.bln !=
- PFprop_reqval_val (p->prop, att)) {
+ if (PFprop_reqval (p->prop, cur_att) &&
+ PFprop_const (p->prop, cur_att) &&
+ (PFprop_const_val (p->prop, cur_att)).val.bln !=
+ PFprop_reqval_val (p->prop, cur_att)) {
/* create an empty table instead */
*p = *PFla_empty_tbl_ (p->schema);
return;
}
+
+ if (PFprop_reqval (p->prop, cur_att)) {
+ count++;
+ att = cur_att;
+ val = PFprop_reqval_val (p->prop, cur_att);
+ }
+
+ }
+
+ if (count == 1) {
+ if (p->kind == la_project)
+ for (unsigned int i = 0; i < p->sem.proj.count; i++)
+ if (att == p->sem.proj.items[i].new) {
+ att = p->sem.proj.items[i].old;
+ break;
+ }
+
+ if (L(p) && L(p)->kind == la_disjunion &&
+ PFprop_const (LL(p)->prop, att) &&
+ PFprop_const (LR(p)->prop, att) &&
+ (PFprop_const_val (LL(p)->prop, att)).val.bln !=
+ (PFprop_const_val (LR(p)->prop, att)).val.bln) {
+ if ((PFprop_const_val (LL(p)->prop, att)).val.bln == val)
+ L(p) = LL(p);
+ else
+ L(p) = LR(p);
+ }
+
+ if (R(p) && R(p)->kind == la_disjunion &&
+ PFprop_const (RL(p)->prop, att) &&
+ PFprop_const (RR(p)->prop, att) &&
+ (PFprop_const_val (RL(p)->prop, att)).val.bln !=
+ (PFprop_const_val (RR(p)->prop, att)).val.bln) {
+ if ((PFprop_const_val (RL(p)->prop, att)).val.bln == val)
+ R(p) = RL(p);
+ else
+ R(p) = RR(p);
+ }
}
/* infer properties for children */
Index: opt_dom.c
===================================================================
RCS file: /cvsroot/monetdb/pathfinder/compiler/algebra/opt/opt_dom.c,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -d -r1.7 -r1.8
--- opt_dom.c 3 Jan 2007 12:32:35 -0000 1.7
+++ opt_dom.c 21 Feb 2007 14:25:02 -0000 1.8
@@ -99,6 +99,27 @@
}
} break;
+ case la_semijoin:
+ /* if the semijoin operator does not prune a row
+ because the domains are identical we can safely
+ remove it. */
+ if (PFprop_subdom (
+ p->prop,
+ PFprop_dom_left (p->prop,
+ p->sem.eqjoin.att1),
+ PFprop_dom_right (p->prop,
+ p->sem.eqjoin.att2)) &&
+ PFprop_subdom (
+ p->prop,
+ PFprop_dom_right (p->prop,
+ p->sem.eqjoin.att2),
+ PFprop_dom_left (p->prop,
+ p->sem.eqjoin.att1))) {
+ *p = *L(p);
+ break;
+ }
+ break;
+
default:
break;
}
Index: opt_const.c
===================================================================
RCS file: /cvsroot/monetdb/pathfinder/compiler/algebra/opt/opt_const.c,v
retrieving revision 1.16
retrieving revision 1.17
diff -u -d -r1.16 -r1.17
--- opt_const.c 4 Jan 2007 15:26:18 -0000 1.16
+++ opt_const.c 21 Feb 2007 14:25:01 -0000 1.17
@@ -656,8 +656,8 @@
/* introduce attach if necessary */
if (PFprop_const_left (p->prop, p->sem.aggr.att)) {
L(p) = add_attach (L(p), p->sem.aggr.att,
- PFprop_const_val (p->prop,
- p->sem.aggr.att));
+ PFprop_const_val_left (p->prop,
+ p->sem.aggr.att));
}
/* if partitiong attribute is constant remove it
@@ -675,7 +675,7 @@
p->sem.aggr.part);
PFla_op_t *ret = add_attach (op, p->sem.aggr.part,
- PFprop_const_val (
+ PFprop_const_val_left (
p->prop,
p->sem.aggr.part));
op->sem.aggr.part = att_NULL;
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Monetdb-pf-checkins mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/monetdb-pf-checkins
