You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by "adarshsanjeev (via GitHub)" <gi...@apache.org> on 2023/10/15 17:17:52 UTC

[PR] HllSketch Merge Aggregator optimizations (druid)

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

   ### Description
   
   This PR attempts to improve the performance of HllSketchMergeAggregators.
   
   <hr>
   
   <!-- Check the items by putting "x" in the brackets for the done things. Not all of these items apply to every PR. Remove the items which are not done or not relevant to the PR. None of the items from the checklist below are strictly necessary, but it would be very helpful if you at least self-review the PR. -->
   
   This PR has:
   
   - [ ] 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] HllSketch Merge Aggregator optimizations (druid)

Posted by "adarshsanjeev (via GitHub)" <gi...@apache.org>.
adarshsanjeev commented on code in PR #15162:
URL: https://github.com/apache/druid/pull/15162#discussion_r1363207654


##########
extensions-core/datasketches/src/main/java/org/apache/druid/query/aggregation/datasketches/hll/HllSketchHolderObjectStrategy.java:
##########
@@ -67,4 +74,32 @@ public HllSketchHolder fromByteBufferSafe(ByteBuffer buffer, int numBytes)
         )
     );
   }
+
+  private boolean isSafeToConvertToNullSketch(ByteBuffer buf)
+  {
+    // TODO: Might need a sanity check here, to ensure that position and offset makes sense.

Review Comment:
   Added a check here



-- 
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] HllSketch Merge Aggregator optimizations (druid)

Posted by "adarshsanjeev (via GitHub)" <gi...@apache.org>.
adarshsanjeev commented on PR #15162:
URL: https://github.com/apache/druid/pull/15162#issuecomment-1793819554

   @imply-cheddar Sure, I'll follow up on that


-- 
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] HllSketch Merge Aggregator optimizations (druid)

Posted by "adarshsanjeev (via GitHub)" <gi...@apache.org>.
adarshsanjeev commented on code in PR #15162:
URL: https://github.com/apache/druid/pull/15162#discussion_r1363217612


##########
extensions-core/datasketches/src/main/java/org/apache/druid/query/aggregation/datasketches/hll/HllSketchHolderObjectStrategy.java:
##########
@@ -48,12 +49,18 @@ public int compare(final HllSketchHolder sketch1, final HllSketchHolder sketch2)
   @Override
   public HllSketchHolder fromByteBuffer(final ByteBuffer buf, final int size)
   {
+    if (size == 0 || isSafeToConvertToNullSketch(buf)) {
+      return HllSketchHolder.of((HllSketch) null);
+    }
     return HllSketchHolder.of(HllSketch.wrap(Memory.wrap(buf, ByteOrder.LITTLE_ENDIAN).region(buf.position(), size)));
   }
 
   @Override
   public byte[] toBytes(final HllSketchHolder sketch)
   {
+    if (sketch.getSketch() == null || sketch.getSketch().isEmpty()) {

Review Comment:
   Good callout! I think I missed this initially. I'll try to make sure that I stick to this in the future.
   Also, renamed the holder parameter.



-- 
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] HllSketch Merge Aggregator optimizations (druid)

Posted by "asdf2014 (via GitHub)" <gi...@apache.org>.
asdf2014 merged PR #15162:
URL: https://github.com/apache/druid/pull/15162


-- 
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] HllSketch Merge Aggregator optimizations (druid)

Posted by "adarshsanjeev (via GitHub)" <gi...@apache.org>.
adarshsanjeev commented on code in PR #15162:
URL: https://github.com/apache/druid/pull/15162#discussion_r1363233247


##########
extensions-core/datasketches/src/main/java/org/apache/druid/query/aggregation/datasketches/hll/HllSketchHolderObjectStrategy.java:
##########
@@ -67,4 +74,32 @@ public HllSketchHolder fromByteBufferSafe(ByteBuffer buffer, int numBytes)
         )
     );
   }
+
+  private boolean isSafeToConvertToNullSketch(ByteBuffer buf)
+  {
+    // TODO: Might need a sanity check here, to ensure that position and offset makes sense.
+
+    // Get org.apache.datasketches.hll.CurMode. This indicates the type of data structure.
+    final int position = buf.position();
+    final int preInts = buf.get(position) & 0X3F; // get(PREAMBLE_INTS_BYTE) & 0X3F
+    final int curMode = buf.get(position + 7) & 3;    // get(MODE_BYTE) & CUR_MODE_MASK
+
+    switch (curMode) {
+      case 0:          // LIST
+        Preconditions.checkArgument(preInts == 2);  // preInts == LIST_PREINTS, Sanity

Review Comment:
   Changed the code here to return false instead. I think the point about using DruidException instead of Guava makes sense.



-- 
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] HllSketch Merge Aggregator optimizations (druid)

Posted by "imply-cheddar (via GitHub)" <gi...@apache.org>.
imply-cheddar commented on code in PR #15162:
URL: https://github.com/apache/druid/pull/15162#discussion_r1360088821


##########
extensions-core/datasketches/src/main/java/org/apache/druid/query/aggregation/datasketches/hll/HllSketchHolderObjectStrategy.java:
##########
@@ -67,4 +74,32 @@ public HllSketchHolder fromByteBufferSafe(ByteBuffer buffer, int numBytes)
         )
     );
   }
+
+  private boolean isSafeToConvertToNullSketch(ByteBuffer buf)
+  {
+    // TODO: Might need a sanity check here, to ensure that position and offset makes sense.
+
+    // Get org.apache.datasketches.hll.CurMode. This indicates the type of data structure.
+    final int position = buf.position();
+    final int preInts = buf.get(position) & 0X3F; // get(PREAMBLE_INTS_BYTE) & 0X3F
+    final int curMode = buf.get(position + 7) & 3;    // get(MODE_BYTE) & CUR_MODE_MASK
+
+    switch (curMode) {
+      case 0:          // LIST
+        Preconditions.checkArgument(preInts == 2);  // preInts == LIST_PREINTS, Sanity

Review Comment:
   `Preconditions.checkArgument` doesn't generate a nice exception for an end user and, this usage of `Preconditions` from Guava is one of the sources of code-level incompatibility between versions of Guava.  In general, it's best to avoid dependence on Guava wherever possible.  For checking an argument like this, it might make sense to add a static method on `DruidException` or have some other utility type place that will do the check and throw a `DruidException` instead of the generic `IllegalArgumentException`.
   
   That said, throwing an exception in this case seems overly zealous.  It seems better to just return false if our assumption is broken here and let the underlying HLL library do what it will with it.



##########
extensions-core/datasketches/src/main/java/org/apache/druid/query/aggregation/datasketches/hll/HllSketchHolderObjectStrategy.java:
##########
@@ -48,12 +49,18 @@ public int compare(final HllSketchHolder sketch1, final HllSketchHolder sketch2)
   @Override
   public HllSketchHolder fromByteBuffer(final ByteBuffer buf, final int size)
   {
+    if (size == 0 || isSafeToConvertToNullSketch(buf)) {
+      return HllSketchHolder.of((HllSketch) null);
+    }
     return HllSketchHolder.of(HllSketch.wrap(Memory.wrap(buf, ByteOrder.LITTLE_ENDIAN).region(buf.position(), size)));
   }
 
   @Override
   public byte[] toBytes(final HllSketchHolder sketch)
   {
+    if (sketch.getSketch() == null || sketch.getSketch().isEmpty()) {

Review Comment:
   Nit: let's rename the variable `sketch` to `holder`.  The code reads funny right now.
   
   Not nit: In the case that this if resolves to false and you return from the final line in this method, the code will have called `sketch.getSketch()` 3 times in this method.  That's 2 more times than it has to and there's no guarantee that `sketch.getSketch()` isn't doing a bunch of work on each independent call.  Yes, you can look at the implementation and see that it's going to be returning a materialized copy on each call after the first, but this code would be significantly improved if it just called `getSketch()` once and then did checks on that return value.  The only time a method should call the exact same getter multiple times in the same execution is when it expects to get different objects on each call.  If it always expects to get the same object, then the code should just get the object once and reuse that reference.  The impact here is minimal, but it is incredibly important that all code be written thinking about how many times methods are called and what references
  should be getting reused, because there are times when it actually does matter.  It's best to have all code follow good practices always than to pick and choose for this one.



##########
extensions-core/datasketches/src/main/java/org/apache/druid/query/aggregation/datasketches/hll/HllSketchHolderObjectStrategy.java:
##########
@@ -67,4 +74,32 @@ public HllSketchHolder fromByteBufferSafe(ByteBuffer buffer, int numBytes)
         )
     );
   }
+
+  private boolean isSafeToConvertToNullSketch(ByteBuffer buf)
+  {
+    // TODO: Might need a sanity check here, to ensure that position and offset makes sense.

Review Comment:
   The contract is that it should be safe to read `size` bytes from the `ByteBuffer`, so just pass size in here and trust that you can read that many bytes.



##########
extensions-core/datasketches/src/main/java/org/apache/druid/query/aggregation/datasketches/hll/HllSketchHolderObjectStrategy.java:
##########
@@ -48,12 +49,18 @@ public int compare(final HllSketchHolder sketch1, final HllSketchHolder sketch2)
   @Override
   public HllSketchHolder fromByteBuffer(final ByteBuffer buf, final int size)
   {
+    if (size == 0 || isSafeToConvertToNullSketch(buf)) {

Review Comment:
   If the `size` parameter is less than 8, then I believe that the `isSafeToConvertToNullSketch` method could end up throwing an exception when it reads out the value for `curMode`.  It would likely make sense to pass the size parameter into the `isSafe...` method and check the size there as well, returning false if it's too small. 



-- 
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] HllSketch Merge Aggregator optimizations (druid)

Posted by "adarshsanjeev (via GitHub)" <gi...@apache.org>.
adarshsanjeev commented on code in PR #15162:
URL: https://github.com/apache/druid/pull/15162#discussion_r1363217932


##########
extensions-core/datasketches/src/main/java/org/apache/druid/query/aggregation/datasketches/hll/HllSketchHolderObjectStrategy.java:
##########
@@ -48,12 +49,18 @@ public int compare(final HllSketchHolder sketch1, final HllSketchHolder sketch2)
   @Override
   public HllSketchHolder fromByteBuffer(final ByteBuffer buf, final int size)
   {
+    if (size == 0 || isSafeToConvertToNullSketch(buf)) {

Review Comment:
   Added a check on size inside the method wherever necessary



-- 
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] HllSketch Merge Aggregator optimizations (druid)

Posted by "gianm (via GitHub)" <gi...@apache.org>.
gianm commented on PR #15162:
URL: https://github.com/apache/druid/pull/15162#issuecomment-1780519338

   FYI I benchmarked this patch on a dataset with 11 groups and a few million sketches going into those groups (so, each Union would get hundreds-of-thousands of calls). It's about 37% faster.
   
   ```
   Query                   Status    Iter     Min     Avg  Median     Max   OK?
   watch_byuser_hll_12_4      200      25     454     463     461     511     Y [patch]
   watch_byuser_hll_12_4      200      25     622     636     636     665     Y [master]
   ```
   
   I also tried the case where the number of groups and number of sketches is similar. In this case the patch is slightly slower. I think it's worth it on balance though. The speedup in the speedup case is a lot bigger than the slowdown in the slowdown case.


-- 
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] HllSketch Merge Aggregator optimizations (druid)

Posted by "adarshsanjeev (via GitHub)" <gi...@apache.org>.
adarshsanjeev commented on PR #15162:
URL: https://github.com/apache/druid/pull/15162#issuecomment-1784597049

   @gianm Thanks for running perf tests on this PR! I've tried running a perf test on a sketch column with ~20M empty sketches and observed somewhat comparable results.
   
   Regarding the PR, while testing, I've noticed one issue with MSQ and estimation on an empty sketch, returning null instead of 0 after this change. I'll look into resolving it.


-- 
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] HllSketch Merge Aggregator optimizations (druid)

Posted by "adarshsanjeev (via GitHub)" <gi...@apache.org>.
adarshsanjeev commented on PR #15162:
URL: https://github.com/apache/druid/pull/15162#issuecomment-1784889319

   Resolved the above


-- 
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] HllSketch Merge Aggregator optimizations (druid)

Posted by "asdf2014 (via GitHub)" <gi...@apache.org>.
asdf2014 commented on code in PR #15162:
URL: https://github.com/apache/druid/pull/15162#discussion_r1379671744


##########
extensions-core/datasketches/src/main/java/org/apache/druid/query/aggregation/datasketches/hll/HllSketchToEstimatePostAggregator.java:
##########
@@ -97,7 +97,11 @@ public Comparator<Double> getComparator()
   @Override
   public Object compute(final Map<String, Object> combinedAggregators)
   {
-    final HllSketchHolder holder = HllSketchHolder.fromObj(field.compute(combinedAggregators));
+    Object hllSketchHolderObject = field.compute(combinedAggregators);
+    if (hllSketchHolderObject == null) {
+      return 0.0d;

Review Comment:
   ```suggestion
         return 0.0D;
   ```



-- 
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