opt_pushranges.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_pushranges
@a M. Kersten
@- Range Propagation
Almost all queries are interested in a few slices
of the table. If applied to a view, the query plans
often contain multiple selections over the same column.
They may also have fixed range arguments comming from
fragmentation criteria.

The purpose of the @sc{pushranges} optimizer is to
minimize the number of table scans by cascading the
range terms as much as possible. Useless instructions
are removed from the plan.

@example
    b := bat.new(:oid,:int);
    s1:= algebra.select(b,1,100);
    s2:= algebra.select(s1,5,95);
    s3:= algebra.select(s2,50,nil);
    s4:= algebra.select(s3,nil,75);
    optimizer.pushranges();
@end example

This lengthly sequence can be compressed into a single one:
@example
    b := bat.new(:oid,:int);
    s1:= algebra.select(b,50,75);
@end example
A union over two range selections from a single
source could also be a target.
@example
    t1:= algebra.select(b,1,10);
    t2:= algebra.select(b,0,5);
    t3:= algebra.union(t1,t2);
@end example
would become
@example
   t3:= algebra.select(0,10);
@end example

@{
The range cascades should be limited to simple blocks.
Furthermore, we should ensure that variables are not re-used
other then in side-effect functions.

The aliasRemoval and constantExpression optimizers should
have done their work. Empty scans are simply dropped,
which leads to a planned cleaning by the dead code optimizer.

@mal
pattern optimizer.pushranges():str
address OPTpushranges;
pattern optimizer.pushranges(mod:str, fcn:str):str
address OPTpushranges
comment "Push constant range selections through the program";

@h
#ifndef _OPT_RANGEPUSH_
#define _OPT_RANGEPUSH_
#include "opt_support.h"
#include "opt_prelude.h"

/* #define DEBUG_OPT_RANGEPUSH */

#endif


@c  
#include "mal_config.h"
#include "opt_pushranges.h"
#include "mal_interpreter.h"	/* for showErrors() */

typedef struct RANGE{
	int used;		/* how often it has been used */
	int lcst, hcst; /* constant variables holding the range bounds */
	int  srcvar;	/* BAT variable on which the range depends */
	int lastupdate, lastrange;
}RangeRec, *Range;

#ifdef DEBUG_OPT_RANGEPUSH
static void 
printRange(MalBlkPtr mb, Range rng, int idx){
	(void) rng;
	stream_printf(GDKout,"[%3d] %5s used=%d\tlcst=%s\t ", 
		idx, getVarName(mb,idx), rng[idx].used,
		(rng[idx].lcst? getVarName(mb,rng[idx].lcst):""));
	stream_printf(GDKout,"hcst=%s\tsource %s ", 
		(rng[idx].hcst? getVarName(mb,rng[idx].hcst):""), 
		(rng[idx].srcvar?getVarName(mb,rng[idx].srcvar):""));
	stream_printf(GDKout,"\tlu=%d\tr=%d", rng[idx].lastupdate, rng[idx].lastrange);
	stream_printf(GDKout,"\n");
}
#endif

static int
OPTpushrangesImplementation(MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
{
	int i,j, limit,actions=0;
	InstrPtr p, *old;
	int x,y,z,typ;
	Range range= (Range) alloca(mb->vtop * sizeof(RangeRec));

	memset((char*) range, 0, mb->vtop * sizeof(RangeRec));
	if( mb->errors) 
		return 0;

#ifdef DEBUG_OPT_RANGEPUSH
	printf("Range select optimizer started\n");
#endif
	(void) stk;
	(void) pci;
	
	limit = mb->stop;
	old = mb->stmt;
@-
In phase I we collect information about constants
@c
	for (i = 0; i < limit; i++) {
		p = old[i];
		if( p->barrier) 
			break; /* end of optimizer */
		for(j=p->retc; j< p->argc; j++)
			range[getArg(p,j)].used++;
		for(j=0; j<p->retc; j++){
			range[getArg(p,j)].lastupdate= i;
			if( range[getArg(p,j)].lastrange == 0)
				range[getArg(p,j)].lastrange= i;
		}
		if( getModuleId(p)== algebraRef && 
			( getFunctionId(p)== selectRef || getFunctionId(p)== uselectRef) ){
@-
The operation X:= algebra.select(Y,L,H,Li,Hi) is analysed.
First, we attempt to propagate the range known for Y onto the 
requested range of X. This may lead to smaller range of
even the conclusion that X is necessarily empty.
Of course, only under the condition that Y has not been changed by a
side-effect since it was bound to X.
@c
			x= getArg(p,1);
			y= getArg(p,2);
			if( range[x].lcst && isConstant(mb,y) ){
				/* merge lowerbound */
				if( ATOMcmp( getVarType(mb,y), 
						VALptr( &getVarConstant(mb,range[x].lcst)), 
						VALptr( &getVarConstant(mb,y)) ) > 0){
					getArg(p,2)= range[x].lcst;
					z= range[x].srcvar;
					if( getArg(p,1) == x && 
						range[z].lastupdate == range[z].lastrange){
						getArg(p,1) = z;
						actions++;
					}
				}
				y= getArg(p,3);
				/* merge higherbound */
				if( ATOMcmp( getVarType(mb,y), 
						VALptr( &getVarConstant(mb,range[x].hcst)), 
						VALptr( &getVarConstant(mb,y)) ) < 0 ||
					ATOMcmp( getVarType(mb,y),
						VALptr( &getVarConstant(mb,y)),
						 ATOMnilptr(getVarType(mb,y)) ) == 0){
					getArg(p,3)= range[x].hcst;
					z= range[x].srcvar;
					if( getArg(p,1) == x && range[z].lastupdate == range[z].lastrange){
						getArg(p,1) = z;
						actions++;
					}
				}
			}
@-
The second step is to assign the result of this exercise to the
result variable.
@c
			x= getArg(p,0);
			if( isConstant(mb, getArg(p,2)) ){
				range[x].lcst = getArg(p,2);
				range[x].srcvar= getArg(p,1);
				range[x].lastupdate= range[x].lastrange = i;
			}
			if( isConstant(mb, getArg(p,3)) ){
				range[x].hcst = getArg(p,3);
				range[x].srcvar= getArg(p,1);
				range[x].lastupdate= range[x].lastrange = i;
			}
@-
If both range bounds are constant, we can also detect empty results.
It is empty if L> H or when L=H and the bounds are !(true,true).
@c
			x= getArg(p,2);
			y= getArg(p,3);
			if( isConstant(mb, x)  &&
				isConstant(mb, y)  ){
				z =ATOMcmp( getVarType(mb,y),
                        VALptr( &getVarConstant(mb,x)),
                        VALptr( &getVarConstant(mb,y)));
				x=  p->argc > 4;
				x= x && isConstant(mb,getArg(p,4));
				x= x && isConstant(mb,getArg(p,5));
				x= x && getVarConstant(mb,getArg(p,4)).val.cval[0];
				x= x && getVarConstant(mb,getArg(p,5)).val.cval[0];
				if( z > 0 || (z==0 && p->argc>4 && !x)) {
					int zero= 0;
					if( mb->var[getArg(p,0)]->props== NULL)
						mb->var[getArg(p,0)]->props= newPropertySet();
					setProperty(mb->var[getArg(p,0)]->props,
							"rows","=",TYPE_int,&zero);
					/* create an empty replacement */
					x= getArgType(mb, p, 1);
					p->argc=1;
					getModuleId(p)= batRef;
					getFunctionId(p)= newRef;
					pushArgument(mb,p, typ=newTypeVariable(mb, getHeadType(x)));
					isConstant(mb,typ)= TRUE;
					pushArgument(mb,p, typ=newTypeVariable(mb, getTailType(x)));
					isConstant(mb,typ)= TRUE;
					actions++;
				}
			}
		}
	}
#ifdef DEBUG_OPT_RANGEPUSH
		for(j=0; j< mb->vtop; j++)
		if( range[j].used )
			printRange(mb,range,j);
#endif
@-
Phase II, if we succeeded in pushing constants around and
changing instructions, we might as well try once more to perform
aliasRemoval, constantExpression, and pushranges.
@c
	return actions;
}
@include optimizerWrapper.mx
@h
@:exportOptimizer(pushranges)@
@c
@:wrapOptimizer(pushranges,OPT_CHECK_ALL)@
@}