In a vectorized engine, what is a selection vector and why keep one instead of compacting the batch after each filter?

## The problem the selection vector solves A vectorized engine works on batches: a few thousand values per column, held in flat buffers. A filter kernel over one of those buffers produces a mask — one bit or byte per position saying whether that row qualified. The question is what to do next, because the *values themselves have not moved*, and other columns of the same batch have not even been looked at. There are two answers. **Compact (also called flatten or coalesce):** allocate fresh buffers and copy, for every column the query still needs, only the surviving values into dense positions 0..k-1. Downstream operators then see an ordinary dense batch of k rows and need no special handling. **Select:** leave every buffer exactly where it is and pass along a *selection vector* — typically an array of the surviving positions, e.g. `[1, 4, 6, 9, ...]`, or equivalently a bitmap. Every downstream operator learns to iterate `for (j = 0; j < sel_count; j++) { i = sel[j]; ... }` instead of `for (i = 0; i < batch_size; i++)`. ## Why selection usually wins The cost of compaction is proportional to *the number of columns carried*, not to the number of columns filtered. A query with a fifteen-column projection and three filters would, under eager compaction, copy fifteen columns three times — and the values copied in step one are largely thrown away in step two. That copying is pure memory traffic, exactly the resource a scan is already stressing. A selection vector turns a chain of predicates into successive narrowings of a tiny index array: 1. `country = 'DE'` scans the country vector, produces `sel` with 300 of 2048 positions. 2. `amount > 100` runs **only over those 300 positions** of the amount vector, producing a shorter `sel`. 3. `status = 'PAID'` narrows further. Only the survivors of the full chain are ever gathered out of the payload columns. This is the execution-layer sibling of the storage idea that you should touch the fewest bytes possible, and it interacts with predicate ordering: cheap and selective predicates first, expensive ones (string matching, arithmetic, function calls) last, evaluated over an already-narrow selection. ## Why selection sometimes loses The indirection is not free, and it has three specific costs: - **Wasted lanes.** A SIMD kernel loads sixteen adjacent values whether or not you want them all. Over a dense batch, all sixteen count. Over a selection of every ninth row, you pay the same load and use one lane. Below some selectivity the packed kernel effectively degrades to scalar speed. - **Wasted cache lines.** Reading position 9, then 400, then 1500 of a column touches three separate cache lines to retrieve three values. A dense batch of the same three values touches one. - **Operator complexity.** Every kernel needs two code paths — flat and selected — or must always pay the indirection. Real engines maintain both, which doubles the kernel surface. Because of this, engines apply a heuristic: keep the selection vector while the batch is still reasonably dense, and compact once the surviving fraction falls below a threshold, so that downstream work runs on dense data again. Certain operators force compaction regardless — anything that builds or probes a hash table, spills, writes out, or crosses a pipeline boundary generally wants dense input. ## Relationship to branch-free filtering The reason a mask exists at all is that vectorized filters are written *without branches*. Instead of `if (amount[i] > 100) emit(i);` — a data-dependent branch the CPU must predict, mispredicting roughly half the time on random data and flushing a deep pipeline each time — the kernel unconditionally computes `mask[i] = amount[i] > 100` for every position, then derives the selection from the mask. Computing results for rows that will be discarded is deliberately cheaper than mispredicting. This is the same reason both arms of a `CASE` may be evaluated for the whole batch and then blended by mask: predictable work beats unpredictable branching. A related detail: converting a mask to a compact index list is itself a vectorized operation on modern CPUs, which is what makes the whole scheme cheap. ## What an interviewer is checking They want to see that you understand execution as a memory-traffic problem, not just an instruction-count problem: the point of the selection vector is *not copying columns you may not need*, and the reason it is not universal is that sparse access wastes the very cache lines and lanes that vectorization exists to exploit. Naming the compaction threshold as a heuristic rather than a fixed rule, and connecting predicate ordering to it, is the senior-level version of the answer.