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 2022/04/09 04:23:43 UTC

[GitHub] [druid] hqx871 opened a new pull request, #12417: Use binary search to improve DimensionRangeShardSpec lookup

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

   <!-- 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. -->
   
   I tried to use binary search to improve DimensionRangeShard lookup, detail is discussed at https://github.com/apache/druid/pull/11848. Hope this is useful to somebody else.
   
   <!-- 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: -->
   
   <!--
   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. -->
   
   <hr>
   
   ##### Key changed/added classes in this PR
    * `BaseDimensionRangeShardSpec`
    * `DimensionRangeShardSpec`
    * `SingleDimensionShardSpec`
    *  `DimensionRangeBucketShardSpec`
   
   <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.
   - [ ] 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

[GitHub] [druid] kfaraz commented on pull request #12417: Use binary search to improve DimensionRangeShardSpec lookup

Posted by GitBox <gi...@apache.org>.
kfaraz commented on PR #12417:
URL: https://github.com/apache/druid/pull/12417#issuecomment-1100202418

   > I have implement hadoop based batch ingestion with range shard spec, by referring the native batch ingestion and hadoop based single_dim ingestion.
   
   @hqx871 , do you mean you have implemented range partitioning for hadoop-based ingestion?
   If yes, it would be great if you would consider contributing those changes here. :)
   It might be very useful for other people using hadoop-based ingestion.


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

[GitHub] [druid] kfaraz commented on a diff in pull request #12417: Use binary search to improve DimensionRangeShardSpec lookup

Posted by GitBox <gi...@apache.org>.
kfaraz commented on code in PR #12417:
URL: https://github.com/apache/druid/pull/12417#discussion_r848497461


##########
core/src/main/java/org/apache/druid/timeline/partition/BaseDimensionRangeShardSpec.java:
##########
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.timeline.partition;
+
+import com.google.common.collect.Ordering;
+import org.apache.druid.data.input.InputRow;
+import org.apache.druid.data.input.StringTuple;
+import org.apache.druid.java.util.common.ISE;
+import org.apache.druid.java.util.common.guava.Comparators;
+
+import javax.annotation.Nullable;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+public abstract class BaseDimensionRangeShardSpec implements ShardSpec
+{
+  protected final List<String> dimensions;
+  @Nullable
+  protected final StringTuple start;
+  @Nullable
+  protected final StringTuple end;
+
+  protected BaseDimensionRangeShardSpec(
+      List<String> dimensions,
+      @Nullable StringTuple start,
+      @Nullable StringTuple end
+  )
+  {
+    this.dimensions = dimensions;
+    this.start = start;
+    this.end = end;
+  }
+
+  @Override
+  public ShardSpecLookup getLookup(final List<? extends ShardSpec> shardSpecs)
+  {
+    return createLookup(dimensions, shardSpecs);
+  }
+
+  private static ShardSpecLookup createLookup(List<String> dimensions, List<? extends ShardSpec> shardSpecs)
+  {
+    BaseDimensionRangeShardSpec[] rangeShardSpecs = new BaseDimensionRangeShardSpec[shardSpecs.size()];
+    for (int i = 0; i < shardSpecs.size(); i++) {
+      rangeShardSpecs[i] = (BaseDimensionRangeShardSpec) shardSpecs.get(i);
+    }
+    final Comparator<StringTuple> startComparator = Comparators.naturalNullsFirst();
+    final Comparator<StringTuple> endComparator = Ordering.natural().nullsLast();
+    final Comparator<BaseDimensionRangeShardSpec> shardSpecComparator = new Comparator<BaseDimensionRangeShardSpec>()
+    {
+      @Override
+      public int compare(BaseDimensionRangeShardSpec o1, BaseDimensionRangeShardSpec o2)
+      {
+        int startComparison = startComparator.compare(o1.start, o2.start);
+        if (startComparison != 0) {
+          return startComparison;
+        }
+        return endComparator.compare(o1.end, o2.end);
+      }
+    };
+    Arrays.sort(rangeShardSpecs, shardSpecComparator);
+
+    return (long timestamp, InputRow row) -> {
+      StringTuple inputRowTuple = getInputRowTuple(dimensions, row);
+      int startIndex = 0;
+      int endIndex = shardSpecs.size() - 1;
+      while (startIndex <= endIndex) {
+        int mid = (startIndex + endIndex) >>> 1;
+        BaseDimensionRangeShardSpec rangeShardSpec = rangeShardSpecs[mid];
+        if (startComparator.compare(inputRowTuple, rangeShardSpec.start) < 0) {
+          endIndex = mid - 1;
+        } else if (endComparator.compare(inputRowTuple, rangeShardSpec.end) < 0) {
+          return rangeShardSpec;
+        } else {
+          startIndex = mid + 1;
+        }
+      }

Review Comment:
   You could use a dummy key. It would still be cleaner than writing the binary search logic yourself.
   Something like this:
   
   ```java
   final StringTuple searchTuple = getInputRowTuple(dimensions, row);
   final BaseDimensionRangeShardSpec searchKey = new DimensionRangeShardSpec(dimensions, searchTuple, searchTuple, 0, 1);
   final int searchResult = Arrays.binarySearch(rangeShardSpecs, searchKey, shardSpecComparator);
   if (searchResult < 0) {
      throw new ISE("row[%s] doesn't fit in any shard[%s]", row, shardSpecs);
   } else {
       return rangeShardSpecs[searchResult];
   }
   ```
   
   Please let me know if this seems cleaner.



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

[GitHub] [druid] kfaraz commented on a diff in pull request #12417: Use binary search to improve DimensionRangeShardSpec lookup

Posted by GitBox <gi...@apache.org>.
kfaraz commented on code in PR #12417:
URL: https://github.com/apache/druid/pull/12417#discussion_r848498587


##########
core/src/main/java/org/apache/druid/timeline/partition/BaseDimensionRangeShardSpec.java:
##########
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.timeline.partition;
+
+import com.google.common.collect.Ordering;
+import org.apache.druid.data.input.InputRow;
+import org.apache.druid.data.input.StringTuple;
+import org.apache.druid.java.util.common.ISE;
+import org.apache.druid.java.util.common.guava.Comparators;
+
+import javax.annotation.Nullable;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+public abstract class BaseDimensionRangeShardSpec implements ShardSpec
+{
+  protected final List<String> dimensions;
+  @Nullable
+  protected final StringTuple start;
+  @Nullable
+  protected final StringTuple end;
+
+  protected BaseDimensionRangeShardSpec(
+      List<String> dimensions,
+      @Nullable StringTuple start,
+      @Nullable StringTuple end
+  )
+  {
+    this.dimensions = dimensions;
+    this.start = start;
+    this.end = end;
+  }
+
+  @Override
+  public ShardSpecLookup getLookup(final List<? extends ShardSpec> shardSpecs)
+  {
+    return createLookup(dimensions, shardSpecs);
+  }
+
+  private static ShardSpecLookup createLookup(List<String> dimensions, List<? extends ShardSpec> shardSpecs)
+  {
+    BaseDimensionRangeShardSpec[] rangeShardSpecs = new BaseDimensionRangeShardSpec[shardSpecs.size()];
+    for (int i = 0; i < shardSpecs.size(); i++) {
+      rangeShardSpecs[i] = (BaseDimensionRangeShardSpec) shardSpecs.get(i);
+    }

Review Comment:
   Ah, that makes sense. I had missed the cast.



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

[GitHub] [druid] hqx871 commented on pull request #12417: Use binary search to improve DimensionRangeShardSpec lookup

Posted by GitBox <gi...@apache.org>.
hqx871 commented on PR #12417:
URL: https://github.com/apache/druid/pull/12417#issuecomment-1098959380

   Thanks for you time @kfaraz to review my code


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

[GitHub] [druid] hqx871 commented on a diff in pull request #12417: Use binary search to improve DimensionRangeShardSpec lookup

Posted by GitBox <gi...@apache.org>.
hqx871 commented on code in PR #12417:
URL: https://github.com/apache/druid/pull/12417#discussion_r848978621


##########
core/src/main/java/org/apache/druid/timeline/partition/BaseDimensionRangeShardSpec.java:
##########
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.timeline.partition;
+
+import com.google.common.collect.Ordering;
+import org.apache.druid.data.input.InputRow;
+import org.apache.druid.data.input.StringTuple;
+import org.apache.druid.java.util.common.ISE;
+import org.apache.druid.java.util.common.guava.Comparators;
+
+import javax.annotation.Nullable;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+public abstract class BaseDimensionRangeShardSpec implements ShardSpec
+{
+  protected final List<String> dimensions;
+  @Nullable
+  protected final StringTuple start;
+  @Nullable
+  protected final StringTuple end;
+
+  protected BaseDimensionRangeShardSpec(
+      List<String> dimensions,
+      @Nullable StringTuple start,
+      @Nullable StringTuple end
+  )
+  {
+    this.dimensions = dimensions;
+    this.start = start;
+    this.end = end;
+  }
+
+  @Override
+  public ShardSpecLookup getLookup(final List<? extends ShardSpec> shardSpecs)
+  {
+    return createLookup(dimensions, shardSpecs);
+  }
+
+  private static ShardSpecLookup createLookup(List<String> dimensions, List<? extends ShardSpec> shardSpecs)
+  {
+    BaseDimensionRangeShardSpec[] rangeShardSpecs = new BaseDimensionRangeShardSpec[shardSpecs.size()];
+    for (int i = 0; i < shardSpecs.size(); i++) {
+      rangeShardSpecs[i] = (BaseDimensionRangeShardSpec) shardSpecs.get(i);
+    }
+    final Comparator<StringTuple> startComparator = Comparators.naturalNullsFirst();
+    final Comparator<StringTuple> endComparator = Ordering.natural().nullsLast();
+    final Comparator<BaseDimensionRangeShardSpec> shardSpecComparator = new Comparator<BaseDimensionRangeShardSpec>()
+    {
+      @Override
+      public int compare(BaseDimensionRangeShardSpec o1, BaseDimensionRangeShardSpec o2)
+      {
+        int startComparison = startComparator.compare(o1.start, o2.start);
+        if (startComparison != 0) {
+          return startComparison;
+        }
+        return endComparator.compare(o1.end, o2.end);
+      }
+    };

Review Comment:
   Got 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

[GitHub] [druid] kfaraz merged pull request #12417: Use binary search to improve DimensionRangeShardSpec lookup

Posted by GitBox <gi...@apache.org>.
kfaraz merged PR #12417:
URL: https://github.com/apache/druid/pull/12417


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

[GitHub] [druid] hqx871 commented on pull request #12417: Use binary search to improve DimensionRangeShardSpec lookup

Posted by GitBox <gi...@apache.org>.
hqx871 commented on PR #12417:
URL: https://github.com/apache/druid/pull/12417#issuecomment-1100503600

   Hi @kfaraz, I will contribute it soon


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

[GitHub] [druid] hqx871 commented on a diff in pull request #12417: Use binary search to improve DimensionRangeShardSpec lookup

Posted by GitBox <gi...@apache.org>.
hqx871 commented on code in PR #12417:
URL: https://github.com/apache/druid/pull/12417#discussion_r850407709


##########
core/src/test/java/org/apache/druid/timeline/partition/DimensionRangeShardSpecTest.java:
##########
@@ -42,264 +39,6 @@
 
   private final List<String> dimensions = new ArrayList<>();
 
-  @Test
-  public void testIsInChunk()
-  {
-    setDimensions("d1", "d2");
-
-    final DimensionRangeShardSpec shardSpec = new DimensionRangeShardSpec(
-        dimensions,
-        StringTuple.create("India", "Delhi"),
-        StringTuple.create("Spain", "Valencia"),
-        10,
-        null
-    );
-
-    // Verify that entries starting from (India, Delhi) until (Spain, Valencia) are in chunk
-    assertTrue(isInChunk(
-        shardSpec,
-        createRow("India", "Delhi")
-    ));

Review Comment:
   get 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

[GitHub] [druid] hqx871 commented on a diff in pull request #12417: Use binary search to improve DimensionRangeShardSpec lookup

Posted by GitBox <gi...@apache.org>.
hqx871 commented on code in PR #12417:
URL: https://github.com/apache/druid/pull/12417#discussion_r850413911


##########
core/src/test/java/org/apache/druid/timeline/partition/DimensionRangeShardSpecTest.java:
##########
@@ -42,264 +39,6 @@
 
   private final List<String> dimensions = new ArrayList<>();
 
-  @Test
-  public void testIsInChunk()

Review Comment:
   done



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

[GitHub] [druid] kfaraz commented on a diff in pull request #12417: Use binary search to improve DimensionRangeShardSpec lookup

Posted by GitBox <gi...@apache.org>.
kfaraz commented on code in PR #12417:
URL: https://github.com/apache/druid/pull/12417#discussion_r850316144


##########
core/src/test/java/org/apache/druid/timeline/partition/DimensionRangeShardSpecTest.java:
##########
@@ -42,264 +39,6 @@
 
   private final List<String> dimensions = new ArrayList<>();
 
-  @Test
-  public void testIsInChunk()
-  {
-    setDimensions("d1", "d2");
-
-    final DimensionRangeShardSpec shardSpec = new DimensionRangeShardSpec(
-        dimensions,
-        StringTuple.create("India", "Delhi"),
-        StringTuple.create("Spain", "Valencia"),
-        10,
-        null
-    );
-
-    // Verify that entries starting from (India, Delhi) until (Spain, Valencia) are in chunk
-    assertTrue(isInChunk(
-        shardSpec,
-        createRow("India", "Delhi")
-    ));

Review Comment:
   These lines (and all the other assertions) could be translated to something like:
   
   ```java
   assertEquals(
      shard1,
      lookup.getShardSpec(timestamp, createRow("India", "Delhi"))
   )
   ```



##########
core/src/test/java/org/apache/druid/timeline/partition/DimensionRangeShardSpecTest.java:
##########
@@ -42,264 +39,6 @@
 
   private final List<String> dimensions = new ArrayList<>();
 
-  @Test
-  public void testIsInChunk()

Review Comment:
   You could create multiple shard specs, representing adjacent (or non-adjacent too if you are testing for it) partitions. Then create a `ShardSpecLookup` using the `getLookup` method. Then convert the assertions accordingly.



##########
core/src/test/java/org/apache/druid/timeline/partition/DimensionRangeShardSpecTest.java:
##########
@@ -42,264 +39,6 @@
 
   private final List<String> dimensions = new ArrayList<>();
 
-  @Test
-  public void testIsInChunk()

Review Comment:
   Please don't remove these tests altogether as there is nothing else testing this behaviour.
   You can convert these tests to test `getLookup` instead.



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

[GitHub] [druid] kfaraz commented on a diff in pull request #12417: Use binary search to improve DimensionRangeShardSpec lookup

Posted by GitBox <gi...@apache.org>.
kfaraz commented on code in PR #12417:
URL: https://github.com/apache/druid/pull/12417#discussion_r848498166


##########
core/src/main/java/org/apache/druid/timeline/partition/BaseDimensionRangeShardSpec.java:
##########
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.timeline.partition;
+
+import com.google.common.collect.Ordering;
+import org.apache.druid.data.input.InputRow;
+import org.apache.druid.data.input.StringTuple;
+import org.apache.druid.java.util.common.ISE;
+import org.apache.druid.java.util.common.guava.Comparators;
+
+import javax.annotation.Nullable;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+public abstract class BaseDimensionRangeShardSpec implements ShardSpec
+{
+  protected final List<String> dimensions;
+  @Nullable
+  protected final StringTuple start;
+  @Nullable
+  protected final StringTuple end;
+
+  protected BaseDimensionRangeShardSpec(
+      List<String> dimensions,
+      @Nullable StringTuple start,
+      @Nullable StringTuple end
+  )
+  {
+    this.dimensions = dimensions;
+    this.start = start;
+    this.end = end;
+  }
+
+  @Override
+  public ShardSpecLookup getLookup(final List<? extends ShardSpec> shardSpecs)
+  {
+    return createLookup(dimensions, shardSpecs);
+  }
+
+  private static ShardSpecLookup createLookup(List<String> dimensions, List<? extends ShardSpec> shardSpecs)
+  {
+    BaseDimensionRangeShardSpec[] rangeShardSpecs = new BaseDimensionRangeShardSpec[shardSpecs.size()];
+    for (int i = 0; i < shardSpecs.size(); i++) {
+      rangeShardSpecs[i] = (BaseDimensionRangeShardSpec) shardSpecs.get(i);
+    }
+    final Comparator<StringTuple> startComparator = Comparators.naturalNullsFirst();
+    final Comparator<StringTuple> endComparator = Ordering.natural().nullsLast();
+    final Comparator<BaseDimensionRangeShardSpec> shardSpecComparator = new Comparator<BaseDimensionRangeShardSpec>()
+    {
+      @Override
+      public int compare(BaseDimensionRangeShardSpec o1, BaseDimensionRangeShardSpec o2)
+      {
+        int startComparison = startComparator.compare(o1.start, o2.start);
+        if (startComparison != 0) {
+          return startComparison;
+        }
+        return endComparator.compare(o1.end, o2.end);
+      }
+    };

Review Comment:
   Something like this:
   
   ```java
       final Comparator<BaseDimensionRangeShardSpec> shardSpecComparator = Comparator
           .comparing((BaseDimensionRangeShardSpec spec) -> spec.start, Comparators.naturalNullsFirst())
           .thenComparing(spec -> spec.end, Ordering.natural().nullsLast());
   
       Arrays.sort(rangeShardSpecs, shardSpecComparator);
   ```



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

[GitHub] [druid] hqx871 commented on a diff in pull request #12417: Use binary search to improve DimensionRangeShardSpec lookup

Posted by GitBox <gi...@apache.org>.
hqx871 commented on code in PR #12417:
URL: https://github.com/apache/druid/pull/12417#discussion_r848889538


##########
core/src/main/java/org/apache/druid/timeline/partition/BaseDimensionRangeShardSpec.java:
##########
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.timeline.partition;
+
+import com.google.common.collect.Ordering;
+import org.apache.druid.data.input.InputRow;
+import org.apache.druid.data.input.StringTuple;
+import org.apache.druid.java.util.common.ISE;
+import org.apache.druid.java.util.common.guava.Comparators;
+
+import javax.annotation.Nullable;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+public abstract class BaseDimensionRangeShardSpec implements ShardSpec
+{
+  protected final List<String> dimensions;
+  @Nullable
+  protected final StringTuple start;
+  @Nullable
+  protected final StringTuple end;
+
+  protected BaseDimensionRangeShardSpec(
+      List<String> dimensions,
+      @Nullable StringTuple start,
+      @Nullable StringTuple end
+  )
+  {
+    this.dimensions = dimensions;
+    this.start = start;
+    this.end = end;
+  }
+
+  @Override
+  public ShardSpecLookup getLookup(final List<? extends ShardSpec> shardSpecs)
+  {
+    return createLookup(dimensions, shardSpecs);
+  }
+
+  private static ShardSpecLookup createLookup(List<String> dimensions, List<? extends ShardSpec> shardSpecs)
+  {
+    BaseDimensionRangeShardSpec[] rangeShardSpecs = new BaseDimensionRangeShardSpec[shardSpecs.size()];
+    for (int i = 0; i < shardSpecs.size(); i++) {
+      rangeShardSpecs[i] = (BaseDimensionRangeShardSpec) shardSpecs.get(i);
+    }
+    final Comparator<StringTuple> startComparator = Comparators.naturalNullsFirst();
+    final Comparator<StringTuple> endComparator = Ordering.natural().nullsLast();
+    final Comparator<BaseDimensionRangeShardSpec> shardSpecComparator = new Comparator<BaseDimensionRangeShardSpec>()
+    {
+      @Override
+      public int compare(BaseDimensionRangeShardSpec o1, BaseDimensionRangeShardSpec o2)
+      {
+        int startComparison = startComparator.compare(o1.start, o2.start);
+        if (startComparison != 0) {
+          return startComparison;
+        }
+        return endComparator.compare(o1.end, o2.end);
+      }
+    };
+    Arrays.sort(rangeShardSpecs, shardSpecComparator);
+
+    return (long timestamp, InputRow row) -> {
+      StringTuple inputRowTuple = getInputRowTuple(dimensions, row);
+      int startIndex = 0;
+      int endIndex = shardSpecs.size() - 1;
+      while (startIndex <= endIndex) {
+        int mid = (startIndex + endIndex) >>> 1;
+        BaseDimensionRangeShardSpec rangeShardSpec = rangeShardSpecs[mid];
+        if (startComparator.compare(inputRowTuple, rangeShardSpec.start) < 0) {
+          endIndex = mid - 1;
+        } else if (endComparator.compare(inputRowTuple, rangeShardSpec.end) < 0) {
+          return rangeShardSpec;
+        } else {
+          startIndex = mid + 1;
+        }
+      }

Review Comment:
   Arrays.binarySearch requires the searchKey to equals one array element, while actually we do need find one that equals or contains the searchKey. For example:
   
   input:
   ```
   searchKey: ["a","a"]
   shardSpecs:[[null,"c"], ["c", "h"],["h",null]]
   ```
   
   then  the expect result is [null, "c"], but the Arrays.binarySearch will return -1, not 0,  which means ["a","a"] <= [null, "c"]. 
   



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

[GitHub] [druid] hqx871 commented on a diff in pull request #12417: Use binary search to improve DimensionRangeShardSpec lookup

Posted by GitBox <gi...@apache.org>.
hqx871 commented on code in PR #12417:
URL: https://github.com/apache/druid/pull/12417#discussion_r847982553


##########
core/src/main/java/org/apache/druid/timeline/partition/BaseDimensionRangeShardSpec.java:
##########
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.timeline.partition;
+
+import com.google.common.collect.Ordering;
+import org.apache.druid.data.input.InputRow;
+import org.apache.druid.data.input.StringTuple;
+import org.apache.druid.java.util.common.ISE;
+import org.apache.druid.java.util.common.guava.Comparators;
+
+import javax.annotation.Nullable;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+public abstract class BaseDimensionRangeShardSpec implements ShardSpec
+{
+  protected final List<String> dimensions;
+  @Nullable
+  protected final StringTuple start;
+  @Nullable
+  protected final StringTuple end;
+
+  protected BaseDimensionRangeShardSpec(
+      List<String> dimensions,
+      @Nullable StringTuple start,
+      @Nullable StringTuple end
+  )
+  {
+    this.dimensions = dimensions;
+    this.start = start;
+    this.end = end;
+  }
+
+  @Override
+  public ShardSpecLookup getLookup(final List<? extends ShardSpec> shardSpecs)
+  {
+    return createLookup(dimensions, shardSpecs);
+  }
+
+  private static ShardSpecLookup createLookup(List<String> dimensions, List<? extends ShardSpec> shardSpecs)
+  {
+    BaseDimensionRangeShardSpec[] rangeShardSpecs = new BaseDimensionRangeShardSpec[shardSpecs.size()];
+    for (int i = 0; i < shardSpecs.size(); i++) {
+      rangeShardSpecs[i] = (BaseDimensionRangeShardSpec) shardSpecs.get(i);
+    }
+    final Comparator<StringTuple> startComparator = Comparators.naturalNullsFirst();
+    final Comparator<StringTuple> endComparator = Ordering.natural().nullsLast();
+    final Comparator<BaseDimensionRangeShardSpec> shardSpecComparator = new Comparator<BaseDimensionRangeShardSpec>()
+    {
+      @Override
+      public int compare(BaseDimensionRangeShardSpec o1, BaseDimensionRangeShardSpec o2)
+      {
+        int startComparison = startComparator.compare(o1.start, o2.start);
+        if (startComparison != 0) {
+          return startComparison;
+        }
+        return endComparator.compare(o1.end, o2.end);
+      }
+    };
+    Arrays.sort(rangeShardSpecs, shardSpecComparator);
+
+    return (long timestamp, InputRow row) -> {
+      StringTuple inputRowTuple = getInputRowTuple(dimensions, row);
+      int startIndex = 0;
+      int endIndex = shardSpecs.size() - 1;
+      while (startIndex <= endIndex) {
+        int mid = (startIndex + endIndex) >>> 1;
+        BaseDimensionRangeShardSpec rangeShardSpec = rangeShardSpecs[mid];
+        if (startComparator.compare(inputRowTuple, rangeShardSpec.start) < 0) {
+          endIndex = mid - 1;
+        } else if (endComparator.compare(inputRowTuple, rangeShardSpec.end) < 0) {
+          return rangeShardSpec;
+        } else {
+          startIndex = mid + 1;
+        }
+      }

Review Comment:
   The array component is BaseDimensionRangeShardSpec while the key is StringTuple, so I can not directly call Arrays.binarySearch



##########
core/src/main/java/org/apache/druid/timeline/partition/BaseDimensionRangeShardSpec.java:
##########
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.timeline.partition;
+
+import com.google.common.collect.Ordering;
+import org.apache.druid.data.input.InputRow;
+import org.apache.druid.data.input.StringTuple;
+import org.apache.druid.java.util.common.ISE;
+import org.apache.druid.java.util.common.guava.Comparators;
+
+import javax.annotation.Nullable;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+public abstract class BaseDimensionRangeShardSpec implements ShardSpec
+{
+  protected final List<String> dimensions;
+  @Nullable
+  protected final StringTuple start;
+  @Nullable
+  protected final StringTuple end;
+
+  protected BaseDimensionRangeShardSpec(
+      List<String> dimensions,
+      @Nullable StringTuple start,
+      @Nullable StringTuple end
+  )
+  {
+    this.dimensions = dimensions;
+    this.start = start;
+    this.end = end;
+  }
+
+  @Override
+  public ShardSpecLookup getLookup(final List<? extends ShardSpec> shardSpecs)
+  {
+    return createLookup(dimensions, shardSpecs);
+  }
+
+  private static ShardSpecLookup createLookup(List<String> dimensions, List<? extends ShardSpec> shardSpecs)
+  {
+    BaseDimensionRangeShardSpec[] rangeShardSpecs = new BaseDimensionRangeShardSpec[shardSpecs.size()];
+    for (int i = 0; i < shardSpecs.size(); i++) {
+      rangeShardSpecs[i] = (BaseDimensionRangeShardSpec) shardSpecs.get(i);
+    }
+    final Comparator<StringTuple> startComparator = Comparators.naturalNullsFirst();
+    final Comparator<StringTuple> endComparator = Ordering.natural().nullsLast();
+    final Comparator<BaseDimensionRangeShardSpec> shardSpecComparator = new Comparator<BaseDimensionRangeShardSpec>()
+    {
+      @Override
+      public int compare(BaseDimensionRangeShardSpec o1, BaseDimensionRangeShardSpec o2)
+      {
+        int startComparison = startComparator.compare(o1.start, o2.start);
+        if (startComparison != 0) {
+          return startComparison;
+        }
+        return endComparator.compare(o1.end, o2.end);
+      }
+    };

Review Comment:
   The start comparator is null first while the end comparator is null last. I do not know how to chaining the comparator



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

[GitHub] [druid] kfaraz commented on a diff in pull request #12417: Use binary search to improve DimensionRangeShardSpec lookup

Posted by GitBox <gi...@apache.org>.
kfaraz commented on code in PR #12417:
URL: https://github.com/apache/druid/pull/12417#discussion_r847946933


##########
core/src/main/java/org/apache/druid/timeline/partition/DimensionRangeShardSpec.java:
##########
@@ -279,25 +253,14 @@ public <T> PartitionChunk<T> createChunk(T obj)
     }
   }
 
-  private boolean isInChunk(InputRow inputRow)
-  {
-    return isInChunk(dimensions, start, end, inputRow);
-  }
-
   public static boolean isInChunk(

Review Comment:
   You could probably remove this method. I don't think it is needed anymore.



##########
core/src/main/java/org/apache/druid/timeline/partition/BaseDimensionRangeShardSpec.java:
##########
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.timeline.partition;
+
+import com.google.common.collect.Ordering;
+import org.apache.druid.data.input.InputRow;
+import org.apache.druid.data.input.StringTuple;
+import org.apache.druid.java.util.common.ISE;
+import org.apache.druid.java.util.common.guava.Comparators;
+
+import javax.annotation.Nullable;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+public abstract class BaseDimensionRangeShardSpec implements ShardSpec
+{
+  protected final List<String> dimensions;
+  @Nullable
+  protected final StringTuple start;
+  @Nullable
+  protected final StringTuple end;
+
+  protected BaseDimensionRangeShardSpec(
+      List<String> dimensions,
+      @Nullable StringTuple start,
+      @Nullable StringTuple end
+  )
+  {
+    this.dimensions = dimensions;
+    this.start = start;
+    this.end = end;
+  }
+
+  @Override
+  public ShardSpecLookup getLookup(final List<? extends ShardSpec> shardSpecs)
+  {
+    return createLookup(dimensions, shardSpecs);
+  }
+
+  private static ShardSpecLookup createLookup(List<String> dimensions, List<? extends ShardSpec> shardSpecs)
+  {
+    BaseDimensionRangeShardSpec[] rangeShardSpecs = new BaseDimensionRangeShardSpec[shardSpecs.size()];
+    for (int i = 0; i < shardSpecs.size(); i++) {
+      rangeShardSpecs[i] = (BaseDimensionRangeShardSpec) shardSpecs.get(i);
+    }
+    final Comparator<StringTuple> startComparator = Comparators.naturalNullsFirst();
+    final Comparator<StringTuple> endComparator = Ordering.natural().nullsLast();
+    final Comparator<BaseDimensionRangeShardSpec> shardSpecComparator = new Comparator<BaseDimensionRangeShardSpec>()
+    {
+      @Override
+      public int compare(BaseDimensionRangeShardSpec o1, BaseDimensionRangeShardSpec o2)
+      {
+        int startComparison = startComparator.compare(o1.start, o2.start);
+        if (startComparison != 0) {
+          return startComparison;
+        }
+        return endComparator.compare(o1.end, o2.end);
+      }
+    };

Review Comment:
   You can try chaining the comparator. See below for an example.
   
   https://github.com/apache/druid/blob/master/indexing-service/src/main/java/org/apache/druid/indexing/common/task/batch/parallel/ParallelIndexSupervisorTask.java#L932-L937



##########
core/src/main/java/org/apache/druid/timeline/partition/BaseDimensionRangeShardSpec.java:
##########
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.timeline.partition;
+
+import com.google.common.collect.Ordering;
+import org.apache.druid.data.input.InputRow;
+import org.apache.druid.data.input.StringTuple;
+import org.apache.druid.java.util.common.ISE;
+import org.apache.druid.java.util.common.guava.Comparators;
+
+import javax.annotation.Nullable;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+public abstract class BaseDimensionRangeShardSpec implements ShardSpec
+{
+  protected final List<String> dimensions;
+  @Nullable
+  protected final StringTuple start;
+  @Nullable
+  protected final StringTuple end;
+
+  protected BaseDimensionRangeShardSpec(
+      List<String> dimensions,
+      @Nullable StringTuple start,
+      @Nullable StringTuple end
+  )
+  {
+    this.dimensions = dimensions;
+    this.start = start;
+    this.end = end;
+  }
+
+  @Override
+  public ShardSpecLookup getLookup(final List<? extends ShardSpec> shardSpecs)
+  {
+    return createLookup(dimensions, shardSpecs);
+  }
+
+  private static ShardSpecLookup createLookup(List<String> dimensions, List<? extends ShardSpec> shardSpecs)
+  {
+    BaseDimensionRangeShardSpec[] rangeShardSpecs = new BaseDimensionRangeShardSpec[shardSpecs.size()];
+    for (int i = 0; i < shardSpecs.size(); i++) {
+      rangeShardSpecs[i] = (BaseDimensionRangeShardSpec) shardSpecs.get(i);
+    }

Review Comment:
   Nit: You could use `shardSpecs.toArray()` for cleaner code.



##########
core/src/main/java/org/apache/druid/timeline/partition/BaseDimensionRangeShardSpec.java:
##########
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.timeline.partition;
+
+import com.google.common.collect.Ordering;
+import org.apache.druid.data.input.InputRow;
+import org.apache.druid.data.input.StringTuple;
+import org.apache.druid.java.util.common.ISE;
+import org.apache.druid.java.util.common.guava.Comparators;
+
+import javax.annotation.Nullable;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+public abstract class BaseDimensionRangeShardSpec implements ShardSpec
+{
+  protected final List<String> dimensions;
+  @Nullable
+  protected final StringTuple start;
+  @Nullable
+  protected final StringTuple end;
+
+  protected BaseDimensionRangeShardSpec(
+      List<String> dimensions,
+      @Nullable StringTuple start,
+      @Nullable StringTuple end
+  )
+  {
+    this.dimensions = dimensions;
+    this.start = start;
+    this.end = end;
+  }
+
+  @Override
+  public ShardSpecLookup getLookup(final List<? extends ShardSpec> shardSpecs)
+  {
+    return createLookup(dimensions, shardSpecs);
+  }
+
+  private static ShardSpecLookup createLookup(List<String> dimensions, List<? extends ShardSpec> shardSpecs)
+  {
+    BaseDimensionRangeShardSpec[] rangeShardSpecs = new BaseDimensionRangeShardSpec[shardSpecs.size()];
+    for (int i = 0; i < shardSpecs.size(); i++) {
+      rangeShardSpecs[i] = (BaseDimensionRangeShardSpec) shardSpecs.get(i);
+    }
+    final Comparator<StringTuple> startComparator = Comparators.naturalNullsFirst();
+    final Comparator<StringTuple> endComparator = Ordering.natural().nullsLast();
+    final Comparator<BaseDimensionRangeShardSpec> shardSpecComparator = new Comparator<BaseDimensionRangeShardSpec>()
+    {
+      @Override
+      public int compare(BaseDimensionRangeShardSpec o1, BaseDimensionRangeShardSpec o2)
+      {
+        int startComparison = startComparator.compare(o1.start, o2.start);
+        if (startComparison != 0) {
+          return startComparison;
+        }
+        return endComparator.compare(o1.end, o2.end);
+      }
+    };
+    Arrays.sort(rangeShardSpecs, shardSpecComparator);
+
+    return (long timestamp, InputRow row) -> {
+      StringTuple inputRowTuple = getInputRowTuple(dimensions, row);
+      int startIndex = 0;
+      int endIndex = shardSpecs.size() - 1;
+      while (startIndex <= endIndex) {
+        int mid = (startIndex + endIndex) >>> 1;
+        BaseDimensionRangeShardSpec rangeShardSpec = rangeShardSpecs[mid];
+        if (startComparator.compare(inputRowTuple, rangeShardSpec.start) < 0) {
+          endIndex = mid - 1;
+        } else if (endComparator.compare(inputRowTuple, rangeShardSpec.end) < 0) {
+          return rangeShardSpec;
+        } else {
+          startIndex = mid + 1;
+        }
+      }
+      throw new ISE("row[%s] doesn't fit in any shard[%s]", row, shardSpecs);
+    };
+  }
+
+  protected static StringTuple getInputRowTuple(List<String> dimensions, InputRow inputRow)
+  {
+    final String[] inputDimensionValues = new String[dimensions.size()];
+    for (int i = 0; i < dimensions.size(); ++i) {
+      List<String> values = inputRow.getDimension(dimensions.get(i));

Review Comment:
   Nit: please add the comment originally present in this method.
   `// Get the values of this dimension, treat multiple values as null`



##########
core/src/main/java/org/apache/druid/timeline/partition/BaseDimensionRangeShardSpec.java:
##########
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.timeline.partition;
+
+import com.google.common.collect.Ordering;
+import org.apache.druid.data.input.InputRow;
+import org.apache.druid.data.input.StringTuple;
+import org.apache.druid.java.util.common.ISE;
+import org.apache.druid.java.util.common.guava.Comparators;
+
+import javax.annotation.Nullable;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+public abstract class BaseDimensionRangeShardSpec implements ShardSpec
+{
+  protected final List<String> dimensions;
+  @Nullable
+  protected final StringTuple start;
+  @Nullable
+  protected final StringTuple end;
+
+  protected BaseDimensionRangeShardSpec(
+      List<String> dimensions,
+      @Nullable StringTuple start,
+      @Nullable StringTuple end
+  )
+  {
+    this.dimensions = dimensions;
+    this.start = start;
+    this.end = end;
+  }
+
+  @Override
+  public ShardSpecLookup getLookup(final List<? extends ShardSpec> shardSpecs)
+  {
+    return createLookup(dimensions, shardSpecs);
+  }
+
+  private static ShardSpecLookup createLookup(List<String> dimensions, List<? extends ShardSpec> shardSpecs)
+  {
+    BaseDimensionRangeShardSpec[] rangeShardSpecs = new BaseDimensionRangeShardSpec[shardSpecs.size()];
+    for (int i = 0; i < shardSpecs.size(); i++) {
+      rangeShardSpecs[i] = (BaseDimensionRangeShardSpec) shardSpecs.get(i);
+    }
+    final Comparator<StringTuple> startComparator = Comparators.naturalNullsFirst();
+    final Comparator<StringTuple> endComparator = Ordering.natural().nullsLast();
+    final Comparator<BaseDimensionRangeShardSpec> shardSpecComparator = new Comparator<BaseDimensionRangeShardSpec>()
+    {
+      @Override
+      public int compare(BaseDimensionRangeShardSpec o1, BaseDimensionRangeShardSpec o2)
+      {
+        int startComparison = startComparator.compare(o1.start, o2.start);
+        if (startComparison != 0) {
+          return startComparison;
+        }
+        return endComparator.compare(o1.end, o2.end);
+      }
+    };
+    Arrays.sort(rangeShardSpecs, shardSpecComparator);
+
+    return (long timestamp, InputRow row) -> {
+      StringTuple inputRowTuple = getInputRowTuple(dimensions, row);
+      int startIndex = 0;
+      int endIndex = shardSpecs.size() - 1;
+      while (startIndex <= endIndex) {
+        int mid = (startIndex + endIndex) >>> 1;
+        BaseDimensionRangeShardSpec rangeShardSpec = rangeShardSpecs[mid];
+        if (startComparator.compare(inputRowTuple, rangeShardSpec.start) < 0) {
+          endIndex = mid - 1;
+        } else if (endComparator.compare(inputRowTuple, rangeShardSpec.end) < 0) {
+          return rangeShardSpec;
+        } else {
+          startIndex = mid + 1;
+        }
+      }

Review Comment:
   You could probably simplify this using `Arrays.binarySearch(array, key, comparator)`



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

[GitHub] [druid] hqx871 commented on a diff in pull request #12417: Use binary search to improve DimensionRangeShardSpec lookup

Posted by GitBox <gi...@apache.org>.
hqx871 commented on code in PR #12417:
URL: https://github.com/apache/druid/pull/12417#discussion_r848018747


##########
core/src/main/java/org/apache/druid/timeline/partition/DimensionRangeShardSpec.java:
##########
@@ -279,25 +253,14 @@ public <T> PartitionChunk<T> createChunk(T obj)
     }
   }
 
-  private boolean isInChunk(InputRow inputRow)
-  {
-    return isInChunk(dimensions, start, end, inputRow);
-  }
-
   public static boolean isInChunk(

Review Comment:
   done



##########
core/src/main/java/org/apache/druid/timeline/partition/BaseDimensionRangeShardSpec.java:
##########
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.timeline.partition;
+
+import com.google.common.collect.Ordering;
+import org.apache.druid.data.input.InputRow;
+import org.apache.druid.data.input.StringTuple;
+import org.apache.druid.java.util.common.ISE;
+import org.apache.druid.java.util.common.guava.Comparators;
+
+import javax.annotation.Nullable;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+public abstract class BaseDimensionRangeShardSpec implements ShardSpec
+{
+  protected final List<String> dimensions;
+  @Nullable
+  protected final StringTuple start;
+  @Nullable
+  protected final StringTuple end;
+
+  protected BaseDimensionRangeShardSpec(
+      List<String> dimensions,
+      @Nullable StringTuple start,
+      @Nullable StringTuple end
+  )
+  {
+    this.dimensions = dimensions;
+    this.start = start;
+    this.end = end;
+  }
+
+  @Override
+  public ShardSpecLookup getLookup(final List<? extends ShardSpec> shardSpecs)
+  {
+    return createLookup(dimensions, shardSpecs);
+  }
+
+  private static ShardSpecLookup createLookup(List<String> dimensions, List<? extends ShardSpec> shardSpecs)
+  {
+    BaseDimensionRangeShardSpec[] rangeShardSpecs = new BaseDimensionRangeShardSpec[shardSpecs.size()];
+    for (int i = 0; i < shardSpecs.size(); i++) {
+      rangeShardSpecs[i] = (BaseDimensionRangeShardSpec) shardSpecs.get(i);
+    }
+    final Comparator<StringTuple> startComparator = Comparators.naturalNullsFirst();
+    final Comparator<StringTuple> endComparator = Ordering.natural().nullsLast();
+    final Comparator<BaseDimensionRangeShardSpec> shardSpecComparator = new Comparator<BaseDimensionRangeShardSpec>()
+    {
+      @Override
+      public int compare(BaseDimensionRangeShardSpec o1, BaseDimensionRangeShardSpec o2)
+      {
+        int startComparison = startComparator.compare(o1.start, o2.start);
+        if (startComparison != 0) {
+          return startComparison;
+        }
+        return endComparator.compare(o1.end, o2.end);
+      }
+    };
+    Arrays.sort(rangeShardSpecs, shardSpecComparator);
+
+    return (long timestamp, InputRow row) -> {
+      StringTuple inputRowTuple = getInputRowTuple(dimensions, row);
+      int startIndex = 0;
+      int endIndex = shardSpecs.size() - 1;
+      while (startIndex <= endIndex) {
+        int mid = (startIndex + endIndex) >>> 1;
+        BaseDimensionRangeShardSpec rangeShardSpec = rangeShardSpecs[mid];
+        if (startComparator.compare(inputRowTuple, rangeShardSpec.start) < 0) {
+          endIndex = mid - 1;
+        } else if (endComparator.compare(inputRowTuple, rangeShardSpec.end) < 0) {
+          return rangeShardSpec;
+        } else {
+          startIndex = mid + 1;
+        }
+      }
+      throw new ISE("row[%s] doesn't fit in any shard[%s]", row, shardSpecs);
+    };
+  }
+
+  protected static StringTuple getInputRowTuple(List<String> dimensions, InputRow inputRow)
+  {
+    final String[] inputDimensionValues = new String[dimensions.size()];
+    for (int i = 0; i < dimensions.size(); ++i) {
+      List<String> values = inputRow.getDimension(dimensions.get(i));

Review Comment:
   added back



##########
core/src/main/java/org/apache/druid/timeline/partition/BaseDimensionRangeShardSpec.java:
##########
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.timeline.partition;
+
+import com.google.common.collect.Ordering;
+import org.apache.druid.data.input.InputRow;
+import org.apache.druid.data.input.StringTuple;
+import org.apache.druid.java.util.common.ISE;
+import org.apache.druid.java.util.common.guava.Comparators;
+
+import javax.annotation.Nullable;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+public abstract class BaseDimensionRangeShardSpec implements ShardSpec
+{
+  protected final List<String> dimensions;
+  @Nullable
+  protected final StringTuple start;
+  @Nullable
+  protected final StringTuple end;
+
+  protected BaseDimensionRangeShardSpec(
+      List<String> dimensions,
+      @Nullable StringTuple start,
+      @Nullable StringTuple end
+  )
+  {
+    this.dimensions = dimensions;
+    this.start = start;
+    this.end = end;
+  }
+
+  @Override
+  public ShardSpecLookup getLookup(final List<? extends ShardSpec> shardSpecs)
+  {
+    return createLookup(dimensions, shardSpecs);
+  }
+
+  private static ShardSpecLookup createLookup(List<String> dimensions, List<? extends ShardSpec> shardSpecs)
+  {
+    BaseDimensionRangeShardSpec[] rangeShardSpecs = new BaseDimensionRangeShardSpec[shardSpecs.size()];
+    for (int i = 0; i < shardSpecs.size(); i++) {
+      rangeShardSpecs[i] = (BaseDimensionRangeShardSpec) shardSpecs.get(i);
+    }

Review Comment:
   Directly call toArray cause compile error as the component is not BaseDimensionRangeShardSpec



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

[GitHub] [druid] hqx871 commented on a diff in pull request #12417: Use binary search to improve DimensionRangeShardSpec lookup

Posted by GitBox <gi...@apache.org>.
hqx871 commented on code in PR #12417:
URL: https://github.com/apache/druid/pull/12417#discussion_r848889538


##########
core/src/main/java/org/apache/druid/timeline/partition/BaseDimensionRangeShardSpec.java:
##########
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.druid.timeline.partition;
+
+import com.google.common.collect.Ordering;
+import org.apache.druid.data.input.InputRow;
+import org.apache.druid.data.input.StringTuple;
+import org.apache.druid.java.util.common.ISE;
+import org.apache.druid.java.util.common.guava.Comparators;
+
+import javax.annotation.Nullable;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.List;
+
+public abstract class BaseDimensionRangeShardSpec implements ShardSpec
+{
+  protected final List<String> dimensions;
+  @Nullable
+  protected final StringTuple start;
+  @Nullable
+  protected final StringTuple end;
+
+  protected BaseDimensionRangeShardSpec(
+      List<String> dimensions,
+      @Nullable StringTuple start,
+      @Nullable StringTuple end
+  )
+  {
+    this.dimensions = dimensions;
+    this.start = start;
+    this.end = end;
+  }
+
+  @Override
+  public ShardSpecLookup getLookup(final List<? extends ShardSpec> shardSpecs)
+  {
+    return createLookup(dimensions, shardSpecs);
+  }
+
+  private static ShardSpecLookup createLookup(List<String> dimensions, List<? extends ShardSpec> shardSpecs)
+  {
+    BaseDimensionRangeShardSpec[] rangeShardSpecs = new BaseDimensionRangeShardSpec[shardSpecs.size()];
+    for (int i = 0; i < shardSpecs.size(); i++) {
+      rangeShardSpecs[i] = (BaseDimensionRangeShardSpec) shardSpecs.get(i);
+    }
+    final Comparator<StringTuple> startComparator = Comparators.naturalNullsFirst();
+    final Comparator<StringTuple> endComparator = Ordering.natural().nullsLast();
+    final Comparator<BaseDimensionRangeShardSpec> shardSpecComparator = new Comparator<BaseDimensionRangeShardSpec>()
+    {
+      @Override
+      public int compare(BaseDimensionRangeShardSpec o1, BaseDimensionRangeShardSpec o2)
+      {
+        int startComparison = startComparator.compare(o1.start, o2.start);
+        if (startComparison != 0) {
+          return startComparison;
+        }
+        return endComparator.compare(o1.end, o2.end);
+      }
+    };
+    Arrays.sort(rangeShardSpecs, shardSpecComparator);
+
+    return (long timestamp, InputRow row) -> {
+      StringTuple inputRowTuple = getInputRowTuple(dimensions, row);
+      int startIndex = 0;
+      int endIndex = shardSpecs.size() - 1;
+      while (startIndex <= endIndex) {
+        int mid = (startIndex + endIndex) >>> 1;
+        BaseDimensionRangeShardSpec rangeShardSpec = rangeShardSpecs[mid];
+        if (startComparator.compare(inputRowTuple, rangeShardSpec.start) < 0) {
+          endIndex = mid - 1;
+        } else if (endComparator.compare(inputRowTuple, rangeShardSpec.end) < 0) {
+          return rangeShardSpec;
+        } else {
+          startIndex = mid + 1;
+        }
+      }

Review Comment:
   Arrays.binarySearch requires the searchKey to equals one array element, while actually we do need find one that equals or contains the searchKey. For example:
   
   input:
   ```
   searchKey: ["a","a"]
   shardSpecs:[[null,"c"], ["c", "h"],["h",null]]
   ```
   
   then  the expect result is [null, "c"], but the Arrays.binarySearch will return -2, not 0. 
   



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