An exact distinct count is needed over a file far larger than memory. What are the three escapes, and what does each charge?

## Why there are exactly three currencies Once an operation is one whose answer a later record can still change, the job needs reach over records it cannot hold resident. There are only three things you can give up to get that reach: **input and output volume** (read the data more times, write intermediates), **exactness** (accept an answer with a stated error bound), or **one more traversal of data you have already read once**. Everything sold as a solution to this problem is one of the three, or a combination of them. | Escape | What you keep | What it charges | What it needs to be true | |---|---|---|---| | Spilled multi-pass run | The exact answer, and usually the expression you already wrote | Reads and writes of the whole input; local disk space, often a multiple of the input | Local storage with the room and the throughput | | Bounded-error answer | One traversal, a small fixed footprint, a fast clock | Exactness — the result carries an error bound | A tolerance agreed with the number's consumers **first** | | Cheap first traversal | The exact answer and a bounded footprint | One extra read of the input, and the engineering to write two steps | An input that can be read a second time, unchanged | ## Escape one — a spilled multi-pass run **Out-of-core execution** means the job writes intermediates to this machine's disk and reads the input more than once, so it can finish work that will not fit. You get the exact answer and, in many designs, you get it without rewriting anything. The charge is volume. The clock stops being set by how fast values are folded and starts being set by how fast bytes move on and off the device, and the space the intermediates occupy is not a rounding error — it is routinely a multiple of the input, on a disk that has to actually have it. A job that dies at the point of writing intermediates because the local volume filled is a common and unglamorous failure. **Whose job this is varies by design, and the difference matters.** In a fully in-memory model, where the whole dataset must be resident before any operation runs, the author writes the piece loop and the combine step by hand. Where the tool's own execution can work through the input a portion at a time and hold intermediates on disk, the expression is unchanged and what changes is an entry point or a setting — and what is left for the author to reason about is only the operations that still have no combine step. ## Escape two — an answer with an error bound A **bounded-error summary** is a fixed-size structure that answers a question approximately with a stated error bound instead of exactly. Its footprint does not grow with the input or with the number of distinct values, and it needs one traversal. For an exact-distinct-style question that is a dramatic trade: unbounded state becomes a constant. The charge is exactness, and it is charged in two places. The obvious one is the number itself. The one candidates miss is **organisational**: the tolerance has to be agreed before you build, with whoever will consume the figure. You cannot retrofit "approximately" onto a number somebody already reconciles against another system — the moment two figures disagree by less than the bound, the conversation is about trust, not about engineering. Deciding the tolerance is a commitment, not a configuration value. ## Escape three — a cheap first traversal The third escape keeps exactness *and* a bounded footprint, and pays instead with time. One traversal computes something small and fixed in size — counts per value range, the set of values that are frequent, the bounds of the data — and that small result tells the second traversal which narrow slice of the input it actually has to retain. The slice fits; the exact answer comes out of it. The charge is one extra read of the whole input, plus two preconditions. The input must be **re-readable** — a feed you can consume only once forecloses this escape entirely — and it must be **unchanged between the two reads**, or the summary from the first no longer describes what the second one sees. ## The trap in all three None of the three makes the operation cheap; each makes it *possible* at a price, and the prices are denominated differently, so they cannot be compared on one axis. Before choosing, answer three questions about the situation rather than about the technique: - **Does the figure have to be exact?** If it is reconciled against anything produced independently, the bounded-error answer is off the table whatever its bound. - **Can the input be read again, unchanged?** If not, both multi-read escapes disappear and the approximate one is all that is left. - **What does this machine actually have spare — disk, or clock?** The spilled run spends storage and read volume; the cheap first traversal spends only read volume; the bounded-error answer spends neither. The strong answer says which currency the requirement in front of you can afford to spend, rather than naming a favourite technique.