that employs a vectorized query processing model.
Apart from achieving high CPU efficiency, Mon-
etDB/X100 is intended to scale up towards non main-
memory (disk-based) datasets. The second part of this
paper is dedicated to describing the architecture of
MonetDB/X100 and evaluating its performance on the
full TPC-H benchmark of size 100GB.
1.1 Outline
This paper is organized as follows. Section 2 provides
an introduction to modern super-scalar (or hyper-
pipelined) CPUs, covering the issues most relevant for
query evaluation performance. In Section 3, we study
TPC-H Query 1 as a micro-benchmark of CPU effi-
ciency, first for standard relational database systems,
then in MonetDB, and finally we descend into a stan-
dalone hand-coded implementation of this query to get
a baseline of maximum achievable raw performance.
Section 4 describes the architecture of our new X100
query processor for MonetDB, focusing on query exe-
cution, but also sketching topics like data layout, in-
dexing and updates.
In Section 5, we present a performance comparison
of MIL and X100 inside the Monet system on the TPC-
H benchmark. We discuss related work in Section 6,
before concluding in Section 7.
2 How CPUs Work
Figure 1 displays for each year in the past decade the
fastest CPU available in terms of MHz, as well as high-
est performance (one thing does not necessarily equate
the other), as well as the most advanced chip manu-
facturing technology in production that year.
The root cause for CPU MHz improvements is
progress in chip manufacturing process scales, that
typically shrink by a factor 1.4 every 18 months (a.k.a.
Moore’s law [13]). Every smaller manufacturing scale
means twice (the square of 1.4) as many, and twice
smaller transistors, as well as 1.4 times smaller wire
distances and signal latencies. Thus one would expect
CPU MHz to increase with inverted signal latencies,
but Figure 1 shows that clock speed has increased even
further. This is mainly done by pipelining: dividing
the work of a CPU instruction in ever more stages.
Less work per stage means that the CPU frequency
can be increased. While the 1988 Intel 80386 CPU
executed one instruction in one (or more) cycles, the
1993 Pentium already had a 5-stage pipeline, to be in-
creased in the 1999 PentiumIII to 14 while the 2004
Pentium4 has 31 pipeline stages.
Pipelines introduce two dangers: (i) if one instruc-
tion needs the result of a previous instruction, it can-
not be pushed into the pipeline right after it, but must
wait until the first instruction has passed through the
pipeline (or a significant fraction thereof), and (ii) in
case of IF-a-THEN-b-ELSE-c branches, the CPU must
130nm
250nm
500nm
pipelining
hyper−pipelining
Alpha21164A
350nm
Athlon
Pentium4
Alpha21164
Alpha21164B
POWER4
Itanium2
Alpha21064A
Alpha21064
1000
10000
1994 1996 1998 2000 2002
1000
10000
1994 1996 1998 2000 2002
1000
10000
1994 1996 1998 2000 2002
1000
10000
1994 1996 1998 2000 2002
inverted gate distance
CPU Performance (SPECcpu int+fp)
CPU MHz
Figure 1: A Decade of CPU Performance
predict whether a will evaluate to true or false. It
might guess the latter and put c into the pipeline, just
after a. Many stages further, when the evaluation of
a finishes, it may determine that it guessed wrongly
(i.e. mispredicted the branch), and then must flush
the pipeline (discard all instructions in it) and start
over with b. Obviously, the longer the pipeline, the
more instructions are flushed away and the higher the
performance penalty. Translated to database systems,
branches that are data-dependent, such as those found
in a selection operator on data with a selectivity that
is neither very high nor very low, are impossible to
predict and can significantly slow down query execu-
tion [17].
In addition, super-scalar CPUs
2
offer the possibility
to take multiple instructions into execution in parallel
if they are independent. That is, the CPU has not one,
but multiple pipelines. Each cycle, a new instruction
can be pushed into each pipeline, provided again they
are independent of all instructions already in execu-
tion. A super-scalar CPU can get to an IPC (Instruc-
tions Per Cycle) of > 1. Figure 1 shows that this has
allowed real-world CPU performance to increase faster
than CPU frequency.
Modern CPUs are balanced in different ways. The
Intel Itanium2 processor is a VLIW (Very Large In-
struction Word) processor with many parallel pipelines
(it can execute up to 6 instructions per cycle) with
only few (7) stages, and therefore a relatively low clock
speed of 1.5GHz. In contrast, the Pentium4 has its
very long 31-stage pipeline allowing for a 3.6GHz clock
speed, but can only execute 3 instructions per cycle.
Either way, to get to its theoretical maximum through-
put, an Itanium2 needs 7x6 = 42 independent instruc-
tions at any time, while the Pentium4 needs 31x3 = 93.
Such parallelism cannot always be found, and there-
fore many programs use the resources of the Itanium2
much better than the Pentium4, which explains why in
benchmarks the performance of both CPUs is similar,
despite the big clock speed difference.
2
Intel introduced the term hyper-pipelined as a synonym for
“super-scalar”, to market its Pentium4 CPU.
