msfroh commented on PR #16240: URL: https://github.com/apache/lucene/pull/16240#issuecomment-5039343744
I've been giving this some more thought, and I think I see the general shape of an incremental path forward: 1. We either modify the `getTermsCount()` method on `MultiTermQuery` or (probably better for backwards compatibility) add an override that takes a `LeafReaderContext`. Either way, in the `scorerSupplier` method, we can get a leaf-specific upper bound on the matching terms count for the query. 2. For PrefixQuery, at least, we can override `getTermsCount(LeafReaderContext)` to seek to the first matching term and to the first non-matching term. The number of matching terms on the current segment is exactly the difference between their `ord()` values (and can be computed in logarithmic time with respect to the term count). 3. The PrefixQuery logic can be generalized to cover any term range (since it's just a special case of a term range). 4. I *think* for any Automaton, we can cheaply compute a covering range. At the very least, if we can identify a minimum and maximum valid transition from the start state, then the range is from the minimum to the maximum + 1. Alternatively, if the number of valid transitions from the start state is small (e.g. a case-insensitive term query), we could just treat it as a union of prefixes. I *think* this will let us correctly identify the cases where the number of matching terms is definitely small and easy to compute (so the `ScorerSupplier` can produce a "true" cost without wasting effort). We could incrementally work towards it in the order given above. (Or maybe I just jump from step 1 straight to step 4, since it already covers steps 2 and 3, and isn't *that* complicated.) At the end of the day, I think I just reached the same line of thinking as @romseygeek had in mind in https://github.com/apache/lucene/pull/16240#issuecomment-4727391762, but I needed to come at it from a different angle to wrap my head around it. -- 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]
