Grow docidsetbuilder to number of results instead of max doc id returned

[jmazanec15]

When creating results, we create a DocIdSetBuilder and grow the results to the max doc id returned in the query.

For instance, if we had 3 results: [2, 2000, 20,000,000], the DocIdSetBuilder would be grown to 20,000,000 docs. This would then cause Lucene to use a bitset instead of a sorted array of integers for the results.

In the case above, the iterator would take 20,000,000 bits (20 MB) instead of 3 * 32 bits/int = 96 bits.

Instead of calling DocIdSetBuilder.grow(maxDoc), we should call DocIdSetBuilder.grow(results.length). Then, lucene can internally handle the optimization of switching from sparse to dense.

We should benchmark this change as well to see if there are any improvements/degradations.

[jmazanec15]

Experimental setup

I ran performance tests on the sift data set which has 1M 128D vectors with a 10K query set. I tested faiss HNSW with m=16, ef_search=64 and ef_construction=64. I setup cluster with 2.1 with 3 c5.xlarge leaders and 1 r5.2xlarge data nodes. The control cluster came from the official 2.1 release. The test cluster was based off of https://github.com/jmazanec15/k-NN-1/tree/change-docsize-iterator. I ran 3 iterations of each. I used 1 primary shard and 0 replicas. Benchmark code can be found in https://github.com/opensearch-project/k-NN/tree/main/benchmarks/osb.

Results

Control

Experiment 1

|                                                 Min Throughput | knn-query-from-data-set |     6.47 |  ops/s |
|                                                Mean Throughput | knn-query-from-data-set |    188.2 |  ops/s |
|                                              Median Throughput | knn-query-from-data-set |   211.49 |  ops/s |
|                                                 Max Throughput | knn-query-from-data-set |   231.17 |  ops/s |
|                                        50th percentile latency | knn-query-from-data-set |  39.0271 |     ms |
|                                        90th percentile latency | knn-query-from-data-set |  52.0604 |     ms |
|                                        99th percentile latency | knn-query-from-data-set |  81.5243 |     ms |
|                                      99.9th percentile latency | knn-query-from-data-set |  133.603 |     ms |
|                                     99.99th percentile latency | knn-query-from-data-set |  854.554 |     ms |
|                                       100th percentile latency | knn-query-from-data-set |   867.14 |     ms |
|                                                     error rate | knn-query-from-data-set |        0 |      % |

Experiment 2

|                                                 Min Throughput | knn-query-from-data-set |      10.87 |  ops/s |
|                                                Mean Throughput | knn-query-from-data-set |     234.99 |  ops/s |
|                                              Median Throughput | knn-query-from-data-set |     251.93 |  ops/s |
|                                                 Max Throughput | knn-query-from-data-set |     260.83 |  ops/s |
|                                        50th percentile latency | knn-query-from-data-set |    35.7589 |     ms |
|                                        90th percentile latency | knn-query-from-data-set |    44.9456 |     ms |
|                                        99th percentile latency | knn-query-from-data-set |    58.0603 |     ms |
|                                      99.9th percentile latency | knn-query-from-data-set |    503.916 |     ms |
|                                     99.99th percentile latency | knn-query-from-data-set |    517.919 |     ms |
|                                       100th percentile latency | knn-query-from-data-set |    1057.44 |     ms |
|                                                     error rate | knn-query-from-data-set |          0 |      % |

Experiment 3

|                                                 Min Throughput | knn-query-from-data-set |    20.74 |  ops/s |
|                                                Mean Throughput | knn-query-from-data-set |    232.5 |  ops/s |
|                                              Median Throughput | knn-query-from-data-set |   246.69 |  ops/s |
|                                                 Max Throughput | knn-query-from-data-set |   253.55 |  ops/s |
|                                        50th percentile latency | knn-query-from-data-set |  37.2449 |     ms |
|                                        90th percentile latency | knn-query-from-data-set |  45.7525 |     ms |
|                                        99th percentile latency | knn-query-from-data-set |   55.398 |     ms |
|                                      99.9th percentile latency | knn-query-from-data-set |  100.796 |     ms |
|                                     99.99th percentile latency | knn-query-from-data-set |  492.354 |     ms |
|                                       100th percentile latency | knn-query-from-data-set |  493.705 |     ms |
|                                                     error rate | knn-query-from-data-set |        0 |    %   |

Test

Experiment 1

|                                                 Min Throughput | knn-query-from-data-set |      6.72 |  ops/s |
|                                                Mean Throughput | knn-query-from-data-set |    188.53 |  ops/s |
|                                              Median Throughput | knn-query-from-data-set |    211.86 |  ops/s |
|                                                 Max Throughput | knn-query-from-data-set |    230.38 |  ops/s |
|                                        50th percentile latency | knn-query-from-data-set |   39.5459 |     ms |
|                                        90th percentile latency | knn-query-from-data-set |   52.3563 |     ms |
|                                        99th percentile latency | knn-query-from-data-set |    78.303 |     ms |
|                                      99.9th percentile latency | knn-query-from-data-set |   137.948 |     ms |
|                                     99.99th percentile latency | knn-query-from-data-set |   853.653 |     ms |
|                                       100th percentile latency | knn-query-from-data-set |   878.597 |     ms |
|                                                     error rate | knn-query-from-data-set |         0 |      % |

Experiment 2

|                                                 Min Throughput | knn-query-from-data-set |    10.67 |  ops/s |
|                                                Mean Throughput | knn-query-from-data-set |   233.56 |  ops/s |
|                                              Median Throughput | knn-query-from-data-set |   250.13 |  ops/s |
|                                                 Max Throughput | knn-query-from-data-set |   257.96 |  ops/s |
|                                        50th percentile latency | knn-query-from-data-set |  36.4199 |     ms |
|                                        90th percentile latency | knn-query-from-data-set |  45.4275 |     ms |
|                                        99th percentile latency | knn-query-from-data-set |  56.1804 |     ms |
|                                      99.9th percentile latency | knn-query-from-data-set |  126.153 |     ms |
|                                     99.99th percentile latency | knn-query-from-data-set |  519.331 |     ms |
|                                       100th percentile latency | knn-query-from-data-set |  524.645 |     ms |
|                                                     error rate | knn-query-from-data-set |        0 |      % |

Experiment 3

|                                                 Min Throughput | knn-query-from-data-set |    10.69 |  ops/s |
|                                                Mean Throughput | knn-query-from-data-set |   254.95 |  ops/s |
|                                              Median Throughput | knn-query-from-data-set |   273.35 |  ops/s |
|                                                 Max Throughput | knn-query-from-data-set |   281.37 |  ops/s |
|                                   50th percentile service time | knn-query-from-data-set |   33.038 |     ms |
|                                   90th percentile service time | knn-query-from-data-set |  41.4406 |     ms |
|                                   99th percentile service time | knn-query-from-data-set |  50.1554 |     ms |
|                                 99.9th percentile service time | knn-query-from-data-set |  511.439 |     ms |
|                                99.99th percentile service time | knn-query-from-data-set |  519.468 |     ms |
|                                  100th percentile service time | knn-query-from-data-set |  1054.82 |     ms |
|                                                     error rate | knn-query-from-data-set |        0 |      % |

Conclusion

Performance is similar on the given data set.

[martin-gaievski]

Seems that data for experiments 2 and 3 do not show much of improvement, and rather worse performance for some metrics. Are these results accurate?

[jmazanec15]

@martin-gaievski For this experiment, Im not sure we will see too much improvement for a data set this small. Overall, the tests above show that the change does not cause any major regressions. We will need to see on a larger data set to see more subtle improvements.

I thought about running a 1B test, but I think the size of the change probably doesnt warrant it. I would like to group a few changes together before running 1B.