Expand description
Turning a vector of flags into the rows it keeps.
This is the other half of a filter. The comparison kernel produces a vector of booleans fast, and
then something has to turn that vector into the positions that survived, which is what an
operator hands downstream. Reading the flags back out one rudb_common::Value at a time
undoes the comparison kernel’s work and then some: on a two million row table a comparison that
costs under a nanosecond a row was followed by a read that cost twenty seven.
§Why the loop has no branch in it
The obvious loop is if kept { push(index) }, and the branch in it is unpredictable by
construction. A filter that keeps every row or no rows predicts perfectly and is also a filter
nobody needed; the filters that matter keep some rows, and which rows is exactly the thing the
data decides rather than the code. A mispredict is somewhere between fifteen and twenty cycles,
so at thirty percent selectivity the branch alone can cost more than everything else in the loop.
So every row writes its own index at the current length and only a row that is kept moves the
length on. The write is unconditional and lands in the same cache line most of the time, the
addition is of a zero or a one, and there is no branch for a predictor to get wrong. That is why
rudb_vector::Selection::from_indices exists: the buffer is filled and counted here and handed
over whole, rather than being pushed into one position at a time with a capacity check per row.
A conjunct that is not the first one does not start from a range of rows, it starts from what
the conjuncts before it left, which is what refine is for. Most conjuncts never get here at
all because crate::compare::refine threads the selection into the comparison itself and
produces the rows directly, and this one catches the conjuncts that are not comparisons.
Three valued logic is what makes this a kernel rather than a line. A filter keeps a row when the
predicate is true, and null is not true, which is what makes WHERE x <> 5 leave out the rows
where x is null. So a row is kept when its flag is set and its validity bit is set, and the
second half of that is the reason the null path reads a word of the mask at a time rather than
asking the vector per row.