[Performance] Optimize num agg using quick select for topN

[vinaykpud]

Describe the bug

Problem: If the number of requested top-N buckets (N) often exceeded or was close to the maximum bucket ordinal, making the use of a PriorityQueue for top-N selection inefficient or redundant.

Solution: Introduced conditional logic to optimize bucket selection:
* If N > max bucket ordinal: No-op (return all buckets).
* If N < max bucket ordinal but N is bellow 10% of max bucket ordinal: Use quickselect for top-N.
* Otherwise: Use PriorityQueue for top-N.

Related component

Search:Performance

Additional Details

Plugins
NA

Screenshots
NA

Host/Environment (please complete the following information):

• Tests using r5.xl host with EBS Gp3 16000 IOPS, 500Gb and 1000 throughput.

Additional context
Add any other context about the problem here.

[vinaykpud]

Benchmark Testing

Test Setup

Cluster Configuration:

• Test approach: Comparative testing with and without the optimization
• Dataset: big5 dataset with 202,000 documents ingested

Data Ingestion:

opensearch-benchmark execute-test --workload=big5 --target-hosts=localhost:9200 \
  --kill-running-processes --workload-params "corpus_size:60,ingest_percentage:0.29" \
  --exclude-tasks="check-cluster-health"

Index Enhancement:

• Additional field added to the index: Custom generated numeric data with 100000 cardinality
• Total buckets: 202,000 (maintaining high cardinality-to-document ratio)

Benchmark Execution:

opensearch-benchmark execute-test --pipeline=benchmark-only --workload=big5 \
  --target-hosts=localhost:9200 --kill-running-processes \
  --include-tasks "numeric-terms-agg" --telemetry=node-stats

• Target task: numeric-terms-agg
• Iteration details for this task: numeric-terms-agg

Updated the size in this task based on the test.

Test Scenarios

Scenario 1: Request Size Exceeds Bucket Count

Configuration:

• Request size: 100,000
• Shard size calculation: size × 1.5 + 10 = 150,010

Without the change:

|                                                  Segment count |                   |           9 |        |
|                                                 Min Throughput | numeric-terms-agg |           2 |  ops/s |
|                                                Mean Throughput | numeric-terms-agg |           2 |  ops/s |
|                                              Median Throughput | numeric-terms-agg |           2 |  ops/s |
|                                                 Max Throughput | numeric-terms-agg |           2 |  ops/s |
|                                        50th percentile latency | numeric-terms-agg |     423.169 |     ms |
|                                        90th percentile latency | numeric-terms-agg |     436.129 |     ms |
|                                        99th percentile latency | numeric-terms-agg |     445.212 |     ms |
|                                       100th percentile latency | numeric-terms-agg |     447.031 |     ms |
|                                   50th percentile service time | numeric-terms-agg |      421.71 |     ms |
|                                   90th percentile service time | numeric-terms-agg |      434.42 |     ms |
|                                   99th percentile service time | numeric-terms-agg |     444.156 |     ms |
|                                  100th percentile service time | numeric-terms-agg |     446.255 |     ms |
|                                                     error rate | numeric-terms-agg |           0 |      % |

With the change:

|                                                  Segment count |                   |           9 |        |
|                                                 Min Throughput | numeric-terms-agg |        1.98 |  ops/s |
|                                                Mean Throughput | numeric-terms-agg |        1.98 |  ops/s |
|                                              Median Throughput | numeric-terms-agg |        1.98 |  ops/s |
|                                                 Max Throughput | numeric-terms-agg |        1.98 |  ops/s |
|                                        50th percentile latency | numeric-terms-agg |     379.352 |     ms |
|                                        90th percentile latency | numeric-terms-agg |     389.096 |     ms |
|                                        99th percentile latency | numeric-terms-agg |     410.804 |     ms |
|                                       100th percentile latency | numeric-terms-agg |     416.678 |     ms |
|                                   50th percentile service time | numeric-terms-agg |     378.019 |     ms |
|                                   90th percentile service time | numeric-terms-agg |     387.778 |     ms |
|                                   99th percentile service time | numeric-terms-agg |     408.871 |     ms |
|                                  100th percentile service time | numeric-terms-agg |     414.099 |     ms |
|                                                     error rate | numeric-terms-agg |           0 |      % |

Scenario 2: Request size close to the number of buckets

Without the change:

|                                                  Segment count |                   |           9 |        |
|                                                 Min Throughput | numeric-terms-agg |           2 |  ops/s |
|                                                Mean Throughput | numeric-terms-agg |           2 |  ops/s |
|                                              Median Throughput | numeric-terms-agg |           2 |  ops/s |
|                                                 Max Throughput | numeric-terms-agg |           2 |  ops/s |
|                                        50th percentile latency | numeric-terms-agg |     324.152 |     ms |
|                                        90th percentile latency | numeric-terms-agg |     337.027 |     ms |
|                                        99th percentile latency | numeric-terms-agg |     348.029 |     ms |
|                                       100th percentile latency | numeric-terms-agg |     349.737 |     ms |
|                                   50th percentile service time | numeric-terms-agg |     322.748 |     ms |
|                                   90th percentile service time | numeric-terms-agg |      335.61 |     ms |
|                                   99th percentile service time | numeric-terms-agg |     346.974 |     ms |
|                                  100th percentile service time | numeric-terms-agg |     348.822 |     ms |
|                                                     error rate | numeric-terms-agg |           0 |      % |

With the change:

|                                                  Segment count |                   |           9 |        |
|                                                 Min Throughput | numeric-terms-agg |        1.98 |  ops/s |
|                                                Mean Throughput | numeric-terms-agg |        1.99 |  ops/s |
|                                              Median Throughput | numeric-terms-agg |        1.99 |  ops/s |
|                                                 Max Throughput | numeric-terms-agg |        1.99 |  ops/s |
|                                        50th percentile latency | numeric-terms-agg |     304.058 |     ms |
|                                        90th percentile latency | numeric-terms-agg |     313.837 |     ms |
|                                        99th percentile latency | numeric-terms-agg |     322.633 |     ms |
|                                       100th percentile latency | numeric-terms-agg |     323.049 |     ms |
|                                   50th percentile service time | numeric-terms-agg |     302.764 |     ms |
|                                   90th percentile service time | numeric-terms-agg |     312.765 |     ms |
|                                   99th percentile service time | numeric-terms-agg |     321.439 |     ms |
|                                  100th percentile service time | numeric-terms-agg |     321.984 |     ms |
|                                                     error rate | numeric-terms-agg |  

Scenario 3: Request size is just above the 20% of bucketSize

size: 13400

Without the change:

|                                                  Segment count |                   |           9 |        |
|                                                 Min Throughput | numeric-terms-agg |        1.99 |  ops/s |
|                                                Mean Throughput | numeric-terms-agg |        1.99 |  ops/s |
|                                              Median Throughput | numeric-terms-agg |        1.99 |  ops/s |
|                                                 Max Throughput | numeric-terms-agg |        1.99 |  ops/s |
|                                        50th percentile latency | numeric-terms-agg |     119.847 |     ms |
|                                        90th percentile latency | numeric-terms-agg |     131.781 |     ms |
|                                        99th percentile latency | numeric-terms-agg |     141.155 |     ms |
|                                       100th percentile latency | numeric-terms-agg |     144.607 |     ms |
|                                   50th percentile service time | numeric-terms-agg |     118.381 |     ms |
|                                   90th percentile service time | numeric-terms-agg |     130.486 |     ms |
|                                   99th percentile service time | numeric-terms-agg |     139.373 |     ms |
|                                  100th percentile service time | numeric-terms-agg |     142.795 |     ms |
|                                                     error rate | numeric-terms-agg |           0 |      % |

With the change:

|                                                  Segment count |                   |           9 |        |
|                                                 Min Throughput | numeric-terms-agg |        1.99 |  ops/s |
|                                                Mean Throughput | numeric-terms-agg |        1.99 |  ops/s |
|                                              Median Throughput | numeric-terms-agg |        1.99 |  ops/s |
|                                                 Max Throughput | numeric-terms-agg |        1.99 |  ops/s |
|                                        50th percentile latency | numeric-terms-agg |     105.571 |     ms |
|                                        90th percentile latency | numeric-terms-agg |     113.951 |     ms |
|                                        99th percentile latency | numeric-terms-agg |      118.87 |     ms |
|                                       100th percentile latency | numeric-terms-agg |     119.426 |     ms |
|                                   50th percentile service time | numeric-terms-agg |     104.197 |     ms |
|                                   90th percentile service time | numeric-terms-agg |     112.863 |     ms |
|                                   99th percentile service time | numeric-terms-agg |     117.386 |     ms |
|                                  100th percentile service time | numeric-terms-agg |     117.688 |     ms |
|                                                     error rate | numeric-terms-agg |           0 |      % |

Scenario 4: Request size bellow 20% of bucket size

size: 6700

Without the change:

|                                                  Segment count |                   |           9 |        |
|                                                 Min Throughput | numeric-terms-agg |        1.99 |  ops/s |
|                                                Mean Throughput | numeric-terms-agg |        1.99 |  ops/s |
|                                              Median Throughput | numeric-terms-agg |        1.99 |  ops/s |
|                                                 Max Throughput | numeric-terms-agg |        1.99 |  ops/s |
|                                        50th percentile latency | numeric-terms-agg |     77.2796 |     ms |
|                                        90th percentile latency | numeric-terms-agg |     86.7455 |     ms |
|                                        99th percentile latency | numeric-terms-agg |     90.2567 |     ms |
|                                       100th percentile latency | numeric-terms-agg |     90.6284 |     ms |
|                                   50th percentile service time | numeric-terms-agg |     75.5727 |     ms |
|                                   90th percentile service time | numeric-terms-agg |      85.178 |     ms |
|                                   99th percentile service time | numeric-terms-agg |     88.2611 |     ms |
|                                  100th percentile service time | numeric-terms-agg |     88.8449 |     ms |
|                                                     error rate | numeric-terms-agg |           0 |      % |

With the change:

|                                                  Segment count |                   |           9 |        |
|                                                 Min Throughput | numeric-terms-agg |           2 |  ops/s |
|                                                Mean Throughput | numeric-terms-agg |           2 |  ops/s |
|                                              Median Throughput | numeric-terms-agg |           2 |  ops/s |
|                                                 Max Throughput | numeric-terms-agg |           2 |  ops/s |
|                                        50th percentile latency | numeric-terms-agg |     79.2366 |     ms |
|                                        90th percentile latency | numeric-terms-agg |     84.6647 |     ms |
|                                        99th percentile latency | numeric-terms-agg |     98.0447 |     ms |
|                                       100th percentile latency | numeric-terms-agg |     99.9183 |     ms |
|                                   50th percentile service time | numeric-terms-agg |     77.8026 |     ms |
|                                   90th percentile service time | numeric-terms-agg |     83.2122 |     ms |
|                                   99th percentile service time | numeric-terms-agg |     96.4292 |     ms |
|                                  100th percentile service time | numeric-terms-agg |     98.4293 |     ms |
|                                                     error rate | numeric-terms-agg |           0 |      % |

So in all the above cases we observed improvement in the latency with this change, especially when the cardinality is high,

Bellow graph shows all the latency comparisons:

Bellow graph shows the heap used, we dont see much difference when we compared with the change.

Bellow graph shows the CPU used, we dont see much difference when we compared with the change.