![](https://csdnimg.cn/release/download_crawler_static/33467925/bg1.jpg)
Vectorization vs. Compilation in Query Execution
Juliusz Sompolski
1
VectorWise B.V.
julek@vectorwise.com
Marcin Zukowski
VectorWise B.V.
marcin@vectorwise.com
Peter Boncz
2
Vrije Universiteit Amsterdam
p.a.boncz@vu.nl
ABSTRACT
Compiling database queries into executable (sub-) programs
provides substantial benefits comparing to traditional inter-
preted execution. Many of these benefits, such as reduced
interpretation overhead, better instruction code locality, and
providing opportunities to use SIMD instructions, have pre-
viously been provided by redesigning query processors to
use a vectorized execution model. In this paper, we try to
shed light on the question of how state-of-the-art compila-
tion strategies relate to vectorized execution for analytical
database workloads on modern CPUs. For this purpose, we
carefully investigate the behavior of vectorized and compiled
strategies inside the Ingres VectorWise database system in
three use cases: Project, Select and Hash Join. One of the
findings is that compilation should always be combined with
block-wise query execution. Another contribution is iden-
tifying three cases where “loop-compilation” strategies are
inferior to vectorized execution. As such, a careful merging
of these two strategies is proposed for optimal performance:
either by incorporating vectorized execution principles into
compiled query plans or using query compilation to create
building blocks for vectorized processing.
1. INTRODUCTION
Database systems provide many useful abstractions such
as data independence, ACID properties, and the possibil-
ity to pose declarative complex ad-hoc queries over large
amounts of data. This flexibility implies that a database
server has no advance knowledge of the queries until run-
time, which has traditionally led most systems to implement
their query evaluators using an interpretation engine. Such
an engine evaluates plans consisting of algebraic operators,
such as Scan, Join, Project, Aggregation and Select. The op-
erators internally include expressions, which can be boolean
1
This work is part of a MSc thesis being written at Vrije
Universiteit Amsterdam.
2
The author also remains affiliated with CWI Amsterdam.
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
Proceedings of the Seventh International Workshop on Data Management
on New Hardware (DaMoN 2011), June 13, 2011, Athens, Greece.
Copyright 2011 ACM 978-1-4503-0658-4 ...$10.00.
conditions used in Joins and Select, calculations used to in-
troduce new columns in Project, and functions like MIN,
MAX and SUM used in Aggregation. Most query inter-
preters follow the so-called iterator-model (as described in
Volcano [5]), in which each operator implements an API that
consists of open(), next() and close() methods. Each next()
call produces one new tuple, and query evaluation follows a
“pull” model in which next() is called recursively to traverse
the operator tree from the root downwards, with the result
tuples being pulled upwards.
It has been observed that the tuple-at-a-time model leads
to interpretation overhead: the situation that much more
time is spent in evaluating the query plan than in actually
calculating the query result. Additionally, this tuple-at-a-
time interpretation model particularly affects high perfor-
mance features introduced in modern CPUs [13]. For in-
stance, the fact that units of actual work are hidden in the
stream of interpreting code and function calls, prevents com-
pilers and modern CPUs from getting the benefits of deep
CPU pipelining and SIMD instructions, because for these
the work instructions should be adjacent in the instruction
stream and independent of each other.
Related Work: Vectorized execution. MonetDB [2]
reduced interpretation overhead by using bulk processing,
where each operator would fully pro cess its input, and only
then invoking the next execution stage. This idea has been
further improved in the X100 project [1], later evolving into
VectorWise, with vectorized execution. It is a form of block-
oriented query processing [8], where the next() method rather
than a single tuple produces a block (typically 100-10000)
of tuples. In the vectorized model, data is represented as
small single-dimensional arrays (vectors), easily accessible
for CPUs. The effect is (i) that the percentage of instruc-
tions spent in interpretation logic is reduced by a factor
equal to the vector-size, and (ii) that the functions that per-
form work now typically process an array of values in a tight
loop. Such tight loops can be optimized well by compilers,
e.g. unrolled when beneficial, and enable compilers to gener-
ate SIMD instructions automatically. Modern CPUs also do
well on such loops, as function calls are eliminated, branches
get more predictable, and out-of-order execution in CPUs
often takes multiple loop iterations into execution concur-
rently, exploiting the deeply pipelined resources of modern
CPUs. It was shown that vectorized execution can improve
data-intensive (OLAP) queries by a factor 50.
Related Work: Loop-compilation. An alternative strat-
egy for eliminating the ill effects of interpretation is using
Just-In-Time (JIT) query compilation. On receiving a query