lance-format / lance-format/lance

Defer index parser selection until full operator context is available

Open
#7,091 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

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

Description

https://github.com/lance-format/lance/pull/7072 fixed an issue where multiple JSON indices on different paths of the same column would route queries to the wrong sub-parser, by introducing MultiQueryParser::select() and calling it at the point of column reference extraction in maybe_indexed_column. That fix works correctly for the JSON multi-path scenario because the column reference itself (e.g. json_extract(json, '$.b')) carries enough information to disambiguate which sub-parser handles it.

However, the fix also surfaces a more general architectural limitation: maybe_indexed_column selects a parser based solely on the column reference — before the full operator context (e.g. >, <, =, IS NULL) is known. When that context matters for parser selection, the wrong parser can be chosen, causing index acceleration to be missed entirely.

Concrete case: Suppose column x has both a bloom filter index and a btree index, and the query is x > 7:

  1. visit_comparison calls maybe_indexed_column(&expr.left) — only Column("x") is visible at this point
  2. MultiQueryParser::select() asks each child parser's is_valid_reference — both bloom and btree accept a bare Column("x") as valid
  3. select() returns whichever child was registered first (e.g., bloom)
  4. visit_comparison then calls bloom.visit_comparison("x", 7, Operator::Gt) — bloom returns None because it only supports equality
  5. The query falls through to a full-table scan, even though btree could have handled x > 7

If the parser selection had been deferred until after visit_comparison knew both the column and the operator (>), the btree index would have been selected.

The root cause is that maybe_indexed_column does not distinguish between two qualitatively different decisions:

  • Reference validation ("does this index handle this column at all?") — appropriate for deciding which JSON path parser to use, where the column reference alone carries enough information
  • Capability matching ("can this index serve this specific query shape?") — requires knowing the operator, which only exists at the parent expression node level

Conflating the two means the first valid parser wins, even if it cannot actually serve the query.

This was previously noted in the existing TODO comment on MultiQueryParser::is_valid_reference:

This is maybe not quite right. We should filter down the list of parsers based on those that consider the reference valid… This will be a problem if the user creates two indexes (e.g. btree and json) on the same column and those two indexes have different reference schemes.

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 tracing maybe_indexed_column, MultiQueryParser::select, is_valid_reference, and visit_comparison, including the existing TODO on parser selection. Reproduce the bloom-filter and btree case for x > 7, then verify that selection accounts for the operator and the query uses the btree path instead of a full-table scan.

Written by the indexing model from the issue text.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.