Appendix CThe machine in one page
A query’s cost is paid to a machine: to its processor, its memory, its storage and its network. The book never times the machine. It counts on a model of it, the same on every computer and in the page, and each chapter that builds a part of the model says what that part leaves out. This page gathers them.
From near to far#
Data travels to the processor through a chain of stores, each larger and slower than the one before it:
- Registers hold the values an instruction works on. A compiled loop keeps its values here (ch19).
- The cache holds the lines of memory used recently. A read the cache holds is a hit; any other is a miss, and waits for memory (ch02). Hash tables and joins live or die by it (ch07, ch08).
- Memory holds what the engine is working on. An operator that must hold more than memory allows writes some of it out and reads it back (ch10).
- Storage holds the files. Object storage answers each request after a delay, however few bytes it asks for, so requests matter as much as bytes (ch03, ch05).
- The network joins machines. Rows that must meet on one machine must cross it (ch15).
The processor itself guesses which way each branch goes, and pays when it guesses wrong, and applies one instruction to several values at once when the code lets it (ch06). Several cores share the machine, and the work of a query must be cut into pieces for them to share it (ch14).
The book’s model#
| Part | The book’s model | Its settings | Built in |
|---|---|---|---|
| Data cache | One level; a line may sit anywhere; the line used longest ago is pushed out | 512 lines of 64 bytes: 32 KiB | ch02 |
| Branch predictor | A two-bit counter for each branch in the code | Four states; predicts taken in the top two | ch06 |
| Vector unit | One instruction applies an operation to a lane-full of values | 4 lanes of eight bytes | ch06 |
| Storage | An object store that logs every request and the bytes it returns | Every byte the scan reads is a byte a request returned | ch03 |
| Memory | A limit on the bytes an operator holds; beyond it, runs are written out and merged | Limits of 10%, 20%, 50% and 100% of the input’s bytes | ch10 |
| Cores | Workers that each take the next morsel when free, and never wait on each other | From 1 to 16 workers | ch14 |
| Machines | Nodes that each hold some row groups, and send rows as Arrow IPC bytes | From 2 to 64 nodes | ch15 |
| The reference | DuckDB, pinned, with one thread, at the book’s build and in the page | DuckDB 1.1.2 | ch01 |
Read from the settings of the book’s simulators and its pinned DuckDB, at build time.
What the model leaves out#
- Time. Every model counts events: misses, mispredictions, instructions, requests, bytes. How long each takes differs from one machine to the next by more than the book’s comparisons do, so a count says which design does less, and a time on your own machine says how much that is worth. The chapters’ timed blocks measure that, in your browser.
- Levels and prediction. A real processor has several levels of cache, fetches lines before they are asked for, and runs instructions out of order while it waits. The models have one level, fetch nothing early, and run in order.
- Sharing. Real cores share memory bandwidth and caches, and real machines share a network. The simulated workers and nodes never wait on each other, except where a chapter counts it.
- Failure and variation. Real storage is sometimes slow and real machines sometimes fail. The models never are, except where ch17 makes one fail on purpose.
Built from commit dc21108.