opt_qep.mx

一个内存数据库的源代码这是服务器端还有客户端

@' 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://monetdb.cwi.nl/Legal/MonetDBLicense-1.1.html
@'
@' 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-2007 CWI.
@' All Rights Reserved.

@f opt_qep
@a M. Kersten
@- Query Execution Plans
A commonly used data structure to represent and manipulate
a query is a tree (or graph). Its nodes represent the
operators and the leaves the operands. 
Such a view comes in handy when you have to re-organize
whole sections of code or to built-up an optimized plan
bottom up, e.g. using a memo structure.

The MAL optimizer toolkit provides functions to
overlay the body of any MAL block with a tree (graph)
structure and to linearize them back into a MAL block.
The linearization order is determined by a recursive
descend tree walk from the anchor points in the source program.

To illustrate, consider the code block:
@example
#T1:= bat.new(:int,:int);
#T2:= bat.new(:int,:int);
#T3:= bat.new(:int,:int);
#T4:= bat.new(:int,:int);
a:= algebra.select(T1,1,3);
b:= algebra.select(T2,1,3);
c:= algebra.select(T3,0,5);
d:= algebra.select(T4,0,5);
e:= algebra.join(a,c);
f:= algebra.join(b,d);
h:= algebra.join(e,f);
optimizer.dumpQEP();
@end example
which produces an indented structure of the query plan.
@example
h := algebra.join(e,f);
    e := algebra.join(a,c);
        a := algebra.select(T1,1,3);
            T1 := bat.new(:int,:int);
        c := algebra.select(T3,0,5);
            T3 := bat.new(:int,:int);
    f := algebra.join(b,d);
        b := algebra.select(T2,1,3);
            T2 := bat.new(:int,:int);
        d := algebra.select(T4,0,5);
            T4 := bat.new(:int,:int);
@end example

Any valid MAL routine can be overlayed with a tree (graph)
view based on the flow dependencies, but not all MAL programs
can be derived from a simple tree. For example, the code snippet
above when interpreted as a linear sequence can not be represented
unless the execution order itself becomes an operator node itself. 

However, since we haven't added or changed the original
MAL program, the routine @code{qep.propagate} produces
the orginial program, where the linear order has
priority. If, however, we had entered new instructions
into the tree, they would have been placed in close proximity
of the other tree nodes.

Special care is given to the flow-of-control blocks, because
to produce a query plan section that can not easily be moved
around.
[give dot examples]
@{
@mal
pattern optimizer.dumpQEP()
address OPTdumpQEP
comment "Produce an indented tree visualisation";
@h
#ifndef _OPT_QEP_
#define _OPT_QEP_
#include "mal.h"
#include "mal_interpreter.h"
#include "opt_prelude.h"
#include "opt_support.h"

#define DEBUG_OPT_QEP     /* show partial result */
typedef struct QEPrecord {
	MalBlkPtr mb;
	InstrPtr p;
	int plimit, climit;		/* capacities */
	struct QEPrecord **parents;	/* at least one link to parent */
	struct QEPrecord **children;
} *QEP;

#define MAXPARENT 4
#define MAXCHILD 8

#endif /* _OPT_QEP_ */
@c
#include "mal_config.h"
#include "opt_qep.h"

static QEP
QEPnew(int p, int c){
	QEP qep;
	qep = (QEP) GDKmalloc( sizeof(struct QEPrecord));
	qep->mb= NULL;
	qep->p = NULL;
	qep->plimit = p;
	if( p )
		qep->parents = (QEP*) GDKzalloc( sizeof(QEP) * p);
	qep->climit = c;
	if( c)
		qep->children = (QEP *) GDKzalloc( sizeof(QEP) * c);
	return qep;
}
static QEP
QEPnewNode(MalBlkPtr mb,InstrPtr p){
	QEP q;
	q= QEPnew(p->retc,p->argc-p->retc+1);
	q->mb= mb;
	q->p = p;
	return q;
}
static QEP
QEPexpandChildren(QEP qep, int extra){
	int i;
	/*extend node */
	qep->children = (QEP*) GDKrealloc( (char*) qep->children, 
				sizeof(QEP) * (qep->climit + extra));
	for(i=qep->climit;i <qep->climit + extra; i++)
		qep->children[i]=0;
	qep->climit = qep->climit + extra;
	return qep;
}

#if 0
static QEP
QEPfree(QEP qep){
	GDKfree(qep->children);
	GDKfree(qep->parents);
	GDKfree(qep);
	return NULL;
}
#endif
@-
Extract a child from the qep, to be inserted somewhere else
@c
#if 0
static QEP
QEPdelete(QEP qep, int pos){
	int i;
	QEP q= NULL;

	for(i=0; i<qep->climit && qep->children[i]; i++){
		if(pos-- == 0) q = qep->children[i];
		if( pos <0 ) qep->children[i]= qep->children[i+1];
		if( i< qep->climit-1) q->children[i]= NULL;
	}
	return q;
}
#endif
QEP
QEPappend(QEP qep, QEP child){
	int i;
	for( i=0; i< qep->climit-1; i++)
		if( qep->children[i] == NULL)
			break;
	if(qep->climit== 0 || qep->children[i]!= NULL )
		qep= QEPexpandChildren(qep,MAXCHILD);
	qep->children[i]= child;
	if( child) 
		child->parents[0]= qep;
	return qep;
}
#if 0
static QEP
QEPinsert(QEP qep, int pos, QEP child){
	int i;
	QEP q= NULL, qn; 
	for( i=0; i< qep->climit; i++){
		if( pos-- == 0){
			q= qep->children[i];
			qep->children[i]= child;
			child->parents[0] =qep;
		}
		if( pos < 0 && i<qep->climit-1){
			qn= qep->children[i+1];
			qep->children[i+1] = q;
			q= qn;
		}
	}
	if( q != NULL)
		qep = QEPappend(qep,q);
	return qep;
}
#endif
@-
The core of the work is focused on building the tree using a flow analysis. 
Building the tree means that we should not allow the same variable can not be used twice.
@c
#define LEAFNODE 2
#define TOPNODE 3

static QEP
QEPbuilt(MalBlkPtr mb){
	QEP qroot= NULL, q= NULL, *vq;
	InstrPtr p;
	int i, j, k, *status;

	vq= (QEP*) GDKmalloc( mb->vtop * sizeof(QEP));
	status= (int*) GDKmalloc( mb->vtop * sizeof(int));
	for(i=0; i<mb->vtop; i++) {
		status[i]= 0;
		vq[i] = 0;
	}

	for(i=1; i< mb->stop-1; i++){
		p= getInstrPtr(mb,i);
		q= QEPnewNode(mb,p);
		for( k=p->retc; k<p->argc; k++) 
		if( ! isConstant(mb, getArg(p,k)) ){
			status[getArg(p,k)]= LEAFNODE;
			if( vq[getArg(p,k)] )
				QEPappend(q, vq[getArg(p,k)]);
		}
		for( k=0; k<p->retc; k++){
			if(	vq[getArg(p,k)] == 0)
				vq[getArg(p,k)] = q;
			status[getArg(p,k)]= TOPNODE;
		}

	}
@-
We may end up with multiple variables not yet bound to a QEP.
@c
	qroot= QEPnew(MAXPARENT,mb->stop);
	for(i=1; i< mb->stop-1; i++){
		p= getInstrPtr(mb,i);
	
		k=0;
		if( p->barrier){
			k++;
			q= QEPnewNode(mb,p);
		} else
		for( j=0; j< p->retc; j++)
		if( status[getArg(p,j)] == TOPNODE){
			q= vq[getArg(p,j)];
			k++;
			break;
		}
		if(k)
			QEPappend(qroot,q);
	}
	GDKfree(vq);
	GDKfree(status);
	return qroot;
}
@-
It may be handy to dump the graph for inspection
or to prepare for the dot program.
@c
static void
QEPdump(stream *f, QEP qep, int indent){
	int i,inc = 0;
	str s;
	if( qep->p){
		for(i=0;i<indent; i++) stream_printf(f," ");
		s= instruction2str(qep->mb,qep->p,0);
		stream_printf(f,"%s\n",s+1);
		GDKfree(s);
		inc = 4;
	}
	for(i=0; i< qep->climit; i++)
	if( qep->children[i])
		QEPdump(f,qep->children[i], indent+ inc);
}
static int
OPTdumpQEPImplementation(MalBlkPtr mb, MalStkPtr stk, InstrPtr p){
	QEP qep;
	(void) stk;
	(void) p;

	qep= QEPbuilt(mb);
	QEPdump(GDKout,qep,0);
	return 1;
}
@include optimizerWrapper.mx
@h
@:exportOptimizer(dumpQEP)@
@c
@:wrapOptimizer(dumpQEP,OPT_CHECK_ALL)@
@}