Repository logo
 

A SQL to C compiler in 500 lines of code

Accepted version
Peer-reviewed

Type

Article

Change log

Authors

ROMPF, TIARK 
AMIN, NADA 

Abstract

jats:titleAbstract</jats:title>jats:pWe 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 toward generative programming. The core of the query engine is an interpreter for relational-algebra operations, written in Scala. Using the open-source lightweight modular staging framework, 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: the first Futamura projection, which states that a process that can specialize an interpreter to any given input program is equivalent to a compiler. In this context, we discuss lightweight modular staging 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.</jats:p>

Description

Keywords

4605 Data Management and Data Science, 46 Information and Computing Sciences, 4609 Information Systems, 4612 Software Engineering

Journal Title

Journal of Functional Programming

Conference Name

Journal ISSN

0956-7968
1469-7653

Volume Title

29

Publisher

Cambridge University Press (CUP)

Rights

All rights reserved