lance-format / lance-format/lance

Auto conflict resolution for `update/delete` then `compact`

Open
#4,604 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement
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 the CommitBuilder
  • Wire the row_id_map or the changed_row_addr https://github.com/lancedb/lance/blob/0fad40d676b24d9355a6b2dbe626111684f1696a/rust/lance/src/dataset/optimize.rs#L590-L596 field to the change_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_compaction then CompactionTask.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

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.