opt_partitionedquery.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_partitionedQuery
@a M. Kersten
@- Partitioned Tables
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.

In the previous section, we already introduced the concept of
a MAT, as the named union of a number of BATs to form a single
virtual BAT.
It can be used as a basis for incremental processing as well.
For this to work, we assume that the MAT components each satisfy
the (memory) resource contraints. 

The operation @sc{optimizer.partitionedQuery} takes these definitions
and encapsulate them in iterator blocks, thereby minimizing the
MAL program 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 optimizer
activities.

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

A snippet of the partitioning optimizer is shown below. It assumes
that the MAT @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]{mat});
	io.print(b);
end qry;
optimizer.partitionedQuery("user","qry");
@end verbatim
The query is transformed into the following version.
@verbatim
function user.qry(a:bat[:oid,:any_1]{mat}):void;
barrier (_5,_6):= mat.newIterator(a);
	io.print(_6);
	redo (_5,_6):= mat.hasMoreElements(a);
exit (_5,_6);
end qry;
@end verbatim
@{
@mal
pattern optimizer.partitionedQuery():str
address OPTpartitionedQuery;
pattern optimizer.partitionedQuery(mod:str, fcn:str):str
address OPTpartitionedQuery
comment "Experiment with partitioned databases";
@h
#ifndef _OPT_PARTITIONED_
#define _OPT_PARTITIONED_
#include "opt_prelude.h"
#include "opt_support.h"

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

extern int OPTvalidFlowNetwork(MalBlkPtr mb, int *first, int *last, int varid);
@-
The first implementation takes a query block and replaces the first
bat variable with its partitioned equivalent.
The external references should be adjusted to permit working
your way through the complete graph incrementally.
They denote an inclusive range.
A copy of the program block is made by default. This could be
optimized away later.
@c
static str
OPTreplacement(MalBlkPtr mb, int *first, int *last, int varid)
{
	InstrPtr *old, p;
	int i, limit, actions = 0;
	int idx = -1, bid = -1;
	int pcf, pcl;
	lng clk= GDKusec();

	setLifespan(mb);
	old = mb->stmt;

	limit = mb->stop;
	newMalBlkStmt(mb, limit + 10);
#ifdef DEBUG_OPT_PARTITIONED
	stream_printf(GDKout, "variable replacement '%s'", getVarName(mb, varid));
	stream_printf(GDKout, " instructions %d-%d ", *first, *last);
	stream_printf(GDKout, " lifespan %d-%d\n", mb->var[varid]->beginLifespan, mb->var[varid]->endLifespan);
#endif
	/* copy prelude into place */
	for (i = 0; i < *first; i++)
		pushInstruction(mb, old[i]);

	actions++;
	/* barrier (idx,bid):= partitions.newIterator(var); */
	p = newInstruction(mb,ASSIGNsymbol);
	setModuleId(p, putName("partitions", 10));
	setFunctionId(p, putName("newIterator", 11));
	p->barrier = BARRIERsymbol;
	idx = newTmpVariable(mb, TYPE_int);
	pushReturn(mb, p, idx);
	bid = newTmpVariable(mb, getVarType(mb, varid));
	pushReturn(mb, p, bid);
	pushArgument(mb, p, varid);
	pushInstruction(mb, p);

	pcf = mb->stop;
	for (i = *first; i <= *last; i++)
		pushInstruction(mb, old[i]);
	pcl = mb->stop;
@-
Before we finalize, we should also check all operations for being applicable 
to partitions as well. Where necessary they should be replaced by an
accumulated version.
@c
	/* finalize the loop */
	/* redo (idx,bid):= partitions.hasMoreElements(var); */
	p = newInstruction(mb,REDOsymbol);
	setModuleId(p, putName("partitions", 10));
	setFunctionId(p, putName("hasMoreElements", 15));
	pushReturn(mb, p, idx);
	pushReturn(mb, p, bid);
	pushArgument(mb, p, varid);
	pushInstruction(mb, p);
	/* exit (idx,bid) */
	p = newInstruction(mb,EXITsymbol);
	pushReturn(mb, p, idx);
	pushReturn(mb, p, bid);
	pushInstruction(mb, p);

	*first = mb->stop;
	/* copy the rest of the program back into place */
	for (; i < limit; i++)
		pushInstruction(mb, old[i]);
	GDKfree(old);
	*last = mb->stop - 1;

	/* now replace variable with the alias bid */
	if (bid != -1)
		replaceAlias(mb, pcf, pcl, varid, bid);
	/* and have to check the baked program */
	optimizerCheck(mb,"partitionedQuery",1,GDKusec()-clk,OPT_CHECK_ALL);
	return MAL_SUCCEED;
}
@-
Not all BATs call for iterator expansion. Unfortunately
we can not check this always at compile time, because
we need the actual BAT identifier.  Therefor the user should
supply the variable instead.
We
@c
static str
OPTneedsExpansion(MalBlkPtr mb, int varid)
{
	int tpe;
	int first, last;
	str msg = 0;

	tpe = getVarType(mb, varid);
	if (isaBatType(tpe) && getHeadType(tpe) == TYPE_oid) {
		first = 1;
		last = mb->stop - 2;
		printf("start first=%d last=%d \n", first, last);
		for (; first < mb->stop && last < mb->stop;) {
			if (OPTvalidFlowNetwork(mb, &first, &last, varid)) {
				printf("replace first=%d last=%d \n", first, last);
				msg = OPTreplacement(mb, &first, &last, varid);
				if (msg)
					return msg;
			} else {
				first = last;
				last = mb->stop - 1;
			}
			printf("first=%d last=%d \n", first, last);
		}
	}
	return MAL_SUCCEED;
}

@-
Calling the optimizer from the MAL context is currently
focussed on replacing the BAT arguments only.
@c
static int
OPTpartitionedQueryImplementation(MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
{
	int i;
	InstrPtr p;

	(void) stk;
	(void) pci;

	p = getInstrPtr(mb, 0);
	for (i = p->retc; i < p->argc; i++) {
		OPTneedsExpansion(mb, p->argv[i]);
	}
	return 0; /* optimizer administration alread handled */
}

@}
@-
The translation of a MAL block into a multi-iterator only works if
the network flow is simple, i.e there exists a 'single' sink, 
or all the information is compressed
into variables that are passed back to the caller as a single value,
or is sent non-interupted to the output channels.
The bottom-line is to avoid expansion.
An assignment to the target is not allowed [to be checked separately]
@{
The validFlowNetwork searches the next basic block to
be considered as safe to expand. It first skips to the
next instruction that uses the variable mentioned.
@c
int
OPTvalidFlowNetwork(MalBlkPtr mb, int *first, int *last, int varid)
{
	int i, k = 0, iocount = 0;
	InstrPtr p;

	for (i = *first; i <= *last; i++) {
		p = getInstrPtr(mb, i);
		for (k = 0; k < p->retc; k++)
			if (getArg(p, k) == varid) {
				*first = i + 1;
				return 0;
			}
		for (k = p->retc; k < p->argc; k++)
			if (getArg(p, k) == varid)
				break;
		if (k < p->argc)
			break;
		if (i == *last) {
			*last = mb->stop;
			return 0;
		}
	}
	*first = i;
	for (; i <= *last; i++) {
		p = getInstrPtr(mb, i);
		if (getFunctionId(p) && strncmp(getFunctionId(p), "print", 5) == 0)
			iocount++;
		else if (p->barrier)
			iocount++;
		else if (p->token == ENDsymbol)
			iocount++;
		if (iocount > 1) {
			*last = i - 1;
			return TRUE;
		}
	}
	return iocount > 0;
}

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