Can we make brute-force faster in the highly filtered case?

[benwtrent]

Description

@jimczi 's PR #130251 shows that we can make significant gains for flat indices when queried with a filter by not doing an exhaustive search of the scorers to build a bitset.

We periodically skip the vector index structure and brute-force if we know the number of vector ops to explore the index is likely higher than just scoring all the vectors referenced by a filter.

One idea is to use Weight#count(LeafReaderContext), and if it provides a count that isn't -1 and something < knnThreshold, don't build the bitset and simply iterate.

I am not sure we can use Scorer#iterator()#count(), as that can just be crazy inaccurate...but maybe its cheaper to check before building the bitset and such?

[elasticsearchmachine]

Pinging @elastic/es-search-relevance (Team:Search Relevance)

[jimczi]

++, the clean fix here is to move the logic into the knn query directly and probably allow for a threshold.

I am not sure we can use Scorer#iterator()#count()

We can do also do it in two steps, first a light one that use the ScoreSupplier#cost and then build the bitset if the cost is higher than the threshold, otherwise run brute force directly. We can still check the bitset cardinality in the second step to avoid the approximate search if it's below the threshold like we do today using k/num_candidates.

[tveasey]

I think we should be able to estimate expensive filter queries cardinalities accurately using random sampling, @jan-elastic is doing this to determine a sample probability when approximating ES|QL queries.