Equality Saturation and Joins
summary
Equality saturation uses egraphs to represent many equivalent programs and extraction picks the cheapest term after saturating rewrites. A relational encoding named egg log turns matching into conjunctive queries with functions and extensible equality so pattern search runs significantly faster than backtracking based matching. A new join design called free join mixes worst case optimal and binary plans, compiles loop/probe schedules, and evaluates faster than DuckDB on tested workloads while showing more robustness to bad statistics.
AI-written summary · about
chapters (7)
- 0:00Introduction
- 1:48Equality saturation
- 5:41Bottlenecks
- 8:57Relational egg log
- 13:53Why relational faster
- 14:35Free join algorithm
- 19:10Summary
related talks
30megg: Fast and Extensible Equality Saturation
17mBetter Together: Unifying Datalog and Equality Saturation
19meqsat: An Equality Saturation Dialect for Non-destructive Rewriting
19mTowards Relational Contextual Equality Saturation
18mAssociativity and Commutativity in Equality Saturation
24mIncremental Equality Saturation
21mImproving Equality Saturation for EDA via Semantic E-Graphs
15mEquality Saturation Theory Exploration à la Carte