Functional Pearl: A SQL to C Compiler in 500 Lines of Code

We present the design and implementation of a SQL query processor that outperforms existing database systems and is written in just about 500 lines of Scala code - a convincing case study that high-level functional programming can handily beat C for systems-level programming where the last drop of performance matters. The key enabler is a shift in perspective towards generative programming. The core of the query engine is an interpreter for relational algebra operations, written in Scala. Using the open-source LMS Framework (Lightweight Modular Staging), we turn this interpreter into a query compiler with very low effort. To do so, we capitalize on an old and widely known result from partial evaluation known as Futamura projections, which state that a program that can specialize an interpreter to any given input program is equivalent to a compiler. In this pearl, we discuss LMS programming patterns such as mixed-stage data structures (e.g. data records with static schema and dynamic field components) and techniques to generate low-level C code, including specialized data structures and data loading primitives.


Published in:
Acm Sigplan Notices, 50, 9, 2-9
Presented at:
20th ACM SIGPLAN International Conference on Functional Programming (ICFP), Vancouver, CANADA, AUG 31-SEP 02, 2015
Year:
2015
Publisher:
New York, Assoc Computing Machinery
ISSN:
0362-1340
Keywords:
Laboratories:




 Record created 2016-02-16, last modified 2018-09-13

Postprint:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)