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: [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]
