lance-format / lance-format/lance

Change SargableQuery::IsIn to hold an Arrow array instead of Vec<ScalarValue>

Open
#7,192 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

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

Description

Summary

SargableQuery::IsIn (and the parallel BloomFilterQuery::IsIn) currently hold Vec<ScalarValue>:

pub enum SargableQuery {
    IsIn(Vec<ScalarValue>),
    ...
}

An IN-list is a homogeneous set of values of a single type — i.e. exactly what an Arrow array represents. Holding it as Vec<ScalarValue> means every consuming index has to re-materialize the values (clone each scalar, often rebuild an Arrow array) on every search, instead of building the array once when the query is constructed.

Motivation

While fixing the BTree lookup path (#7186), CPU profiling of the warm-cache IN/equality benchmarks showed the dominant cost is allocation + memmove from building an Arrow array out of the Vec<ScalarValue> per query (ScalarValue::iter_to_array), plus per-value ScalarValue clone/drop churn. The previous BTreeMap-based path avoided this by comparing ScalarValues directly against tree keys; querying the lookup batch directly wants an array.

If IsIn carried an ArrayRef, the array would be built once at query-construction time (expression.rs::visit_in_list) and flow through each index's lookup with zero per-search allocation. BTree could compare it directly against the min/max columns; bitmap/zonemap would index into it.

Proposed change
  • Change SargableQuery::IsIn(Vec<ScalarValue>) -> IsIn(ArrayRef) and BloomFilterQuery::IsIn likewise.
  • Build the array once in visit_in_list (note: it returns Option, so handle the fallible iter_to_array).
  • Update consumers (btree, bitmap, zonemap, bloomfilter) and tests.
Scope / notes
  • This is a cross-cutting change to a public-ish enum touching several index types and ~10 test sites, which is why it's split out of #7186 rather than bundled in.
  • Equals/Range/LikePrefix remain ScalarValue/Bound<ScalarValue> (single-value); only the multi-value IsIn becomes an array.
  • Consider whether bindings (Python/Java) construct SargableQuery directly; if so, keep parameter names consistent.

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

Read expression.rs::visit_in_list first and trace SargableQuery::IsIn and BloomFilterQuery::IsIn through the btree, bitmap, zonemap, and bloomfilter consumers. Check the roughly ten affected tests and any binding construction sites; done means arrays are built at query construction and all index and test paths compile and pass without per-search materialization.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
database
Issue type
Refactor
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
55/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.