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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
