How types can turn a SQL interpreter into a SQL compiler
summary
A 3,000–4,000 line Scala prototype called LegoBase generates low-level C and achieves up to >10x (peak) speedups versus commercial DBs and up to 20x versus dbx, beating Hyper in the paper’s benchmarks and earning a VLDB best paper. It uses LMS staging, mixed-stage data structures, and memory-mapped I/O so an interpreted SQL engine compiles into tight code (example: a query drops from ~38s to ~3.7s).
AI-written summary · about
chapters (14)
- 0:00Introduction
- 1:03Constraints in databases
- 2:06Minimal SQL processor in Scala
- 11:53Abstractions for SQL
- 15:56Parsing SQL to algebra
- 17:40Query operators: scan and project
- 20:28Filtering and joins
- 23:41Interpreter performance
- 25:52Interpreter to compiler
- 28:03Lightweight modular staging
- 30:29Low-level code generation
- 34:24Scaling to real systems
- 35:47Conclusion
- 36:29Q&A
related talks
13mWriting an Interpreter in SQL for Fun and No Profit!
14mAutomated Translation of Functional Big Data Queries to SQL
32mBecause SQL is everywhere but you don't want to use it
16mA Compiler for Fused Relational Operations on Multisets
36mBeyond dbt: Modern SQL Transformation and Lineage with SQLGlot and SQLMesh
42mThe Resurgence of SQL
49mScylla, Charybdis, and the mystery of Quill
18mTranslating canonical SQL to imperative code in Coq