Struct StringColumn 

pub struct StringColumn { /* private fields */ }

A column of strings: the views, and the one arena the long ones live in.

The arena is append only, so an offset recorded in a view stays correct for the life of the column even though the arena’s address does not. That is the property a Vec<u8> has and a raw pointer into it does not, and it is the reason a view holds an offset.

This was a Vec<Vec<u8>> of fixed size blocks, which meant reading one long string was two dependent loads, the outer vector’s element to find the block’s data pointer and then the bytes. One arena makes it one, from a base the compiler can keep in a register across a row loop, and it deletes the case where a string longer than a block needed a block of its own. On server3, over a chunk of 1024 strings, comparing a column against a literal went from 14.9 nanoseconds a row to 13.2 at 40 bytes a string and from 14.2 to 12.9 at 120, gathering half the rows from 29.5 to 25.3 and from 36.9 to 29.1, and building the column from 12.0 to 8.9 at 40 bytes.

The one number that got worse, and what it actually is

Building a column whose payload passes 128 KiB, which at 1024 rows means strings averaging more than 128 bytes, went the other way: 14.6 nanoseconds a row to 41.0. That is not the copy and it is not the doubling, it is glibc. An allocation that size comes from mmap rather than the heap, so it is handed back to the kernel when the column is dropped and the next chunk faults every page of it in again, while sixteen KiB blocks come back off a free list already faulted. Run the same benchmark with MALLOC_MMAP_THRESHOLD_ raised and the arena builds that column in 9.6 nanoseconds a row against the blocks’ 16.2, so the design is not what is slow there.

The fix is that a chunk’s payload should come from a pool the engine owns rather than from malloc per chunk, which is the buffer manager at layer three and is where this belongs. Self::reserve_bytes is the part that is available now, and it recovers a quarter of it.

Equality is about the strings and not about the arena

Self::over means two columns holding exactly the same strings can hold completely different arenas, because one of them was built by copying the strings in and the other was built over a page that already had them somewhere in it with other strings in between. Derived equality would call those two columns different, and every test in the workspace that compares two vectors would then be asserting on how a column was built rather than on what is in it. So equality is the strings, position by position, which is the only definition that survives the seam.

Implementations

impl StringColumn

pub fn footprint(&self) -> usize

How many bytes of memory this column is holding.

The views and the arena. A short string lives inside its view and costs nothing beyond it, which is the whole reason the representation exists, so a column of short strings costs sixteen bytes a string and a column of long ones costs sixteen plus the bytes themselves.

pub fn new() -> Self

An empty column.

pub fn with_capacity(capacity: usize) -> Self

An empty column with room for capacity strings.

pub fn over(arena: Buffer<u8>) -> Self

A column with no strings in it yet, over an arena that already holds bytes.

The seam spec/engine/03-data-plane.md section 3.5 asks for. Without it the only way in is Self::push, which copies, so a scan reading a Parquet page of strings copies every byte of the page into an arena and the query then reads the copy. With it the page is the arena: the scan hands the bytes over once, records where each string starts with Self::push_in_place, and nothing is copied but the views.

It is useful today, because a reader that already has the page in a Vec<u8> can move it in rather than copy out of it. It matters at layer three, when the Buffer is the pinned page itself and the move is not even that.

Appending with Self::push afterwards still works and still appends to the arena. That is the case to keep away from once a real page is in here, because writing through a borrowed buffer copies it, which is Buffer::to_mut and is the whole page.

pub fn into_page(self) -> Self

This column with its arena held as a page, so that a copy of it does not copy the bytes.

The views are still copied, because they are a Vec and a run of them is what a cut of the column is. Sixteen bytes a row rather than every byte of every string, which is the same split the StringView form already makes for the same reason.

pub fn from_parts(views: Vec<StringView>, arena: Buffer<u8>) -> Self

A column from views that already point into arena.

The way back in from Self::into_parts, for the caller that took a column apart to hold the payload once and the views many times and now wants a column again. Nothing here checks that a view points inside the arena, for the same reason Self::bytes answers None rather than panicking when one does not: a view that points nowhere reads as no bytes, which is the empty string, and that is a wrong answer rather than an unsound one.

pub fn viewing(&self, at: impl Iterator<Item = usize>) -> Option<Self>

The values at at, over this column’s arena rather than over a copy of the bytes.

What a cut, a gather and a flatten of a column whose payload is a page all want. A view says where its bytes are, so putting the views in a different order or keeping only some of them leaves every one of them pointing at the same bytes it pointed at before, and the answer is the same column of strings the copying version builds. Sixteen bytes a row move and the payload does not, which is the split Self::into_page exists to make and is what the StringView form of a vector already makes for itself.

None when the arena is this column’s own rather than a page, because then there is no sharing to be had: cloning an owned arena copies every byte of it, including the bytes of every value the caller did not ask for, and the copying version is both smaller and faster. A producer that means its payload to be read many times says so with Self::into_page.

A position this column does not have comes back as the empty string, which is what the copying version writes for a position that resolved to nowhere.

pub fn len(&self) -> usize

How many strings are in the column.

pub fn is_empty(&self) -> bool

Whether the column has no strings in it.

pub fn views(&self) -> &[StringView]

The views, for a kernel that wants to compare prefixes without reading any payload.

pub fn push(&mut self, text: &str) -> usize

Appends a string and returns its index.

pub fn push_from(&mut self, source: &Self, index: usize) -> usize

Appends the string at index of another column, and returns its index here.

This is what a gather and a slice over a string column want, and it is worth having next to Self::push because that one takes a &str and the only way to get one out of a column is Self::get, which validates UTF-8. Validating there is a waste on this path twice over: the bytes were validated on the way into the source column, and a copy cannot make valid bytes invalid. Reading a ClickBench partition spent eight percent of its cycles on that second validation.

A position past the end of the source appends the empty string, which is what the copy loop wants for a row that resolved to nowhere.

pub fn push_bytes(&mut self, bytes: &[u8]) -> usize

Appends bytes that are not required to be text, and returns their index.

What a BLOB is stored through. The column is the same column either way, because a string here is already a length and some bytes and text is the reading rather than the storage, so a blob costs nothing extra and shares every kernel that works on views. What it does not share is Self::get, which answers None for bytes that are not a string, so a caller holding blobs reads them with Self::bytes.

pub fn push_in_place(&mut self, offset: usize, len: usize) -> Result<usize>

Records a string that is already in the arena, and returns its index.

The half of the seam that does the work. Self::over puts the page in, this says where in it a string is, and between them a column of long strings is built without the payload being touched at all.

A string short enough to sit inside a view is copied into the view, which is at most twelve bytes and is what makes it readable without going near the arena at all. Everything longer keeps its bytes where they are and the view records the offset.

Errors

If the range is not inside the arena, or if the bytes are not valid UTF-8. The validation is the one cost this seam does not remove, and it is here rather than skipped because Self::get hands back a &str and a column that cannot produce one for a string it claims to hold is a wrong answer rather than a slow one. Skipping it is not an option a DuckDB compatible reader has either: DuckDB reads a Parquet byte array that is not UTF-8 and throws Invalid Input Error, so a reader that let it through would disagree about which files are readable at all.

pub fn push_bytes_in_place( &mut self, offset: usize, len: usize, ) -> Result<usize>

The same seam for a column whose bytes were never claimed to be text.

What a BLOB or a BIT page is read through. Self::push_in_place validates because the caller is promising a &str later and a column that cannot produce one is a wrong answer. A blob promises nothing of the sort: its whole point is that the bytes are bytes, so the validation there is not a check that has been skipped, it is a check about a claim nobody made. Self::get answers None for a row put in this way and Self::bytes answers it, which is the same split Self::push_bytes already has.

Errors

If the range is not inside the arena.

pub fn arena(&self) -> &[u8]

The bytes the long strings live in.

For a column over a page this is the page, including whatever of it no view points at. The offsets in the views are offsets into exactly this, which is what makes them meaningful to a reader that put the page here in the first place.

pub fn into_parts(self) -> (Vec<StringView>, Buffer<u8>)

The views and the arena, taken out of the column rather than borrowed from it.

What the string view form of a vector is built from. It takes self because the point of that form is that the arena moves into an Arc and is never copied again, and a method that borrowed would have to clone every byte of the arena to hand one over.

pub fn bytes(&self, index: usize) -> Option<&[u8]>

The bytes at index, or None past the end.

This is what a comparison, a hash and an equality check all actually want, and it is worth having separately from Self::get because that one validates UTF-8 and they do not need it. Everything in a column arrived through Self::push, which takes a &str, so the bytes are valid either way and the validation is a scan of the payload that changes no answer. On a varchar filter it was measured at most of the per row cost.

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

The string at index, or None past the end.

pub fn iter(&self) -> impl Iterator<Item = &str>

Every string in order.

pub fn heap_bytes(&self) -> usize

Total bytes of payload held in the arena, which is what the memory accounting wants.

For a column over a page it is the page and not the part of it any view points at, which is the right answer for accounting, because the page is what is resident.

pub fn reserve_bytes(&mut self, bytes: usize)

Room for bytes of payload, taken in one allocation rather than as the strings arrive.

A builder that knows the total byte count, which a scan reading a page and a gather copying a column both do, saves the doubling entirely. Nothing is wrong without it, which is why it is a hint and not a constructor argument.

Not for a column built by Self::over on a page it shares, because reserving writes and a write through a shared buffer copies the whole page out first. Such a column is not appended to anyway: its strings are already in its arena and Self::push_in_place records where.

pub fn reserve_views(&mut self, count: usize)

Room for count more strings, taken in one allocation rather than as they arrive.

The views and not the payload, which is the half Self::reserve_bytes does not cover and is the only half that matters to a column built by Self::over, whose payload is already there. A Parquet page of a hundred thousand strings is one and three quarter megabytes of views, and growing that from nothing is twenty allocations and a copy of everything written so far each time.

Trait Implementations

impl Clone for StringColumn

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for StringColumn

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

Formats the value using the given formatter.

impl Default for StringColumn

fn default() -> Self

Returns the “default value” for a type.

impl Eq for StringColumn

impl<'a> Extend<&'a str> for StringColumn

fn extend<T: IntoIterator<Item = &'a str>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: T)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<'a> FromIterator<&'a str> for StringColumn

fn from_iter<T: IntoIterator<Item = &'a str>>(iter: T) -> Self

Creates a value from an iterator.

impl PartialEq for StringColumn

Two columns are equal when they hold the same strings in the same order, whatever their arenas look like.

See the note on StringColumn. Comparing the views is not enough on its own either, because two views of the same long string at different offsets in different arenas are different views, so the comparison is length, then view by view with the payload read for the ones that are not inline. The prefix inside the view is what makes that cheap: a pair that differs in the first four bytes or in the length is settled without either arena being touched.

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

Equality operator ==.

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

Inequality operator !=.