Passing DBs through continuations
2 days ago
- #database-optimization
- #continuation-passing-style
- #functional-programming
- The article discusses improving database query performance using continuation-passing style (CPS) for operator fusion, moving from materialized intermediate results to compiled, efficient code.
- Traditional iterator models incur overhead from dynamic dispatch; vectorization and compilation are solutions but require significant effort. CPS offers a shortcut by enabling automatic fusion of operations.
- CPS defines operators (e.g., inc, dbl) to take continuations instead of returning lists, allowing chaining without intermediate allocations. Inlining expands chains into fused loops.
- Prela uses CPS to map relational algebra operators (like compose and product) to columnar execution, reducing joins to simple loops over dense arrays, matching performance of systems like DuckDB.
- CPS cleanly separates engine responsibilities (mapping queries) from compiler optimization, making Prela extensible and efficient, with performance reliant on assumptions like dense primary keys and null-free data.