Database Reference
In-Depth Information
(uniqueness, sortedness, min/max) that are exploited at runtime under vari-
ous circumstances. We show below an example of translating an SQL query
into expressions in the BAT Algebra to illustrate the advantages of executing
the BAT Algebra expressions. The details of the algebra are not important,
but rather this example is intended to illustrate the operators used that ex-
ecute this query. Note that the algebraic expressions represent an execution
plan.
Example: The SQL Query
SELECT DISTINCT P.firstname,P.lastname, SUM(I.price)
FROM Person P, Item I
WHERE P.id = I.buyer and I.year = 2007
GROUP BY P.Firstname,P.lastname
translates into BAT algebra:
s := reverse(mark(uselect(Item year, 2007)))
b := join(s ,Item buyer)
p := join(b,reverse(Person id))
r := reverse(mark(reverse(p)))
g := group(join(r ,Person firstname), join (r ,Person lastname))
a:=
(join(join(reverse(g), r ), Item price)
[ print ]( join(g,Person firstname), join (g,Person lastname), a)
{
sum
}
A potential disadvantage of the DSM model is the large number of joins needed
to relate columns, also visible in the above plan, which has eight join opera-
tors. However, note that only a single join operation is a real value-based join
(shown in boldface); all other joins are cases where a TID tail-column from
a known min/max range is joined into a dense head-column that spans that
range. The property detection in MonetDB successfully derives all such joins
into a fetch-join algorithm which for each left input fetches a single tail result
from the right input using a positional array lookup. Note that fetch-join is a
linear operation at very low CPU cost (a single load instruction). Therefore,
MonetDB turns out to perform no expensive additional joins relative to N-ary
storage model (NSM) execution engines that store tuple records contiguously
in disk pages.
The BAT Algebra core process arrays directly and thus forgoes locking and
other transaction processing operations. Rather, a separate module with ex-
plicit locking primitives and WAL (write ahead log) functionality is offered.
Thus, it is up to the various front ends to ensure that queries do not con-
flict (referred to as ACID properties), if needed. Note that some front ends
do not perform online updates (which is typical in scientific applications and
data-mining tools) and therefore do not need to use any transaction man-
agement. The advantage in MonetDB is that such applications do not suffer
any overhead from transaction facilities that they do not use. The SQL and
XQuery front ends both offer full ACID properties, showing that a separation
