Query Optimization and Evaluation 3: Variable Elimination and Tensor Decomposition
summary
Introduces a concrete plan: represent aggregation as sum-product queries, build a compact intermediate (factorized/tensor) representation via variable elimination and tree decompositions, and bound its worst-case size with the polymatroid bound (then linearize via Shannon-flow). Shows 4-cycle detection drops from quadratic to n^{1.5}, k-walk counting becomes essentially O(k·E), and disjunctive datalog / tensor decomposition mixes multiple decompositions to reach these exponents. Notes implementation challenges: exploding decompositions, recursion, and counting vs decision remain open.
AI-written summary · about
chapters (15)
- 0:00Query optimization challenges
- 1:14Worst-case output size limits
- 4:50Sum-product queries as abstraction
- 9:13Optimality with input/output
- 11:31Meta query plan with IR
- 16:06Variable elimination
- 20:06Decorrelating subqueries
- 26:50Tree decompositions and message passing
- 31:17Minimizing intermediate sizes
- 37:05Tensor decomposition with trees
- 41:27Disjunctive datalog rules
- 47:20Output size bounds for datalog
- 51:15Shannon flow inequality
- 55:37Open problems and future
- 1:01:28Q&A
related talks
41mOptimizing Relational Programs I
36mOptimizing Relational Programs II
51mFactorized Databases
44mIntermediate Relational Algorithm Design
21mRecent Advances in Incremental View Maintenance
33mChordal Structure and Polynomial Systems
16mA Compiler for Fused Relational Operations on Multisets
14mDeductive Optimization of Relational Data Storage