Proposal: Data Overlay files for fast targeted writes

[wjones127]

Motivation

We want to make writing granular cell-level updates fast. For example: fill in NULL embeddings that are present in 1% of rows. Current solutions require too much write amplification.

Solution

Allow each fragment to have Overlay Files: data files that contain a subset of columns and rows, which replace values in data files.

Overview

Data.Overlay.Overview.-.1080p.mov

Spec changes

The proposal is written in this PR: #7381 Comment directly on that PR to discuss the proposal.

[wjones127]

Vote open here: #7447

[westonpace]

Very clear overview, thanks for creating the video. The concept seems simple enough though it does add more complexity it doesn't seem too nightmarish.

If there is a take then how do we quickly determine if we need to access an overlay file or not? Do we have to read the entire overlay file as part of every take operation?

[wjones127]

Each overlay file has two pieces of metadata in the manifest:

1. The field ids it contains, just like data files. This is inside the DataFile message.
2. A RoaringBitmap containing all the row offsets it contains.

You have to walk all the overlay files, but you should have all the metadata you need in the manifest to decide which file any given cell is.

There's some pressure to keep the overlay files narrow--too many of them, or too broad offset bitmaps can make the manifest large. That should be avoided (a) by choosing a different write strategy when it's not appropriate or (b) compacting into data files.

[wjones127]

Merged the spec change as experimental feature #7381

Next few PRs in progress:

1. feat: data overlay files — model, feature flag, and write/commit path #7535
2. feat: resolve data overlay files on the take (and scan) read path #7536
3. feat(python): expose DataOverlay commit operation #7540
4. feat(index): mask data overlay files in scalar and vector index queries #7549
5. feat: overlay-aware compaction scheduler and rewrite #7567