You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by GitBox <gi...@apache.org> on 2020/05/02 13:42:21 UTC
[GitHub] [druid] wjhypo opened a new pull request #9810: Feature add segment pruning for hash based shard spec
wjhypo opened a new pull request #9810:
URL: https://github.com/apache/druid/pull/9810
Fixes #9809.
### Description
Currently segment pruning uses the time interval. For further filtering on secondary partitions, only single dimension ShardSpec is supported (done in #2982). For hash based partitioning (`HashBasedNumberedShardSpec`), we can also apply pruning by rehash the `partitionDimensions` in the query filter to locate segments.
This PR addresses this by rehashing the `partitionDimensions` values in `HashBasedNumberedShardSpec` from the query filter using the same hashing mechanism used during ingestion, and use the hashed value mod `partitions` to determine if it equals `partitionNum` of a segment. We only attempt pruning if 1) all `partitionDimensions` present in the query filter and 2) the values of `partitionDimensions` are discrete values not range values because we can't hash range values and 3) during ingestion time, `partitionDimensions` are explicitly set because otherwise the hash during ingestion is based on all dimensions plus the truncated input timestamp according to QueryGranularity instead of just `partitionDimensions` and we don't record timestamp in shard spec. Then we enumerate all combinations of the values of the dimensions in `partitionDimensions` drawn from the filter and check if the hashed value mod `partitions` matches the `partitionNum` of a segment. E.g., if the query contains filter "dim1 = v1 and dim2 in (v2, v3, v4)", then the hash values we will check are: hash(v1, v2), hash(v1, v3), hash(v1, v4).
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.)
- [x] added documentation for new or modified features or behaviors.
- [x] 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/licenses.yaml)
- [x] 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.
- [ ] 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.
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
[GitHub] [druid] jihoonson commented on a change in pull request #9810: Add segment pruning for hash based shard spec
Posted by GitBox <gi...@apache.org>.
jihoonson commented on a change in pull request #9810:
URL: https://github.com/apache/druid/pull/9810#discussion_r462038053
##########
File path: core/src/main/java/org/apache/druid/timeline/partition/HashBasedNumberedShardSpec.java
##########
@@ -192,4 +229,71 @@ public String toString()
", partitionDimensions=" + partitionDimensions +
'}';
}
+
+ @Override
+ public boolean possibleInDomain(Map<String, RangeSet<String>> domain)
+ {
+ // If no partitionDimensions are specified during ingestion, hash is based on all dimensions plus the truncated
+ // input timestamp according to QueryGranularity instead of just partitionDimensions. Since we don't store the
+ // timestamp after ingestion, bypass this case
Review comment:
Hmm, did you mean queryGranularity instead of timestamp? Druid does store timestamp, but it's not possible to get the query granularity after ingestion.
##########
File path: core/src/main/java/org/apache/druid/timeline/partition/HashBasedNumberedShardSpec.java
##########
@@ -90,10 +98,39 @@ public int getNumBuckets()
return partitionDimensions;
}
+ @Override
+ public List<String> getDomainDimensions()
+ {
+ return partitionDimensions;
+ }
+
@Override
public boolean isInChunk(long timestamp, InputRow inputRow)
{
- return (((long) hash(timestamp, inputRow)) - bucketId) % numBuckets == 0;
+ return Math.abs(hash(timestamp, inputRow) % numBuckets) == bucketId % numBuckets;
+ }
+
+ /**
+ * Check if the current segment possibly holds records if the values of dimensions in {@link #partitionDimensions}
+ * are of {@code partitionDimensionsValues}
+ *
+ * @param partitionDimensionsValues An instance of values of dimensions in {@link #partitionDimensions}
+ *
+ * @return Whether the current segment possibly holds records for the given values of partition dimensions
+ */
+ private boolean isInChunk(Map<String, String> partitionDimensionsValues)
+ {
+ assert !partitionDimensions.isEmpty();
+ List<Object> groupKey = Lists.transform(
+ partitionDimensions,
+ o -> Collections.singletonList(partitionDimensionsValues.get(o))
+ );
+ try {
+ return Math.abs(hash(jsonMapper, groupKey) % numBuckets) == bucketId % numBuckets;
Review comment:
Can we extract `Math.abs(hash % numBuckets) == bucketId % numBuckets` as a common method so that we can avoid a [mistake that you have fixed](https://github.com/apache/druid/pull/9810#discussion_r418961446) in the future?
----------------------------------------------------------------
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.
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
[GitHub] [druid] jihoonson commented on a change in pull request #9810: Add segment pruning for hash based shard spec
Posted by GitBox <gi...@apache.org>.
jihoonson commented on a change in pull request #9810:
URL: https://github.com/apache/druid/pull/9810#discussion_r462597040
##########
File path: server/src/test/java/org/apache/druid/client/CachingClusteredClientTest.java
##########
@@ -1541,6 +1543,135 @@ public void testSingleDimensionPruning()
Assert.assertEquals(expected, ((TimeseriesQuery) capture.getValue().getQuery()).getQuerySegmentSpec());
}
+ @Test
+ public void testHashBasedPruning()
+ {
+ DimFilter filter = new AndDimFilter(
+ new SelectorDimFilter("dim1", "a", null),
+ new BoundDimFilter("dim2", "e", "zzz", true, true, false, null, StringComparators.LEXICOGRAPHIC),
+ // Equivalent filter of dim3 below is InDimFilter("dim3", Arrays.asList("c"), null)
+ new AndDimFilter(
+ new InDimFilter("dim3", Arrays.asList("a", "c", "e", "g"), null),
+ new BoundDimFilter("dim3", "aaa", "ddd", false, false, false, null, StringComparators.LEXICOGRAPHIC)
+ )
+ );
+
+ final Druids.TimeseriesQueryBuilder builder = Druids.newTimeseriesQueryBuilder()
+ .dataSource(DATA_SOURCE)
+ .filters(filter)
+ .granularity(GRANULARITY)
+ .intervals(SEG_SPEC)
+ .context(CONTEXT)
+ .intervals("2011-01-05/2011-01-10")
+ .aggregators(RENAMED_AGGS)
+ .postAggregators(RENAMED_POST_AGGS);
Review comment:
You can fix the ci failure by adding `.randomQueryId()` here.
##########
File path: core/src/main/java/org/apache/druid/timeline/partition/HashBasedNumberedShardSpec.java
##########
@@ -192,4 +229,71 @@ public String toString()
", partitionDimensions=" + partitionDimensions +
'}';
}
+
+ @Override
+ public boolean possibleInDomain(Map<String, RangeSet<String>> domain)
+ {
+ // If no partitionDimensions are specified during ingestion, hash is based on all dimensions plus the truncated
+ // input timestamp according to QueryGranularity instead of just partitionDimensions. Since we don't store the
+ // timestamp after ingestion, bypass this case
Review comment:
Thanks for making it more clear!
##########
File path: core/src/main/java/org/apache/druid/timeline/partition/HashBasedNumberedShardSpec.java
##########
@@ -90,10 +98,39 @@ public int getNumBuckets()
return partitionDimensions;
}
+ @Override
+ public List<String> getDomainDimensions()
+ {
+ return partitionDimensions;
+ }
+
@Override
public boolean isInChunk(long timestamp, InputRow inputRow)
{
- return (((long) hash(timestamp, inputRow)) - bucketId) % numBuckets == 0;
+ return Math.abs(hash(timestamp, inputRow) % numBuckets) == bucketId % numBuckets;
+ }
+
+ /**
+ * Check if the current segment possibly holds records if the values of dimensions in {@link #partitionDimensions}
+ * are of {@code partitionDimensionsValues}
+ *
+ * @param partitionDimensionsValues An instance of values of dimensions in {@link #partitionDimensions}
+ *
+ * @return Whether the current segment possibly holds records for the given values of partition dimensions
+ */
+ private boolean isInChunk(Map<String, String> partitionDimensionsValues)
+ {
+ assert !partitionDimensions.isEmpty();
+ List<Object> groupKey = Lists.transform(
+ partitionDimensions,
+ o -> Collections.singletonList(partitionDimensionsValues.get(o))
+ );
+ try {
+ return Math.abs(hash(jsonMapper, groupKey) % numBuckets) == bucketId % numBuckets;
Review comment:
:+1:
----------------------------------------------------------------
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.
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
[GitHub] [druid] wjhypo commented on pull request #9810: Add segment pruning for hash based shard spec
Posted by GitBox <gi...@apache.org>.
wjhypo commented on pull request #9810:
URL: https://github.com/apache/druid/pull/9810#issuecomment-650467117
@clintropolis Tagging you as an additional reviewer, thanks!
----------------------------------------------------------------
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.
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
[GitHub] [druid] wjhypo commented on a change in pull request #9810: Add segment pruning for hash based shard spec
Posted by GitBox <gi...@apache.org>.
wjhypo commented on a change in pull request #9810:
URL: https://github.com/apache/druid/pull/9810#discussion_r462085471
##########
File path: core/src/main/java/org/apache/druid/timeline/partition/HashBasedNumberedShardSpec.java
##########
@@ -90,10 +98,39 @@ public int getNumBuckets()
return partitionDimensions;
}
+ @Override
+ public List<String> getDomainDimensions()
+ {
+ return partitionDimensions;
+ }
+
@Override
public boolean isInChunk(long timestamp, InputRow inputRow)
{
- return (((long) hash(timestamp, inputRow)) - bucketId) % numBuckets == 0;
+ return Math.abs(hash(timestamp, inputRow) % numBuckets) == bucketId % numBuckets;
+ }
+
+ /**
+ * Check if the current segment possibly holds records if the values of dimensions in {@link #partitionDimensions}
+ * are of {@code partitionDimensionsValues}
+ *
+ * @param partitionDimensionsValues An instance of values of dimensions in {@link #partitionDimensions}
+ *
+ * @return Whether the current segment possibly holds records for the given values of partition dimensions
+ */
+ private boolean isInChunk(Map<String, String> partitionDimensionsValues)
+ {
+ assert !partitionDimensions.isEmpty();
+ List<Object> groupKey = Lists.transform(
+ partitionDimensions,
+ o -> Collections.singletonList(partitionDimensionsValues.get(o))
+ );
+ try {
+ return Math.abs(hash(jsonMapper, groupKey) % numBuckets) == bucketId % numBuckets;
Review comment:
Good call! Changed. Actually I have to extract only `Math.abs(hash % numBuckets)` because in the function used by ingestion `static ShardSpecLookup createHashLookup` only needs `Math.abs(hash % numBuckets)` instead of the whole statement you mentioned.
##########
File path: core/src/main/java/org/apache/druid/timeline/partition/HashBasedNumberedShardSpec.java
##########
@@ -192,4 +229,71 @@ public String toString()
", partitionDimensions=" + partitionDimensions +
'}';
}
+
+ @Override
+ public boolean possibleInDomain(Map<String, RangeSet<String>> domain)
+ {
+ // If no partitionDimensions are specified during ingestion, hash is based on all dimensions plus the truncated
+ // input timestamp according to QueryGranularity instead of just partitionDimensions. Since we don't store the
+ // timestamp after ingestion, bypass this case
Review comment:
Oh, I mean in the shard spec, we don't store truncated timestamps of the events that fall into the shard. I've rephrased it. Let me know if it makes sense or needs more clarification.
----------------------------------------------------------------
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.
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
[GitHub] [druid] jihoonson merged pull request #9810: Add segment pruning for hash based shard spec
Posted by GitBox <gi...@apache.org>.
jihoonson merged pull request #9810:
URL: https://github.com/apache/druid/pull/9810
----------------------------------------------------------------
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.
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
[GitHub] [druid] jihoonson commented on pull request #9810: Add segment pruning for hash based shard spec
Posted by GitBox <gi...@apache.org>.
jihoonson commented on pull request #9810:
URL: https://github.com/apache/druid/pull/9810#issuecomment-665936775
Also, please fix the CI.
----------------------------------------------------------------
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.
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
[GitHub] [druid] wjhypo commented on a change in pull request #9810: Add segment pruning for hash based shard spec
Posted by GitBox <gi...@apache.org>.
wjhypo commented on a change in pull request #9810:
URL: https://github.com/apache/druid/pull/9810#discussion_r462614783
##########
File path: server/src/test/java/org/apache/druid/client/CachingClusteredClientTest.java
##########
@@ -1541,6 +1543,135 @@ public void testSingleDimensionPruning()
Assert.assertEquals(expected, ((TimeseriesQuery) capture.getValue().getQuery()).getQuerySegmentSpec());
}
+ @Test
+ public void testHashBasedPruning()
+ {
+ DimFilter filter = new AndDimFilter(
+ new SelectorDimFilter("dim1", "a", null),
+ new BoundDimFilter("dim2", "e", "zzz", true, true, false, null, StringComparators.LEXICOGRAPHIC),
+ // Equivalent filter of dim3 below is InDimFilter("dim3", Arrays.asList("c"), null)
+ new AndDimFilter(
+ new InDimFilter("dim3", Arrays.asList("a", "c", "e", "g"), null),
+ new BoundDimFilter("dim3", "aaa", "ddd", false, false, false, null, StringComparators.LEXICOGRAPHIC)
+ )
+ );
+
+ final Druids.TimeseriesQueryBuilder builder = Druids.newTimeseriesQueryBuilder()
+ .dataSource(DATA_SOURCE)
+ .filters(filter)
+ .granularity(GRANULARITY)
+ .intervals(SEG_SPEC)
+ .context(CONTEXT)
+ .intervals("2011-01-05/2011-01-10")
+ .aggregators(RENAMED_AGGS)
+ .postAggregators(RENAMED_POST_AGGS);
Review comment:
👍 Pushed a fix. Also thanks for the wiki, I will avoid force pushes in the future.
----------------------------------------------------------------
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.
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
[GitHub] [druid] wjhypo commented on pull request #9810: Add segment pruning for hash based shard spec
Posted by GitBox <gi...@apache.org>.
wjhypo commented on pull request #9810:
URL: https://github.com/apache/druid/pull/9810#issuecomment-650356463
@jihoonson Hi Jihoon, could you help get someone to review if it helps query performance?
----------------------------------------------------------------
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.
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
[GitHub] [druid] clintropolis commented on pull request #9810: Add segment pruning for hash based shard spec
Posted by GitBox <gi...@apache.org>.
clintropolis commented on pull request #9810:
URL: https://github.com/apache/druid/pull/9810#issuecomment-651506344
>@clintropolis Tagging you as an additional reviewer, thanks!
Oops, sorry I missed this one. Can you fix up conflicts? I'll go ahead and have a look
----------------------------------------------------------------
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.
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
[GitHub] [druid] wjhypo commented on pull request #9810: Add segment pruning for hash based shard spec
Posted by GitBox <gi...@apache.org>.
wjhypo commented on pull request #9810:
URL: https://github.com/apache/druid/pull/9810#issuecomment-651992994
@jihoonson @clintropolis Thanks for reviewing! I've fixed the conflicts.
----------------------------------------------------------------
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.
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
[GitHub] [druid] wjhypo commented on pull request #9810: Add segment pruning for hash based shard spec
Posted by GitBox <gi...@apache.org>.
wjhypo commented on pull request #9810:
URL: https://github.com/apache/druid/pull/9810#issuecomment-657778727
@jihoonson @clintropolis Could you let me know your comments if there's any? Thanks!
----------------------------------------------------------------
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.
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
[GitHub] [druid] wjhypo commented on a change in pull request #9810: Feature add segment pruning for hash based shard spec
Posted by GitBox <gi...@apache.org>.
wjhypo commented on a change in pull request #9810:
URL: https://github.com/apache/druid/pull/9810#discussion_r418961446
##########
File path: core/src/main/java/org/apache/druid/timeline/partition/HashBasedNumberedShardSpec.java
##########
@@ -73,7 +81,7 @@ public boolean isCompatible(Class<? extends ShardSpec> other)
@Override
public boolean isInChunk(long timestamp, InputRow inputRow)
{
- return (((long) hash(timestamp, inputRow)) - getPartitionNum()) % getPartitions() == 0;
+ return (Math.abs(hash(timestamp, inputRow)) - getPartitionNum()) % getPartitions() == 0;
Review comment:
Query time hashing should yield the same value as that produced during ingestion time. This should be a bug. Before this change, no one is using this api so no issue pops up before. During indexing, which segment to put a record into is by calling `getLookup` function below, in which the 32 bit hashed value is forced to stay as a positive integer by applying `Math.abs`. While here, it was casting the 32 bit hashed value to a long to force it stay as a positive integer. If the hashed value is 0xff_ff_ff_ff, Math.abs(0xff_ff_ff_ff) is different from (long)(0xff_ff_ff_ff). It's better to make the change here than in `getLookup` for backward compatibility otherwise users who have already used hash based partitioning can't leverage the pruning and pruning will be wrong unless they redo the ingestion to update segments.
----------------------------------------------------------------
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.
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
[GitHub] [druid] jihoonson commented on pull request #9810: Add segment pruning for hash based shard spec
Posted by GitBox <gi...@apache.org>.
jihoonson commented on pull request #9810:
URL: https://github.com/apache/druid/pull/9810#issuecomment-650467988
Hi @wjhypo, apologize for delayed review. I might be able to take a look next week.
----------------------------------------------------------------
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.
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