You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by gs...@apache.org on 2024/08/09 16:16:21 UTC
(lucene) branch main updated: Get better cost estimate on MultiTermQuery over few terms (#13201)
This is an automated email from the ASF dual-hosted git repository.
gsmiller pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new 4d04cc26a95 Get better cost estimate on MultiTermQuery over few terms (#13201)
4d04cc26a95 is described below
commit 4d04cc26a95016fcdf033a220d67e11ecd377261
Author: Michael Froh <fr...@amazon.com>
AuthorDate: Fri Aug 9 09:16:15 2024 -0700
Get better cost estimate on MultiTermQuery over few terms (#13201)
---------
Co-authored-by: Greg Miller <gs...@gmail.com>
---
lucene/CHANGES.txt | 2 +
...AbstractMultiTermQueryConstantScoreWrapper.java | 82 +++++++++++++---------
.../apache/lucene/search/TestWildcardQuery.java | 39 ++++++++++
3 files changed, 89 insertions(+), 34 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 0c823f1e326..3538bbeaf24 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -297,6 +297,8 @@ Improvements
* GITHUB#12627: patch HNSW graphs to improve reachability of all nodes from entry points
+* GITHUB#13201: Better cost estimation on MultiTermQuery over few terms. (Michael Froh)
+
Optimizations
---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/search/AbstractMultiTermQueryConstantScoreWrapper.java b/lucene/core/src/java/org/apache/lucene/search/AbstractMultiTermQueryConstantScoreWrapper.java
index 7a705c0ef4d..fc18b0476a7 100644
--- a/lucene/core/src/java/org/apache/lucene/search/AbstractMultiTermQueryConstantScoreWrapper.java
+++ b/lucene/core/src/java/org/apache/lucene/search/AbstractMultiTermQueryConstantScoreWrapper.java
@@ -154,38 +154,17 @@ abstract class AbstractMultiTermQueryConstantScoreWrapper<Q extends MultiTermQue
List<TermAndState> collectedTerms)
throws IOException;
- private IOSupplier<WeightOrDocIdSetIterator> rewrite(LeafReaderContext context, Terms terms)
- throws IOException {
- assert terms != null;
-
- final int fieldDocCount = terms.getDocCount();
- final TermsEnum termsEnum = q.getTermsEnum(terms);
- assert termsEnum != null;
-
- final List<TermAndState> collectedTerms = new ArrayList<>();
- boolean collectResult = collectTerms(fieldDocCount, termsEnum, collectedTerms);
- if (collectResult && collectedTerms.isEmpty()) {
- return null;
+ private WeightOrDocIdSetIterator rewriteAsBooleanQuery(
+ LeafReaderContext context, List<TermAndState> collectedTerms) throws IOException {
+ BooleanQuery.Builder bq = new BooleanQuery.Builder();
+ for (TermAndState t : collectedTerms) {
+ final TermStates termStates = new TermStates(searcher.getTopReaderContext());
+ termStates.register(t.state, context.ord, t.docFreq, t.totalTermFreq);
+ bq.add(new TermQuery(new Term(q.field, t.term), termStates), BooleanClause.Occur.SHOULD);
}
- return () -> {
- if (collectResult) {
- // build a boolean query
- BooleanQuery.Builder bq = new BooleanQuery.Builder();
- for (TermAndState t : collectedTerms) {
- final TermStates termStates = new TermStates(searcher.getTopReaderContext());
- termStates.register(t.state, context.ord, t.docFreq, t.totalTermFreq);
- bq.add(
- new TermQuery(new Term(q.field, t.term), termStates), BooleanClause.Occur.SHOULD);
- }
- Query q = new ConstantScoreQuery(bq.build());
- final Weight weight = searcher.rewrite(q).createWeight(searcher, scoreMode, score());
- return new WeightOrDocIdSetIterator(weight);
- } else {
- // Too many terms to rewrite as a simple bq.
- // Invoke rewriteInner logic to handle rewriting:
- return rewriteInner(context, fieldDocCount, terms, termsEnum, collectedTerms);
- }
- };
+ Query q = new ConstantScoreQuery(bq.build());
+ final Weight weight = searcher.rewrite(q).createWeight(searcher, scoreMode, score());
+ return new WeightOrDocIdSetIterator(weight);
}
private boolean collectTerms(int fieldDocCount, TermsEnum termsEnum, List<TermAndState> terms)
@@ -240,9 +219,44 @@ abstract class AbstractMultiTermQueryConstantScoreWrapper<Q extends MultiTermQue
return null;
}
- final long cost = estimateCost(terms, q.getTermsCount());
- IOSupplier<WeightOrDocIdSetIterator> weightOrIteratorSupplier = rewrite(context, terms);
- if (weightOrIteratorSupplier == null) return null;
+ assert terms != null;
+
+ final int fieldDocCount = terms.getDocCount();
+ final TermsEnum termsEnum = q.getTermsEnum(terms);
+ assert termsEnum != null;
+
+ List<TermAndState> collectedTerms = new ArrayList<>();
+ boolean collectResult = collectTerms(fieldDocCount, termsEnum, collectedTerms);
+
+ final long cost;
+ if (collectResult) {
+ // Return a null supplier if no query terms were in the segment:
+ if (collectedTerms.isEmpty()) {
+ return null;
+ }
+
+ // TODO: Instead of replicating the cost logic of a BooleanQuery we could consider rewriting
+ // to a BQ eagerly at this point and delegating to its cost method (instead of lazily
+ // rewriting on #get). Not sure what the performance hit would be of doing this though.
+ long sumTermCost = 0;
+ for (TermAndState collectedTerm : collectedTerms) {
+ sumTermCost += collectedTerm.docFreq;
+ }
+ cost = sumTermCost;
+ } else {
+ cost = estimateCost(terms, q.getTermsCount());
+ }
+
+ IOSupplier<WeightOrDocIdSetIterator> weightOrIteratorSupplier =
+ () -> {
+ if (collectResult) {
+ return rewriteAsBooleanQuery(context, collectedTerms);
+ } else {
+ // Too many terms to rewrite as a simple bq.
+ // Invoke rewriteInner logic to handle rewriting:
+ return rewriteInner(context, fieldDocCount, terms, termsEnum, collectedTerms);
+ }
+ };
return new ScorerSupplier() {
@Override
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestWildcardQuery.java b/lucene/core/src/test/org/apache/lucene/search/TestWildcardQuery.java
index 04807eb19ae..4dfca8101fd 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestWildcardQuery.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestWildcardQuery.java
@@ -21,6 +21,7 @@ import org.apache.lucene.document.Document;
import org.apache.lucene.document.Field;
import org.apache.lucene.index.DirectoryReader;
import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.LeafReaderContext;
import org.apache.lucene.index.MultiTerms;
import org.apache.lucene.index.Term;
import org.apache.lucene.index.Terms;
@@ -418,4 +419,42 @@ public class TestWildcardQuery extends LuceneTestCase {
reader.close();
dir.close();
}
+
+ public void testCostEstimate() throws IOException {
+ Directory dir = newDirectory();
+ RandomIndexWriter writer = new RandomIndexWriter(random(), dir);
+ for (int i = 0; i < 1000; i++) {
+ Document doc = new Document();
+ doc.add(newStringField("body", "foo bar", Field.Store.NO));
+ writer.addDocument(doc);
+ doc = new Document();
+ doc.add(newStringField("body", "foo wuzzle", Field.Store.NO));
+ writer.addDocument(doc);
+ doc = new Document();
+ doc.add(newStringField("body", "bar " + i, Field.Store.NO));
+ writer.addDocument(doc);
+ }
+ writer.flush();
+ writer.forceMerge(1);
+ writer.close();
+
+ IndexReader reader = DirectoryReader.open(dir);
+ IndexSearcher searcher = newSearcher(reader);
+ LeafReaderContext lrc = reader.leaves().get(0);
+
+ WildcardQuery query = new WildcardQuery(new Term("body", "foo*"));
+ Query rewritten = searcher.rewrite(query);
+ Weight weight = rewritten.createWeight(searcher, ScoreMode.COMPLETE_NO_SCORES, 1.0f);
+ ScorerSupplier supplier = weight.scorerSupplier(lrc);
+ assertEquals(2000, supplier.cost()); // Sum the terms doc freqs
+
+ query = new WildcardQuery(new Term("body", "bar*"));
+ rewritten = searcher.rewrite(query);
+ weight = rewritten.createWeight(searcher, ScoreMode.COMPLETE_NO_SCORES, 1.0f);
+ supplier = weight.scorerSupplier(lrc);
+ assertEquals(3000, supplier.cost()); // Too many terms, assume worst-case all terms match
+
+ reader.close();
+ dir.close();
+ }
}