You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by "aho135 (via GitHub)" <gi...@apache.org> on 2025/06/23 21:17:19 UTC
[PR] Sort JSON keys to fix comparator inconsistency (druid)
aho135 opened a new pull request, #18169:
URL: https://github.com/apache/druid/pull/18169
<!-- Thanks for trying to help us make Apache Druid be the best it can be! Please fill out as much of the following information as is possible (where relevant, and remove it when irrelevant) to help make the intention and scope of this PR clear in order to ease review. -->
<!-- Please read the doc for contribution (https://github.com/apache/druid/blob/master/CONTRIBUTING.md) before making this PR. Also, once you open a PR, please _avoid using force pushes and rebasing_ since these make it difficult for reviewers to see what you've changed in response to their reviews. See [the 'If your pull request shows conflicts with master' section](https://github.com/apache/druid/blob/master/CONTRIBUTING.md#if-your-pull-request-shows-conflicts-with-master) for more details. -->
Fixes #18156
<!-- Replace XXXX with the id of the issue fixed in this PR. Remove this section if there is no corresponding issue. Don't reference the issue in the title of this pull-request. -->
<!-- If you are a committer, follow the PR action item checklist for committers:
https://github.com/apache/druid/blob/master/dev/committer-instructions.md#pr-and-issue-action-item-checklist-for-committers. -->
### Description
<!-- Describe the goal of this PR, what problem are you fixing. If there is a corresponding issue (referenced above), it's not necessary to repeat the description here, however, you may choose to keep one summary sentence. -->
<!-- Describe your patch: what did you change in code? How did you fix the problem? -->
<!-- If there are several relatively logically separate changes in this PR, create a mini-section for each of them. For example: -->
When sorting StructuredData objects there is scenario that causes an IllegalArgumentException in TimSort. This occurs when there are two equivalent JSON objects with different key ordering being compared with a third object. This is demonstrated in the test case.
I am not sure if we should sort the keys at ingestion time, or just sort them for the purposes of the hash computation in StructuredData.
<!--
In each section, please describe design decisions made, including:
- Choice of algorithms
- Behavioral aspects. What configuration values are acceptable? How are corner cases and error conditions handled, such as when there are insufficient resources?
- Class organization and design (how the logic is split between classes, inheritance, composition, design patterns)
- Method organization and design (how the logic is split between methods, parameters and return types)
- Naming (class, method, API, configuration, HTTP endpoint, names of emitted metrics)
-->
<!-- It's good to describe an alternative design (or mention an alternative name) for every design (or naming) decision point and compare the alternatives with the designs that you've implemented (or the names you've chosen) to highlight the advantages of the chosen designs and names. -->
<!-- If there was a discussion of the design of the feature implemented in this PR elsewhere (e. g. a "Proposal" issue, any other issue, or a thread in the development mailing list), link to that discussion from this PR description and explain what have changed in your final design compared to your original proposal or the consensus version in the end of the discussion. If something hasn't changed since the original discussion, you can omit a detailed discussion of those aspects of the design here, perhaps apart from brief mentioning for the sake of readability of this PR description. -->
<!-- Some of the aspects mentioned above may be omitted for simple and small changes. -->
#### Release note
Sort keys in JSON objects to resolve a transitivity bug in the StructuredData comparator
<!-- Give your best effort to summarize your changes in a couple of sentences aimed toward Druid users.
If your change doesn't have end user impact, you can skip this section.
For tips about how to write a good release note, see [Release notes](https://github.com/apache/druid/blob/master/CONTRIBUTING.md#release-notes).
-->
<hr>
##### Key changed/added classes in this PR
* `ColumnSerializerUtils`
* `StructuredDataTest`
<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:
- [X] been self-reviewed.
- [ ] added documentation for new or modified features or behaviors.
- [X] 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.
- [X] 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.
- [X] 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] Sort JSON keys to fix comparator inconsistency (druid)
Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #18169:
URL: https://github.com/apache/druid/pull/18169#discussion_r2162777897
##########
processing/src/test/java/org/apache/druid/segment/nested/StructuredDataTest.java:
##########
@@ -95,6 +95,18 @@ public void testCompareTo()
}
+ @Test
+ public void testCompareToWithDifferentJSONOrder()
Review Comment:
Since this change introduces a subtle behavioral difference in how JSON columns are ingested or queried, could we also include a SQL query test? I think one option could be to add some rows with similar values we have here to a new column in `CalciteNestedDataQueryTest` and run a `GROUP BY` on the added column. Prior to the sorting behavior in this patch, the `GROUP BY` results with "duplicate values" would differ but now the results would be more inline with mysql with sorted keys?
--
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] Sort JSON keys to fix comparator inconsistency (druid)
Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 merged PR #18169:
URL: https://github.com/apache/druid/pull/18169
--
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] Sort JSON keys to fix comparator inconsistency (druid)
Posted by "aho135 (via GitHub)" <gi...@apache.org>.
aho135 commented on code in PR #18169:
URL: https://github.com/apache/druid/pull/18169#discussion_r2175714584
##########
processing/src/test/java/org/apache/druid/segment/nested/StructuredDataTest.java:
##########
@@ -95,6 +95,18 @@ public void testCompareTo()
}
+ @Test
+ public void testCompareToWithDifferentJSONOrder()
Review Comment:
Thanks for the review @clintropolis!
Sounds good, since key ordering during comparison is the minimal change to resolve the transitivity bug I'll revert to that. I do think in a follow up PR it could be worthwhile to have an option to sort keys at ingestion time though. I would imagine that this has some performance benefits at query time, especially for json with a large number of keys.
--
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] Sort JSON keys to fix comparator inconsistency (druid)
Posted by "aho135 (via GitHub)" <gi...@apache.org>.
aho135 commented on code in PR #18169:
URL: https://github.com/apache/druid/pull/18169#discussion_r2164463138
##########
processing/src/test/java/org/apache/druid/segment/nested/StructuredDataTest.java:
##########
@@ -95,6 +95,18 @@ public void testCompareTo()
}
+ @Test
+ public void testCompareToWithDifferentJSONOrder()
Review Comment:
Thanks for the review @abhishekrb19!
This current implementation only sorts the keys prior to hash computation, but key order remains the same. This is the minimal change to fix the transitivity bug. If we want to align with MySQL and Postgres jsonb then I can make these changes on the ColumnSerializerUtils.SMILE_MAPPER
The current behavior does align with Postgres json. What do you think the preferred behavior should be?
--
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] Sort JSON keys to fix comparator inconsistency (druid)
Posted by "aho135 (via GitHub)" <gi...@apache.org>.
aho135 commented on code in PR #18169:
URL: https://github.com/apache/druid/pull/18169#discussion_r2164463138
##########
processing/src/test/java/org/apache/druid/segment/nested/StructuredDataTest.java:
##########
@@ -95,6 +95,18 @@ public void testCompareTo()
}
+ @Test
+ public void testCompareToWithDifferentJSONOrder()
Review Comment:
Thanks for the review @abhishekrb19!
This current implementation only sorts the keys prior to hash computation. This is the minimal change to fix the transitivity bug. If we want to align with MySQL and Postgres jsonb then I can make these changes on the ColumnSerializerUtils.SMILE_MAPPER
The current behavior does align with Postgres json. What do you think the preferred behavior should be?
--
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] Sort JSON keys to fix comparator inconsistency (druid)
Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #18169:
URL: https://github.com/apache/druid/pull/18169#discussion_r2176140134
##########
processing/src/test/java/org/apache/druid/segment/nested/StructuredDataTest.java:
##########
@@ -95,6 +95,18 @@ public void testCompareTo()
}
+ @Test
+ public void testCompareToWithDifferentJSONOrder()
Review Comment:
Yeah, works for me. We can tackle the ingest-time ordering in a follow up if needed.
--
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] Sort JSON keys to fix comparator inconsistency (druid)
Posted by "clintropolis (via GitHub)" <gi...@apache.org>.
clintropolis commented on code in PR #18169:
URL: https://github.com/apache/druid/pull/18169#discussion_r2174420681
##########
processing/src/test/java/org/apache/druid/segment/nested/StructuredDataTest.java:
##########
@@ -95,6 +95,18 @@ public void testCompareTo()
}
+ @Test
+ public void testCompareToWithDifferentJSONOrder()
Review Comment:
I actually think it is fine to only do the key ordering during comparison, and maybe even preferable since it leaves the 'raw' json identical to how it was ingested.
>Enables better rollup during ingestion on json columns. Also, it would align with the current behavior of MySQL and Postgres's jsonb type. Postgres's json [type](https://www.postgresql.org/docs/current/datatype-json.html) preserves ingest-time order but doesn't support grouping on those columns.
I would think the key ordering would have very limited impact on the rollup factor; the sorting here is arbitrary since there isn't really a natural way to sort json, so it just needs to be 'stable' so we don't run into the error this PR aims to fix (good find btw).
--
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] Sort JSON keys to fix comparator inconsistency (druid)
Posted by "abhishekrb19 (via GitHub)" <gi...@apache.org>.
abhishekrb19 commented on code in PR #18169:
URL: https://github.com/apache/druid/pull/18169#discussion_r2162774283
##########
processing/src/main/java/org/apache/druid/segment/nested/StructuredData.java:
##########
@@ -46,7 +47,7 @@ public class StructuredData implements Comparable<StructuredData>
private static long computeHash(StructuredData data)
{
try {
- final byte[] bytes = ColumnSerializerUtils.SMILE_MAPPER.writeValueAsBytes(data.value);
+ final byte[] bytes = ColumnSerializerUtils.SMILE_MAPPER.writer(SerializationFeature.ORDER_MAP_ENTRIES_BY_KEYS).writeValueAsBytes(data.value);
Review Comment:
Could you define this as a static final constant `ObjectWriter` in this class so it can be reused if needed instead of instantiating a new object? Also, please include a comment on why this option is needed.
##########
processing/src/test/java/org/apache/druid/segment/nested/StructuredDataTest.java:
##########
@@ -95,6 +95,18 @@ public void testCompareTo()
}
+ @Test
+ public void testCompareToWithDifferentJSONOrder()
Review Comment:
Since this change introduces a subtle behavioral difference in how JSON columns are ingested or queried, could we also include a SQL query test? I think one option could be to add some rows with similar values we have here to a new column in `CalciteNestedDataQueryTest` and run a `GROUP BY` on the added column. Prior to the sorting behavior in this patch, the `GROUP BY` results would differ but now the results would be more inline with mysql with sorted keys?
--
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] Sort JSON keys to fix comparator inconsistency (druid)
Posted by "aho135 (via GitHub)" <gi...@apache.org>.
aho135 commented on code in PR #18169:
URL: https://github.com/apache/druid/pull/18169#discussion_r2176088973
##########
processing/src/test/java/org/apache/druid/segment/nested/StructuredDataTest.java:
##########
@@ -95,6 +95,18 @@ public void testCompareTo()
}
+ @Test
+ public void testCompareToWithDifferentJSONOrder()
Review Comment:
One way I was thinking to do this would be to add a new property in NestedDataColumnSchema (e.g. sortMapKeys). Then we can pass this value to StructuredData so it knows whether it needs to sort map keys before the hash computation
--
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] Sort JSON keys to fix comparator inconsistency (druid)
Posted by "aho135 (via GitHub)" <gi...@apache.org>.
aho135 commented on code in PR #18169:
URL: https://github.com/apache/druid/pull/18169#discussion_r2164463138
##########
processing/src/test/java/org/apache/druid/segment/nested/StructuredDataTest.java:
##########
@@ -95,6 +95,18 @@ public void testCompareTo()
}
+ @Test
+ public void testCompareToWithDifferentJSONOrder()
Review Comment:
Thanks for the review @abhishekrb19!
This current implementation only sorts the keys prior to hash computation. This is the minimal change to fix the transitivity bug. If we want to align with MySQL and Postgres jsonb then I can make these changes on the ColumnSerializerUtils.SMILE_MAPPER
--
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