When a few variables belong together, we put them in a struct. Programmers do this automatically without thinking about it much.
And most of the time it's the right choice.
Structs are simple, fast, and predictable. But once in a while they break down. This is the story of one of those cases.
One of our customers reported a strange performance problem. A new use case processed about the same amount of data as their existing pipelines, but it ran much slower.
That was unusual. Our engine normally keeps up with the data customers send. So we felt compelled to take a closer look.
In Feldera, users define input data as SQL tables and output data as SQL views. We compile the SQL in between into a Rust program that incrementally evaluates the query.
Each row of a table becomes a Rust struct.
Here is an (anonymized) excerpt from the workload that triggered the slowdown:
create table user (
anon0 boolean NULL,
anon1 boolean NULL,
anon2 boolean NULL,
anon3 boolean NULL,
anon4 VARCHAR NULL,
anon5 VARCHAR NULL,
anon6 VARCHAR NULL,
anon7 INT NULL,
anon8 SHOPPING_CART NULL,
anon9 BOOLEAN NULL,
anon10 BOOLEAN NULL,
anon11 BOOLEAN NULL,
anon12 VARCHAR NULL,
anon13 VARCHAR NULL,
anon14 VARCHAR NULL,
anon15 VARCHAR NULL,
anon16 VARCHAR NULL,
anon17 VARCHAR NULL,
anon18 VARCHAR NULL,
anon10 VARCHAR NULL,
anon11 VARCHAR NULL,
# ...
# the list goes on and on...
# ...
anon715 VARCHAR NULL,Our SQL compiler turns this into a Rust struct:
#[derive(Clone, Debug, Eq, PartialEq, Default, PartialOrd, Ord)]
pub struct struct_832943b1fac84177 {
field0: Option<bool>,
field1: Option<bool>,
field2: Option<bool>,
field3: Option<bool>,
field4: Option<SqlString>,
field5: Option<SqlString>,
field6: Option<SqlString>,
field7: Option<i32>,
field8: Option<struct_1b1bf3264e30bced>,
field9: Option<bool>,
field10: Option<bool>,
field11: Option<bool>,
field12: Option<SqlString>,
// ...
// the list goes on and on...
// ...
field715: Option<SqlString>,This struct has hundreds of fields, almost all of them optional.
That comes directly from SQL. Nullable columns become Option<T> in Rust.
So this workload produced rows with hundreds of optional fields.
Let’s inspect the memory layout of a smaller version of the struct (just the first 8 fields).
I used the memoffset crate to dump the layout:
(size=40B, align=8)
Offset
0x00 ┌──────────────────────────────────────────────┐
│ field7: Option<i32> │
│ size 8, align 4 │
│ bytes: [discriminant + i32 (+ padding)] │
0x08 ├──────────────────────────────────────────────┤
│ field4: Option<SqlString> (8B) │
│ SqlString is 8B (ArcStr pointer) │
0x10 ├──────────────────────────────────────────────┤
│ field5: Option<SqlString> (8B) │
0x18 ├──────────────────────────────────────────────┤
│ field6: Option<SqlString> (8B) │
0x20 ├──────────────────────────────────────────────┤
│ field0: Option<bool> (1B) │
0x21 ├──────────────────────────────────────────────┤
│ field1: Option<bool> (1B) │
0x22 ├──────────────────────────────────────────────┤
│ field2: Option<bool> (1B) │
0x23 ├──────────────────────────────────────────────┤
│ field3: Option<bool> (1B) │
0x24 ├──────────────────────────────────────────────┤
│ padding (4B) rounds total size to mult. of 8 │
0x28 └──────────────────────────────────────────────┘A few things stand out:
- The Rust compiler reordered the fields. That is normal for Rust structs.
Option<bool>andOption<SqlString>are essentially free. Rust uses niche optimizations to encodeNonewithout extra space. For example,SqlStringis anArcStrpointer, which Rust guarantees is never null (viaNonNull).- The only real overhead comes from
Option<i32>, the unpackedOption<bool>values, and the padding at the end.
Overall this layout is already quite efficient. Even with several Options, the struct only takes 40 bytes.
So the in-memory representation is not the problem.
Feldera is almost always used for datasets that don’t fit in memory.
So these structs eventually get written to disk.
That means we need to serialize them.
We use rkyv, a zero-copy serialization framework for Rust. With rkyv, serialization is usually just a few derive macros away:
#[derive(Debug, rkyv::Archive, rkyv::Serialize, rkyv::Deserialize)]
pub struct struct_832943b1fac84177 {
field0: Option<bool>,
field1: Option<bool>,
field2: Option<bool>,
field3: Option<bool>,
field4: Option<SqlString>,
field5: Option<SqlString>,
field6: Option<SqlString>,
field7: Option<i32>
}Under the hood, rkyv generates an archived representation of the struct.
If we inspect the expanded code (cargo expand), we find something like this:
/// An archived [`struct_832943b1fac84177`]
pub struct Archivedstruct_832943b1fac84177 {
/// The archived counterpart of [`struct_832943b1fac84177::field0`]
field0: rkyv::option::Option<bool>,
/// The archived counterpart of [`struct_832943b1fac84177::field1`]
field1: rkyv::option::Option<bool>,
/// The archived counterpart of [`struct_832943b1fac84177::field2`]
field2: rkyv::option::Option<bool>,
/// The archived counterpart of [`struct_832943b1fac84177::field3`]
field3: rkyv::option::Option<bool>,
/// The archived counterpart of [`struct_832943b1fac84177::field4`]
field4: rkyv::option::Option<rkyv::string::ArchivedString>,
/// The archived counterpart of [`struct_832943b1fac84177::field5`]
field5: rkyv::option::Option<rkyv::string::ArchivedString>,
/// The archived counterpart of [`struct_832943b1fac84177::field6`]
field6: rkyv::option::Option<rkyv::string::ArchivedString>,
/// The archived counterpart of [`struct_832943b1fac84177::field7`]
field7: rkyv::option::Option<i32>
}A few things are happening here:
- Every struct gets its own
Archivedcounterpart that defines the serialized layout. - The transformation applies recursively to every field.
- Primitive types (bool, i32, etc.) archive to themselves.
- More complex types use special archived versions such as ArchivedOption and ArchivedString.
So far this all looks reasonable, but it’s also where things start to go awry.
If we look at how ArchivedString is implemented, it looks roughly like this:
static const INLINE_CAPACITY: usize = 15;
#[derive(Clone, Copy)]
#[repr(C)]
struct InlineRepr {
bytes: [u8; INLINE_CAPACITY],
len: u8,
}
/// An archived string representation that can inline short strings.
pub union ArchivedStringRepr {
out_of_line: OutOfLineRepr,
inline: InlineRepr,
}This layout is clever. Short strings are stored inline, avoiding an allocation.
But it breaks an important Rust optimization.
Earlier we saw that Option<T> can sometimes store None for free by using a niche value (for example, a null pointer). ArchivedString no longer has such a niche. All byte patterns are now valid, because the inline representation uses the entire buffer.
That means Option<ArchivedString> must store an explicit discriminant.
So the Option is no longer free.
This struct we saw earlier had 700+ of optional fields.
In Rust you would never design a struct like this. You would pick a different layout long before reaching 700 Options.
But SQL schemas often look like this. Columns are nullable by default, and wide tables are common.
That becomes a problem once we serialize them. Here is the archived layout for the smaller 8-field struct we looked at earlier:
• struct_...::Archived (rkyv size_64)
(size=88B, align=8)
Offset
0x00 ┌──────────────────────────────────────────────┐
│ field4: Archived<Option<SqlString>> │
│ size: 24B │
| (16 bytes SqlString, 8 bytes Option) │
0x18 ├──────────────────────────────────────────────┤
│ field5: Archived<Option<SqlString>> │
│ size: 24B │
0x30 ├──────────────────────────────────────────────┤
│ field6: Archived<Option<SqlString>> │
│ size: 24B │
0x48 ├──────────────────────────────────────────────┤
│ field7: Archived<Option<i32>> │
│ size: 8B │
0x50 ├──────────────────────────────────────────────┤
│ field0: Archived<Option<bool>> │
│ size: 2B │
0x52 ├──────────────────────────────────────────────┤
│ field1: Archived<Option<bool>> │
│ size: 2B │
0x54 ├──────────────────────────────────────────────┤
│ field2: Archived<Option<bool>> │
│ size: 2B │
0x56 ├──────────────────────────────────────────────┤
│ field3: Archived<Option<bool>> │
│ size: 2B │
0x58 └──────────────────────────────────────────────┘Notice the strings: 16 bytes for the archived string, 8 bytes for the Option discriminant. Even if the string is empty or if the value is None.
So the archived struct ends up being 88 bytes. The in-memory version was 40 bytes. More than 2x larger.
The fix is simple: we stop storing Option<T> and instead we store a bitmap that records which fields are None.
During serialization the layout looks like this:
Each bit in the bitmap corresponds to one field:
0 → field is None
1 → field is present
When we deserialize a row we check the bitmap first.
- If the bit is
0, the field isNone. - If the bit is
1, we read the value and wrap it inSome(...).
Finding None
To use the bitmap trick we need to answer one question during serialization:
Is this field None?
That sounds easy, but the serializer is generic over some type T.
Rust does not have reflection, so we cannot simply ask whether T is an Option.
Fortunately we control the types that appear in these structs.
So we introduce a small helper trait:
pub trait NoneUtils {
type Inner;
fn is_none(&self) -> bool;
fn unwrap_or_self(&self) -> &Self::Inner;
fn from_inner(inner: Self::Inner) -> Self;
}The idea is simple: treat Option<T> and T uniformly.
Option<T> exposes whether it is None and gives access to the inner value:
impl<T> NoneUtils for Option<T> {
type Inner = T;
fn is_none(&self) -> bool {
self.is_none()
}
fn unwrap_or_self(&self) -> &Self::Inner {
self.as_ref()
.expect("NoneUtils::unwrap_or_self called on None")
}
fn from_inner(inner: Self::Inner) -> Self {
Some(inner)
}
}Everything else behaves as if it is always present:
impl<T> NoneUtils for T {
type Inner = T;
fn is_none(&self) -> bool {
false
}
fn unwrap_or_self(&self) -> &Self::Inner {
self
}
fn from_inner(inner: Self::Inner) -> Self {
inner
}
}With this trait the serializer can treat every field the same way.
It asks is_none() to update the bitmap, then serializes with unwrap_or_self() if the value exists.
Now we have the building block we need: NoneUtils.
It lets the serializer ask two questions for any field:
- is this value
None? - if not, give me the inner value
That is enough to change the serialized layout of the struct.
The two new steps for serializing are:
- Write a bitmap that records which fields are
None. - Serialize the fields without their
Optionwrappers.
Conceptually the layout looks like this:
| bitmap | field0 | field1 | field2 | field3 | ... |The bitmap stores one bit per field:
bit = 1 → value present
bit = 0 → value was NoneThe fields themselves are stored without Option:
During serialization we call: value.unwrap_or_self()
This removes the Option overhead from the archived layout.
Deserialization reverses the process.
We consult the bitmap to reconstruct each field:
if bitmap[i] == 0
return None
else
read value
return Some(value)Again, NoneUtils hides the details via T::from_inner(inner).
The code that generates all this logic is produced automatically by a macro.
The layout with removed Options is compact, simple, and cache-friendly.
But there is another opportunity here: not every row always looks the same. If many fields are NULL, reserving space for every field sequentially wastes space. In this situation we can store only the values that actually exist.
Because field types can have different sizes with variable lengths, we cannot compute their offsets ahead of time.
So the sparse layout keeps an index of relative pointers to the stored values:
| bitmap | ptrs | values... |The bitmap still records which fields are present. The ptrs vector contains a
relative pointer for each present field that points into the value area. When reading a field we first check the bitmap. If the bit is set, we use the pointer to
jump directly to the archived value.
This lets us skip NULL fields entirely while still supporting fast access. For wide SQL tables with many optional columns, this can reduce the row size dramatically.
For tables with hundreds of nullable columns the gains add up. A string that was None or empty would always consume 24 bytes before, but now consumes just 1 bit in the best case.
In the workload that started this investigation we reduced the serialized row size by roughly 2x. Disk IO dropped accordingly. Throughput returned to the level the customer expected.
Rust structs are great.
But they assume something important:
Most fields exist.
SQL tables generally make the opposite assumption:
Most fields might not exist.
If you combine these three things:
- hundreds of nullable columns
- small strings and/or sparse data
- row-oriented storage
The overheads of a plain struct layout start to become a bottleneck.
The fix was surprisingly simple. With rkyv offering lots of flexibiliy here as the serialization framework. We could keep the in-memory struct interface and just change the serialized format which now chooses the best representation (dense vs. sparse) on a per-row basis.
Sometimes the best optimization is not a clever algorithm. Sometimes it is just changing the shape of the data.