M2b.1: Selection vectors, so a filter stops copying

Part of #79. The design is section 4 of `docs/specs/engine/02-execution-model.md` and the data model it borrows is `docs/specs/engine/duckdb/01-data-model.md`.

This is the scope the engine spec says to do last, because it is the one that touches what every operator does with a chunk. It is also the largest remaining win in the pipeline, and #520 is what made that measurable: the filter operator no longer writes columns nobody reads, and what is left is that it writes the columns somebody does read, over and over, once per condition.

## What the problem looks like

TPC-H q6's predicate is five conditions over four columns. Today that lowers to five compares and five filters, and each filter writes out every column it keeps. The row count falls as it goes, but the first filter is writing four full columns of eight hundred thousand rows and the whole chain writes about seventy megabytes to answer a query whose answer is a hundred and twelve thousand rows.

A selection vector is a list of indices into an array. A filter that writes one has moved four bytes per surviving row instead of thirty two, and the columns it did not touch are still the arrays the scan handed over.

## The shape

A chunk's columns are no longer all the same thing. A column is either dense, meaning its element i is row i of the chunk, or it is under the chunk's selection, meaning its element `sel[i]` is row i. A chunk with no selection has every column dense, which is what every chunk is today.

That distinction is the whole design. A filter over a chunk with no selection writes a selection and moves no column data at all. A filter over a chunk that already has one composes the two, and gathers only the columns that were computed since the last filter, which are small and few.

## The work

- [x] A `Selection` type, and `Chunk` carrying one with a dense flag per column
- [x] `Chunk.flatten()`, which gathers every column that is not dense and clears the selection
- [x] Every operator flattens on entry, so that adding the type changes no answer anywhere
- [x] A gather through an ascending selection that costs about what a filtered copy costs. Nothing below this line is worth doing until this one is done, see the measurement below
- [x] Positions narrowed from `Int` to `UInt32`, which halves the index traffic the gather reads
- [x] `Filter` writes a selection instead of copying, composing with the one it was given. Tried in #532 and reverted in #538
- [x] A flatten threshold, chosen by measurement, for when a sparse selection is worse than a copy
- [x] `Compute` and `Cast` read through the selection, gathering the operands they need. Tried in #532 and reverted in #538
- [x] `Project` passes a selection through, since reordering columns moves no rows. Tried in #532 and reverted in #538
- [x] A compare that feeds a filter writes the selection itself, building no mask column and gathering no operand
- [x] `Limit` slices a selection rather than the columns under it
- [ ] Join output as a selection per side, which is the case the spec says we currently materialize most

## Quality

- [x] The q6 probe rerun before and after, in the pull request that turns it on
- [x] A test that a selected chunk and a flattened one give the same answer through every operator
- [ ] The existing suite passes unchanged at every step, since none of this is visible above the pipeline

## What it is expected to be worth

The spec's own prediction is modest on db-benchmark, because those queries are short chains with one or two operator boundaries. TPC-H q6 is the opposite and is where the number should move: counting data movement, the predicate chain should go from about seventy megabytes to about twenty three.

## What it turned out to be worth, measured

A six times slowdown when the predicate keeps most of its input, which is why #532 was reverted by #538.

The first measurement timed only q6's whole five condition predicate, saw the two routes overlap, and called it a wash. That is the one point on the curve where they meet. Per condition count, six million rows, thirty two thread desktop, best of fifteen runs, milliseconds:

| conditions | rows kept | before #532 | with #532 | after #538 |
| --- | --- | --- | --- | --- |
| 1 | 4,284,405 | 6.5 | 38.7 | 6.4 |
| 2 | 856,959 | 7.1 | 16.0 | 7.1 |
| 3 | 466,640 | 7.4 | 13.0 | 7.4 |
| 4 | 233,654 | 7.7 | 10.1 | 7.7 |
| 5 | 112,256 | 7.9 | 7.7 | 7.8 |

One condition keeps seven rows in ten, five conditions keep about one in fifty. So the selection is six times slower on a predicate that keeps most of its input and only breaks even where the answer has nearly vanished. Most filters are the first kind.

The cause is that a mask and a selection describe the same answer with opposite cost profiles, and the kernels that consume them are not the same speed. A mask is one byte per input row. A selection is eight bytes per surviving row, so it is the smaller description only below one row in eight. On the same chunk of 65536 int64 rows keeping seven in ten: copying one column through the mask with `filter_any` is 43 microseconds, gathering one column back through the positions with `take_any` is 120, and writing the positions is another 110. The copy reads and writes sequentially, the gather does a scalar indexed load per row, and arranging the operators differently does not touch that ratio.

A selection can only win by avoiding column copies, and #520 had already stopped the filter copying the columns nothing downstream reads. There were not enough copies left to pay for one gather at the end.

## What has to happen before this is tried again

The gather, which is the new first box. A selection is always ascending, so reading a column through one is a sequential walk with holes in it and there is no good reason for it to cost nearly three times what the filtered copy costs. Narrowing the positions to `UInt32` is the other half, since the gather reads eight bytes of index for every eight bytes of value it moves.

If those two land and a gather comes within say a third of a filtered copy, the arithmetic changes sign and the rest of the list is worth doing. If they do not, this design does not fit this engine's layout and the issue should be closed rather than carried.

The seventy megabytes this issue originally predicted was counted before #520 landed. After it the chain moves much less than that, which is the other half of why the prediction was wrong.

## What the gather measured, and so where this stands

Both of those boxes landed in #706 and the answer is that the arithmetic changes sign. One chunk of 131072 rows, kept rows scattered by a pseudorandom mask rather than by a stride, both sides pinned to one core, microseconds:

| | filtered copy | gather through the selection |
| --- | --- | --- |
| half the rows kept | 123 | 69 |
| nine tenths kept | 127 | 121 |
| one tenth kept | 120 | 15 |
| half kept, column has nulls | 383 | 95 |
| half kept, column of text | 1048 | 1072 |

Writing the selection is 36 microseconds, down from 304. The 304 was a mispredicted branch per row and it was the real problem: a selection cost nearly twice what copying the column it was meant to save copying cost, so the old "43 against 120 and another 110 to write the positions" was measuring a branch and a core count mismatch as well as a gather.

So a chunk at half selectivity is 36 plus 69 against 123 for a single column, and 36 plus 69 times the columns actually read against 123 times every column, for anything wider. The rest of the list is worth doing.

Start with section 4 of docs/specs/engine/02-execution-model.md and the data model in docs/specs/engine/duckdb/01-data-model.md, then trace the join output path. Implement the remaining per-side selection handling, preserve equivalence between selected and flattened chunks, and run the existing suite and q6 probe to verify correctness and movement costs.

Written by the indexing model from the issue text.