Eric Love

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2019-181

December 20, 2019

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-181.pdf

Because of the low arithmetic intensity of relational database operators, the performance of in-memory column stores ought to be bound by main-memory bandwidth, and in practice, highly-optimized operator implementations already achieve close to their peak theoretical performance. By itself, this would imply that hardware acceleration for analytics would be of limited utility, but I show that the emergence of full-query compilation presents new opportunities to reduce memory traffic and trade computation for communication, meaning that database-oriented processors may yet be worth designing.

Moreover, the communication costs of queries on a given processor and memory hierarchy are determined by factors below the level of abstraction expressed in traditional query plans, such as how operators are (or are not) fused together, how execution is parallelized and cache-blocked, and how intermediate results are arranged in memory. I present a Scala- embedded programming language called Ressort that exposes these machine-level aspects of query compilation, and which emits parallel C++/OpenMP code as its target to express a greater range of algorithmic variants for each query than would be easy to study by hand.

Advisors: Krste Asanović

---

BibTeX citation:

@phdthesis{Love:EECS-2019-181,
    Author= {Love, Eric},
    Title= {Compiling Communication-Minimizing Query Plans},
    School= {EECS Department, University of California, Berkeley},
    Year= {2019},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-181.html},
    Number= {UCB/EECS-2019-181},
    Abstract= {Because of the low arithmetic intensity of relational database operators, the performance of in-memory column stores ought to be bound by main-memory bandwidth, and in practice, highly-optimized operator implementations already achieve close to their peak theoretical performance. By itself, this would imply that hardware acceleration for analytics would be of limited utility, but I show that the emergence of full-query compilation presents new opportunities to reduce memory traffic and trade computation for communication, meaning that database-oriented processors may yet be worth designing.

Moreover, the communication costs of queries on a given processor and memory hierarchy are determined by factors below the level of abstraction expressed in traditional query plans, such as how operators are (or are not) fused together, how execution is parallelized and cache-blocked, and how intermediate results are arranged in memory. I present a Scala- embedded programming language called Ressort that exposes these machine-level aspects of query compilation, and which emits parallel C++/OpenMP code as its target to express a greater range of algorithmic variants for each query than would be easy to study by hand.},
}

EndNote citation:

%0 Thesis
%A Love, Eric 
%T Compiling Communication-Minimizing Query Plans
%I EECS Department, University of California, Berkeley
%D 2019
%8 December 20
%@ UCB/EECS-2019-181
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-181.html
%F Love:EECS-2019-181