Query Optimization and Evaluation 2: Worst-Case Optimal Join Algorithms
summary
Three classes of worst‑case approaches appear: JAAT, VAAT, IAAT (join‑at‑a‑time, variable‑at‑a‑time, inequality‑at‑a‑time). The paper proves VAAT meets the AGM/chain bounds and JAAT meets integral edge‑cover bounds, and converts dual LPs / Shannon‑flow inequalities into the PANDA algorithm that achieves the polymatroid bound (up to polylog and query‑size factors) by LP‑derived heavy/light partitions and many proof‑to‑operator steps; proof lengths and polylog blowup remain practical open problems.
AI-written summary · about
chapters (11)
- 0:00Worst-case optimal joins intro
- 1:00Join algorithm hierarchy
- 6:25JAAT limits on triangle query
- 7:29VAAT proof and backtracking
- 16:48Generalizing VAAT to queries
- 20:06Shannon-flow inequalities
- 37:01From Shannon-flow to IAAT
- 40:18Triangle query with PANDA
- 48:33Path query and PANDA thresholds
- 57:24Summary and open problems
- 57:50Q&A
related talks
38mIncremental View Maintenance: Beyond Worst-Case Analysis I
01h 09mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: I
26mIncremental View Maintenance: Beyond Worst-Case Analysis II
55mSort vs Hash A Duality
44mIntermediate Relational Algorithm Design
19mAccessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: II
29mDirect Access for Conjunctive Queries with Aggregation
21mRecent Advances in Incremental View Maintenance