Massively Parallel Evaluation of Relational Queries I
summary
Massively parallel relational evaluation uses the BSP/MPC model with p servers, r rounds and maximum load L; concrete one‑round algorithms use randomized hashing into a hypercube: intersection gets load ≈ N/p, Cartesian product uses a √p grid with load ≈ 2N/√p, triangles use a 3‑D grid with load ≈ N/p^{2/3}. Analysis gives a closed form via fractional edge packing and an explicit upper bound product(|S_j|^{u_j})/p^{1/Σu_j}; lower bounds use counting/info and require matching database (freq ≤ N/p) assumptions for tightness.
AI-written summary · about
chapters (16)
- 0:00Intro
- 2:41TALK OUTLINE
- 4:33MODELING MASSIVE PARALLELISM
- 6:56MPC MODEL: COMPUTATION
- 8:23MPC MODEL: PARAMETERS
- 10:13MPC PARAMETERS
- 14:25EXAMPLE: SET INTERSECTION
- 16:51EXAMPLE: CARTESIAN PRODUCT
- 24:10MATCHING DATABASES
- 26:18COMPUTING TRIANGLES
- 29:41THE HYPERCUBE ALGORITHM
- 32:44CHOOSING OPTIMAL SHARES (2)
- 36:53MINIMIZING THE LOAD
- 40:40PACKINGS FOR THE TRIANGLE
- 42:30THEOREM #1 (UPPER BOUND)
- 44:37THEOREM #2 (LOWER BOUND)
related talks
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
01h 05mGraph Algorithms in the MPC Model
53mMapReduce Algorithmics
01h 06mSampling in Query Evaluation 1
16mA Compiler for Fused Relational Operations on Multisets
20mPolygon: Symbolic Reasoning for SQL using Conflict-Driven Under-Approximation Search
30mThree Goals in Parallel Graph Computations: High Performance, High Productivity, and Reduced Comm...
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds