apache / apache/lucene

Can we do "doc at a time scoring" from the BKD tree for exact queries? [LUCENE-8854]

Open
#9,897 2 comments 0 reactions 0 assignees View on GitHub
legacy-jira-priority:Major type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

Random idea: normally our point queries must walk the BKD tree, building up a sparse or dense bitset as a 1st pass, then in 2nd pass run the "normal" query scorers (postings, doc values), because the docids coming out across leaf blocks are not in docid order, like postings and doc values.

But, if the query is an exact point query, I think we tie break our within leaf block sorts by docid, and that'd even apply across multiple leaf blocks (if that value occurs enough times) and so for that case we could avoid the 2 passes and do it all in one pass maybe?

---
Migrated from [LUCENE-8854](https://issues.apache.org/jira/browse/LUCENE-8854) by Michael McCandless (@mikemccand), updated Jun 13 2019

Contributor guide

Open the contributing guide

Research direction

Start by tracing Lucene's BKD-tree exact point-query path and the current two-pass scoring flow described in the issue. Determine whether doc IDs remain ordered across matching leaf blocks, then validate that a one-pass scorer preserves existing query results and scoring behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.