opt_heuristics.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_heuristics
@- Heuristic rewrites rules
One of the oldest optimizer tricks in relational query processing is
to apply heuristic rules to reduce the processing cost. For example,
a selection predicate is pushed through another operator to reduce
the number of tuples to consider.
Heuristic rewrites are relatively easy to apply in a context where 
the expression is still close to a relational algebra tree.
Therefore, many of the standard rewrite rules are already applied by the SQL
front-end as part of its strategic optimization decisions.

Finding rewrite opportunities within a linear MAL program may
be more difficult. For, the pattern should respect the flow
of control that may already be introduced.
The last resort for the optimizer builder is to write a
C-function to look for a pattern of interest and transform it.
The code base contains an example how to built such 
user specific optimizer routines.
It translates the pattern:
@example
y:= reverse(R);
z:= select(y,l,h);          
@end example
into the statement:
@example
z:= selectHead(x,R,l,h) 
@end example

@{
@-
During a final pass through the program, we can convert all combinators 
back into their elementary steps.
@= fndOperator
	(( getModuleId(@1)==0 || (@2 && idcmp(getModuleId(@1),@2)==0) ) &&
		 (getFunctionId(@1)==0 || (@3 && idcmp(getFunctionId(@1),@3)==0) ))
@-
A more complete implementation should als push the selection through
multiple operators. In particular, a reverse operator may obscure
the opportunity to perform the select push through. 
@h
#ifndef _OPT_HEURISTICS_
#define _OPT_HEURISTICS_

#include "mal.h"
#include "mal_function.h"
#include "mal_scenario.h"
#include "mal_builder.h"

#include "opt_prelude.h"
#include "mal_interpreter.h"
#include "opt_support.h"

#endif
@c
#include "mal_config.h"
#include "opt_heuristics.h"
int
SPcombi000(MalBlkPtr mb, int pc1, int pc2)
{
	InstrPtr p, q;

	p = getInstrPtr(mb, pc1);
	q = getInstrPtr(mb, pc2);
	if (@:fndOperator(p, "bat", "reverse")@) {
		if (@:fndOperator(q, "algebra", "select")@) {
			if (p->argv[0] == q->argv[1]) {
				setModuleId(p, putName("algebra", 7));
				setFunctionId(p, putName("reverse_select", 14));
				p = pushArgument(mb, p, q->argv[1]);
				p = pushArgument(mb, p, q->argv[2]);
				p = pushArgument(mb, p, q->argv[3]);
				removeInstruction(mb, q);
				chkFlow(mb);
				chkDeclarations(mb, TRUE);
				return 1;
			}
		}
	}
	return 0;
}

int
SPsqueezer000(MalBlkPtr mb, int pc1, int pc2)
{
	InstrPtr p, q;

	p = getInstrPtr(mb, pc1);
	q = getInstrPtr(mb, pc2);
	(void) p;
	(void) q;		/* do something useful later on */
	return 0;
}

static int
OPTheuristicsImplementation(MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
{
	int i, k, combis = 0, squeeze = 0;
	InstrPtr p;

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

	/* process the combinators */
	for (i = 0; i < mb->stop - 1; i++) {
		p = getInstrPtr(mb, i);
		for (k = i + 1; k < mb->stop && isAlife(mb, p->argv[0], k); k++)
			if (SPcombi000(mb, i, k)) {
#ifdef DEBUG_OPT_OPTIMIZER
				stream_printf(GDKout, "Combinator found\n");
				printInstruction(GDKout, mb, getInstrPtr(mb, i), LIST_MAL_ALL);
#endif
				combis++;
				k--;	/* an instruction has been removed */
				setLifespan(mb);	/* expensive but needed */
			}
	}
	/* process the squeezers */
	for (i = 0; i < mb->stop - 1; i++) {
		p = getInstrPtr(mb, i);
		for (k = i + 1; k < mb->stop && isAlife(mb, p->argv[0], k); k++)
			if (SPsqueezer000(mb, i, k)) {
#ifdef DEBUG_OPT_OPTIMIZER
				stream_printf(GDKout, "Squeezer found\n");
				printInstruction(GDKout, mb, getInstrPtr(mb, i), LIST_MAL_ALL);
#endif
				squeeze++;
				k--;	/* an instruction has been removed */
			}
	}
	return squeeze;
}

@-
Pushing a selection geared at the left operand through the join operator
is more complex, because you can only recognize those instances when later
on the semijoin is recognized. The pattern we are looking for
@T
\begin{verbatim}
AD := join (AB, CD);
ZZ := semijoin (AB, AD);
Za := select(ZZ, l,h);
\end{verbatim}
@-
Note that this operation depends on HRoptimizer, because it already
pushes down the selection through the semijoin.
Should be done differently

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

@}