[PR] perf: Optimize HLL sketch merge by avoiding unnecessary HLL_8 to HLL_4 conversion (druid)

["maytasm (via GitHub)" <gi...@apache.org>]

maytasm opened a new pull request, #19482:
URL: https://github.com/apache/druid/pull/19482

   perf: Optimize HLL sketch merge by avoiding unnecessary HLL_8 to HLL_4 conversion
   
   ### Description
   
   This is a further improvement built on top of https://github.com/apache/druid/pull/13737
   
     - When two Union-backed HllSketchHolder instances are merged on the broker (e.g. during ParallelMergeCombiningSequence), the old code called other.getSketch() which invokes Union.getResult() — defaulting to HLL_4 output type. Since the Union internally stores data as HLL_8, this triggers an expensive convertToHll4 operation with an O(K) curMinAndNum scan. The receiving union then immediately converts the HLL_4 sketch back to HLL_8 internally.
     - This change detects the union-to-union merge case and calls Union.getResult(TgtHllType.HLL_8) instead, which returns an HLL_8 sketch via a cheap byte[].clone(). The receiving union accepts any HLL type, so correctness is preserved.
     - Adds a mergeUnionHolders benchmark to DataSketchesHllBenchmark covering this merge path.
   
   ### Testing Results
   
   Flame Graph Analysis: Before vs After this PR
   The below flame graphs are taken of the same query. The query is a group by on high cardinality dimension with APPROX_COUNT_DISTINCT_DS_HLL
   
   Before (avg of 2 runs, ~11 min total):
     - convertToHll4: ~1,541 samples (7.5% of HLL work)
     - curMinAndNum: ~1,553 samples (8.1% of HLL work)
     - Total HLL samples: ~20,261
     - Total flame graph samples: ~5.1M
   
   After (avg of 2 runs, ~700s total):
     - convertToHll4: 0 samples — completely eliminated
     - curMinAndNum: 0 samples — completely eliminated
     - copyAs (the cheap HLL_8 same-type copy): ~191 samples (1.3% of HLL work)
     - Total HLL samples: ~15,135
     - Total flame graph samples: ~2.8M
     
   The expensive HLL_8 → HLL_4 conversion and the O(K) curMinAndNum scan are gone. The replacement copyAs(HLL_8) path is just a byte[].clone() at ~191 samples — roughly 16x cheaper than the old path (~3,094 combined samples eliminated, replaced by ~191).
   
   The overall HLL footprint dropped by ~25% (20,261 → 15,135 samples), and total wall time dropped from ~11 min to ~700s.
   
   ##### Key changed/added classes in this PR
    * `extensions-core/datasketches/src/main/java/org/apache/druid/query/aggregation/datasketches/hll/HllSketchHolder.java`
   
   This PR has:
   
   - [x] been self-reviewed.
      - [ ] using the [concurrency checklist](https://github.com/apache/druid/blob/master/dev/code-review/concurrency.md) (Remove this item if the PR doesn't have any relation to concurrency.)
   - [ ] added documentation for new or modified features or behaviors.
   - [ ] a release note entry in the PR description.
   - [ ] added Javadocs for most classes and all non-trivial methods. Linked related entities via Javadoc links.
   - [ ] added or updated version, license, or notice information in [licenses.yaml](https://github.com/apache/druid/blob/master/dev/license.md)
   - [ ] added comments explaining the "why" and the intent of the code wherever would not be obvious for an unfamiliar reader.
   - [ ] added unit tests or modified existing tests to cover new code paths, ensuring the threshold for [code coverage](https://github.com/apache/druid/blob/master/dev/code-review/code-coverage.md) is met.
   - [ ] added integration tests.
   - [ ] been tested in a test Druid cluster.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org

Re: [PR] perf: Optimize HLL sketch merge by avoiding unnecessary HLL_8 to HLL_4 conversion (druid)

["gianm (via GitHub)" <gi...@apache.org>]

gianm merged PR #19482:
URL: https://github.com/apache/druid/pull/19482


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org