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 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 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_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. A scan over a page where the format guarantees UTF-8 wants to validate the page once instead of once per string, which is a pass the layer three reader makes and is not something this type can do on its behalf.

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 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.

Trait Implementations

impl Clone for StringColumn

fn clone(&self) -> StringColumn

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() -> StringColumn

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 !=.