General overview. MonetDB belongs to the class of database management systems designed primarilly for datawarehouse environments. They are characterised by large repositories, which are mostly queried for business intelligence decisions. They also appear frequently in the area of science, where observations are collected into a warehouse for subsequent scientific analysis. The design is focussed on bulk processing where ever possible. Aimed at maximal efficient use of the hardware for large scale processing. This design objective is reflected at all levels of the architecture and the functionality offered to the user. Although MonetDB/SQL provides a full-fledged SQL interface, it has not been tuned towards high-volume transaction processing with its accompanying multi-level ACID properties.
Storage model. The storage model deployed in MonetDB is a significant deviation of traditional database systems. It represents relational tables using vertical fragmentation, by storing each column in a separate {(surrogate,value)} table, called a BAT (Binary Association Table). The left column, also denoted as head, contains object-identifiers (OID), and the right column, the tail, contains attribute values. The head is always a dense and sorted list. MonetDB relies on a low-level relational algebra called the BAT algebra, which takes BATs and scalar values as input. The complete result is always stored in (intermediate) BATs, and the result of an SQL query is a collection of BATs. BAT storage takes the form of two simple memory arrays, one for the head and one for the tail column. For variable-width types we split the tail column into two parts. One part with the concatenated data values and a part with offsets into the former.
Internally, MonetDB stores columns as memory mapped files. They are optimized for the typical situation that the head column is a densely ascending numerical identifier (0,1,2,..); in which case the head array storage can be kept implicit. OID lookup becomes as fast array indexed read into the tail column. In effect, this use of arrays in virtual memory exploits the fast in-hardware address to disk-block mapping implemented by the MMU (memory management unit) in a CPU to provide an O(1) positional database lookup mechanism.
Execution model. The MonetDB kernel is an abstract machine, programmed in the MonetDB Assemblee Language (MAL). Each relational algebra operator corresponds to a MAL instruction. Each BAT algebra operator maps to a simple MAL instruction, which has zero degrees of freedom: it does not take complex expressions as parameter. Rather, complex expressions are broken down into a sequence of BAT algebra operators that each perform a simple operation on an entire column of values (``bulk processing''). This allows the implementation of the BAT algebra to forsake an expression interpreting engine; rather all BAT algebra operations in the implementation map onto simple array operations. For instance, the BAT algebra expression
R:bat[:oid,:oid]:=select(B:bat[:oid,:int], V:int);
can be implemented at the C code level like:
for (i = j = 0; i < n; i++)
if (B.tail[i] == V)
R.tail[j++] = i;
The BAT algebra operators have the advantage that tight for-loops create high data access and instruction locality. Such simple loops are amenable to compiler optimization (loop pipelining, vectorization, blocking, strength reduction), and CPU out-of-order speculative execution.
Software stack MonetDB's query processing scheme is centered around three software layers. The top is formed by the query language parser and a heuristic, language-and data model-specific optimizer to reduce the amount of data produced by intermediates and to exploit catalogue knowledge, such as join-indices. The output is a logical plan expressed in MAL.
The second tier consists of a collection of optimizer modules, which are assembled into optimization pipelines. Each optimizer takes a MAL plan and tranforms it into a more efficient ones, optionally sprinkled with resource management directives. The modules provide facilities ranging from symbolic processing up to just-in-time data distribution and execution. The approach breaks with the hitherto omnipresent cost-based optimizers by recognition that not all decisions can be cast together in a single cost formula. Operating on the common binary-relational back-end algebra, these optimizer modules are shared by all front-end data models and query languages.
The third tier, the MAL interpreter, contains the library of highly optimized implementation of the binary relational algebra operators. They maintain properties over the object accessed to gear the selection of subsequent algorithms. For example, the Select operator can benefit both from sorted-ness of the BAT or it may call for a sample to derive the expected sizes. The interface is described in the MAL module sections.
SQL front-end. The BAT storage layer combined with the MAL algebra provides a flexible architecture to accomodate a wide variety of query languages. The relational front-end decomposes tables by column, in BATs with a dense (non-stored) OID head, and a tail column with values. For each relational table, a BAT with deleted positions is kept. Delta BATs are designed to delay updates to the main columns, and allow a relatively cheap snapshot isolation mechanism (only the delta BATs are copied). MonetDB/SQL also keeps additional BATs for join indices; and value indices are created on-the-fly.