Changeset: 0b0cba05f046 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=0b0cba05f046
Modified Files:
monetdb5/optimizer/opt_reorder.mx
sql/backends/monet5/sql.mx
sql/backends/monet5/sql_gencode.mx
sql/benchmarks/ATIS/Tests/select_group.stable.out
sql/benchmarks/tpch/LOCKED/Tests/01-22.stable.out
sql/benchmarks/tpch/LOCKED/Tests/15.stable.out
sql/benchmarks/tpch/Tests/01-22.stable.out
sql/benchmarks/tpch/Tests/15.stable.out
sql/include/sql_relation.h
sql/server/bin_optimizer.c
sql/server/rel_bin.c
sql/server/rel_dump.c
sql/server/rel_exp.c
sql/server/rel_exp.h
sql/server/rel_optimizer.c
sql/server/rel_prop.c
sql/server/rel_prop.h
sql/server/rel_schema.c
sql/server/rel_select.c
sql/server/rel_select.h
sql/server/rel_updates.c
sql/server/rel_updates.h
sql/server/sql_rel2bin.c
sql/server/sql_statement.c
sql/server/sql_statement.h
sql/test/BugTracker-2011/Tests/groupby_primary_key.Bug-2807.stable.out
sql/test/bugs/Tests/rangejoin_optimize_bug.stable.out
Branch: default
Log Message:
Partial reimplemented the reorder optimizer. The goal of the reimplementation
was more 'streaming'/io-pipelining of q1/q6 etc tpch like queries.
This is done making sure that 'a computed' bat's depending statements are
executed right after it, ie we try to limit the live time of intermediates.
(SF-100 q1 (partitioned) went down from >60 minutes to < 5 minutes)
fix in rel_select.c to make subqueries (with correlation) semijoins again.
added rewrites (or improved)
push semijoin under groupby
semi/antiJoin(a,join(a,b)) into semi/anti(a,b)
antijoin(a,union(b,c)) into antijoin(antijoin(a,b),c)
split groupby/projections (the sql compiler generates a single
groupby in for example select avg(a)*5, this rewrites split this in
a groupby and a project.
reduce group by expressions based on primary key (ie if you already
group by on a primary key, then extra columns of the same table
do not reduce the groups anymore). We now join back these columns
after the group by (with a join with the base table, basically late
projection).
Reduces the cost of q10 (of tpch).
diffs (truncated from 1924 to 300 lines):
diff --git a/monetdb5/optimizer/opt_reorder.mx
b/monetdb5/optimizer/opt_reorder.mx
--- a/monetdb5/optimizer/opt_reorder.mx
+++ b/monetdb5/optimizer/opt_reorder.mx
@@ -83,14 +83,16 @@
@c
typedef struct{
int cnt;
+ int used;
+ int pos,pos2;
int stmt[];
} *Node, NodeRecord;
static Node *
-OPTdependencies(Client cntxt, MalBlkPtr mb){
+OPTdependencies(Client cntxt, MalBlkPtr mb, int **Ulist){
Node *list = (Node *) GDKzalloc(sizeof(Node) * mb->stop);
- int *var = (int*) GDKzalloc(sizeof(int) * mb->vtop);
- int i,j;
+ int *var = (int*) GDKzalloc(sizeof(int) * mb->vtop), *uselist = NULL;
+ int i,j,sz=0;
InstrPtr p = NULL;
int block = 0;
@@ -113,70 +115,111 @@
GDKfree(var);
return 0;
}
- list[i]->cnt= p->argc;
- for( j=p->retc; j<p->argc; j++)
- list[i]->stmt[j]= var[getArg(p,j)];
+ list[i]->cnt = p->argc;
+ for( j=p->retc; j<p->argc; j++) {
+ list[i]->stmt[j] = var[getArg(p,j)];
+ list[var[getArg(p,j)]]->used++;
+ }
/* keep the assignment order */
- for( j= 0; j < p->retc; j++)
- if ( var[ getArg(p,j)] )
- list[i]->stmt[j] = var [getArg(p,j)];
- /* remember the last assignment */
+ for( j= 0; j < p->retc; j++) {
+ if ( var[ getArg(p,j)] ) {
+ //list[i]->stmt[j] = var [getArg(p,j)];
+ // escape we should avoid reused variables.
+ for (i--; i>=0; i--)
+ GDKfree(list[i]);
+ GDKfree(list);
+ GDKfree(var);
+ return 0;
+ }
+ }
+ /* remember the last assignment */
for( j=0; j<p->retc; j++)
- var[getArg(p,j)]= i;
- /* and also remember when it was last used.
- this would lead to more breath-first processing,
- something we want to avoid.
- for( j=p->retc; j<p->argc; j++)
- var[getArg(p,j)]= i;
- */
+ var[getArg(p,j)] = i;
}
@-
mnstr_printf(cntxt->fdout,"DEPENDENCY TABLE\n");
for(i=0;i<mb->stop; i++)
- if( list[i]->cnt){
- mnstr_printf(cntxt->fdout,"[%d]",i);
- for(j=p->retc; j< list[i]->cnt; j++)
- mnstr_printf(cntxt->fdout," %d",list[i]->stmt[j]);
+ if( list[i]->cnt){
+ mnstr_printf(cntxt->fdout,"%s.%s [%d,%d]",
+ mb->stmt[i]->modname,
+ mb->stmt[i]->fcnname, i, list[i]->used);
+ for(j=p->retc; j< list[i]->cnt; j++)
+ mnstr_printf(cntxt->fdout, " %d",
list[i]->stmt[j]);
+ mnstr_printf(cntxt->fdout,"\n");
+ }
+@c
+ for(i=0;i<mb->stop; i++) {
+ list[i]->pos = sz;
+ list[i]->pos2 = sz;
+ sz += list[i]->used;
+ }
+ uselist = GDKzalloc(sizeof(int)*sz);
+
+ for(i=0;i<mb->stop; i++) {
+ if (list[i]->cnt) {
+ p= getInstrPtr(mb,i);
+ for(j=p->retc; j< list[i]->cnt; j++) {
+ uselist[list[list[i]->stmt[j]]->pos2] = i;
+ list[list[i]->stmt[j]]->pos2++;
+ }
+ }
+ }
+@-
+ for(i=0, sz = 0; i<mb->stop; i++) {
+ mnstr_printf(cntxt->fdout,"%d is used by", i);
+ for(j=0; j<list[i]->used; j++, sz++)
+ mnstr_printf(cntxt->fdout," %d", uselist[sz]);
mnstr_printf(cntxt->fdout,"\n");
}
@c
+
if ( block ){
for (i--; i>=0; i--)
GDKfree(list[i]);
+ GDKfree(uselist);
GDKfree(list);
GDKfree(var);
return NULL;
}
GDKfree(var);
+ *Ulist = uselist;
return list;
}
static void
-OPTremoveDep(Node *list, int lim){
+OPTremoveDep(Node *list, int lim)
+{
int i;
- for( i=0; i< lim; i++)
- if( list[i])
- GDKfree(list[i]);
+
+ for (i=0; i< lim; i++)
+ if (list[i])
+ GDKfree(list[i]);
GDKfree(list);
}
static void
-OPTdepthfirst(Client cntxt, MalBlkPtr mb, int pc, InstrPtr old[], Node dep[])
+OPTbreadthfirst(Client cntxt, MalBlkPtr mb, int pc, int max, InstrPtr old[],
Node dep[], int *uselist)
{
int i;
InstrPtr p;
- p= old[pc];
- old[pc] = 0;
- if( p == NULL)
+ if (pc > max)
return;
- for (i= 0; i< dep[pc]->cnt; i++)
- OPTdepthfirst(cntxt, mb,dep[pc]->stmt[i], old, dep);
- OPTDEBUGreorder{
- mnstr_printf(cntxt->fdout,"dump[%d]:",pc);
- printInstruction(cntxt->fdout,mb,0,p,LIST_MAL_STMT |
LIST_MAPI);
- }
- pushInstruction(mb, p);
+
+ p = old[pc];
+ if (p == NULL)
+ return;
+
+ for (i= p->retc; i< dep[pc]->cnt; i++)
+ OPTbreadthfirst(cntxt, mb, dep[pc]->stmt[i], max, old, dep,
uselist);
+ if (old[pc] != NULL) {
+ old[pc] = 0;
+ pushInstruction(mb, p);
+ }
+ if (getFunctionId(p) == leftjoinRef || getFunctionId(p) == newRef ||
+ getFunctionId(p) == deriveRef || getFunctionId(p) ==
mirrorRef)
+ for (i = 0; i< dep[pc]->used; i++)
+ OPTbreadthfirst(cntxt, mb, uselist[dep[pc]->pos+i],
max, old, dep, uselist);
}
static int
@@ -184,12 +227,12 @@
{
int i,j, start;
InstrPtr *old;
- int limit, slimit;
+ int limit, slimit, *uselist = NULL;
Node *dep;
(void) cntxt;
(void) stk;
- dep = OPTdependencies(cntxt,mb);
+ dep = OPTdependencies(cntxt,mb,&uselist);
if ( dep == NULL)
return 0;
limit= mb->stop;
@@ -201,24 +244,28 @@
pushInstruction(mb,old[0]);
old[0]=0;
for( i=1; i<limit; i++)
- if ( getModuleId(old[i]) == datacyclotronRef && getFunctionId(old[i])
== bindRef){
- pushInstruction(mb,old[i]);
- old[i] = 0;
- }
+ if ( getModuleId(old[i]) == datacyclotronRef &&
getFunctionId(old[i]) == bindRef){
+ pushInstruction(mb,old[i]);
+ old[i] = 0;
+ }
start=1;
- for( i=1; i<limit; i++){
+ for (i=1; i<limit; i++){
p= old[i];
if ( p == 0)
continue;
if( p->token == ENDsymbol)
break;
- if( hasSideEffects(p,TRUE) || (getModuleId(p) != sqlRef &&
isUpdateInstruction(p)) || isUnsafeFunction(p) || p->barrier ){
- OPTdepthfirst(cntxt, mb, i, old, dep);
+ if( hasSideEffects(p,FALSE) || isUnsafeFunction(p) ||
p->barrier ){
+ OPTbreadthfirst(cntxt, mb, i, i, old, dep, uselist);
/* remove last instruction and keep for later */
- p= mb->stmt[mb->stop-1];
- mb->stmt[mb->stop-1]=0;
- mb->stop--;
+ if (p == mb->stmt[mb->stop-1]) {
+ p= mb->stmt[mb->stop-1];
+ mb->stmt[mb->stop-1]=0;
+ mb->stop--;
+ } else {
+ p = 0;
+ }
/* collect all seen sofar by backward grouping */
/* since p has side-effects, we should secure all seen
sofar */
for(j=i-1; j>=start;j--) {
@@ -226,9 +273,10 @@
mnstr_printf(cntxt->fdout,"leftover:
%d",start+1);
printInstruction(cntxt->fdout,mb,0,old[j],LIST_MAL_STMT | LIST_MAPI);
}
- OPTdepthfirst(cntxt, mb, j, old, dep);
+ OPTbreadthfirst(cntxt, mb, j, i, old, dep,
uselist);
}
- pushInstruction(mb,p);
+ if (p)
+ pushInstruction(mb,p);
start = i+1;
}
}
diff --git a/sql/backends/monet5/sql.mx b/sql/backends/monet5/sql.mx
--- a/sql/backends/monet5/sql.mx
+++ b/sql/backends/monet5/sql.mx
@@ -1455,6 +1455,7 @@
b->currIndex = NULL;
b->vtop = 0;
b->q = NULL;
+ b->mvc_var = 0;
return b;
}
@@ -1466,6 +1467,7 @@
b->console = isAdministrator(c);
b->mvc = m;
b->client = c;
+ b->mvc_var = 0;
return backend_reset(b);
}
diff --git a/sql/backends/monet5/sql_gencode.mx
b/sql/backends/monet5/sql_gencode.mx
--- a/sql/backends/monet5/sql_gencode.mx
+++ b/sql/backends/monet5/sql_gencode.mx
@@ -577,6 +577,7 @@
if (s->op1) {
if (VAR_GLOBAL(s->flag)) { /* globals */
int tt = tail_type(s)->type->localtype;
+
q = newStmt1(mb, sqlRef, "getVariable");
q = pushArgument(mb, q, sql->mvc_var);
q = pushStr(mb, q,
s->op1->op4.aval->data.val.sval);
diff --git a/sql/benchmarks/ATIS/Tests/select_group.stable.out
b/sql/benchmarks/ATIS/Tests/select_group.stable.out
--- a/sql/benchmarks/ATIS/Tests/select_group.stable.out
+++ b/sql/benchmarks/ATIS/Tests/select_group.stable.out
@@ -37,7 +37,7 @@
[ "SATURDAY", 6, 64 ]
[ "SUNDAY", 7, 64 ]
% sys.day_name, sys.day_name # table_name
-% day_name, L2 # name
+% day_name, L3 # name
% char, wrd # type
% 9, 2 # length
[ "MONDAY", 64 ]
@@ -57,7 +57,7 @@
[ "JULY", "SUNDAY" ]
#select day_name.day_name,flight_day.day_code,count(*) from
flight_day,day_name where day_name.day_code=flight_day.day_code group by
flight_day.day_code,day_name.day_name order by day_code;
% sys.day_name, sys.flight_day, sys.flight_day # table_name
-% day_name, day_code, L3 # name
+% day_name, day_code, L4 # name
% char, decimal, wrd # type
% 9, 2, 2 # length
[ "MONDAY", 1, 64 ]
@@ -68,57 +68,57 @@
[ "SATURDAY", 6, 64 ]
[ "SUNDAY", 7, 64 ]
% sys.aircraft # table_name
-% L4 # name
+% L5 # name
% decimal # type
% 2 # length
[ 278 ]
% sys. # table_name
-% L5 # name
+% L6 # name
% double # type
% 22 # length
_______________________________________________
Checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
