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