Paper Info
Title
Functional pearl: a SQL to C compiler in 500 lines of code
Abstract
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.
Year
DOI
Venue
2015
10.1145/2858949.2784760
International Conf on Function Programming
Keywords
Field
DocType
Futamura Projections,Generative Programming,Query Compilation,SQL,Staging
SQL,Data structure,Programming language,Scala,Functional programming,Partial evaluation,Computer science,Theoretical computer science,Compiler,Query by Example,Source lines of code
Conference
Volume
Issue
ISSN
50
9
0362-1340
Citations 
PageRank 
References 
10
0.52
21
Authors
2
Name
Order
Citations
PageRank
Tiark Rompf174345.86
Nada Amin216611.47