lance-format / lance-format/lance
Change SargableQuery::IsIn to hold an Arrow array instead of Vec<ScalarValue>
Nobody has claimed this yet.
- 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)andBloomFilterQuery::IsInlikewise. - Build the array once in
visit_in_list(note: it returnsOption, so handle the fallibleiter_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/LikePrefixremainScalarValue/Bound<ScalarValue>(single-value); only the multi-valueIsInbecomes an array.- Consider whether bindings (Python/Java) construct
SargableQuerydirectly; if so, keep parameter names consistent.
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
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