Zipf caps data-parallel speedup

How it behaves

One input on the horizontal axis, the others held fixed.

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

• K = 10⁶ → H_K ≈ 14.4: the top key is ≈ 7% of rows
• on 200 executors, 93% sit idle at the end

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

• Execution Engine Runtime

  Once a query plan is chosen, why does the machine still sit idle, and what does each mechanism of a query runtime pay to buy that idle time back?

  $$1/H_K,H_K\approx \ln K+0.58$$

  Read it in place →