opt_factorize.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_factorize
@a M. Kersten
@- Code Factorization
In most real-life situations queries are repeatedly called with
only slight changes in their parameters. This situation can be
captured by the query compilers by keeping a cache of recent query
plans. In MonetDB context such queries are represented as parameterized
MAL programs.

To further optimize the cached functions it might help to
split the query plan into two sections. One section with
those actions that do not depend on the arguments given and
another section that contains the heart of the query using
all information.
Such a program can be represented by a MAL factory, which is
a re-entrend query plan.

An example of how factorize changes the code is shown below:
@verbatim
function test(s:str):lng;
    b:= bat.new(:int,:str);
    bat.insert(b,1,"hello");
    z:= algebra.select(b,s,s);
    i:= aggr.count(z);
    return i;
end test;
optimizer.factorize("user","test");
@end verbatim
which translates into the following block: 
@verbatim
factory user.test(s:str):lng;
    b := bat.new(:int,:str);
    bat.insert(b,1,"hello");
barrier always := true;
    z := algebra.select(b,s,s);
    i := aggr.count(z);
    yield i;
    redo always;
exit always;
end test;
@end verbatim
The factorizer included is a prototype implementation
of MAL factorization. The approach taken is to split the program
into two pieces and wrap it as a MAL factory. The optimization
assumes that the database is not changed on tables accessed only
once during the factory lifetime. Such changes should be detected
from the outside and followed by re-starting the factory.

A refined scheme where the user can identify the 'frozen'
parameters is left for the future. As the mapping of a query
to any of the possible available factories to deal with the request.
For the time being we simple reorganize the plan for all
parameters

Caveats. The factorize operation interferes with 
@sc{optimizer.expressionAccumulation()}
because that may overwrite the arguments.
For the time being this is captured in a local routine.
@{
@mal
pattern optimizer.factorize():str
address OPTfactorize;
pattern optimizer.factorize(mod:str, fcn:str):str
address OPTfactorize
comment "Turn function into a factory";

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

/* #define DEBUG_OPT_FACTORIZE     show partial result */
#endif
@c
#include "mal_config.h"
#include "opt_factorize.h"
#include "mal_interpreter.h"	/* for showErrors() */
#include "mal_builder.h"

@+ Factorize Implementation
Factorize of the code is defensive. An intruction group is
added to the repeated part when analysis gets too complicated,
e.g. when a variable is used within a guarded block.
Moving instruction out of the guarded block is a separate
optimization step.

@c
static int
OPTallowed(InstrPtr p)
{
	if (getModuleId(p) && strcmp(getModuleId(p), "batcalc") == 0) {
		if (isUnsafeInstruction(p))
			return 0;
	}
	return 1;
}

static int
OPTfactorizeImplementation(MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
{
	int i, k,  v, noop = 0, se;
	InstrPtr p;
	int fk = 0, sk = 0, blk = 0, blkstart = 0;
	int *varused, returnseen = 0;
	InstrPtr *first, *second;

	(void) pci;
	(void) stk;		/* to fool compilers */

	setLifespan(mb);
	varused = GDKmalloc(mb->vtop * sizeof(int));
	for (i = 0; i < mb->vtop; i++)
		varused[i] = 0;

	/* add parameters to use list */
	p = getInstrPtr(mb, 0);
	for (i = 0; i < p->argc; i++)
		varused[i] = 1;

	first = (InstrPtr *) GDKmalloc(mb->stop * sizeof(InstrPtr));
	second = (InstrPtr *) GDKmalloc(mb->stop * sizeof(InstrPtr));
	for (i = 0; i < mb->stop; i++)
		first[i] = second[i] = 0;

	first[fk++] = getInstrPtr(mb, 0);	/* to become a factory */
	for (i = 1; i < mb->stop - 1; i++) {
		p = getInstrPtr(mb, i);
		se = 0;
		for (k = 0; k < p->argc; k++)
			if (varused[p->argv[k]])
				se++;

		/* detect blocks they are moved to the second part */
		/* a more clever scheme can be designed though */
		if (p->barrier) {
			if (p->barrier == BARRIERsymbol || p->barrier == CATCHsymbol) {
				if (blkstart == 0)
					blkstart = i;
				blk++;
			} else if (p->barrier == EXITsymbol) {
				blk--;
				if (blk == 0)
					blkstart = 0;
			}
		}

		/* beware, none of the target variables may live
		   before the cut point.  */
		for (k = 0; k < p->retc; k++)
			if (getVar(mb, p->argv[k])->beginLifespan < i || !OPTallowed(p))
				se = 0;
		if (p->barrier == RETURNsymbol) {
			se = 1;
			p->barrier = YIELDsymbol;
			returnseen = 1;
		}

		if (se == 0 && blk == 0)
			first[fk++] = p;
		else {
			if (blkstart) {
				/* copy old block stuff */
				for (k = blkstart; k < i; k++)
					second[sk++] = first[k];
				fk = blkstart;
				blkstart = 0;
			}
			second[sk++] = p;
			for (k = 0; k < p->retc; k++)
				varused[p->argv[k]] = 1;
		}
	}
	second[sk++] = getInstrPtr(mb, i);
	/* detect need for factorization, assume so */
	if (noop || sk == 0) {
		GDKfree(varused);
		GDKfree(first);
		GDKfree(second);
		/* remove the FToptimizer request */
		return 1;
	}

	first[0]->token = FACTORYsymbol;

	GDKfree(mb->stmt);
	mb->stmt = (InstrPtr *) GDKmalloc((mb->stop + 4) * sizeof(InstrPtr));

	mb->stop = mb->stop + 4;

	k = 0;
	for (i = 0; i < fk; i++)
		mb->stmt[k++] = first[i];

	/* added control block */
	v = newVariable(mb, GDKstrdup("always"), TYPE_bit);
	p = newInstruction(NULL,BARRIERsymbol);
	pushReturn(mb, p, v);
	pushBit(mb,p,TRUE);
	mb->stmt[k++] = p;

	for (i = 0; i < sk - 1; i++)
		mb->stmt[k++] = second[i];

	/* finalize the factory */
	if (returnseen == 0) {
		p = newInstruction(NULL,YIELDsymbol);
		pushReturn(mb, p, findVariable(mb, getFcnName(mb)));
		mb->stmt[k++] = p;
	}
	p = newInstruction(NULL,REDOsymbol);
	pushReturn(mb, p, v);
	mb->stmt[k++] = p;

	p = newInstruction(NULL,EXITsymbol);
	pushReturn(mb, p, v);
	mb->stmt[k++] = p;

	/* add END statement */
	mb->stmt[k++] = second[i];

	mb->stop = k;

	GDKfree(varused);
	GDKfree(first);
	GDKfree(second);
	return 1;
}

@include optimizerWrapper.mx
@h
@:exportOptimizer(factorize)@
@c
@:wrapOptimizer(factorize,OPT_CHECK_ALL)@
@}