apache / apache/lucene

Wrong cost calculation in prefix/wildcard queries [LUCENE-9399]

Open
#10,439 0 comments 0 reactions 0 assignees View on GitHub
affects-version:8.5.2 legacy-jira-priority:Minor module:core/other type:bug
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

When running a prefix query that matches more than 16 terms a BitSet is built for that subquery with the **DocIdSetBuilder**.
The cost of the subquery calculated in that class too.
If I get it right, the idea behind the calculation is to get the frequency of every matched term, sum it all and then divide by the average number of terms per doc. It makes sense but it seems like the sum is not calculated properly:

```java
public void add(DocIdSetIterator iter) throws IOException {
if (bitSet != null) {
bitSet.or(iter);
return;
}
int cost = (int) Math.min(Integer.MAX_VALUE, iter.cost());
BulkAdder adder = grow(cost);
```

Instead of adding the frequency of every term, it stops after the `grow()` creates a bitset. From that moment add() will not call grow and the "counter" variable that stands for the sum of all frequencies will not grow anymore.

In the end, it can create a prefix query with a full bitset (or almost full) that has a low cost. That query can become a leader in a conjunction query.

It's important to say that even if the function is fixed as mentioned above, the cost might still result in a much lower cost than it should.
For example, If we look for all the terms which start with "strin\*" in a java_code field. String term and 20 more terms will match that query. The String Term will match most of the documents but the cost will be pretty low because of the calculation (sum_of_frequencies / avarage_number_of_terms_per_doc).

Maybe we can count every new bit added to the bitset.

---
Migrated from [LUCENE-9399](https://issues.apache.org/jira/browse/LUCENE-9399) by Nir Finkelstein

Contributor guide

Open the contributing guide

Research direction

Start by locating DocIdSetBuilder and its add(DocIdSetIterator) method, then trace how grow() and the cost counter behave after a bitset is created. Reproduce a prefix or wildcard query matching more than 16 terms and inspect its cost in a conjunction. Done means the cost reflects the resulting bitset or matched documents accurately, with regression coverage for the reported case.

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
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.