lance-format / lance-format/lance
Auto conflict resolution for `update/delete` then `compact`
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 7.1k
- Forks
- 852
- Avg merge
- 3d 18h
- Merged PRs (30d)
- 272
Description
Design
When compaction happens, the row addresses change. To be able to handle row-level conflicts, we will need compaction to emit a change_of_address mapping.
Update and delete transactions generate an affected_rows bitmap that tell them which row addresses need to be masked from the table. When they rebase on top of a compaction, they need run their affected_rows bitmap through the change_of_address mapping.
When compaction rebases on top of update/delete transactions, it needs to run the new deletion files through it's change_of_address mapping to generate new deletion files for the compacted data. Rows that were originally deleted and compacted out of the data will not appear in the mapping and will be dropped. But rows that have been deleted after will be mapped to an actual location.
TODO: update/delete then compact
- Add
change_of_address()parameter / method to theCommitBuilder - Wire the
row_id_mapor thechanged_row_addrhttps://github.com/lancedb/lance/blob/0fad40d676b24d9355a6b2dbe626111684f1696a/rust/lance/src/dataset/optimize.rs#L590-L596 field to thechange_of_address()mapping. - Implement the rebase with the change of address, using the map to adjust the deletion vectors.
- Write a test validating that if we commit update prior to compaction, we can successfully rebase the compaction
- Run compaction without committing (
plan_compactionthenCompactionTask.execute()) - Run update query to update one row
- Run delete query to delete one row
- Commit compaction
- Validate the row that was deleted is now gone
- Validate the row that was updated has new value and old value doesn't exist
- Run compaction without committing (
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with CommitBuilder and the row_id_map or changed_row_addr field in rust/lance/src/dataset/optimize.rs around lines 590-596. Trace plan_compaction, CompactionTask.execute(), and the update/delete rebase paths to understand how deletion vectors are represented. Done means the listed compaction, update, and delete sequence rebases successfully and the test confirms the deleted row is absent while the updated row has only its new value.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- data-engineering, databases
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 28/100