apache / apache/lucene

BlockMaxConjunctionScorer's simplified way of computing max scores hurts performance [LUCENE-8759]

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

Description

BlockMaxConjunctionScorer computes the minimum value that the score should have after each scorer in order to be able to interrupt scorer as soon as possible. For instance say scorers A, B and C produce maximum scores that are equal to 4, 2 and 1. If the minimum competitive score is X, then the score after scoring A, B and C must be at least X, the score after scoring A and B must be at least X-1 and the score after scoring A must be at least X-1-2.

However this is made a bit more complex than that due to floating-point numbers and the fact that intermediate score values are doubles which only get casted to a float after all values have been summed up. In order to keep things simple, BlockMaxConjunctionScore has the following comment and code

```Java
// Also compute the minimum required scores for a hit to be competitive
// A double that is less than 'score' might still be converted to 'score'
// when casted to a float, so we go to the previous float to avoid this issue
minScores[minScores.length - 1] = minScore > 0 ? Math.nextDown(minScore) : 0;
```

It simplifies the problem by calling Math.nextDown(minScore). However this is problematic because it defeats the fact that TopScoreDocCollector calls setMinCompetitiveScore on the float value that is immediately greater than the k-th greatest hit so far.

nextDown(minScore) is not the value that we need. The value that we need is the smallest double that converts to minScore when casted to a float, which would be half-way between nextDown(minScore) and minScore. In some cases this would help get better performance out of conjunctions, especially if some clauses produce constant scores.

MaxScoreSumPropagator#setMinCompetitiveScore has the same issue.

---
Migrated from [LUCENE-8759](https://issues.apache.org/jira/browse/LUCENE-8759) by Adrien Grand (@jpountz), updated Apr 16 2019
Attachments: [LUCENE-8759.patch](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-8759/LUCENE-8759.patch)

Contributor guide

Open the contributing guide

Research direction

Start with BlockMaxConjunctionScorer's minimum-score calculation and MaxScoreSumPropagator#setMinCompetitiveScore, then inspect the related competitive-score handling and existing tests. Reproduce or benchmark conjunction scoring with floating-point thresholds, and verify that the computed bounds preserve correctness while allowing the intended early interruption.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.