Rethinking SIMD Vectorization for In-Memory Databases
Orestis Polychroniou
∗
Columbia University
orestis@cs.columbia.edu
Arun Raghavan
Oracle Labs
arun.raghavan@oracle.com
Kenneth A. Ross
†
Columbia University
kar@cs.columbia.edu
ABSTRACT
Analytical databases are continuously adapting to the un-
derlying hardware in order to saturate all sources of par-
allelism. At the same time, hardware evolves in multiple
directions to explore different trade-offs. The MIC architec-
ture, one such example, strays from the mainstream CPU
design by packing a larger number of simpler cores per chip,
relying on SIMD instructions to fill the performance gap.
Databases have been attempting to utilize the SIMD ca-
pabilities of CPUs. However, mainstream CPUs have only
recently adopted wider SIMD registers and more advanced
instructions, since they do not rely primarily on SIMD for
efficiency. In this paper, we present novel vectorized designs
and implementations of database operators, based on ad-
vanced SIMD operations, such as gathers and scatters. We
study selections, hash tables, and partitioning; and com-
bine them to build sorting and joins. Our evaluation on the
MIC-based Xeon Phi co-processor as well as the latest main-
stream CPUs shows that our vectorization designs are up to
an order of magnitude faster than the state-of-the-art scalar
and vector approaches. Also, we highlight the impact of ef-
ficient vectorization on the algorithmic design of in-memory
database operators, as well as the architectural design and
power efficiency of hardware, by making simple cores com-
parably fast to complex cores. This work is applicable to
CPUs and co-processors with advanced SIMD capabilities,
using either many simple cores or fewer complex cores.
1. INTRODUCTION
Real time analytics are the steering wheels of big data
driven business intelligence. Database customer needs have
extended beyond OLTP with high ACID transaction through-
put, to interactive OLAP query execution across the entire
database. As a consequence, vendors offer fast OLAP solu-
tions, either by rebuilding a new DBMS for OLAP [28, 37],
or by improving within the existing OLTP-focused DBMS.
∗
Work partly done when first author was at the Oracle Labs.
†
Supported by NSF grant IIS-1422488 and an Oracle gift.
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 cita-
tion on the first page. Copyrights for components of this work owned by others than
ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or re-
publish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
SIGMOD ’15, May 31 - June 04, 2015, Melbourne, VIC, Australia.
Copyright 2015 ACM 978-1-4503-2758-9/15/05 ...$15.00.
http://dx.doi.org/10.1145/2723372.2747645.
The advent of large main-memory capacity is one of the
reasons that blink-of-an-eye analytical query execution has
become possible. Query optimization used to measure blocks
fetched from disk as the primary unit of query cost. Today,
the entire database can often remain main-memory resident
and the need for efficient in-memory algorithms is apparent.
The prevalent shift in database design for the new era
are column stores [19, 28, 37]. They allow for higher data
compression in order to reduce the data footprint, minimize
the number of columns accessed per tuple, and use column
oriented execution coupled with late materialization [9] to
eliminate unnecessary accesses to RAM resident columns.
Hardware provides performance through three sources of
parallelism: thread parallelism, instruction level parallelism,
and data parallelism. Analytical databases have evolved to
take advantage of all sources of parallelism. Thread par-
allelism is achieved, for individual operators, by splitting
the input equally among threads [3, 4, 5, 8, 14, 31, 40],
and in the case of queries that combine multiple operators,
by using the pipeline breaking points of the query plan to
split the materialized data in chunks that are distributed to
threads dynamically [18, 28]. Instruction level parallelism is
achieved by applying the same operation to a block of tu-
ples [6] and by compiling into tight machine code [16, 22].
Data parallelism is achieved by implementing each operator
to use SIMD instructions effectively [7, 15, 26, 30, 39, 41].
The different sources of parallelism were developed as a
means to deliver more performance within the same power
budget available per chip. Mainstream CPUs have evolved
on all sources of parallelism, featuring massively superscalar
pipelines, out-of-order execution of tens of instructions, and
advanced SIMD capabilities, all replicated on multiple cores
per CPU chip. For example, the latest Intel Haswell ar-
chitecture issues up to 8 micro-operations per cycle with
192 reorder buffer entries for out-of-order execution, 256-bit
SIMD instructions, two levels of private caches per core and
a large shared cache, and scales up to 18 cores per chip.
Concurrently with the evolution of mainstream CPUs, a
new approach on processor design has surfaced. The design,
named the many-integrated-cores (MIC) architecture, uses
cores with a smaller area (transistors) and power footprint
by removing the massively superscalar pipeline, out-of-order
execution, and the large L3 cache. Each core is based on a
Pentium 1 processor with a simple in-order pipeline, but
is augmented with large SIMD registers, advanced SIMD
instructions, and simultaneous multithreading to hide load
and instruction latency. Since each core has a smaller area
and power footprint, more cores can be packed in the chip.
剩余15页未读，继续阅读
资源评论
