apache / apache/lucene

TermsQuery as MultiTermQuery can dramatically overestimate its cost

Open
#12,483 4 comments 0 reactions 0 assignees View on GitHub
type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

### Description

I've run across an interestingly adversarial setup for the new TermsQuery implementation. We have an index that is using a block-join structure, with the parent document being a merchant record and the children being individual transactions. Doing a range query filtered by some specific merchant ids turns out to be surprisingly slow. The range query in particular takes a long time, because it covers a large portion of the document space but can't use some of our shortcut heuristics (eg LUCENE-7641 that will invert the search to find docs that *don't* match) because the parent docs don't have the timestamp field. In combination with the filter, though, I would have expected things to still be quick, because the range query is using IndexOrDocValuesQuery and so a filter that narrows the search down to a fraction of the index ought to select the doc-by-doc checking path. However, it turns out that the cost estimation code in AbstractMultiTermQueryConstantScoreWrapper will calculate a very large cost if the field you're filtering on isn't an ID field - in this case, we have a sort of mid-level cardinality where each value represents a few percent of the index, which ends up yielding a cost estimate of the total number of docs in the index minus 100 or so. Explicitly using a boolean disjunction instead of a TermsQuery yields a much more accurate cost estimate and correctly selects doc-by-doc range checking, giving a much more performant query.

We used to automatically rewrite TermsQuery to a simple boolean disjunction if there were fewer than 16 terms. I wonder if the more complex machinery we are using now is overkill for these small term sets, and we should just go back to this simple rewrite in those cases?

Contributor guide

Open the contributing guide

Research direction

Start by tracing TermsQuery as a MultiTermQuery into AbstractMultiTermQueryConstantScoreWrapper, focusing on how cost is estimated for non-ID fields and how IndexOrDocValuesQuery chooses its path. Compare the estimate with an explicit boolean disjunction for small term sets, and verify that the problematic block-join range-query scenario selects the doc-by-doc path and avoids the overestimate.

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.