Improve DiskBBQ filtered search through filtering centroids

[benwtrent]

Description

When doing a filtered search over DiskBBQ, do the simple thing and explore more centroids until we capture the expected overall percentage of vectors.

However, this means we just explore more and more centroids, scoring more and visiting useless centroids. While we don't actually do any vector ops, its interesting to see how docID decoding and figuring out there are not matches, becomes a strangely dominate cost.

I think we can speed up highly filtered search through adding (though this may be expensive) an additional mapping from vectorOrd -> [centroid_primary, centroid_overspill]

When we detect very specific filters, such that the probability of hitting the vectors in a centroid becomes very low, we can do a first pass with that restricted filter to gather the matching centroids, and then only score those.

This should be optional as I expect it to add overhead at index and index size, though I expect the index size to not be effect way too much?

//cc @jimczi

[elasticsearchmachine]

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

[benwtrent]

Incidentally, I think this will unlock some merge time benefits as now we will have the relationship

vector -> centroid

instead of only

centroid -> vector

Which may allow us to:

• merge nearest centroids to gather initial layer of hkmeans
• iterate the vectors, utilizing their centroid to find their appropriate assignment given first hkmeans centroids
• split and iterate hkmeans as normal
• initialize the final iteration passes based on original centroids

[benwtrent]

I would imagine the logic for when this should be done is something like:

• Likelihood a vector is randomly within a centroid
• Compare that likelihood with the filter likelihood
• If that is past some threshold, gather the valid assignments and their counts
• Account for bias in centroid scoring order (biasing towards highly represented clusters & higher scoring ones)

I would expect the filter percentage must be tiny (1%?) for this to really pay off.

[benwtrent]

Addressed by:

• [DiskBBQ] save same vector operations when performing centroid filtering #138312
• [DiskBBQ] Fix Computation of DocsPerCentroid #138173
• [DiskBBQ] avoid EsAcceptDocs bug by calling cost before building iterator #138127
• [DiskBBQ] Support for centroid filtering for restrictive filters #137959