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?
Who this mechanism is for: a developer who writes code and knows basic SQL, but has never looked inside a query engine. You do not need to know how a database executes a query. Every technical term is explained the first time it appears, and again in the glossary at the end. This mechanism assumes only that you have a rough idea of what a CPU core, a thread, a cache and a network are. A short primer follows the introduction.
The story we will follow
Mateo is a query-engine engineer at Gridlark, a company that analyzes electricity use for power utilities. He owns Lark, Gridlark's in-house SQL engine. Lark runs on a cluster of 40 machines (16 cores and 64 GB of memory each) and reads Parquet files (a column-oriented file format). The main table is readings: about 40 billion rows per month, one row per smart-meter reading, with the columns meter_id, ts (timestamp), kwh, tariff_zone and status. Two smaller tables help: meters (about 12 million rows) and tariffs (a few hundred rows). Lark runs three kinds of work: dashboards that must answer in seconds, a nightly billing job that runs for hours, and a new experiment on a "functions-as-a-service" platform.
Hana is the head of the data platform. She owns the cluster budget, and she asks the questions that engineers prefer to avoid: "Why is the cluster busy but slow? Why did the invoice go up?" A separate team writes the planner, the part of the engine that chooses which steps to run and in which order. The planner team is good. This mechanism is about the next stage: how the chosen plan is actually run on real cores and real machines.
During this mechanism, Mateo and Hana meet seven problems, one at the start of each article below. Each problem looks like a bug. Each one is actually a consequence of how a query runtime must behave. At the end of each article, we go back and solve the problem with the article's mechanisms.
This is the main idea of this whole mechanism:
How this mechanism is organized
- 1
Three idlenesses
Why is elapsed time not "work divided by capacity", and what are the only three reasons a machine sits idle?
Case40 machines at 25% CPU
- 2
Inside one worker
What does it cost to hand a row from one operator to the next, and how do Volcano, push, vectorized, compiled and morsel-driven designs change that cost?
Case40 times slower than a C loop
- 3
Across machines
When the handoff costs milliseconds and can fail, how do DAG, BSP, actor and serverless designs answer, and how do we choose?
CaseThe nightly job that restarts from zero
- 4
Where parallelism comes from
Why does adding cores stop helping, and how do stealing, scheduling and speculation work?
CaseTwice the machines, 90 minutes instead of 50
- 5
Skew and elasticity
What do you do when one piece of work is simply too big, and when does adding machines mid-query pay off?
CaseOne meter id with 7% of the rows
- 6
The shuffle
Why does moving rows between stages cost a *product* of two widths, and which designs reduce the damage?
CaseToo many open files
CaseA faster network made compression slower
After that: a summary, hands-on labs, interview questions and a glossary.
One request: keep the arithmetic. Almost every section ends in a small formula, and each formula gives a number you can compute for your own system before you build anything.
What do I do, and what does each option cost?
Choose an execution model
A workload must run: on one machine, or across many as a pipelined or materialized dataflow, bulk-synchronous rounds, actors or serverless functions? Three questions, then the arithmetic that decides how failures are survived.
ChoosePlan the parallelism
Before adding workers: find the ceiling set by the largest partition, the stages set by pipeline breakers, whether the costly operator can be split at all, how to size tasks, and when speculation and elastic scaling pay.
DesignHandle skew and elasticity
A stage's last tasks run far longer than the rest: plot duration against input bytes to tell imbalance, a straggler and skew apart, then apply the fix that works for that one.
DiagnoseDesign a shuffle
Data must be repartitioned across machines: compute bytes per connection against the storage floor, cap the width, shrink the data first, then choose hash or sort, a shuffle service, compression and serialization.
Design
Can I see it myself?
Barriers multiply variance
Reproduce E[max]/E[mean] ≈ 1 + c·√(2 ln n) and the BSP rule that the penalty multiplies by the number of rounds.
SimulatePython with NumPyMeasure the cost of a boundary: tuple-at-a-time against batches
See the "fixed cost per control transfer" with your own numbers.
MeasurePython with NumPyFind the best batch size on your machine
Check the claim "batch size is chosen so the working set stays in cache, about L1 size ÷ row width".
MeasurePython with NumPyCompute a compilation break-even
Turn "compilation has a break-even data volume" into a measured number.
MeasurePython with NumPy, numbaPer-row UDF versus vectorized UDF
Score 5 million rows with x * 0.3 + 2.0 per row and vectorized in blocks of 100 to 1,000,000; and the time to read and write the data.
MeasurePython with pandas, NumPy, PyArrowWhole-query restart against task retry
Check that expected whole-query attempts grow like e^(nTλ).
SimulatePythonThe Zipf ceiling on data-parallel speedup
Turn "the largest partition is your serial fraction" into a number.
SimulatePython with NumPyTriage plot, salting and the join product
Classify three kinds of long tail, then fix skew by salting, and see that join skew multiplies.
SimulatePython with NumPy, matplotlibMany small reads against few large reads: the transfer floor
Measure the minimum efficient transfer size on your own disk, then compute a shuffle width ceiling from it.
MeasurePythonWhen does shuffle compression pay? And a non-deterministic partition function
Measure codec throughput and ratio on shuffle-like data, then apply C > BW · r/(r−1).
Measure · Break itPython
Can I reason about it under questioning?
Interview questions
Short questions on how a query runtime keeps machines busy, such as execution models, distributed tasks, barriers, skew, scheduling and the shuffle, each with an answer you could give aloud and a link to the full explanation.
Scenarios
Longer problems on query runtimes, of the kind asked in senior interviews: each one estimated with numbers, diagnosed, and answered with its trade-offs.
The tensions this mechanism takes a position on. Each recurs across mechanisms.
Ideas this mechanism meets that keep coming back, mechanism after mechanism.