lance-format / lance-format/lance

perf: delete builds the dataset-wide row id index only to translate ids it does not need

Open
#9,320 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

performance
Dominant language
Rust
Stars
7.1k
Forks
852
Avg merge
3d 18h
Merged PRs (30d)
272

Description

Description

On a dataset with stable row ids, DeleteJob scans _rowid, captures the ids of the rows its predicate matched, and then builds the dataset-wide RowIdIndex through get_row_id_index purely to translate those ids back into the row addresses the deletion vectors need. Deleted rows keep no ids, so the round trip is avoidable: the scan can capture _rowaddr directly. On a dataset without stable row ids _rowid already is the address, so the same addresses come out; only the accumulator changes.

Measured on a local (not memory://) dataset with --profile release-no-lto: building the index cold costs 0.6 ms at 500 fragments / 50k rows and 3.6 ms at 5000 fragments / 100k rows. The whole one-row delete on the 500-fragment dataset takes about 47 ms, so that cost is not visible. The win is a simplification whose size grows with fragment count; it is not a significant speedup. Where nothing else in the plan needs it, capturing _rowaddr also keeps a delete of a few rows from holding a dataset-wide structure in memory. On object storage the same change would avoid reading fragments' external row-id metadata; the local fixture keeps that metadata inline, so the measurement does not exercise that path.

Steps to reproduce
// A delete whose predicate does not fold to a literal takes this path:
//   DeleteJob::execute_impl -> scanner.with_row_id().project(&[ROW_ID])
//   -> make_rowid_capture_stream -> get_row_id_index(&dataset)
//   -> CapturedRowIds::row_addrs(index)
let mut dataset = /* dataset written with enable_stable_row_ids: true */;
dataset.delete("id = 12345").await.unwrap();
Expected behavior

DeleteJob resolves the addresses it needs without building the row id index itself.

Lance version

13.0.0-beta.3 (main)

Language binding

Rust

Environment

macOS ARM, local storage.

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 at DeleteJob::execute_impl and follow scanner.with_row_id().project(&[ROW_ID]) into make_rowid_capture_stream, get_row_id_index, and CapturedRowIds::row_addrs. Check how the capture can use _rowaddr directly for stable and non-stable row ids. Done means DeleteJob resolves deletion addresses without building the dataset-wide RowIdIndex and the shown delete path still works.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
databases
Issue type
Refactor
Difficulty
3/5
Estimated time
1-2 days
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
74/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.