Struct Vector 

pub struct Vector { /* private fields */ }

A type, a length, a validity representation and some data.

Implementations

impl Vector

pub fn flat(ty: LogicalType, data: Data) -> Result<Self>

A flat vector of data, all valid.

Errors

If the data’s physical layout is not the one the type calls for. That check is here rather than left to the caller because a vector whose type and layout disagree is a wrong answer waiting to be read out, and it costs one comparison at construction to prevent.

pub fn from_values(ty: LogicalType, values: &[Value]) -> Result<Self>

A flat vector built from single values, with the nulls among them turning into validity.

The slow way in, and the only way in that anything outside this crate has. It is what an INSERT, a VALUES clause and a test build a column with, all of which arrive holding values rather than a run of i32. Nothing on a scan path calls it: a scan produces a run of data directly and hands it to Self::flat.

Errors

If a value is not one the type can hold, or if the type is one that cannot be stored flat yet, which today means the nested types.

pub fn constant(ty: LogicalType, value: Value, len: usize) -> Self

A vector of len copies of one value.

Costs one value regardless of the length, which is what makes a literal in a predicate free and what makes a projection of a constant free.

pub fn sequence(start: i64, step: i64, len: usize) -> Self

A vector of len values starting at start and stepping by step.

This is what a row identifier column is, and it costs sixteen bytes rather than eight kilobytes. A scan that produces row ids for a later fetch produces one of these.

pub fn dictionary(codes: Vec<u32>, values: Vector) -> Result<Self>

A vector of codes into a smaller vector of distinct values.

The form the whole M3 thesis rests on. A dictionary vector handed to a group by is an integer column, and an aggregate over one is an aggregate over integers no matter what the logical type says.

A dictionary over a dictionary is composed into one level here rather than left as two, so the form has a depth of one always and a kernel that reads Self::dictionary_parts is reading the values rather than another layer of codes. Two filters over the same chunk build the second case and four conjuncts pushed down separately build four of it.

The cost of leaving them stacked turned out to be a cliff rather than a slope. Every loop in rudb-kernels reaches for the values behind the codes with Self::data, a dictionary pointing at a dictionary has no data to hand back, so the second level does not make the kernels slower, it turns them off and drops the work onto the row at a time path that exists to be correct rather than fast. Measured on server3 over a chunk of two numeric columns and a consumer of two vectorized passes, one level reads at 3.5 nanoseconds a row and two levels at 104, and the third and fourth levels cost almost nothing more because the first one had already given up everything there was to give. Composing is one pass over the outer codes, which the range check above is already making.

The one dictionary that is not composed past is one carrying a validity of its own. A dictionary is built all valid and only Self::with_validity can change that, so such a vector is saying that its nulls are at this level rather than in the values it points at, and composing past it would drop them.

Errors

If any code is past the end of the value vector.

pub fn runs(ends: Vec<u32>, values: Vector) -> Result<Self>

A vector of runs, one value each, with the row each run ends at.

ends is exclusive and strictly increasing, so run i covers the rows from ends[i - 1] to ends[i] and run zero starts at nothing. The length of the vector is the last end.

The depth is one, the same way a dictionary’s is, and for a sharper reason. Every kernel that wants runs wants the value of a run without another search, and a run length vector over a run length vector turns one search into two and then into three. Rather than compose, this refuses: nothing in the engine builds a stacked one, because Self::run_encoded only ever reads a flat body, so a stacked one is a caller doing something by hand and the useful answer is to say so rather than to quietly do a pass of work they did not ask for.

A run over a dictionary is fine and is not that case. The two forms answer different questions and a column that is both clustered and low cardinality genuinely wants both.

Errors

If there is not exactly one value per run, if the ends do not increase, or if the values are themselves run length encoded.

pub fn run_encoded(&self) -> Result<Self>

The same values as runs, when there are few enough runs for that to be smaller.

Costs one pass over the column to find out, which is why this is a call somebody makes rather than something a constructor does. The decision is the same arithmetic every time: a row in flat form costs one value, a run costs one value plus the four bytes of its end, so runs are smaller once there are fewer than about half as many runs as rows, and the narrower the column the more runs it takes. RUNS_PAY_AT is that ratio, written down rather than spelt into an if, because it is the number a sweep will want to move.

Only a flat body is looked at. A constant and a sequence are already one value and two numbers, so there is nothing to win, and a dictionary that is also clustered is a real case that wants its codes run length encoded rather than its values, which is a different function and not this one.

Two adjacent nulls are one run. Two adjacent equal values with a null between them are three, because the null is a value of the column as far as anything reading it is concerned.

Errors

If the type has no flat layout, which today means the nested types.

pub fn packed( ty: LogicalType, words: Vec<u64>, width: u32, base: i128, len: usize, ) -> Result<Self>

A vector of len integers packed width bits each, every one an offset from base.

The way in for a reader that already has the packed bits, which is what a column file holds and what a network frame carries. Nothing unpacks on the way in, so a scan of a packed column hands the bits straight to the chunk and the cost of the form is paid by whoever reads a value rather than by the scan.

The range check is on the two ends rather than on every code, which is the whole check. A code is between zero and 2^width - 1 by construction, so if base and base + 2^width - 1 both fit the column’s layout then every value does, and that is two comparisons instead of one per row.

Errors

If the type is not one of the integer layouts, if the width is not between one and PACKED_WIDTH_MAX, if there are not enough words for the length, or if either end of the range would not fit the type.

pub fn bit_packed(&self) -> Result<Self>

The same values bit packed, when the range of the column makes that smaller.

Costs one pass to find the range and one to write the bits, which is why this is a call somebody makes rather than something a constructor does. It is the counterpart of Self::run_encoded and the decision has the same shape: a row flat costs the width of its layout, a row packed costs the bits the column’s range needs, and the form is worth having only when the second is a good deal smaller than the first. PACKING_PAYS_AT is that ratio, written down rather than spelt into an if, because it is the number a sweep will want to move.

Only a flat integer body is looked at. A constant and a sequence are already smaller than any packing of them, a dictionary’s codes are the thing that would want packing rather than its values, and a float has no range to pack into since the bits of an f64 are not an integer that arithmetic on the column agrees with.

The range is taken over every slot including the null ones, which hold a zero. A column of large values with one null in it therefore packs a range that reaches down to zero and comes out wider than it needed to be. The alternative is a pass that consults the validity per slot to find the range and a second rule for what to write into a null slot, and this form exists to make reads cheap rather than to squeeze the last bit out of a sparse column.

A column whose values are all the same packs to nothing at all, and rather than invent a zero bit code this declines and leaves it to Self::run_encoded, which turns that column into one run and is smaller than any packing of it.

Errors

If the packed bits and the length disagree, which would be a bug here rather than a caller doing something wrong.

pub fn with_validity(self, validity: Validity) -> Self

The same vector with a different validity.

pub fn logical_type(&self) -> &LogicalType

What kind of values these are.

pub fn len(&self) -> usize

How many values there are.

pub fn is_empty(&self) -> bool

Whether there are no values.

pub fn footprint(&self) -> usize

How many bytes of memory this vector is holding.

What the memory limit charges for it. A constant and a sequence hold one value and two numbers however long they are, which is the point of both forms, so the number here is the form’s cost and not the column’s width times its length.

A dictionary counts its values in full, and two vectors sharing one dictionary each report all of it. That over counts, deliberately: working out that two operators are looking at the same Arc means threading identity through the accounting, and a limit that over counts refuses a query that would have fit while a limit that under counts lets one through that does not. The first is a worse answer to give and the second is a worse thing to be.

pub fn validity(&self) -> &Validity

Which of the values are not null.

pub fn form(&self) -> Form

Which physical form this vector is in.

pub fn data(&self) -> Option<&Data>

The data, for a flat vector, and None for any other form.

A kernel that wants a slice asks for it and takes the flat path if it gets one. A kernel that can do better on a constant or a dictionary checks Self::form first.

pub fn constant_value(&self) -> Option<&Value>

The one value, for a constant vector, and None for any other form.

A kernel comparing a column against a literal wants the literal once rather than 1024 times, and Self::value_at on a constant clones it on every call because it has to be able to hand back a Value for any form. This is the accessor that lets the specialized path hoist the clone out of the loop.

pub fn dictionary_parts(&self) -> Option<(&[u32], &Self)>

The codes and the values, for a dictionary vector, and None for any other form.

The reason a kernel needs this rather than reading the dictionary through Self::value_at is the entire argument for the form existing. A filter against a dictionary column of 1024 rows and 40 distinct values is 40 comparisons and 1024 lookups, not 1024 comparisons, and there is no way to write that loop without seeing the codes.

Note what the validity of the returned vector means. A dictionary keeps its nulls in the vector it points at, and the dictionary’s own validity says nothing about them, so a caller deciding whether row i is null has to ask the value vector about codes[i] rather than asking this vector about i. Self::flatten has the same note on it for the same reason, because getting this wrong is a null that survives being selected and comes out as a zero.

pub fn run_parts(&self) -> Option<(&[u32], &Self)>

The run ends and the run values, for a run length vector, and None for any other form.

The ends are exclusive and increasing, and there is exactly one value per run, so a kernel that wants to walk this walks the pairs and never asks which run a row is in. That is the whole argument for the form: an aggregate over a clustered column is one multiply per run instead of one add per row, and there is no way to write that loop without seeing the ends.

The nulls are in the values, the way a dictionary’s are, so a caller deciding whether row i is null asks the value vector about the run rather than asking this vector about i.

pub fn positions(&self) -> Option<(Cow<'_, [u32]>, &Self)>

Where each row’s value is, for the two forms that keep their values somewhere else.

A dictionary and a run length vector are the same shape seen from a kernel: a run of positions and a vector to read them out of. The difference is that a dictionary stores the positions and a run length vector works them out, and a kernel writing values[at[row]] does not care which. So every specialization written against Self::dictionary_parts covers both forms by asking this instead, and the day a third form with an indirection arrives it covers that one too without any of those kernels being reopened.

The run length side costs an allocation of one position per row and a pass to fill it, which is the same four bytes a row a dictionary was already carrying and is paid once per kernel call rather than once per row. That is the price of this being one accessor rather than a second arm in eighteen kernels, and it is not the last word: a kernel that wants a run at a time reads Self::run_parts and pays nothing, which is the specialization this makes it possible to skip writing until a sweep says it is worth it.

pub fn packed_parts(&self) -> Option<Packed<'_>>

The bits and what they mean, for a bit packed vector, and None for any other form.

What a kernel needs to stay in code space. A comparison against a literal is the case that pays: column > 900 over a column packed from a base of 40 is code > 860, which is the same shift and mask the read was going to do anyway and no unpacking at all, and a literal outside the packed range answers the whole vector without reading a bit of it. None of that can be written without seeing the width and the base.

pub fn sequence_parts(&self) -> Option<(i64, i64)>

The start and the step, for a sequence vector, and None for any other form.

pub fn value_at(&self, index: usize) -> Value

The value at index, as a single value.

This is the slow path on purpose. It is what a result set is read out with and what a test asserts on, and an operator that calls it per row is an operator that has already lost the argument the vector interface exists to win.

pub fn text_at(&self, index: usize) -> Option<&str>

The text at index, borrowed rather than copied.

Self::value_at on a VARCHAR column allocates a String per call, and a group by that reads a string column keys on one string per input row. This hands back the bytes where they already are, so a caller with somewhere to put them does not go to the allocator at all.

None for a null, for an index past the end, for a column that is not VARCHAR, and for the constant and sequence forms, whose values are not stored per position. A caller that gets None has to fall back to Self::value_at, which is correct for all of those.

pub fn iter(&self) -> impl Iterator<Item = Value> + '_

Every value in order, as single values.

pub fn slice(&self, at: usize, len: usize) -> Result<Self>

A contiguous run of the values, in the form they are already in.

This is the cut Self::gather cannot do. A gather walks a dictionary to its leaf and copies, so gathering a piece of a dictionary encoded column hands back a flat one, and a caller that only wanted the first thousand rows of a page has silently paid for a copy and thrown the dictionary away. A group by over a dictionary encoded column is the case that cares, and it is most of ClickBench.

So each form is cut as itself. A dictionary keeps its dictionary and slices its codes, a sequence stays arithmetic with its start moved along, a constant stays a shorter constant, and a flat body is the one that genuinely has to copy its range.

The dictionary itself is shared rather than copied, so a cut is the codes and nothing else. It used to be copied, and on a read of a ClickBench partition that copy was ten percent of the cycles: a page holds one dictionary and is cut into chunk sized pieces, so the whole dictionary was copied once per chunk to be read the same way each time.

Errors

If the range runs past the end of the vector, or if the type has no flat layout and the body is one that has to be copied.

pub fn flatten(&self) -> Result<Self>

The same values in flat form.

Flattening a vector that is already flat is free. Flattening any other form costs a copy, which is exactly why the other forms exist and why nothing on the hot path should call this. It is here for the operators that genuinely cannot do better and for the tests that check the other forms against it.

A call that copies counts itself against Cause::Flatten, because a flatten on a hot path is the most expensive thing in this crate and the only way to find one is to have the number. A call on a vector that is already flat does not count, since it neither copies nor gives anything up.

Errors

If the type is one this crate cannot store flat yet, which today means the nested types.

pub fn gather(&self, indices: &[u32]) -> Result<Self>

The values at the given positions, copied, in a form that does not point back at this vector.

This is the copying counterpart to Self::dictionary, and the two are the two halves of the decision spec/07-execution.md section 7.1 describes. Which half is right is measured rather than argued, and Chunk::compact is where the measurement is written down.

A dictionary chain is walked to its leaf first and the codes composed on the way down, so the copy runs once over the data rather than once per level, and a position that is null at any level comes out null here. The copy is a typed loop per physical layout rather than a Value per row, which is the whole point of it and is what Self::flatten now goes through too.

Errors

If the type has no flat layout, which today means the nested types.

Trait Implementations

impl AsRef<Vector> for Vector

So that a kernel can take its operands as either a list of vectors or a list of references.

A caller that built a Vec<Vector> and a caller whose operands are already somewhere else, in a chunk or in an evaluator’s scratch, want the same kernel. Without this the second kind has to clone every operand into a Vec to satisfy the signature, and a clone of a vector is a copy of the whole column, so the type would be charging real memory traffic for nothing.

fn as_ref(&self) -> &Vector

Converts this type into a shared reference of the (usually inferred) input type.

impl Clone for Vector

fn clone(&self) -> Vector

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Vector

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl PartialEq for Vector

fn eq(&self, other: &Vector) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl StructuralPartialEq for Vector