[Monetdb-developers] difficulty in understanding final query execution plan

Stefan Manegold 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:
> Hello
> 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
result BAT.

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
are returned.

> BAT_select

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.
> http://p.sf.net/sfu/intel-sw-dev

> _______________________________________________
> Monetdb-developers mailing list
> Monetdb-developers at lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/monetdb-developers

| 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 mailing list