Breaking the Memory Wall in
MonetDB
by Peter a. boncz, Martin l. Kersten, and stefan Manegold
abstract
In the past decades, advances in speed of commodity CPUs
have far outpaced advances in RAM latency. Main-memory
access has therefore become a performance bottleneck for
many computer applications; a phenomenon that is widely
known as the “memory wall.” In this paper, we report how
research around the MonetDB database system has led to a
redesign of database architecture in order to take advantage
of modern hardware, and in particular to avoid hitting the
memory wall. This encompasses (i) a redesign of the query
execution model to better exploit pipelined CPU architectures and CPU instruction caches; (ii) the use of columnar
rather than row-wise data storage to better exploit CPU data
caches; (iii) the design of new cache-conscious query processing algorithms; and (iv) the design and automatic calibration of memory cost models to choose and tune these
cache-conscious algorithms in the query optimizer.
1. intRoDuction
Database systems have become pervasive components in
the information technology landscape, and this importance
continues to drive an active database research community,
both academic and industrial. Our focus here is on so-called
architecture-conscious database research that studies the
data management challenges and opportunities offered by
advances in computer architecture. This area of research
started receiving impetus 10 years ago1, 2 when it became
clear that database technology was strongly affected by the
emergence of the “memory wall”—the growing imbalance
between CPU clock-speed and RAM latency.
Database technology, as still employed in the majority
of today’s commercial systems, was designed for hardware
of the 1970–1980s and application characteristics that
existed at the time. This translates into the assumption of
disk I/O being the dominating performance factor, and an
architecture tuned to supporting so-called online transaction processing (OLTP) workloads. That is, sustaining simple lookup/update queries at high throughput. In contrast,
modern hardware has since become orders of magnitude
faster but also orders of magnitude more complex, and critical database applications now include—besides OLTP—the
online analysis of huge data volumes stored in data warehouses, driven by tools that explore hidden trends in the
data, such as online analytical processing (OLAP) tools that
visualize databases as multidimensional cubes, and data
mining tools that automatically construct knowledge models over these huge data-sets. This changed situation has
recently made the research community realize that database
architecture as it used to be is up for a full rewrite,
21 and to
make future systems self-tuning to data distributions and
workloads as they appear.
4
In this paper, we summarize the work in the MonetDBa
project that has focused on redefining database architecture
by optimizing its major components (data storage, query
processing algebra, query execution model, query processing algorithms, and query optimizer) toward better use of
modern hardware in database applications that analyze
large data volumes. One of the primary goals in this work
has been breaking the memory wall.
Our focus here is the following innovations:
Vertical storage: Whereas traditionally, relational database systems store data in a row-wise fashion (which
favors single record lookups), MonetDB uses columnar
storage which favors analysis queries by better using CPU
cache lines.
Bulk query algebra: Much like the CISC versus RISC idea
applied to CPU design, the MonetDB algebra is
deliberately simplified with respect to the traditional
relational set algebra to allow for much faster implementation on modern hardware.
Cache-conscious algorithms: The crucial aspect in overcoming the memory wall is good use of CPU caches, for
which careful tuning of memory access patterns is
needed. This called for a new breed of query processing
algorithms, of which we illustrate radix-partitioned hash-join in some detail.
Memory access cost modeling: For query optimization to
work in a cache-conscious environment, we developed a
methodology for creating cost models that takes the
cost of memory access into account. In order to work on
diverse computer architectures, these models are
parameterized at runtime using automatic calibration
techniques.
2. PReLiminaRies
Computer architecture evolution in the past decades has
had many facets. A general trend is that “latency lags bandwidth,”
16 which holds for both magnetic disk and RAM. This
a MonetDB is distributed using a nonrestrictive open-source license, see
http://monetdb.cwi.nl
A previous version of this paper entitled “Database Architecture Optimized for the New Bottleneck: Memory Access”
appeared in the Proceedings of the International Conference
on Very Large Data Bases (September 1999), pp. 54–65.