Why does restricting 50 million rows down to 3 still cost a full pass and a table-length intermediate?
answer
- selection is not a search
- cost follows the source, not survivors
- one entry per row, always
- fusing removes allocation, not the pass
basics
~20 sBecause selection by condition is not a search. An outcome is computed for every one of the 50 million rows and held as a condition column of that length; only then are the 3 true positions addressed. Rarity makes the result small, not the work.
solid answer
~40 sSelecting by condition is two steps, and the expensive one is proportional to the **source**. The condition step produces one outcome per row — a *condition column* 50 million entries long — because which rows match is exactly what that step is computing; no row can be skipped on the grounds that it will not match. Only the addressing step scales with the 3 survivors, and it is the cheap half. The intermediate's storage varies by design — a byte per row, packed bits, or nothing at all where the condition is fused into the pass that reads the rows — but one entry per row is the constant, and nothing makes it shorter than the table. Deferring or fusing changes the *allocation*; it does not remove the pass.
code
pseudocode · 8 linesoutcomes = evaluate_condition_over(amount_column, EXCEEDS, 100)
# outcomes has 50,000,000 entries -- one per row of the source
result = address_rows_with(table, outcomes)
# result has 3 rows -- every column of them
# cost(evaluate_condition_over) grows with 50,000,000
# cost(address_rows_with) grows with 3go deeper
Remember the direction: the work follows how many rows went in, not how many came out. Three rows out of fifty million is a small answer produced by a large amount of work.
Explain the split — the condition step and the intermediate scale with the source, the addressing step and the result scale with the survivors — and say that one entry per row is fixed while the entry's size is a design choice.
When a restriction is reported as slow, ask how many rows reached it and how many separate conditions were evaluated over them. Reducing the number of passes is the lever; making a rare match cheap is not available.
The standing question is whether a pipeline's steps are written to be read or written to be fused. Buying inspectability with a materialised intermediate at every step is a real cost that someone should have chosen deliberately.
## Selection is not a search The intuition that a rare match should be cheap comes from lookup: ask an access path for a key and it walks a small structure to the answer. Selecting by condition does nothing of the kind. It computes, for every row, whether that row satisfies the condition — and the only way to know that a row does not satisfy it is to evaluate it. A condition that matches 3 rows in 50 million and one that matches 49 million cost the same in the step that dominates. So the shape of the cost is: - **Condition step** — one outcome produced per row of the source. Proportional to 50 million. - **Intermediate** — one entry held per row of the source. Proportional to 50 million. - **Addressing step** — the true positions collected into the result. Proportional to 3. - **Result footprint** — 3 rows wide by however many columns. Proportional to 3. Two of those four follow the source and two follow the survivors, and the two that follow the source are the ones that hurt. ## What the intermediate actually costs One entry per row is the invariant; the *size* of an entry is a design choice and you should not carry a number in your head from one tool to another: - Some designs store each outcome as a whole byte, which is simple and fast to address. - Some pack outcomes as bits, trading a factor of eight in space for a little work on access. - Some carry a separate validity record alongside, because an outcome may be neither true nor false and that has to be represented somewhere. - Some never materialise the column: the condition is folded into the same pass that reads the rows, so the outcomes exist only as they are consumed. The honest statement is therefore not "the intermediate costs *n* bytes" but "the intermediate has *n* entries, and what an entry costs is the design's business". ## Eager against fused | | eager evaluation | fused into the pass | |---|---|---| | rows examined | all of them | all of them | | outcome column materialised | yes, full length | often not at all | | chained conditions | each operator's result allocated | built as one expression | | what you can inspect | the intermediate, by name | usually only the result | The row highlighted by that table is the first one: **both models look at every row**. What a recorded-plan or fused design buys is that the full-length intermediate need not exist, and that a chain of several conditions need not allocate one full-length object per operator. It does not buy skipping rows. Believing otherwise is the standard mistake when someone first meets a deferred design and expects a rare condition to become instant. ## What does change the cost Within the two-step model itself, very little. The levers are structural rather than syntactic: 1. **Do not build the condition more than once.** Computing the same full-length outcome column twice in a pipeline pays the dominant cost twice; name it and reuse it, subject to it still lining up with the rows you apply it to. 2. **Combine before addressing, not after.** Two successive restrictions each pay their own pass over what reaches them; one condition evaluated once pays one — though how that composes depends on the evaluation model. 3. **Narrow the source before the condition is evaluated over it**, where you have that option. The pass is proportional to rows reaching the condition, so anything that reduces that count earlier reduces the dominant term. Notice that none of these makes the rare match cheap. They reduce how many full passes you make, not the cost of a pass. ## What this tells you about a pipeline A sequence of ten restrictions written as ten steps is ten passes over progressively smaller inputs, plus up to ten full-length intermediates, in an eager design; the same ten written as one condition is one pass and one outcome column. That is a real difference and it is measurable, but it is a difference in the *number of passes*, not in whether a pass happens at all. When someone reports that a restriction is slow, the useful first question is not "how many rows came back" — that number is nearly irrelevant — but "how many rows went in, and how many separate conditions were evaluated over them".
- Does a rare condition ever cost less than a common one?Only in the cheap half. The outcome column is the same length either way and every row is examined either way; the addressing step and the result's footprint scale with the survivors. A rare match makes the output small, which is not the same as making the operation fast.
- What actually makes the intermediate smaller?Nothing makes it shorter than the table — one entry per row is fixed. What varies is the entry: a byte per row, packed bits, or no materialisation at all where the condition is fused into the pass that reads the rows. Those are design choices, not knobs you can assume.
- Two restrictions applied one after the other, or one combined condition — which costs less?Under eager evaluation the combined form usually wins: one pass and one outcome column instead of two of each, though the second restriction's pass is over a smaller input. Under a design that fuses the expression the two forms can collapse to the same plan, so measure rather than assume.
saying these in an interview costs you the question
- Assumes the cost scales with the number of surviving rows
- Expects evaluation to stop once a rare match is found
- Thinks the outcome column is free because entries are tiny
- Believes deferring the work means the rows are not examined
- Quotes one tool's bytes-per-entry as if it were universal