lance-format / lance-format/lance
Avoid keeping all update data in memory in `update_columns`
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 7.1k
- Forks
- 852
- Avg merge
- 3d 18h
- Merged PRs (30d)
- 272
Description
Description
Currently, Fragment::update_columns uses HashJoiner to join fragment data with the updated values.
The relevant code is:
rust/lance/src/dataset/fragment.rs—update_columns/update_columns_with_offsetsrust/lance/src/dataset/hash_joiner.rs—HashJoiner::try_new
HashJoiner::try_new collects the entire RHS into memory before performing the join:
Hold all data in memory for simple implementation. Can do external sort later.
This makes memory consumption proportional to the total size of the update data and can lead to OOM for large updates, especially for datasets containing large variable-size columns (List, String, Binary, etc.).
For example, updating most or all rows of a large dataset with a List<Int32> column containing ~1000 values per row can easily require many GB of memory just for the RHS data, in addition to the hash index and join keys.
It would be useful to make this path bounded-memory for large updates.
Possible approaches
A few options that might be worth considering:
Streaming / sort-merge join
If both sides are already ordered by the join key, the join could be performed batch-by-batch without materializing the entire RHS.
This could be particularly interesting for _rowaddr / _rowid if their ordering can be guaranteed.
Pros: low and predictable memory usage, no large hash table.
Cons: requires ordered inputs; supporting arbitrary keys may require external sorting.
External sort-merge join
Sort the input using bounded-memory external sorting and then perform a streaming merge join.
Pros: bounded memory and works with initially unsorted data.
Cons: additional implementation complexity, temporary storage and I/O; preserving physical row order on the LHS may also complicate the update path.
Partitioned / spillable hash join
Keep the current hash-join approach, but partition/spill the RHS once it exceeds a memory budget and process it in smaller pieces.
Pros: closer to the current implementation and does not require globally ordered keys.
Cons: requires spill management and may require additional work to preserve the current streaming update/write behavior.
The main goal here is not necessarily to replace HashJoiner with a specific algorithm, but to make large updates bounded in memory.
I'd be interested in maintainers' thoughts on which approach would fit Lance's architecture and future direction best.
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 rust/lance/src/dataset/fragment.rs, focusing on update_columns and update_columns_with_offsets, then read HashJoiner::try_new in rust/lance/src/dataset/hash_joiner.rs. Determine which bounded-memory join strategy fits the update path; done means large updates no longer materialize the entire RHS in memory while preserving the existing update behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- data-engineering, databases
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Needs clarification
- Newbie friendliness
- 35/100