lance-format / lance-format/lance

Avoid keeping all update data in memory in `update_columns`

Open
#8,939 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

feature performance
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.rsupdate_columns / update_columns_with_offsets
  • rust/lance/src/dataset/hash_joiner.rsHashJoiner::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

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 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.