Storage model

Storage model mk Wed, 02/26/2014 - 13:03

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 {(OID,value)} table,  also called a BAT (Binary Association Table). 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.

Each column, or BAT, is implemented as an ordinary C-array where the OID maps to the index in the array possibly extended with a so-called sequence-base offset. The persistent version of a BAT is a memory mapped file. OID lookup becomes a 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.

To ensure fast access wherever possible, all (relational) operators exploit a small set of properties maintained under updates and intermediates creation.

seq       - the sequence base, a mapping from array index 0 into a OID value
key       - the values in the column are unique
nil       - there is at least one NIL value
nonil     - it is unknown if there NIL values
dense     - the numeric values in the column form a dense sequence
sorted    - the column contains a sorted list for ordered domains
revsorted - the column contains a reversed sorted list