Add utility to measure vector search CPU cost sweeping across varying inputs like topK, vector count, dimension, segment count while preserving recall

[mikemccand]

Unlike lexical search, where CPU cost is fixed (ish) for a given set of documents and queries, regardless of one segment or N segments, vector search is trickier. (The ish caveat is because there is a fixed per-segment cost to check terms dict, initialize iterators, etc., so there is some "widening tax" even for lexical search).

It's fun to model the cost of Lucene's vector query (HNSW crawl) since the algorithm is theoretically O(log(N)), but there is some floor cost that drives back to O(N). E.g. if vector count is small, Lucene should fallback to brute force (indeed Lucene now doesn't build HNSW graph for tiny segments, by default, so all queries will be brute force for that segment). Or, for good recall, if you have a moderate number of vectors in the HNSW graph, you still need a fairly large ef-search (ef is exploration factor, really the size of the exploration priority queue -- fanout (additive) and oversample (multiplicative) are different ways to express the same thing) so there is a floor for that, driving CPU cost back to linear scan behavior.

Another cost driver from more segments is Lucene's optimistic vector query compensation for vectors falling randomly across segments. We assume law of large numbers (LoLN) is working (NOTE: it likely isn't, for an index with near-real-time updates, because the frequently updated documents will often be "different" in some way (at Amazon it's the more engaged / purchased products that are updated more frequently), and that'll produce newly flushed segments that are mostly these "different" documents, etc.) and add a small sqrt(topK) ish "let's overcollect a bit" factor when collecting from each segment. If LoLN isn't working, the vector query will go back to those leaves that might have further good vector matches and collect some more, iterating we get all radius or top K vector matches.

So that "widening tax" (more segments -> more total CPU cost) is inherent thanks to LoLN (happy path), or non-LoLN (unhappy path -- more rounds of collection). This tool would help us understand that too.

This tool should just runknnPerfTest.py across sweep of these input parameters and record / plot results. It should record all results, show total CPU cost, but also query latency on idle-ish CPU with many cores, since they trade off based on number of segments (currently the fundamental work unit is a single segment -- Lucene cannot sub-divide those (yet)).

Where this all will get interesting is 1) the relative size of the elusive "constant factors" that always seem to bring these big-oh discussions back to reality, and 2) where the gradual switchover is in practice from log(N) to N CPU cost.

[mikemccand]

Also note that this tool might approximate what a distributed search system (Opensearch, Elasticsearch) will see as total vector search cost due to sharding. It's not quite the same because these search engines do not implement the optimistic concurrency of Lucene's vector query... they may not even add the sqrt(K) LoLN factor? But it's otherwise the same problem -- searching across N shards/segments and merging to final topK hits.