You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "msfroh (via GitHub)" <gi...@apache.org> on 2026/10/08 20:14:49 UTC
[PR] Improve cost estimate for AutomatonQuery [lucene]
msfroh opened a new pull request, #16801:
URL: https://github.com/apache/lucene/pull/16801
### Description
This change moves the estimateCost logic from
AbstractMultiTermQueryConstantScoreWrapper to the subclasses of MultiTermQuery. For AutomatonQuery, we approximate the automaton by a covering range to find potentially-matching terms up to a low limit.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Improve cost estimate for AutomatonQuery [lucene]
Posted by "msfroh (via GitHub)" <gi...@apache.org>.
msfroh commented on PR #16801:
URL: https://github.com/apache/lucene/pull/16801#issuecomment-6068568777
@txwei , @romseygeek -- it took me a while to get around to this, but I think this is a happy medium for cost estimation over `AutomatonQuery`, as discussed at https://github.com/apache/lucene/pull/16240#issuecomment-5039343744.
I have a plan/idea around how to extend the "covering terms" estimate to properly do a sort of `IndexOrDocValueQuery` for `MultiTermQuery` that finally does the best possible thing in the presence of leading wildcards (though I tend to agree with @rmuir's past suggestion that the best possible thing to do with leading wildcards is throw them in the trash).
It's essentially a three-way choice:
1. If the field does not have doc values, or if `leadCost` is comparable to the estimated number of matching docs (as calculated by this PR), then we just apply `CONSTANT_SCORE_*_REWRITE`. We can call this `strategy T`.
2. Else, we definitely have doc values, which means that we have a `TermsEnum` that supports `ord()`. We find the bounds on terms covered by the automaton (using the code in `AutomatonQuery` in this PR, or something like it), and compare their `ord()` values. The difference is an upper bound on the number of matching terms.
1. If the number of matching terms is small, we use `DOC_VALUES_REWRITE` to collect the matching term ordinals into a bitset. Let's call this `strategy DV-eager`.
2. If the number of (potentially) matching terms is large (e.g. leading wildcard over a big term dictionary), then we do a `TwoPhaseIterator` whose `match()` resolves the ordinal back to the `BytesRef` and runs the automaton. (We can cache ordinal -> result to avoid this step for the same ordinal.) This is `strategy DV-lazy`.
Writing `T` for the number of terms the query must traverse and `D` for the estimated number of
matching documents (`MultiTermQuery#estimateCost`), the rough cost models are:
```
strategy T: T + D
strategy DV-eager: T + leadCost
strategy DV-lazy: log T + leadCost × r (r = ords per doc × ordinal-resolution cost)
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Improve cost estimate for AutomatonQuery [lucene]
Posted by "txwei (via GitHub)" <gi...@apache.org>.
txwei commented on code in PR #16801:
URL: https://github.com/apache/lucene/pull/16801#discussion_r4300799137
##########
lucene/core/src/java/org/apache/lucene/search/MultiTermQuery.java:
##########
@@ -317,6 +317,14 @@ public long getTermsCount() {
return -1;
}
+ /**
+ * Return an upper-bound on the number of documents matched by this query. If not known,
+ * terms.getSumDocFreq() will be returned.
+ */
+ public long estimateCost(Terms terms) throws IOException {
Review Comment:
Is there a reason why this doesn't copy the existing static helper with the two branches? That way we would be able to reduce some duplicated code.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Improve cost estimate for AutomatonQuery [lucene]
Posted by "txwei (via GitHub)" <gi...@apache.org>.
txwei commented on code in PR #16801:
URL: https://github.com/apache/lucene/pull/16801#discussion_r4300672434
##########
lucene/core/src/java/org/apache/lucene/search/TermInSetQuery.java:
##########
@@ -164,6 +164,27 @@ public long getTermsCount() {
return termData.size();
}
+ @Override
+ public long estimateCost(Terms terms) throws IOException {
+ // Estimate the cost. If the MTQ can provide its term count, we can do a better job
+ // estimating.
+ // Cost estimation reasoning is:
+ // Since we know how many query terms there are...
+ // a. Assume every query term matches at least one document (queryTermsCount).
+ // b. Determine the total number of docs beyond the first one for each term.
+ // That count provides a ceiling on the number of extra docs that could match beyond
+ // that first one. (We omit the first since it's already been counted in 2a).
+ // For id fields (i.e. docFreq = 1 for every term), the estimated cost will be equal
+ // to the number of query terms.
+ // See: LUCENE-10207
+ long potentialExtraCost = terms.getSumDocFreq();
+ final long indexedTermCount = terms.size();
+ if (indexedTermCount != -1) {
+ potentialExtraCost -= indexedTermCount;
+ }
+ return termData.size() + potentialExtraCost;
Review Comment:
can we cap by `terms.getrDocCount()`? If `TermInSetQuery` has more terms than the segment's dictionary, or if this is a multi valued field with `sumDocFreq` > `docCount`, we could provide a tighter estimation here
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Improve cost estimate for AutomatonQuery [lucene]
Posted by "rmuir (via GitHub)" <gi...@apache.org>.
rmuir commented on PR #16801:
URL: https://github.com/apache/lucene/pull/16801#issuecomment-6090804577
i wonder if it makes sense to go even simpler, just drive behavior by finite/infinite. We don't even need to compute it, see PR #11813 for some details. Basically the queries pass the info already.
I realize this might not be as fancy as what you have in mind, but I think it works in practice. If the automaton accepts an infinite language then it can be assumed to match many terms.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Improve cost estimate for AutomatonQuery [lucene]
Posted by "romseygeek (via GitHub)" <gi...@apache.org>.
romseygeek commented on code in PR #16801:
URL: https://github.com/apache/lucene/pull/16801#discussion_r4228338145
##########
lucene/core/src/java/org/apache/lucene/search/MultiTermQuery.java:
##########
@@ -317,6 +317,22 @@ public long getTermsCount() {
return -1;
}
+ /**
+ * Return an upper-bound on the number of documents matched by this query. If not known,
+ * terms.getSumDocFreq() will be returned.
+ */
+ public final long estimateCost(Terms terms) {
Review Comment:
ScorerSupplier.cost() can throw an IOException, so I think it's fine for estimateCost() to throw one as well
##########
lucene/core/src/java/org/apache/lucene/search/AutomatonQuery.java:
##########
@@ -171,4 +179,136 @@ public boolean isAutomatonBinary() {
public long ramBytesUsed() {
return ramBytesUsed;
}
+
+ private static final int TERM_LIMIT_FOR_COST = 16;
+
+ @Override
+ protected long innerEstimateCost(Terms terms) throws IOException {
+ // Special cases of automata
+ if (compiled.type == CompiledAutomaton.AUTOMATON_TYPE.NONE) {
+ return 0;
+ } else if (compiled.type == CompiledAutomaton.AUTOMATON_TYPE.ALL) {
+ return terms.getSumDocFreq();
+ } else if (compiled.type == CompiledAutomaton.AUTOMATON_TYPE.SINGLE) {
+ TermsEnum t = terms.iterator();
+ return t.seekExact(compiled.term) ? t.docFreq() : 0;
+ }
+ assert compiled.type == CompiledAutomaton.AUTOMATON_TYPE.NORMAL;
+ // Special case: Few terms overall
+ if (terms.size() < TERM_LIMIT_FOR_COST) {
+ // Exhaustively sum cost of matching terms
+ long cost = 0;
+ ByteRunnable byteRunnable = compiled.getByteRunnable();
+ TermsEnum t = terms.iterator();
+ BytesRef term;
+ while ((term = t.next()) != null) {
+ if (byteRunnable.run(term.bytes, term.offset, term.length)) {
+ cost += t.docFreq();
+ }
+ }
+ return cost;
+ }
+ // General case. Find a covering range
+ BytesRef lowerBound = getBound(5, false);
+ BytesRef upperBound = getBound(5, true);
+ incrementBytesRef(upperBound);
+ TermsEnum t = terms.iterator();
+ TermsEnum.SeekStatus seekStatus = t.seekCeil(lowerBound);
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ // Automaton range is lexicographically greater than all terms
+ return 0;
+ } else if (upperBound.length == 0) {
+ // The upper bound is unbounded (usually a leading wildcard). Assume match-all.
+ return terms.getSumDocFreq();
+ } else if (t.term().compareTo(upperBound) >= 0) {
+ // Automaton range is lexicographically lower than all terms
+ return 0;
+ }
+ long cost = 0;
+ for (int i = 0; i < TERM_LIMIT_FOR_COST; i++) {
+ cost += t.docFreq();
Review Comment:
Yeah I worry that this is quite complex and still possibly expensive, when the core idea is to avoid running the automaton if it is costly to find the first match. I wonder if there are some simpler heuristics we can use here? eg detecting leading wildcards and returning very high costs for those, vs a lower fixed cost for anything with a fixed prefix.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Improve cost estimate for AutomatonQuery [lucene]
Posted by "msfroh (via GitHub)" <gi...@apache.org>.
msfroh commented on PR #16801:
URL: https://github.com/apache/lucene/pull/16801#issuecomment-6124947825
> i wonder if it makes sense to go even simpler, just drive behavior by finite/infinite. We don't even need to compute it, see PR https://github.com/apache/lucene/pull/11813 for some details. Basically the queries pass the info already.
For AutomatonQuery, it looks like we always pass `false` for `finite` (but we ignore that for the `NONE`/`SINGLE` compiled types).
Instead, I decided to strip out the helper methods to find the term bounds and just keep the special cases, particularly the "term dictionary is small" case.
Talking w/ @romseygeek at Community over Code, he suggested that the top special cases (where we look at `compiled.type`) should be moved into the constructor and used to override the `RewriteMethod`. We could directly rewrite `NONE` to `MatchNoDocsQuery`, `ALL` to `FieldExistsQuery`, and `SINGLE` to `TermQuery`. That means taking `CompiledAutomaton` in the constructor, though, which is a bigger refactoring that (IMO) belongs in a separate PR.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Improve cost estimate for AutomatonQuery [lucene]
Posted by "msfroh (via GitHub)" <gi...@apache.org>.
msfroh commented on code in PR #16801:
URL: https://github.com/apache/lucene/pull/16801#discussion_r4224163528
##########
lucene/core/src/java/org/apache/lucene/search/AutomatonQuery.java:
##########
@@ -171,4 +179,136 @@ public boolean isAutomatonBinary() {
public long ramBytesUsed() {
return ramBytesUsed;
}
+
+ private static final int TERM_LIMIT_FOR_COST = 16;
+
+ @Override
+ protected long innerEstimateCost(Terms terms) throws IOException {
+ // Special cases of automata
+ if (compiled.type == CompiledAutomaton.AUTOMATON_TYPE.NONE) {
+ return 0;
+ } else if (compiled.type == CompiledAutomaton.AUTOMATON_TYPE.ALL) {
+ return terms.getSumDocFreq();
+ } else if (compiled.type == CompiledAutomaton.AUTOMATON_TYPE.SINGLE) {
+ TermsEnum t = terms.iterator();
+ return t.seekExact(compiled.term) ? t.docFreq() : 0;
+ }
+ assert compiled.type == CompiledAutomaton.AUTOMATON_TYPE.NORMAL;
+ // Special case: Few terms overall
+ if (terms.size() < TERM_LIMIT_FOR_COST) {
+ // Exhaustively sum cost of matching terms
+ long cost = 0;
+ ByteRunnable byteRunnable = compiled.getByteRunnable();
+ TermsEnum t = terms.iterator();
+ BytesRef term;
+ while ((term = t.next()) != null) {
+ if (byteRunnable.run(term.bytes, term.offset, term.length)) {
+ cost += t.docFreq();
+ }
+ }
+ return cost;
+ }
+ // General case. Find a covering range
+ BytesRef lowerBound = getBound(5, false);
+ BytesRef upperBound = getBound(5, true);
+ incrementBytesRef(upperBound);
+ TermsEnum t = terms.iterator();
+ TermsEnum.SeekStatus seekStatus = t.seekCeil(lowerBound);
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ // Automaton range is lexicographically greater than all terms
+ return 0;
+ } else if (upperBound.length == 0) {
+ // The upper bound is unbounded (usually a leading wildcard). Assume match-all.
+ return terms.getSumDocFreq();
+ } else if (t.term().compareTo(upperBound) >= 0) {
+ // Automaton range is lexicographically lower than all terms
+ return 0;
+ }
+ long cost = 0;
+ for (int i = 0; i < TERM_LIMIT_FOR_COST; i++) {
+ cost += t.docFreq();
Review Comment:
I'm not sure if it makes sense to run the automaton over the term before including its cost.
It gives us a tighter bound, but it will be throw-away work if we exhaust the `TERM_LIMIT_FOR_COST` budget and just fall back to the match all estimate anyway.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Improve cost estimate for AutomatonQuery [lucene]
Posted by "txwei (via GitHub)" <gi...@apache.org>.
txwei commented on code in PR #16801:
URL: https://github.com/apache/lucene/pull/16801#discussion_r4300721577
##########
lucene/join/src/java/org/apache/lucene/search/join/TermsQuery.java:
##########
@@ -99,6 +99,17 @@ public long getTermsCount() {
return terms.size();
}
+ @Override
+ public long estimateCost(Terms terms) throws IOException {
+ // Copied from org.apache.lucene.search.TermInSetQuery.estimateCost
+ long potentialExtraCost = terms.getSumDocFreq();
+ final long indexedTermCount = terms.size();
+ if (indexedTermCount != -1) {
+ potentialExtraCost -= indexedTermCount;
+ }
+ return terms.size() + potentialExtraCost;
Review Comment:
```suggestion
return this.terms.size() + potentialExtraCost;
```
The `terms` parameter here shadows the class field. Or can we rename the class to prevent this collision?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org