lance-format / lance-format/lance

Filtered read performance optimizations

Open
#4,189 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

There are a few bottlenecks in the planning phase of filtered reads that could probably be optimized. These are most noticeable when reading small amounts of data from a large dataset (e.g. applying a btree index) when all the data is in memory.

  • RowIdTreeMap::insert_range seems kind of slow. This makes RowIdTreeMap::from(range) slow which means RowIdSequence::mask_to_offset_ranges is slow which means apply_index_result in FilteredReadStream::create_plan is slow.
  • The apply_index_result step is run once for each fragment, in serial order. It is not parallelized because that would mess up range_offset and filtered_range_offset. However, we could probably calculate just those offsets first (in a vec) and then parallelize the apply_index_result step

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 by reading RowIdTreeMap::insert_range and tracing its use through RowIdTreeMap::from, RowIdSequence::mask_to_offset_ranges, and FilteredReadStream::create_plan. Examine how range_offset and filtered_range_offset are calculated before changing the serial apply_index_result work. Done means filtered-read planning is measurably faster while preserving correct offsets and results.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data-engineering, performance
Issue type
Refactor
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
42/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.