[VOTE] Add DeltaBlobLayout encoding for delta-encoded blob columns

[beinan]

Proposal

Add a new DeltaBlobLayout variant to the PageLayout protobuf oneof in encodings_v2_1.proto, enabling binary delta encoding for blob columns.

Motivation

When storing source code datasets (e.g., file revision histories from Git repositories), consecutive rows often differ by only a few lines. Today each blob is stored independently. Delta encoding can reduce storage by 5-10x for such workloads by storing only the binary differences (copy/insert instructions) between similar values.

This is directly motivated by the Git Lake project — storing the world's Git data in Lance.

Design

The new layout is a thin wrapper, structurally identical to BlobLayout:

message DeltaBlobLayout {
  PageLayout inner_layout = 1;
  repeated RepDefLayer layers = 2;
}

message PageLayout {
  oneof layout {
    MiniBlockLayout mini_block_layout = 1;
    ConstantLayout constant_layout = 2;
    FullZipLayout full_zip_layout = 3;
    BlobLayout blob_layout = 4;
    DeltaBlobLayout delta_blob_layout = 5;  // NEW
  }
}

How it works

• Descriptor struct: (position, size, kind, base_offset) — extends the blob descriptor with kind (DeltaBase=4 or Delta=5 in BlobKind) and base_offset (distance back to base value)
• Encoding: Groups of N consecutive values where the first is stored as-is (base), subsequent values are stored as Git-style binary deltas (copy/insert instructions) against the previous value. Chain depth is configurable (default 4). Falls back to a new base when delta doesn't achieve 20% savings.
• Decoding: DeltaBlobPageScheduler reads descriptors, expands ranges to include required bases, loads bytes from external buffers, applies delta chains, returns reconstructed values.
• Algorithm: Rabin rolling hash over 16-byte windows for match finding, Git-compatible copy/insert opcode format.

Backwards compatibility

• New field number (5) in the PageLayout oneof — old readers will see an unknown field and fail gracefully
• Only activated when field metadata lance-encoding:delta-blob = "true" is set — existing data is unaffected
• Two new BlobKind variants (DeltaBase=4, Delta=5) with proper TryFrom<u8> handling

PR

#6733

Vote

Please vote with:

• 👍 (+1) to approve
• 👎 (-1) to reject (please explain)

The vote will be open for 72 hours. Requires 3 binding +1 votes and no binding -1 votes to pass.

[hpvd]

this maybe somehow related to this discussion which also addresses duplicated blob data #6592

[westonpace]

I like this idea. I am a little curious how this will eventually evolve to handle blob v2.

In blob v2 we can store blobs inside a data file (inline), in a "pack file" (packed) or with a file-per-blob scheme (dedicated / external). The solution here would handle the inline case. I think we can definitely extend it for the packed case.

Maybe we just can't do this for the file-per-blob schemes? If we do try to somehow support cross-file references we might have to deal with complexities like "what happens if a row referenced by another row is deleted and that delete is materialized".

Anyways, +1 to the general idea. I'll post more specific feedback on the PR.

[beinan]

Thanks @westonpace! I definitely think we should support both inline and blob v2 (specifically the packed format). In our use cases, we often partition the data by ID, which means we naturally need the blobs to be packed externally from the Lance fragment itself.

Regarding your concern about materialized deletes breaking cross-references: the impact should actually be quite lightweight. We aren't keeping a single base blob for a long sequence of rows. Instead, we maintain multiple base blobs (creating a new base every 5 diffs on average). Because these delta chains are so short, if a base row is deleted and materialized during compaction, the process would only need to rebase a very small handful of dependent deltas. It prevents the cascading complexity you'd get with deep delta chains.

[Xuanwo]

I like this idea too. I prefer to view it as a new layer on top of Lance blob rather than a new layout.

Lance's Blob V2 introduced the concept of blob placement in Lance, which decouples the user's bytes from the physical storage. As a further step of Blob V2, we can also decouple Lance's logical blob from the physical blob. In other words, this is an encoding layer for blobs.

Here is my current solution for all the recent feature requests:

• Exact share: logical blob X, Y, Z → physical blob A
• Delta blob: logical blob X → physical blob A, logical blob Y → physical blob A + B
• Chunked blob: logical blob X → physical blob A[0..100]

Inside this blob layer, I think features like delta blob should be added as a codec inside a packed blob instead of as a new blob layout. That way, all information related to delta blob becomes part of the internal details of this codec and is not related to the Lance file spec. We could even use a Lance file to store those delta blobs.

What do you think?

[DanielMao1]

I like this idea too. I prefer to view it as a new layer on top of Lance blob rather than a new layout.

Lance's Blob V2 introduced the concept of blob placement in Lance, which decouples the user's bytes from the physical storage. As a further step of Blob V2, we can also decouple Lance's logical blob from the physical blob. In other words, this is an encoding layer for blobs.

Here is my current solution for all the recent feature requests:

• Exact share: logical blob X, Y, Z → physical blob A
• Delta blob: logical blob X → physical blob A, logical blob Y → physical blob A + B
• Chunked blob: logical blob X → physical blob A[0..100]

Inside this blob layer, I think features like delta blob should be added as a codec inside a packed blob instead of as a new blob layout. That way, all information related to delta blob becomes part of the internal details of this codec and is not related to the Lance file spec. We could even use a Lance file to store those delta blobs.

What do you think?

A great idea — we'd like to extend it. Building on your codec proposal, could we add a plugin system on the Rust side where users register custom UDF-style codecs to encode/decode different kinds of blobs? Blobs come in many forms, and if the decoding could
happen on the Lance side rather than downstream of the read pipeline. We'd like a registration hook — a user-supplied decode(bytes, hints) -> bytes (and an optional streaming variant that gets an EncodingsIo handle) that the scheduler invokes inline right after fetch, before returning to Python.
This way the codec runs in the same tokio task as IO, can pipeline with the next fetch, holds reusable state across blobs, and avoids the Python ↔ Rust boundary + GIL cost we currently pay in every consumer.

[beinan]

Great proposal @Xuanwo! I like the idea of treating delta encoding as a new layer rather than a new layout — it keeps the file spec clean and unifies nicely with exact-share and chunked blobs.

One question about read performance: with the current DeltaBlobLayout approach, the delta chain metadata (kind, base_offset) lives in the page descriptors, so the reader knows upfront which external buffer ranges to fetch for bases and deltas, and can batch them into a single I/O request.

If we move this into a codec inside packed blobs, where would the delta chain metadata live?

In the packed blob index — the reader could still pre-plan all I/O at index time (no extra hop). But it means the packed blob index needs to carry delta-specific fields.
Inside the blob data itself — the reader wouldn't know a blob is delta-encoded until it reads it, discovers it's a delta, then has to issue another read for the base. That's an extra I/O hop per delta value.
Do you envision the packed blob index carrying enough metadata to batch delta chain reads? Or is there another way to avoid the extra round-trip?

[jaystarshot]

I think this is like h265 (video) and we can borrow some ideas from there late (binary tree references instead of fixed intervals etc)

[hpvd]

now there is a full
Lance Blob v2 Object Layer Proposal
#7174

detailing the idea of separation of physical and logical blob from #6736 (comment)