apache / apache/lucene

qweight.matches(LeafReaderContext ctx, int doc) can be prohibitively slow for large TermInSet queries

Open
#13,391 1 comment 0 reactions 0 assignees View on GitHub
type:bug
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

### Description

I stumbled across this one in a real-life application, where matches-API based highlighting of a query like this:

field:(a OR b OR c OR d OR ...)

took very long to complete, even though query execution itself is blazing fast. The reason is (I think!) in how the MultiTermQuery handles matches - the AbstractMultiTermQueryConstantScoreWrapper returns a disjunction of iterators from a terms enum:

```
@Override
public Matches matches(LeafReaderContext context, int doc) throws IOException {
final Terms terms = context.reader().terms(q.field);
if (terms == null) {
return null;
}
return MatchesUtils.forField(
q.field,
() ->
DisjunctionMatchesIterator.fromTermsEnum(
context, doc, q, q.field, q.getTermsEnum(terms)));
}
```

but for a large set of alternatives, the loop scan inside fromTermsEnum can take a long time until it hits the right document:
```
static MatchesIterator fromTermsEnum(
LeafReaderContext context, int doc, Query query, String field, BytesRefIterator terms)
throws IOException {
Objects.requireNonNull(field);
Terms t = Terms.getTerms(context.reader(), field);
TermsEnum te = t.iterator();
PostingsEnum reuse = null;
for (BytesRef term = terms.next(); term != null; term = terms.next()) {
if (te.seekExact(term)) {
PostingsEnum pe = te.postings(reuse, PostingsEnum.OFFSETS);
if (pe.advance(doc) == doc) {
return new TermsEnumDisjunctionMatchesIterator(
new TermMatchesIterator(query, pe), terms, te, doc, query);
} else {
reuse = pe;
}
}
}
return null;
}
```

I've no idea what the fix can be here, just mentioning the problem before I forget it.

### Version and environment details

_No response_

Contributor guide

Open the contributing guide

Research direction

Start in AbstractMultiTermQueryConstantScoreWrapper.matches and follow DisjunctionMatchesIterator.fromTermsEnum, especially its terms-enumeration loop and postings advance. Reproduce the slowdown with a large TermInSet query and matches-based highlighting. Done means the large-query matches path is no longer prohibitively slow while preserving matching and highlighting behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
backend, performance, search
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.