Query Optimization and Evaluation 4: Instance Optimality
summary
Covers instance optimality for query evaluation with concrete claims, tools and limits: defines comparison and gap/box certificates, reduces joins to a geometric box cover problem, and introduces a proof system based on geometric resolution and dyadic boxes. Presents the Minesweeper/Tetris family (preloaded, reloaded, balanced), proves treewidth‑1 is instance optimal up to polylog, gives upper bound certificate_size^(tw+1) and matching ordered‑resolution lower bounds, and shows an unrestricted lower bound ~certificate_size^(n/2); dyadic encoding adds a practical polylog cost.
AI-written summary · about
chapters (9)
- 0:00Instance optimality in databases
- 1:46Why instance optimality matters
- 8:40Instance optimality for set intersection
- 22:36Generalizing to join queries
- 33:12Dyadic boxes and proofs
- 41:19Tetris algorithm and initializations
- 51:17Instance optimality bounds for trees
- 53:30Open problems and future work
- 1:04:10Q&A
related talks
29mUnderstanding Queries by Conditional Instances
20mPolygon: Symbolic Reasoning for SQL using Conflict-Driven Under-Approximation Search
28mThe Logic of Counting Query Answers
38mThe Intensional-Extensional Problem in Probabilistic Databases
01h 05mHomomorphism Counts: Expressive Power and Query Algorithms
41mOptimizing Relational Programs I
26mIncremental View Maintenance: Beyond Worst-Case Analysis II
35mApproximating Certain and Possible Answers Beyond Sets