opt_generators.mx

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

@' The contents of this file are subject to the MonetDB Public
@' License Version 1.0 (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/MonetDBGicense-1.0.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 Monet 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_generators
@a M. Kersten
@- Iterator query processing
Limitations on the addressing space in older PCs and the need
for distributed storage makes that BATs ideally should be 
looked upon as a union of smaller BATs which are processed
within the (memory) resource limitations given.

The operation @sc{optimizer.generators} takes @sc{pbm.generator} definitions
and encapsulate them in iterator blocks, thereby minimizing the
MAL memory footprint.

The optimizer is designed incrementally. The focus is
on supporting the SQL front-end. In particularly, the
operators considered is a limited subset of MAL. Occurrence
of an operator outside this set terminates the loop.

The general strategy is to select a portion of the workflow
related to a variable and encapsulate it with
an iterator over the BAT partitions. In doing so, we replace
operators with their incremental counter part, alike the
mergetable optimizer.

A snippet of the partitioning optimizer is shown below. It assumes
that the partitioned BAT @sc{a0} consists of the components @sc{a1,a2,a3}.
A subsequent call of the partition optimizer will replace
the print command with an iterator.
@verbatim

function qry(a:bat[:oid,:any_1]
	b:bat[void,:int]:= pdbm.generator("Sales2005")
	i:= algebra.count(b);
	io.print(i);
end qry;
optimizer.generators("user","qry");
@end verbatim
The query is transformed into the following version.
@verbatim
function user.qry(a:bat[:oid,:any_1]{mat}):void;
	i:= 0;
barrier b:= mat.newIterator("Sales2005");
	_8:= aggr.count(b);
	i:= i+ _8;
	redo b:= mat.getNextElement(a);
exit b;
	io.print(i);
end qry;
@end verbatim
@{
@+ Implementation
The implementation is somewhat complicated by the fact that MAL
programs contains (implicit) flow of control. This calls for
a two stage machine, where we are copying all instructions into place
until we encounter a generator. Then we reorganize
the plan until this generator and its dependencies are exhausted
or a packing operation is required before proceeding.

The safe line is that at any time we can safe partial results in
a partition BAT, which is scanned the next time we need it.
The implementation may even decide to pack components together.

To minimize the impact of the generators, it is adviced to
first normalize the query plan, moving related instructions close
together.
@mal
pattern optimizer.generators():str
address OPTgenerators;
pattern optimizer.generators(mod:str, fcn:str):str
address OPTgenerators
comment "Resolve the multi-table definitions";

@h
#ifndef _MAL_BATLOOPS_
#define _MAL_BATLOOPS_
#include "opt_prelude.h"
#include "opt_support.h"
#include "mal_builder.h"
#include "pbm.h"

opt_export str BGoptimizer(MalBlkPtr mb, MalStkPtr stk, InstrPtr p);
/* #define DEBUG_OPT_BATLOOPS     show partial result */

#endif
@c
#include "mal_config.h"
#include "opt_generators.h"

static int
isPBMalias(int idx, int mvar[], int top){
	int i;
	for(i =0; i<top; i++)
		if( mvar[i]== idx) return i;
	return -1;
}

static void BGcloseLoop(MalBlkPtr mb, int m, InstrPtr *stmt ){
	InstrPtr r;
	r = newInstruction(mb, ASSIGNsymbol);
	r->barrier= REDOsymbol;
	setModuleId(r, getModuleId(stmt[m]));
	setFunctionId(r,putName("getNextElement",14));
	getArg(r,0)= getArg(stmt[m],0);
	pushArgument(mb,r,getArg(stmt[m],1));
	pushInstruction(mb,r);

	r = newInstruction(mb, ASSIGNsymbol);
	r->barrier= EXITsymbol;
	getArg(r,0)= getArg(stmt[m],0);
	pushInstruction(mb,r);

}
static void BGkeepPartial(MalBlkPtr mb, int i, InstrPtr p){
	InstrPtr r;
	char tmpname[128];
	r = newInstruction(mb, ASSIGNsymbol);
	setModuleId(r, pbmRef);
	setFunctionId(r,depositRef);
	getArg(r,0)= newTmpVariable(mb,TYPE_any);
	snprintf(tmpname,128,"pbat_%s", getVarName(mb,getArg(p,0)));
	pushStr(mb,r,tmpname);
	pushArgument(mb,r,getArg(p,0));
	insertInstruction(mb,r,i);
}
@-
The key administration is to keep track of the outstanding
iterator blocks and whether a variable represents a PBAT result.
The table mloop contains the PC of the corresponding iterator.
@c
#define GEN_CLOSED 0
#define GEN_OPENED 1
#define GEN_PARTIAL 2
#define GEN_PACKED 4

int
OPTgeneratorsImplementation(MalBlkPtr mb, MalStkPtr stk, InstrPtr p){
	InstrPtr *old=0, q,r, stmt[256];
	int oldtop, keep=0,i,j,k,m=0;
#ifndef NDEBUG
	int oldsize;
#endif
	int iter=0,index[256]; /* active nesting level <=mtop*/
	int  mtop=0, mvar[256], mstatus[256];
	int size,match,actions=0;
	char tmpname[128];
#ifdef DEBUG_OPT_BATLOOPS
	stream_printf(GDKout,"Start generators optimizer\n");
	printFunction(GDKout, mb, 0);
#endif

	setLifespan(mb); /* to detect future variable use */
	old = mb->stmt;
	oldtop= mb->stop;
#ifndef NDEBUG
	oldsize= mb->ssize;
#endif
	size = (mb->stop *1.2 < mb->ssize)? mb->ssize: mb->stop *1.2;
	mb->stmt = (InstrPtr *) GDKzalloc(size  * sizeof(InstrPtr));
	mb->ssize = size ;
	mb->stop = keep;


	for( i=0; i<oldtop-1; i++){
		p= old[i];
@-
Deal with iterator requests aimed at partitioned BATs.
Generators are stacked for inspection. They don't correspond to
code immediately.
@c
		if( getModuleId(p)== pbmRef && getFunctionId(p)== generatorRef) {
			getFunctionId(p)= putName("newIterator",11);
			p->barrier = BARRIERsymbol;
			mvar[mtop] = getArg(p,0);
			mstatus[mtop] = GEN_CLOSED; /* not yet opened */
			stmt[mtop++]= p;
			continue;
		}
@-
Some instructions are easy to deal with
@c
		if( p->token== NOOPsymbol || 
			p->token== REMsymbol){
			pushInstruction(mb,p);
			continue;
		}
@-
In the general case it is more difficult. An incremental operation may exist,
but also the operation is targeted at the partitioned bat itself, without
interference with others.
In that case we can wrape the code in an iterator or rely on such a routine
to be available in the @sc{pbm} module.
The case below is to used as a starting point for experimentation.
@c
		if( getFunctionId(p) == setWriteModeRef && getModuleId(p) == batRef){
			for(k=0;k<mtop;k++)
			if( mvar[k]== getArg(p,1)){
				r= copyInstruction(stmt[m]);
				getArg(r,0)= getArg(p,0);
				getArg(r,1)= getArg(stmt[k],1);
				getArg(p,1)= getArg(stmt[k],1);
				getModuleId(p)= pbmRef;

				mvar[mtop] = getArg(r,0);
				mstatus[mtop]= GEN_CLOSED;
				stmt[mtop]= r;
				index[iter++]= mtop;
				mtop++;
			}
			pushInstruction(mb,p);
			continue;
		}
@-
Not all instructions can be replaced by the sequence. We have to
group them and check for them individually.
@c
		if( (getModuleId(p)== algebraRef 	&& getFunctionId(p)== selectRef) ||
			(getModuleId(p)== algebraRef 	&& getFunctionId(p)== uselectRef) ||
			(getModuleId(p)== algebraRef 	&& getFunctionId(p)== likeselectRef) ||
			(getModuleId(p)== batRef 		&& getFunctionId(p)== reverseRef) ||
			(getModuleId(p)== batRef 		&& getFunctionId(p)== mirrorRef) ||
			(getModuleId(p)== algebraRef 	&& getFunctionId(p)== markTRef) ||
			(getModuleId(p)== algebraRef	&& getFunctionId(p)== kdifferenceRef) ||
			(getModuleId(p)== algebraRef	&& getFunctionId(p)== kunionRef) ||
			(getModuleId(p)== algebraRef	&& getFunctionId(p)== joinRef) ||
			(getModuleId(p)== algebraRef	&& getFunctionId(p)== semijoinRef) ||
			(getModuleId(p)== batRef		&& getFunctionId(p)== setAccessRef) ||
			(getModuleId(p)== batRef		&& getFunctionId(p)== appendRef)  ||
			(getModuleId(p)== batRef		&& getFunctionId(p)== deleteRef) ||
			(getModuleId(p)== batRef		&& getFunctionId(p)== setWriteModeRef) 
			){
@-
Locate the arguments that depend on a partitioned BAT.
If their iterator is not opened, the we should do so first.
Moreover, the result is again a partial result, to be
added to the loop nesting table, but this time claim it is already openend.
@c
			match=0;
			for(k=p->retc; k<p->argc;k++)
			if( (m=isPBMalias(getArg(p,k),mvar,mtop)) >= 0) {
				if( mstatus[m]== GEN_CLOSED){
					r= copyInstruction(stmt[m]);
					pushInstruction(mb,r);
					mstatus[m]= GEN_OPENED;
					index[iter++]=m;
				}
				match++;
			}
@-
The net effect of the operation is a partial result, which
may turn into a partition BAT 
@c
			if( match){
				pushInstruction(mb,p);
				r = newInstruction(mb, ASSIGNsymbol);
				r->barrier= BARRIERsymbol;
				setModuleId(r,pbmRef);
				setFunctionId(r,putName("newIterator",11));
				getArg(r,0)= getArg(p,0);
				snprintf(tmpname,128,"pbat_%s", getVarName(mb,getArg(p,0)));
				pushStr(mb,r,tmpname);

				mvar[mtop] = getArg(r,0);
				mstatus[mtop]= GEN_PARTIAL;
				stmt[mtop]= r;
				index[iter++]= mtop;
				mtop++;
				actions++;
				continue;
			}
		} 
@-
Handle the rewrite v:=aggr.count(b) and sum()
In this case we have to include an initialization statement before the
generator.
@c
		if( ((getModuleId(p)==aggrRef && getFunctionId(p)== countRef) || 
			(getModuleId(p)==aggrRef && getFunctionId(p)== minRef && p->argc==3) ||
			(getModuleId(p)==aggrRef && getFunctionId(p)== maxRef && p->argc==3) ||
			(getModuleId(p)==aggrRef && getFunctionId(p)==sumRef && p->argc==2)) &&
			(m=isPBMalias(getArg(p,1),mvar,mtop)) >= 0){
			r = newInstruction(mb,ASSIGNsymbol);
			getArg(r,0)= getArg(p,0);
			pushInt(mb,r,0);

@-
The initializing variable should be initialized before the loop
in which the partial result is constructed. This requires analysis
of the partial dependences and to find the loop structure in which
the partial result was introduced.
For the time, we simply move it before the last barrier that
references a newIterator
@c
			
			m= 0;
			for(k= mb->stop-1; k>0; k--){
				q= getInstrPtr(mb,k);
				if( getModuleId(q)== pbmRef && 
					getFunctionId(q)== putName("newIterator",11))
					m=k;
			}
			insertInstruction(mb,r,m);

			q= copyInstruction(p);
			k= newTmpVariable(mb,TYPE_int);
			getArg(q,0)= k;
			pushInstruction(mb,q);

			q= newInstruction(mb,ASSIGNsymbol);
			setModuleId(q,calcRef); 
			if( getFunctionId(p)== countRef || getFunctionId(p)== sumRef)
				setFunctionId(q,plusRef);
			else
				setFunctionId(q,getFunctionId(p));
			getArg(q,0)= getArg(r,0);
			q= pushArgument(mb,q,getArg(r,0));
			q= pushArgument(mb,q,k);
			pushInstruction(mb,q);
			continue;
		} 
@-
Any side-effect operator should be either postponed or terminates
the generator.
It is up to the strength reduction to move instructions safely out of
the loop.
Otherwise we have to decide on either packing them or replacement.
@c
		match=0;
		for(j=p->retc; j<p->argc; j++)
		if(  isPBMalias(getArg(p,j),mvar,mtop) >= GEN_OPENED) {
			m=i; match++;
		}
@-
We now have an unsafe operation with potentially a reference to
a partitioned BAT.
All other instructions should be checked for dependencies.
All other use is considered once-only
and the instruction should be moved outside the loop.
Moreover, it then terminates the block in which it was used.
@c
		for(k=iter-1;k>=0; k--)
		if(mstatus[index[k]]== GEN_OPENED) {
			BGcloseLoop(mb,index[k],stmt);
			mstatus[index[k]]= GEN_CLOSED;
		} else
		if( mstatus[index[k]]== GEN_PARTIAL){
			if( getVar(mb,getArg(stmt[index[k]],0))->endLifespan>= i){
				BGkeepPartial(mb,mb->stop,stmt[index[k]]);
				r= newInstruction(mb,ASSIGNsymbol);
				getModuleId(r)=pbmRef;
				getFunctionId(r)=putName("discard",7);
				getArg(r,0)= newTmpVariable(mb, TYPE_any);
				snprintf(tmpname,128,"pbat_%s", 
						getVarName(mb,getArg(stmt[index[k]],0)));
				pushStr(mb,r,tmpname);
				assert(oldtop<oldsize-1);
				old[oldtop]= old[oldtop-1];
				old[oldtop-1]=r;
				oldtop++;
			}
			mstatus[index[k]]= GEN_CLOSED;
		} else
		iter = 0;
		
		for( k= p->retc; k<p->argc; k++)
		if(	(m=isPBMalias(getArg(p,k),mvar,mtop)) >= 0){
#ifdef DEBUG_OPT_BATLOOPS
			stream_printf(GDKout,"Dependency resolution k=%d\n",k);
			printInstruction(GDKout,mb,p,0);
#endif
			r = newInstruction(mb, ASSIGNsymbol);
			setModuleId(r,pbmRef);
			setFunctionId(r,packRef);
			getArg(r,0)= getArg(stmt[m],0);
			pushInstruction(mb,r);
			mstatus[m]= GEN_PACKED;
			actions++;
			break;
		}
		pushInstruction(mb,p);
	}
@-
At this stage we should close any open generators.
@c
	for(i=iter-1; i>=0; i--)
	if( mstatus[index[i]]== GEN_OPENED){
		BGcloseLoop(mb,index[i],stmt);
	}
	pushInstruction(mb,old[oldtop-1]);
	GDKfree(old);
	(void) stk; 
#ifdef DEBUG_OPT_BATLOOPS
	stream_printf(GDKout,"Result of generators optimizer\n");
	printFunction(GDKout, mb, 0);
#endif
	return actions;
}
@include optimizerWrapper.mx
@h
@:exportOptimizer(generators)@
@c
@:wrapOptimizer(generators,OPT_CHECK_ALL)@
@}