apache / apache/lucene

MultiTermQueryConstantScoreBlendedWrapper#rewrite performance optimization ideas

Open
#14,313 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

There are many implementations of MultiTermQuery, such as TermInSetQuery、FuzzyQuery、WildcardQuery、PrefixQuery、TermRangeQuery、RegexpQuery、TermsQuery、AutomatonQuery Wait, so optimizing the performance of MultiTermQuery has corresponding performance improvements for various queries.

`The default logic is as follows:`
1. When the number of terms is less than or equal to 16, rewrite it as BooleanQuery
2. When the number of terms is greater than 16, traverse the posting list corresponding to each term to collect document ids

> 2.1. If the document frequency corresponding to this term is less than or equal to 512, record the document ID in otherTerms

> 2.2. If the document frequency corresponding to the term is greater than 512, add the posting list corresponding to the term to the priority queue highFrequent Terms

3. Encapsulate the 16 posting lists contained in otherTerms and highFrequency Terms into the set subs
4. Use the Disjunction DISIApproximation wrapper to jointly participate in the collection of document numbers during the merging of posting lists

`The optimization idea is as follows:`
1. Traverse the posting list corresponding to each term and delay processing, so that it can be returned in advance when encountering the following situations

> 1.1. A term matches all documents

> 1.2. A term matches all documents contained in that field

2. The frequency of documents corresponding to a certain term is very high, less than or equal to reader. maxDoc() -4096. When encountering a large posting list, reverse collection can be performed. At this time, the posting lists corresponding to other terms can be traversed, and the corresponding document IDs can be deleted from the reverse collected set. If the reverse collected set is empty, it means that all documents are matched and can be returned in advance. If it is not empty, the document IDs contained in the reverse collection set are also relatively small, and the performance will be fast when merging the reverse linked list later
3. When the term iteration is completed and it is found that the number of terms is equal to the number of terms contained in the field, all documents are included, and there is no need to traverse the posting list of each term.

I have already implemented this optimization myself and it has been about half a year since it was launched in the production environment. Currently, I have not found any customer feedback issues, but the code changes are slightly significant. Is the Lucene community interested? If so, I will submit a PR.

`The test results are as follows:`

1. A term match all docs scene : Performance improvement by 80 times
2. A term matches all documents containing that field scene : Performance improvement by 70 times
3. contains all terms scene : Performance improvement by 80 times
4. Reverse collection : Performance improvement by 8 times

Contributor guide

Open the contributing guide

Research direction

No source files, tests, or entry points are named. Start by locating MultiTermQueryConstantScoreBlendedWrapper and reviewing its current rewrite behavior against the optimization ideas described; done would require an agreed design, implementation, and validation of the reported performance scenarios.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.