mal_scheduler.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 mal_scheduler
@a M. Kersten
@* Scheduler framework
A key design decision for this MonetDB  version is to create a clean
processing pipeline: compile-, optimize-, schedule- and execute.
The MAL scheduler controls the actual execution of a program through a number of
techniques described here. It accepts a program with the intend to execute it
as soon as possible with the best possible behavior.

Note that the scheduler should only work on temporary plans. Keeping an 
execution schedule in the symbol table calls for a sound administration
to invalidate it. This assumed that such decisions are taken by a cooperative
front-end compiler, e.g. SQL. For the remainder we assume a volatile MAL 
program is available.

Recall that the MAL optimizer already had an opportunity to massage the program
into something that has a better execution behavior. These optimizations
necessarily rely on static (or stale) information, such as histograms, indices,
and rewrite heuristics. It is the task of the scheduler to achieve this 
performance objective (or better), while at the same time guaranteeing 
great throughput.

Unlike the optimizer, the scheduler has access to the calling parameters,
runtime stack for the about-to-be-executed plan, and system resources,
such as globally cached results. Moreover, a scheduler can be called at any time
during a MAL interpreter loop to re-consider the actions to be taken.
This gives many more opportunities to improve performance.
This does not hold for e.g. compiled code, nor X100 back ends)

Much like the optimizer framework, there are many aspects you can deal with
at scheduling time. The easiest is to simply do nothing and rely on
the MAL interpreter, which is the default action when no scheduler directive 
is found. 

In most cases, however, you would like a scheduler to take a specific action.
It typically rewrites, extends, or reshuffles the query plan as it is being
prepared for execution or even during its execution.
In this process it can use the optimizer infrastructure, provided the 
changes are isolated to a private instance. This should be prepared
before the interpreter is started and requires care during execution to
ensure proper behaviour. The upfront cost attached is to make a complete
copy of the program code and to assure that the definitions in the
symbol table remain intact.

To make its life easy, it is assumed that all scheduler decisions to be
taken before the back-end is called reside in the module 'scheduler'.
Any action to be taken during execution is kept in module 'rescheduler'.

What scheduler operators are provided?

The generic scheduler presented here shows a series of techniques that 
might be useful in construction of your own scheduler.

@emph{Run isolation (RUNisolated)}
Goal: to isolate changes to the query plan from others
Rationale: A scheduler may change the order, and actual function calls.
These changes should be confined to a single execution. The next time around
there may be a different situation to take care off. This is achieved by
replacing the current program with a private copy.
Note that this process may involve a deep analysis to identify the pieces
needed for isolation, e.g. for SQL we would extract a copy from the SQL query
cache using code expension.
Just massaging the call to the cached plan is not effective.
Impact: cost of program copying may become an issue.

@emph{Run trace (RUNtracing)}
Goal: to collect performance data for either direct monitoring or post-analysis
Rationale:The performance profiling option in the interpreter is overly expensive,
because it is also called for simple statements. One way out of this, is to
inject specific performance metric calls at places where it counts.
For example, you could wrap calls calls to a specific module or operation.

@emph{Run notification (RUNnotification)}
Goal: to inject notification calls to awaiting servers
Rationale: Operations on the database may require side effects to take place, 
such as activating a trigger (implemented as a factory)

@emph{Update notification (RUNupdateNotification)}
Goal: Updates to the Boxes may have to  forwarded to stand-by replicas.
Rationale: actually a refinement of the notification scheme, but geared at
maintaining a replicated system.

@emph{Materialized Execution Scheduler (MEscheduler)}
Goal:to transfor the program into fragment-based processing
Rationale: to reduce the impact of resource limitations, such
as main memory, in the face of materialized intermediate.

@emph{Run parallelization (RUNparallel)}
Goal: to improve throughput/response time by exploiting parallel hardware

@emph{Run stepping RUNstepping}
goal: to return to the scheduler at specific points in the program
execution. For example to re-consider the scheduling actions.
Note that this requires a scheme to 'backtrack' in the scenario

@emph{Cache management (RUNbatCaching}
Goal: to capture expensive BAT operations and to keep them around for
re-use. 

@emph{JIT compilation}
Use the Mcc just in time compilation feature to derive and link
a small C-program.

What the scheduler could do more?
A separete thread of control can be used to administer the
information needed by concurrent scheduler calls.

One of the areas to be decided upon is whether the scheduler is
also the place to manage the stack spaces. It certainly could
reconcile parallel executions by inspection of the stack.

Upon starting the scheduler decisions, we should (regularly)
refresh our notion on the availability of resources.
This is kept around in a global structure and is the basis for
micro scheduling decisions.
@{
@h
#ifndef _MAL_SCHEDULER
#define _MAL_SCHEDULER
#include "mal.h"
#include "mal_instruction.h"
#include "mal_client.h"

#define DEBUG_MAL_SCHEDULER

#ifdef HAVE_SYS_TIMES_H
# include <sys/times.h>
#endif

#if OSVER < 560 && defined(SOLARIS)
#include "/usr/ucbinclude/sys/rusage.h"
#include "/usr/ucbinclude/sys/resource.h"
#endif

#ifdef HAVE_SYS_RESOURCE_H
#include <sys/resource.h>
#endif

struct {
	/*mallinfo memory; */
	/* rusage memused; */
	int cpuload;		/* hard to get */
} runtime;

#ifdef WIN32
#ifndef LIBMAL_SCHEDULER
#define sched_export extern __declspec(dllimport)
#else
#define sched_export extern __declspec(dllexport)
#endif
#else
#define sched_export extern
#endif

sched_export str MALscheduler(Client c);
sched_export str debugScheduler(MalBlkPtr mb, MalStkPtr stk, InstrPtr pci);

#endif /* MAL_SCEDULER */

@+ Scheduler implementation
@= schedulerCleanup
	if(@1) {
		removeInstruction(mb,@1);
		chkFlow(mb);
	}
@c
#include "mal_config.h"
#include "mal_scheduler.h"
#include "mal_interpreter.h"	/* for showErrors() */
#include "opt_prelude.h"
#include "opt_macro.h"

str
debugScheduler(MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
{
	Client cntxt = MCgetClient();

	(void) stk;

	cntxt->debugScheduler = cntxt->debugScheduler ? FALSE : TRUE;
	@:schedulerCleanup(pci)@
	return MAL_SUCCEED;
}

@-
The implementation approach of the scheduler aligns with that of the
optimizer. We look for specific scheduler module calls and act accordingly.
The result should be a MAL block that can be executed by the corresponding
engine. 
@c
str
schedulerMALBlock(MalBlkPtr mb)
{
	InstrPtr p;
	int callMALinterpreter = 1, pc, cnt = 0;
	str msg = NULL;
	int loops = 0;

#ifdef DEBUG_MAL_SCHEDULER
	int oldstop = mb->stop;
#endif
	/* update the runtime status */

	do {
		cnt = 0;
		for (pc = 0; pc < mb->stop; pc++) {
			p = getInstrPtr(mb, pc);
			if (getModuleId(p) && idcmp(getModuleId(p), "scheduler") == 0) {
				cnt++;
				callMALinterpreter++;
				if (p->fcn)
					/* all schedulers should behave like patterns */
					/* However, we don;t have a stack now */
					msg = (str) (*p->fcn) (mb, 0, p);
				if (msg) {
					GDKerror(msg);
					showErrors();
					return msg;
				}
				pc--;	/*scheduler statement has been removed */
			}
		}
	} while (cnt && loops++ < 64);
	if (callMALinterpreter)
		return MAL_SUCCEED;
#ifdef DEBUG_MAL_SCHEDULER
	if (MCgetClient()->debugScheduler && oldstop != mb->stop) {
		stream_printf(GDKout, "Scheduler effect %d -> %d instructions\n", oldstop, mb->stop);
	}
#endif
	if (cnt >= 64)
		throw(MAL, "scheduler.MALscheduler", "too many optimization cycles\n");
	return MAL_SUCCEED;
}

str
MALscheduler(Client c)
{
	return schedulerMALBlock(c->curprg->def);
}

@}
@+ Run isolation
Run isolation involves making available a private copy for further massaging.
The easiest is to duplicate the MAL program attached to the Client record.
After scheduling and execution, it can be simply thrown away, bringing the
original request into view again from the backup associated with the client
record. 
The minor problem is that the program could call itself recursively.
This niche problem is ignored for now.

The first example create a private copy, leaving out the scheduler call.
@example
function main();
	print("start running\n");
	scheduler.isolate();
	print("done\n");
	showFunction();
@end example
@{
@c
str
RUNisolate(MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
{
	Client cntxt = MCgetClient();

	(void) stk;
	if (cntxt->backup)
		throw(MAL, "scheduler.isolation", "no space for backup");
	cntxt->backup = cntxt->curprg;
	cntxt->curprg->def = copyMalBlk(mb);
	removeInstruction(cntxt->curprg->def, p);
	return MAL_SUCCEED;
}

@}
@-
The second example is derived from the SQL environment, which
produces two MAL functions: one (already) stored in the query cache
and a program to be executed in the client record.
The latter lives only for the duration of the call and need
not be safeguarded. Thus, we immediately call the scheduler
to expand the code from the query cache, propagating the
actual parameters.
The SQL specific scheduler is called to bind the table 
columns and to make statistics known as properties.
This creates a situation where a cost-based optimizer could
step in and re-arrange the plan, which is ignored for now.
@example
function sql_cache.qry01(int A1, bit A2);
	t1:= sql.bind("schema","tables",0,0);
	...
end qry01;

function main();
	scheduler.inline("sql_cache","qry01");
	scheduler.sqlbind();
	sql_cache.qry01(12,false);
@end example

These scheduler interventions are called for by the SQL compiler.
It may have flagged the cached version as a high potential for
dynamic optimization, something that is not known at the MAL level.
[The current optimizer also generates a factory, that should be
done here and upon explicit request]
@c
str
RUNinline(MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
{
	Symbol qc;
	str modnme = getVarConstant(mb, getArg(p, 1)).val.sval;
	str fcnnme = getVarConstant(mb, getArg(p, 2)).val.sval;

	(void) stk;
	(void) p;
	qc = findMALSymbol(modnme, fcnnme);

	if (qc)
		MACROprocessor(mb, qc);

	return MAL_SUCCEED;
}

@-
The SQL scheduler is presented merely as an example. The real one
is located in  the SQL libraries for it needs specific information.
@c
str
RUNsqlbind(MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
{
	int i;
	str msg = MAL_SUCCEED;
	Client cntxt = MCgetClient();
	Symbol sqlbind = findMALSymbol("sql", "bind");
	MALfcn f = getSignature(sqlbind)->fcn;

	for (i = 0; i < mb->stop; i++) {
		p = getInstrPtr(mb, i);
		if (p->fcn == f) {
			if ((msg = reenterMAL(cntxt, mb, i, i + 1, stk, 0, 0)))
				break;
			/* fetch the BAT properties and turn off this instruction */
			p->token = NOOPsymbol;
		}
	}
#ifdef DEBUG_MAL_SCHEDULER
	stream_printf(GDKout, "scheduler.sqlbind results\n");
	printFunction(GDKout, mb, LIST_MAL_ALL);
#endif
	return msg;
}

@}