None optimization (part 2) #5409

gz · 2026-01-10T22:28:26Z

This changes the way tuples are serialized/deserialized to optimize sparse tuples.

before a TupX<> would be serialized as a struct of

struct ArchivedTupX
  t1: T1
  t2: T2
etc.

The new format is:

struct NewArchviedTup

  bitmap: [u64; len]
  rel_ptrs: ArchivedVec<RelPtrI32>
  <serialized form of all items that are not None (bit in bitmap corresponding to field not set) follows here
   with rel_ptrs pointing to them>

the trade-off is:

if data is sparse, this is great because we reduce a None value to 1bit
if the data is not sparse it adds overhead: (a rel_ptr which is 4 byte per field that is not none + the bitmap which is 8 byte for every 64 tup entries)

some things to consider:

Potential improvements could be to compress the RelPtrI32 further to a I16 (by storing diff from current to next(?))
Some smart way to get rid of rel_ptrs entirely (I doubt it can be done?)
an adaptive serialization/deserialization (only use this format if data is really sparse)

Breaking Changes?

Storage Format / Checkpoints

Increased storage format versions.

Describe Incompatible Changes

We are writing a different storage format for Tup<> types. We ensure it's backward compatible by distinguishing new and old formats using the version in the respective files.

- Stores None's as 1-bit in a bitmap - In case something isn't None, store as the value in a dynamically sized-list Signed-off-by: Gerd Zellweger <mail@gerdzellweger.com>

Signed-off-by: Gerd Zellweger <mail@gerdzellweger.com>

Add code to generate batch files in different formats and makes sure we can read them correctly in the future. Signed-off-by: Gerd Zellweger <mail@gerdzellweger.com>

Copilot

Pull request overview

This PR optimizes the serialization format for tuples containing Option types by implementing a sparse encoding strategy. Instead of storing the full size of each field even when None, the new format uses a bitmap to mark None fields and only serializes non-None values.

Changes:

Implemented bitmap-based sparse tuple serialization for more efficient storage of tuples with many None values
Incremented storage format version from 3 to 4 to support the new tuple encoding
Added backward compatibility layer to deserialize v3 files using the legacy format

Reviewed changes

Copilot reviewed 21 out of 29 changed files in this pull request and generated 8 comments.

Show a summary per file

File	Description
crates/feldera-macros/src/tuples.rs	Core implementation of the new bitmap-based tuple serialization format
crates/dbsp/src/storage/file/format.rs	Incremented VERSION_NUMBER from 3 to 4
crates/dbsp/src/storage/file.rs	Added Deserializer wrapper with version tracking
crates/dbsp/src/storage/file/reader.rs	Updated readers to pass version information for backward compatibility
crates/storage-test-compat/*	New compatibility testing crate with golden file tests
crates/feldera-macros/tests/*	Added comprehensive tests for new tuple serialization

Copilot · 2026-01-10T22:32:05Z

crates/storage-test-compat/src/lib.rs

@@ -0,0 +1,419 @@
+use std::collections::BTreeMap;


Corrected spelling of 'optimziation' to 'optimization' in the PR title.

Copilot · 2026-01-10T22:32:05Z

crates/feldera-macros/tests/compile.rs

+{
+    #[inline]
+    fn eq(&self, other: &Self) -> bool {
+        unsafe { self.get_t0() == other.get_t0() && self.get_t1() == other.get_t1() }


The unsafe block here is unnecessary since get_t0() and get_t1() already contain the necessary unsafe operations internally. The unsafe should be removed to avoid misleading safety implications.

Suggested change

unsafe { self.get_t0() == other.get_t0() && self.get_t1() == other.get_t1() }

self.get_t0() == other.get_t0() && self.get_t1() == other.get_t1()

Copilot · 2026-01-10T22:32:05Z

crates/feldera-macros/tests/compile.rs

+        let t0_cmp = unsafe { self.get_t0().cmp(other.get_t0()) };
+        if t0_cmp != core::cmp::Ordering::Equal {
+            return t0_cmp;
+        }
+        unsafe { self.get_t1().cmp(other.get_t1()) }


The unsafe block is unnecessary here. The get_t0() method already handles unsafe operations internally, and calling cmp() on the returned references doesn't require unsafe.

Suggested change

let t0_cmp = unsafe { self.get_t0().cmp(other.get_t0()) };

if t0_cmp != core::cmp::Ordering::Equal {

return t0_cmp;

}

unsafe { self.get_t1().cmp(other.get_t1()) }

let t0_cmp = self.get_t0().cmp(other.get_t0());

if t0_cmp != core::cmp::Ordering::Equal {

return t0_cmp;

}

self.get_t1().cmp(other.get_t1())

Copilot · 2026-01-10T22:32:06Z

crates/feldera-macros/tests/compile.rs

+        let t0_cmp = unsafe { self.get_t0().cmp(other.get_t0()) };
+        if t0_cmp != core::cmp::Ordering::Equal {
+            return t0_cmp;
+        }
+        unsafe { self.get_t1().cmp(other.get_t1()) }


The unsafe block is unnecessary. Remove it since the comparison of archived values doesn't require unsafe after the references are obtained.

Suggested change

let t0_cmp = unsafe { self.get_t0().cmp(other.get_t0()) };

if t0_cmp != core::cmp::Ordering::Equal {

return t0_cmp;

}

unsafe { self.get_t1().cmp(other.get_t1()) }

let t0_cmp = self.get_t0().cmp(other.get_t0());

if t0_cmp != core::cmp::Ordering::Equal {

return t0_cmp;

}

self.get_t1().cmp(other.get_t1())

Copilot · 2026-01-10T22:32:06Z

crates/dbsp/src/storage/file/reader.rs

                Some(false)
            }
-            VERSION_NUMBER => Some(true),
+            x if x >= 3 => Some(true),


This condition accepts any version >= 3, including future versions that may not exist yet or be incompatible. Change to x if x >= 3 && x <= VERSION_NUMBER to only accept known compatible versions.

Suggested change

x if x >= 3 => Some(true),

3..=VERSION_NUMBER => Some(true),

Copilot · 2026-01-10T22:32:06Z

crates/feldera-macros/src/tuples.rs

+                let version = (deserializer as &mut dyn ::core::any::Any)
+                    .downcast_mut::<::dbsp::storage::file::Deserializer>()
+                    .map(|deserializer| deserializer.version())
+                    .expect("passed wrong deserializer");


The error message "passed wrong deserializer" is unclear. Consider changing to "Deserializer must be of type dbsp::storage::file::Deserializer for version tracking support" to better explain the issue.

Suggested change

.expect("passed wrong deserializer");

.expect("Deserializer must be of type dbsp::storage::file::Deserializer for version tracking support");

Copilot · 2026-01-10T22:32:07Z

crates/feldera-macros/src/tuples.rs

+                    .downcast_mut::<::dbsp::storage::file::Deserializer>()
+                    .map(|deserializer| deserializer.version())
+                    .expect("passed wrong deserializer");
+                if version <= 3 {


The version check should use a named constant instead of the magic number 3. Define const LAST_LEGACY_VERSION: u32 = 3; and use that for clarity and maintainability.

Suggested change

if version <= 3 {

const LAST_LEGACY_VERSION: u32 = 3;

if version <= LAST_LEGACY_VERSION {

Signed-off-by: Gerd Zellweger <mail@gerdzellweger.com>

blp

I looked over this, thanks for making this work. I'm impressed that rkyv was flexible enough.

blp · 2026-01-12T21:58:19Z

crates/feldera-macros/src/tuples.rs

+                let mut w = 0usize;
+                while w < word {
+                    idx += 64usize - (self.bitmap[w].count_ones() as usize);
+                    w += 1;
+                }


for w in self.bitmap[..word] { idx += w.count_zeros() as usize; }

blp · 2026-01-12T22:00:11Z

crates/feldera-macros/src/tuples.rs

+                let mask = if bit == 0 { 0 } else { (1u64 << bit) - 1 };
+                let none_before = (self.bitmap[word] & mask).count_ones() as usize;
+                idx + bit - none_before


if bit > 0 { let mask = (1u64 << bit) - 1; idx += (self.bitmap[word] & mask).count_zeros() as usize; } idx

(I think your code is correct, I just found myself rewriting it to better understand it.)

blp · 2026-01-12T22:05:25Z

crates/storage-test-compat/golden-files/golden-batch-v3-snappy.feldera

Thanks for adding the "golden batch"es.

This is an optimization added to the new Tup storage format we used to write things into files as Some(x) but this leads to unnecessary overheads when the Option can not be elided. By extending IsNone with ability to extract the inner type and reconstruct the Option in case of Option types we can avoid storing things as Option<T> and just use T plus a bitfield. Signed-off-by: Gerd Zellweger <mail@gerdzellweger.com>

gz · 2026-01-13T00:14:48Z

thanks @blp ! sorry you might have to review this again in a little bit because I made a bunch of changes so things are optimal in most (all?) cases of data ... but I'll incorporate your suggestions

blp · 2026-01-13T00:23:02Z

thanks @blp ! sorry you might have to review this again in a little bit because I made a bunch of changes so things are optimal in most (all?) cases of data ... but I'll incorporate your suggestions

No worries

gz added 6 commits January 10, 2026 14:16

Add dynamic None optimization to ArchivedTup.

3905031

- Stores None's as 1-bit in a bitmap - In case something isn't None, store as the value in a dynamically sized-list Signed-off-by: Gerd Zellweger <mail@gerdzellweger.com>

Plumb file version into rkyv deserializer

a07ae6f

Handle V3 tuple layout in rkyv deserialization

7226a54

Add Tup65 option string storage test

99712f6

[dbsp] remove unused code.

4ead46b

Signed-off-by: Gerd Zellweger <mail@gerdzellweger.com>

[dbsp+storage] infra for testing storage format backwards compatibility.

d0d581c

Add code to generate batch files in different formats and makes sure we can read them correctly in the future. Signed-off-by: Gerd Zellweger <mail@gerdzellweger.com>

Copilot AI review requested due to automatic review settings January 10, 2026 22:28

Copilot started reviewing on behalf of gz January 10, 2026 22:28 View session

gz changed the title ~~None optimziation part 2~~ None optimiziation (part 2) Jan 10, 2026

Copilot AI reviewed Jan 10, 2026

View reviewed changes

gz requested review from blp and removed request for blp January 10, 2026 22:34

gz marked this pull request as draft January 11, 2026 19:33

[feldera-macros] update generated code

c98b96f

Signed-off-by: Gerd Zellweger <mail@gerdzellweger.com>

blp changed the title ~~None optimiziation (part 2)~~ None optimization (part 2) Jan 12, 2026

blp reviewed Jan 12, 2026

View reviewed changes

gz added 3 commits January 12, 2026 16:48

WIP: tuple format selection heuristics

f62d0ac

Unify tuple bitmap format and update heuristics

e90d7e3

Use standard rkyv for small tuples

1223154

gz force-pushed the none-optimziation-part2.2 branch from 422f201 to 1223154 Compare January 13, 2026 23:52

	unsafe { self.get_t0() == other.get_t0() && self.get_t1() == other.get_t1() }
	self.get_t0() == other.get_t0() && self.get_t1() == other.get_t1()

	.expect("passed wrong deserializer");
	.expect("Deserializer must be of type dbsp::storage::file::Deserializer for version tracking support");

	if version <= 3 {
	const LAST_LEGACY_VERSION: u32 = 3;
	if version <= LAST_LEGACY_VERSION {

None optimization (part 2) #5409

Are you sure you want to change the base?

None optimization (part 2) #5409

Uh oh!

Conversation

gz commented Jan 10, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Breaking Changes?

Describe Incompatible Changes

Uh oh!

Copilot AI left a comment

Choose a reason for hiding this comment

Pull request overview

Reviewed changes

Uh oh!

Copilot AI Jan 10, 2026

Choose a reason for hiding this comment

Uh oh!

Copilot AI Jan 10, 2026

Choose a reason for hiding this comment

Uh oh!

Copilot AI Jan 10, 2026

Choose a reason for hiding this comment

Uh oh!

Copilot AI Jan 10, 2026

Choose a reason for hiding this comment

Uh oh!

Copilot AI Jan 10, 2026

Choose a reason for hiding this comment

Uh oh!

Copilot AI Jan 10, 2026

Choose a reason for hiding this comment

Uh oh!

Copilot AI Jan 10, 2026

Choose a reason for hiding this comment

Uh oh!

blp left a comment

Choose a reason for hiding this comment

Uh oh!

blp Jan 12, 2026

Choose a reason for hiding this comment

Uh oh!

blp Jan 12, 2026

Choose a reason for hiding this comment

Uh oh!

blp Jan 12, 2026

Choose a reason for hiding this comment

Uh oh!

gz commented Jan 13, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

blp commented Jan 13, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

gz commented Jan 10, 2026 •

edited

Loading

gz commented Jan 13, 2026 •

edited

Loading