Massively Parallel Evaluation of Relational Queries II
summary
Shows a precise round-vs-load tradeoff: for path queries diameter k the load falls from N/p^{1/4} with one round toward N/p as rounds increase, and achieving load <N for transitive closure requires nonconstant rounds under matching databases. Skew is handled by isolating heavy hitters, using semi-join episodes and server allocation per heavy value to cut load versus a single-round hash join. Worst-case acyclic joins use a canonical edge cover and path cover to limit Cartesian products to one relation per path, and two-table output sensitivity hits N/p + sqrt(OUT)/p optimal.
AI-written summary · about
chapters (8)
- 0:00Round-load trade-offs
- 3:24Data skew challenges
- 6:15Heavy hitters and two rounds
- 11:50Worst-case optimal algorithms
- 15:13Canonical edge covers
- 20:06Recursive decomposition
- 24:37Output-sensitive algorithms
- 29:01Hybrid join strategies
related talks
26mRelational E-matching
40mAdaptive query optimization in PostgreSQL
27mSpeed and Precision: Mastering Graph Traversal With Quantified Path Patterns
15mSpeeding up Symbolic Reasoning for Relational Queries
07mJoin Algorithms Meet New Constraints: Scalability, Latency and Privacy
55mSort vs Hash A Duality
14mDeductive Optimization of Relational Data Storage
10mQuery, Communication and Discrepancy