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.

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

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

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

Equality operator ==.

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

Inequality operator !=.

impl StructuralPartialEq for StringColumn