Optimizing Relational Programs I

on YouTube ↗41m

" summary

Tool builds a compact tree automaton that encodes many equivalent programs by merging states for equal subexpressions, grows it by applying rewrite rules until saturation, then extracts a cheapest implementation via a generalized Dijkstra on hyperedges. Key claims: this yields a huge (even infinite) search space compression, associativity/commutativity causes combinatorial blowup, DAG extraction becomes NP‑hard, and the correct extraction encoding uses equality saturation plus ASP vs ILP (answer‑set programming fixes an ILP counterexample).

AI-written summary · about

" chapters (7)

1. 0:00Workshop overview
2. 3:51Program optimization as search
3. 10:39Tree automata for programs
4. 22:27Equality saturation
5. 27:14Finding fastest program
6. 34:02Extracting optimal programs
7. 40:41Closing

" related talks

• 05mRelational ProgrammingRemy Wang · 9th Annual Simons Institute Industry Day
• 18mParikh's Theorem Made SymbolicAnthony W. Lin, Matthew Hague, Artur Jez · POPL 2024
• 15mSpeeding up Symbolic Reasoning for Relational QueriesChenglong Wang · OOPSLA 2018
• 15mUniversal Scalability in Declarative Program Analysis (with Choice-Based Combination(…)Yannis Smaragdakis, Neville Grech, Anastasios Antoniadis, Ilias Tsatiris · OOPSLA 2025
• 13mAccelerating Program Analyses in Datalog by Merging Library FactsXin Zhang, Lu Zhang, Yingfei Xiong, Chenyang Yang, Yifan Chen, Hao Tang, Xiaoyin Wang · SAS 2021
• 01h 01mDatalog and Equality SaturationMax Willsey · Logic and Algebra for Query Evaluation 2023
• 17mBetter Together: Unifying Datalog and Equality SaturationZachary Tatlock, Oliver Flatt, Max Willsey, Yihong Zhang, Yisu Remy Wang, David Cao, Philip Zucker, Eli Rosenthal · PLDI 2023
• 01h 03mQuery Optimization and Evaluation 3: Variable Elimination and Tensor DecompositionHung Ngo · Logic and Algorithms in Database Theory and AI Boot Camp