[Monetdb-developers] difficulty in understanding final query execution plan
Stefan.Manegold at cwi.nl
Mon Mar 22 20:11:36 CET 2010
On Sun, Mar 21, 2010 at 10:29:09PM +0530, anshul gangwar wrote:
> What will be the leaves in final query execution plan tree.
Please bear in mind that MonetDB is a real working and grown system, not a
designed textbook. Moreover, it does work very differently from "classical"
relational text-book DBMSs, after all, it is a bulk-processing
(operator-at-a-time) memory-optimized column-store, not a pipelining
(tuple-at-a-time) disk-optimized row-store.
Hence, there is no simple general answer to your questions. In the first
place, in practice there is no such thing as a "final query execution
plan/tree". In MonetDB, queries are eventually trans lated in to a liner
MAL (MoentDB5/SQL) or MIL (MonetDB4/XQuery) program that replresents the
representation of the given query in MonetDB's binary (read 2-column)
relational algebra on MonetDB's primary data-structure, i.e., BATs (Binary
Association Tables). Please see the MonetDB website at
http://monetdb.cwi.nl/ as well as related publications
(http://monetdb.cwi.nl/Development/Research/Articles/) for background
information about MonetDB. As a general introduction, you might want to
start, e.g., with Peter Boncz's PhD thesis
In a sense, this MAL or MIL program is the "final plan", as all operators and
their execution order are defined.
At runtime, i.e., while interpreting the MAL/MIL program and executiong the
operators, each operator dynamically choses the most suitable algorithm and
implementation for the properties of the given inputs (BATs). Such choises
range from, e.g., has-join s. merge-join, and hash-select vs.
binary-search vs. scan-select to which operand of a join to use as inner
and which as outer, or whether a range select on a sorted BAT can be
executed as a simple slice operation that just returns a view on the
selected tuple as opposed to copying the qualifying tuples into a separate
Most details of the implementation are at most documented by comments in the
code, or just by the code itself. See MonetDB/src/gdk/* for details.
> What does that BATfetchjoin does,
A join between two BATs [any_1,oid] & [oid,any_2] where the head of the
right BAT forms a dense ascending sequence of OIDs (think: tuple IDs) can
effectively and efficiently be executed using positional lookup of the
left's tail values in the right BAT. The matching left head and right tail
A range-selection of values between the given lower and higher boundary;
if both bondaries are identical, it is a point-selection;
if either boundary is NIL (NULL), the other is interpreted as lower/upper
bound of a single-sided (open) range-selection;
if both boundaries are NIL (NULL), all non-NULL values are returned.
BAT_select works on the tail of a BAT and return either only the
heads (think: IDs) of the matching tuples (BUNs) (if argument tail==FALSE) or
both head and tail, i.e., the complete matching BUN (if argument
See also `help("select");` in MIL.
> BATjoin actually does in simple language.
An equi-join of two BATs, i.e, it
returns all BUNs, consisting of a head-value from 'left' and
a tail-value from 'right' for which there are BUNs in 'left'
and 'right' with equal tail- resp. head-value (i.e. the join
columns are projected out).
See also `help("join");` in MIL.
To make any use of these details, you need to be (get) very familiar with
the core internals of MonetDB, basically by studying and understanding the
code in MonetDB/src/gdk/ .
Hope this helps you further.
> The INTERNET now has a personality. YOURS! See your Yahoo! Homepage. http://in.yahoo.com/
> Download Intel® Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> Monetdb-developers mailing list
> Monetdb-developers at lists.sourceforge.net
| Dr. Stefan Manegold | mailto:Stefan.Manegold at cwi.nl |
| CWI, P.O.Box 94079 | http://www.cwi.nl/~manegold/ |
| 1090 GB Amsterdam | Tel.: +31 (20) 592-4212 |
| The Netherlands | Fax : +31 (20) 592-4199 |
More information about the developers-list