Deductive Optimization of Relational Data Storage
summary
A system called Castor synthesizes specialized on-disk layouts and native executables from known query templates, serializing the static database ahead of time and guaranteeing relational equivalence via deductive rewrite rules in a layout algebra. Example: Demomatch traces get range and hash indexes plus row stores chosen by deduction. Evaluation on TPC-H against Hyper shows automated layout synthesis saves memory and speeds reads by up to two orders of magnitude, with a cost model selecting among many transformation sequences.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:11Static Databases
- 0:45Architecture
- 1:44Traditional Query Optimizers
- 2:04Castor Query Optimizer
- 3:40Semantic Composition
- 4:32Deductive Synthesis
- 5:48Demomatch: Example Query
- 6:17Storing the log Relation
- 10:38Final Layout: Low Level
- 11:35Evaluation
- 13:21Conclusions
related talks
41mOptimizing Relational Programs I
36mOptimizing Relational Programs II
05mRelational Programming
41mNo stats, no problem: building feedback-driven optimizers for lakehouses
15mIncremental Processing of Structured Data in Datalog
17mTowards Iterative Relational Algebra on the GPU
17mBring Your Own Data Structures to Datalog
26mRelational E-matching