apache / apache/lucene

Performance regression from 9x to 10x from leading wildcard (unanchored MultiTermQuery)

Open
#16,223 0 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

**Summary**

Since 10.0, an unanchored MultiTermQuery — a leading wildcard like `*foo*`, or a leading-.* regexp — used as a FILTER/MUST clause in a BooleanQuery can be dramatically slower than in 9x, even when the overall query matches zero documents.

The cause is that the term-dictionary scan for these queries moved from a lazy step (`ScorerSupplier#get()`) to an eager one (`Weight#scorerSupplier()`). `scorerSupplier()` is meant to be the cheap "planning" phase, and doing the scan there defeats a parent conjunction's ability to short-circuit before the scan runs.

**Root cause**

`AbstractMultiTermQueryConstantScoreWrapper#scorerSupplier()` now calls `collectTerms()` eagerly (to compute an accurate cost and to return null when no terms match, so a parent BooleanQuery can short-circuit). For a query with an unknown term count (any automaton query — `getTermsCount() == -1`), collectTerms walks the field's term dictionary, and a leading wildcard can't seek, so it must visit every term. The worst case is when it matches few/no terms and never reach the 16-term threshold, it scans the entire term dictionary.

Because BooleanWeight builds a ScorerSupplier for every clause up front, this scan runs before the conjunction can discover that a sibling required clause matches nothing. In 9 the scan lived in `get()`, so an empty sibling short-circuited the conjunction and the wildcard's get() was never called.

**Performance analysis**
From local benchmarking
| scenario | 9.11.1 | 10.1.0 | change |
|---|---|---|---|
| Build the `ScorerSupplier` only (no scorer built yet) | ~0.01 ms | ~41 ms | **~4000× slower** |
| `FILTER(*foo*) AND FILTER()` → 0 hits | ~0.15 ms | ~53 ms | **~350× slower** |
| Wildcard scorer actually built (`ScorerSupplier#get()`), nothing skips it | ~40 ms | ~50 ms | ~unchanged |

**Potential fixes (Open for discussion)**
1. Defer collectTerms to get() when term count is unknown https://github.com/apache/lucene/pull/16222. We'll keep the eager path only for known, bounded term sets. The trade-off here is it reverts some of the cost estimation improvements brought by #13201.
2. A more targeted "is this automaton seekable/anchored?" signal so anchored automaton queries keep precise cost and only truly-unanchored ones defer. Cleaner in principle, but there's no obvious cheap signal (a non-empty common prefix doesn't guarantee a cheap scan).
3. Bound the eager scan effort and fall back to lazy? This sounds over complicated.

Contributor guide

Open the contributing guide

Research direction

Start by reading AbstractMultiTermQueryConstantScoreWrapper#scorerSupplier(), ScorerSupplier#get(), Weight#scorerSupplier(), and BooleanWeight to trace when term collection occurs. Reproduce the listed wildcard-and-empty-term benchmark, then compare the proposed lazy and eager paths. Done means an agreed fix preserves short-circuiting without regressing the stated cost behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.