Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on PR #19138: URL: https://github.com/apache/druid/pull/19138#issuecomment-4424123484 What are the next steps? -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] - To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on PR #19138: URL: https://github.com/apache/druid/pull/19138#issuecomment-4423756339 Merged latest master into this branch and resolved 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. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] - To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r3212197419
##
processing/src/main/java/org/apache/druid/timeline/IntervalTree.java:
##
@@ -0,0 +1,796 @@
+/*
+ * 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;
+
+import com.google.common.base.Predicate;
+import org.apache.druid.java.util.common.StringUtils;
+import org.jetbrains.annotations.NotNull;
+import org.jetbrains.annotations.VisibleForTesting;
+import org.joda.time.Interval;
+
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NavigableMap;
+import java.util.NavigableSet;
+import java.util.Set;
+import java.util.SortedMap;
+import java.util.function.BiConsumer;
+
+/**
+ * A variation of Interval Trees (https://en.wikipedia.org/wiki/Interval_tree)
+ * Custom optimizations for faster interval search and additional support for
specific joda Interval comparator
+ * arithmetic used in the project
+ *
+ *
+ * Multiple different intervals can be added to the tree. It can then be
searched to find all intervals matching a given
+ * interval. The user specifies the match condition, such as encompassing the
given interval, overlapping, etc. The
+ * search can return multiple results as multiple intervals in the tree could
match the criteria.
+ *
+ * Using the tree, reduces the search time from O(N) iterating through all the
intervals, to roughly O(log2(N)).
+ * Furthermore, a value can be associated with each interval, which is also
returned in the search result.
+ *
+ *
+ * The tree is a binary search tree sorted by interval start time. The
intervals are stored as nodes in the tree.
+ * Additional state containing the minimum and maximum interval bounds of the
entire subtree under a node is also
+ * stored in each node. This helps speed up the search for matching intervals
by skipping unsuitable subtrees that will
+ * not contain a matching candidate interval.
+ *
+ * To optimize the balancing cost w.r.t the operation time, the tree is not
balanced on every modification operation.
+ * Rather, a configurable imbalance tolerance from the theoretical ideal
height of log2(N) is allowed, breaching which
+ * triggers the rebalance.
+ *
+ * Not thread safe.
+ *
+ */
+public class IntervalTree extends AbstractMap implements
NavigableMap
+{
+ // The compartor for comparing the interval start timnes
+ Comparator startComparator;
+ // The comparator for comparing interval end times
+ Comparator endComparator;
+
+ @VisibleForTesting
+ Node root;
+ int size;
+
+ // Deviation allowed from ideal height for the maximum height on either side
of the tree, expressed as a
+ // percentage of ideal height
+ int imbalanceTolerance = 50;
+
+ EntrySet entrySet = new EntrySet();
+
+ public IntervalTree(Comparator startComparator,
Comparator endComparator)
+ {
+this.startComparator = startComparator;
+this.endComparator = endComparator;
+ }
+
+ public int getImbalanceTolerance()
+ {
+return imbalanceTolerance;
+ }
+
+ public void setImbalanceTolerance(int imbalanceTolerance)
+ {
+this.imbalanceTolerance = imbalanceTolerance;
+ }
+
+ static class Node implements Map.Entry
+ {
+Interval interval;
+T value;
+int height;
+// The full interval range of the subtree formed by this Node
+Interval range;
+Node parent;
+Node left;
+Node right;
+
+private static final String PRINT_FORMAT = "{\n"
++ "%sinterval = %s\n"
++ "%svalue = %s\n"
++ "%sheight = %d\n"
++ "%srange = %s\n"
++ "%sleft = %s\n"
++ "%sright = %s\n"
++ "%s}";
+
+private String print(int level)
+{
+ String prefix = "\t".repeat(level);
+ Str
Re: [PR] Interval tree for managing segment metadata in memory (druid)
FrankChen021 commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r3208936240
##
processing/src/main/java/org/apache/druid/timeline/IntervalTree.java:
##
@@ -0,0 +1,796 @@
+/*
+ * 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;
+
+import com.google.common.base.Predicate;
+import org.apache.druid.java.util.common.StringUtils;
+import org.jetbrains.annotations.NotNull;
+import org.jetbrains.annotations.VisibleForTesting;
+import org.joda.time.Interval;
+
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NavigableMap;
+import java.util.NavigableSet;
+import java.util.Set;
+import java.util.SortedMap;
+import java.util.function.BiConsumer;
+
+/**
+ * A variation of Interval Trees (https://en.wikipedia.org/wiki/Interval_tree)
+ * Custom optimizations for faster interval search and additional support for
specific joda Interval comparator
+ * arithmetic used in the project
+ *
+ *
+ * Multiple different intervals can be added to the tree. It can then be
searched to find all intervals matching a given
+ * interval. The user specifies the match condition, such as encompassing the
given interval, overlapping, etc. The
+ * search can return multiple results as multiple intervals in the tree could
match the criteria.
+ *
+ * Using the tree, reduces the search time from O(N) iterating through all the
intervals, to roughly O(log2(N)).
+ * Furthermore, a value can be associated with each interval, which is also
returned in the search result.
+ *
+ *
+ * The tree is a binary search tree sorted by interval start time. The
intervals are stored as nodes in the tree.
+ * Additional state containing the minimum and maximum interval bounds of the
entire subtree under a node is also
+ * stored in each node. This helps speed up the search for matching intervals
by skipping unsuitable subtrees that will
+ * not contain a matching candidate interval.
+ *
+ * To optimize the balancing cost w.r.t the operation time, the tree is not
balanced on every modification operation.
+ * Rather, a configurable imbalance tolerance from the theoretical ideal
height of log2(N) is allowed, breaching which
+ * triggers the rebalance.
+ *
+ * Not thread safe.
+ *
+ */
+public class IntervalTree extends AbstractMap implements
NavigableMap
+{
+ // The compartor for comparing the interval start timnes
+ Comparator startComparator;
+ // The comparator for comparing interval end times
+ Comparator endComparator;
+
+ @VisibleForTesting
+ Node root;
+ int size;
+
+ // Deviation allowed from ideal height for the maximum height on either side
of the tree, expressed as a
+ // percentage of ideal height
+ int imbalanceTolerance = 50;
+
+ EntrySet entrySet = new EntrySet();
+
+ public IntervalTree(Comparator startComparator,
Comparator endComparator)
+ {
+this.startComparator = startComparator;
+this.endComparator = endComparator;
+ }
+
+ public int getImbalanceTolerance()
+ {
+return imbalanceTolerance;
+ }
+
+ public void setImbalanceTolerance(int imbalanceTolerance)
+ {
+this.imbalanceTolerance = imbalanceTolerance;
+ }
+
+ static class Node implements Map.Entry
+ {
+Interval interval;
+T value;
+int height;
+// The full interval range of the subtree formed by this Node
+Interval range;
+Node parent;
+Node left;
+Node right;
+
+private static final String PRINT_FORMAT = "{\n"
++ "%sinterval = %s\n"
++ "%svalue = %s\n"
++ "%sheight = %d\n"
++ "%srange = %s\n"
++ "%sleft = %s\n"
++ "%sright = %s\n"
++ "%s}";
+
+private String print(int level)
+{
+ String prefix = "\t".repeat(level);
+
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r3205279430
##
processing/src/main/java/org/apache/druid/timeline/IntervalTree.java:
##
@@ -0,0 +1,796 @@
+/*
+ * 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;
+
+import com.google.common.base.Predicate;
+import org.apache.druid.java.util.common.StringUtils;
+import org.jetbrains.annotations.NotNull;
+import org.jetbrains.annotations.VisibleForTesting;
+import org.joda.time.Interval;
+
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NavigableMap;
+import java.util.NavigableSet;
+import java.util.Set;
+import java.util.SortedMap;
+import java.util.function.BiConsumer;
+
+/**
+ * A variation of Interval Trees (https://en.wikipedia.org/wiki/Interval_tree)
+ * Custom optimizations for faster interval search and additional support for
specific joda Interval comparator
+ * arithmetic used in the project
+ *
+ *
+ * Multiple different intervals can be added to the tree. It can then be
searched to find all intervals matching a given
+ * interval. The user specifies the match condition, such as encompassing the
given interval, overlapping, etc. The
+ * search can return multiple results as multiple intervals in the tree could
match the criteria.
+ *
+ * Using the tree, reduces the search time from O(N) iterating through all the
intervals, to roughly O(log2(N)).
+ * Furthermore, a value can be associated with each interval, which is also
returned in the search result.
+ *
+ *
+ * The tree is a binary search tree sorted by interval start time. The
intervals are stored as nodes in the tree.
+ * Additional state containing the minimum and maximum interval bounds of the
entire subtree under a node is also
+ * stored in each node. This helps speed up the search for matching intervals
by skipping unsuitable subtrees that will
+ * not contain a matching candidate interval.
+ *
+ * To optimize the balancing cost w.r.t the operation time, the tree is not
balanced on every modification operation.
+ * Rather, a configurable imbalance tolerance from the theoretical ideal
height of log2(N) is allowed, breaching which
+ * triggers the rebalance.
+ *
+ * Not thread safe.
+ *
+ */
+public class IntervalTree extends AbstractMap implements
NavigableMap
+{
+ // The compartor for comparing the interval start timnes
+ Comparator startComparator;
+ // The comparator for comparing interval end times
+ Comparator endComparator;
+
+ @VisibleForTesting
+ Node root;
+ int size;
+
+ // Deviation allowed from ideal height for the maximum height on either side
of the tree, expressed as a
+ // percentage of ideal height
+ int imbalanceTolerance = 50;
+
+ EntrySet entrySet = new EntrySet();
+
+ public IntervalTree(Comparator startComparator,
Comparator endComparator)
+ {
+this.startComparator = startComparator;
+this.endComparator = endComparator;
+ }
+
+ public int getImbalanceTolerance()
+ {
+return imbalanceTolerance;
+ }
+
+ public void setImbalanceTolerance(int imbalanceTolerance)
+ {
+this.imbalanceTolerance = imbalanceTolerance;
+ }
+
+ static class Node implements Map.Entry
+ {
+Interval interval;
+T value;
+int height;
+// The full interval range of the subtree formed by this Node
+Interval range;
+Node parent;
+Node left;
+Node right;
+
+private static final String PRINT_FORMAT = "{\n"
++ "%sinterval = %s\n"
++ "%svalue = %s\n"
++ "%sheight = %d\n"
++ "%srange = %s\n"
++ "%sleft = %s\n"
++ "%sright = %s\n"
++ "%s}";
+
+private String print(int level)
+{
+ String prefix = "\t".repeat(level);
+ Str
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r3205217759
##
processing/src/main/java/org/apache/druid/timeline/IntervalTree.java:
##
@@ -0,0 +1,796 @@
+/*
+ * 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;
+
+import com.google.common.base.Predicate;
+import org.apache.druid.java.util.common.StringUtils;
+import org.jetbrains.annotations.NotNull;
+import org.jetbrains.annotations.VisibleForTesting;
+import org.joda.time.Interval;
+
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NavigableMap;
+import java.util.NavigableSet;
+import java.util.Set;
+import java.util.SortedMap;
+import java.util.function.BiConsumer;
+
+/**
+ * A variation of Interval Trees (https://en.wikipedia.org/wiki/Interval_tree)
+ * Custom optimizations for faster interval search and additional support for
specific joda Interval comparator
+ * arithmetic used in the project
+ *
+ *
+ * Multiple different intervals can be added to the tree. It can then be
searched to find all intervals matching a given
+ * interval. The user specifies the match condition, such as encompassing the
given interval, overlapping, etc. The
+ * search can return multiple results as multiple intervals in the tree could
match the criteria.
+ *
+ * Using the tree, reduces the search time from O(N) iterating through all the
intervals, to roughly O(log2(N)).
+ * Furthermore, a value can be associated with each interval, which is also
returned in the search result.
+ *
+ *
+ * The tree is a binary search tree sorted by interval start time. The
intervals are stored as nodes in the tree.
+ * Additional state containing the minimum and maximum interval bounds of the
entire subtree under a node is also
+ * stored in each node. This helps speed up the search for matching intervals
by skipping unsuitable subtrees that will
+ * not contain a matching candidate interval.
+ *
+ * To optimize the balancing cost w.r.t the operation time, the tree is not
balanced on every modification operation.
+ * Rather, a configurable imbalance tolerance from the theoretical ideal
height of log2(N) is allowed, breaching which
+ * triggers the rebalance.
+ *
+ * Not thread safe.
+ *
+ */
+public class IntervalTree extends AbstractMap implements
NavigableMap
+{
+ // The compartor for comparing the interval start timnes
+ Comparator startComparator;
+ // The comparator for comparing interval end times
+ Comparator endComparator;
+
+ @VisibleForTesting
+ Node root;
+ int size;
+
+ // Deviation allowed from ideal height for the maximum height on either side
of the tree, expressed as a
+ // percentage of ideal height
+ int imbalanceTolerance = 50;
+
+ EntrySet entrySet = new EntrySet();
+
+ public IntervalTree(Comparator startComparator,
Comparator endComparator)
+ {
+this.startComparator = startComparator;
+this.endComparator = endComparator;
+ }
+
+ public int getImbalanceTolerance()
+ {
+return imbalanceTolerance;
+ }
+
+ public void setImbalanceTolerance(int imbalanceTolerance)
+ {
+this.imbalanceTolerance = imbalanceTolerance;
+ }
+
+ static class Node implements Map.Entry
+ {
+Interval interval;
+T value;
+int height;
+// The full interval range of the subtree formed by this Node
+Interval range;
+Node parent;
+Node left;
+Node right;
+
+private static final String PRINT_FORMAT = "{\n"
++ "%sinterval = %s\n"
++ "%svalue = %s\n"
++ "%sheight = %d\n"
++ "%srange = %s\n"
++ "%sleft = %s\n"
++ "%sright = %s\n"
++ "%s}";
+
+private String print(int level)
+{
+ String prefix = "\t".repeat(level);
+ Str
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r3205217759
##
processing/src/main/java/org/apache/druid/timeline/IntervalTree.java:
##
@@ -0,0 +1,796 @@
+/*
+ * 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;
+
+import com.google.common.base.Predicate;
+import org.apache.druid.java.util.common.StringUtils;
+import org.jetbrains.annotations.NotNull;
+import org.jetbrains.annotations.VisibleForTesting;
+import org.joda.time.Interval;
+
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NavigableMap;
+import java.util.NavigableSet;
+import java.util.Set;
+import java.util.SortedMap;
+import java.util.function.BiConsumer;
+
+/**
+ * A variation of Interval Trees (https://en.wikipedia.org/wiki/Interval_tree)
+ * Custom optimizations for faster interval search and additional support for
specific joda Interval comparator
+ * arithmetic used in the project
+ *
+ *
+ * Multiple different intervals can be added to the tree. It can then be
searched to find all intervals matching a given
+ * interval. The user specifies the match condition, such as encompassing the
given interval, overlapping, etc. The
+ * search can return multiple results as multiple intervals in the tree could
match the criteria.
+ *
+ * Using the tree, reduces the search time from O(N) iterating through all the
intervals, to roughly O(log2(N)).
+ * Furthermore, a value can be associated with each interval, which is also
returned in the search result.
+ *
+ *
+ * The tree is a binary search tree sorted by interval start time. The
intervals are stored as nodes in the tree.
+ * Additional state containing the minimum and maximum interval bounds of the
entire subtree under a node is also
+ * stored in each node. This helps speed up the search for matching intervals
by skipping unsuitable subtrees that will
+ * not contain a matching candidate interval.
+ *
+ * To optimize the balancing cost w.r.t the operation time, the tree is not
balanced on every modification operation.
+ * Rather, a configurable imbalance tolerance from the theoretical ideal
height of log2(N) is allowed, breaching which
+ * triggers the rebalance.
+ *
+ * Not thread safe.
+ *
+ */
+public class IntervalTree extends AbstractMap implements
NavigableMap
+{
+ // The compartor for comparing the interval start timnes
+ Comparator startComparator;
+ // The comparator for comparing interval end times
+ Comparator endComparator;
+
+ @VisibleForTesting
+ Node root;
+ int size;
+
+ // Deviation allowed from ideal height for the maximum height on either side
of the tree, expressed as a
+ // percentage of ideal height
+ int imbalanceTolerance = 50;
+
+ EntrySet entrySet = new EntrySet();
+
+ public IntervalTree(Comparator startComparator,
Comparator endComparator)
+ {
+this.startComparator = startComparator;
+this.endComparator = endComparator;
+ }
+
+ public int getImbalanceTolerance()
+ {
+return imbalanceTolerance;
+ }
+
+ public void setImbalanceTolerance(int imbalanceTolerance)
+ {
+this.imbalanceTolerance = imbalanceTolerance;
+ }
+
+ static class Node implements Map.Entry
+ {
+Interval interval;
+T value;
+int height;
+// The full interval range of the subtree formed by this Node
+Interval range;
+Node parent;
+Node left;
+Node right;
+
+private static final String PRINT_FORMAT = "{\n"
++ "%sinterval = %s\n"
++ "%svalue = %s\n"
++ "%sheight = %d\n"
++ "%srange = %s\n"
++ "%sleft = %s\n"
++ "%sright = %s\n"
++ "%s}";
+
+private String print(int level)
+{
+ String prefix = "\t".repeat(level);
+ Str
Re: [PR] Interval tree for managing segment metadata in memory (druid)
FrankChen021 commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r3201845126
##
processing/src/main/java/org/apache/druid/timeline/IntervalTree.java:
##
@@ -0,0 +1,796 @@
+/*
+ * 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;
+
+import com.google.common.base.Predicate;
+import org.apache.druid.java.util.common.StringUtils;
+import org.jetbrains.annotations.NotNull;
+import org.jetbrains.annotations.VisibleForTesting;
+import org.joda.time.Interval;
+
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NavigableMap;
+import java.util.NavigableSet;
+import java.util.Set;
+import java.util.SortedMap;
+import java.util.function.BiConsumer;
+
+/**
+ * A variation of Interval Trees (https://en.wikipedia.org/wiki/Interval_tree)
+ * Custom optimizations for faster interval search and additional support for
specific joda Interval comparator
+ * arithmetic used in the project
+ *
+ *
+ * Multiple different intervals can be added to the tree. It can then be
searched to find all intervals matching a given
+ * interval. The user specifies the match condition, such as encompassing the
given interval, overlapping, etc. The
+ * search can return multiple results as multiple intervals in the tree could
match the criteria.
+ *
+ * Using the tree, reduces the search time from O(N) iterating through all the
intervals, to roughly O(log2(N)).
+ * Furthermore, a value can be associated with each interval, which is also
returned in the search result.
+ *
+ *
+ * The tree is a binary search tree sorted by interval start time. The
intervals are stored as nodes in the tree.
+ * Additional state containing the minimum and maximum interval bounds of the
entire subtree under a node is also
+ * stored in each node. This helps speed up the search for matching intervals
by skipping unsuitable subtrees that will
+ * not contain a matching candidate interval.
+ *
+ * To optimize the balancing cost w.r.t the operation time, the tree is not
balanced on every modification operation.
+ * Rather, a configurable imbalance tolerance from the theoretical ideal
height of log2(N) is allowed, breaching which
+ * triggers the rebalance.
+ *
+ * Not thread safe.
+ *
+ */
+public class IntervalTree extends AbstractMap implements
NavigableMap
+{
+ // The compartor for comparing the interval start timnes
+ Comparator startComparator;
+ // The comparator for comparing interval end times
+ Comparator endComparator;
+
+ @VisibleForTesting
+ Node root;
+ int size;
+
+ // Deviation allowed from ideal height for the maximum height on either side
of the tree, expressed as a
+ // percentage of ideal height
+ int imbalanceTolerance = 50;
+
+ EntrySet entrySet = new EntrySet();
+
+ public IntervalTree(Comparator startComparator,
Comparator endComparator)
+ {
+this.startComparator = startComparator;
+this.endComparator = endComparator;
+ }
+
+ public int getImbalanceTolerance()
+ {
+return imbalanceTolerance;
+ }
+
+ public void setImbalanceTolerance(int imbalanceTolerance)
+ {
+this.imbalanceTolerance = imbalanceTolerance;
+ }
+
+ static class Node implements Map.Entry
+ {
+Interval interval;
+T value;
+int height;
+// The full interval range of the subtree formed by this Node
+Interval range;
+Node parent;
+Node left;
+Node right;
+
+private static final String PRINT_FORMAT = "{\n"
++ "%sinterval = %s\n"
++ "%svalue = %s\n"
++ "%sheight = %d\n"
++ "%srange = %s\n"
++ "%sleft = %s\n"
++ "%sright = %s\n"
++ "%s}";
+
+private String print(int level)
+{
+ String prefix = "\t".repeat(level);
+
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on PR #19138: URL: https://github.com/apache/druid/pull/19138#issuecomment-4392330677 Addressed comments from @FrankChen021 -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] - To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r3197446363
##
processing/src/main/java/org/apache/druid/timeline/IntervalTree.java:
##
@@ -0,0 +1,797 @@
+/*
+ * 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;
+
+import com.google.common.base.Predicate;
+import org.apache.druid.java.util.common.StringUtils;
+import org.jetbrains.annotations.NotNull;
+import org.jetbrains.annotations.VisibleForTesting;
+import org.joda.time.Interval;
+
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NavigableMap;
+import java.util.NavigableSet;
+import java.util.Set;
+import java.util.SortedMap;
+import java.util.function.BiConsumer;
+
+/**
+ * A variation of Interval Trees (https://en.wikipedia.org/wiki/Interval_tree)
+ * Custom optimizations for faster interval search and additional support for
specific joda Interval comparator
+ * arithmetic used in the project
+ *
+ *
+ * Multiple different intervals can be added to the tree. It can then be
searched to find all intervals matching a given
+ * interval. The user specifies the match condition, such as encompassing the
given interval, overlapping, etc. The
+ * search can return multiple results as multiple intervals in the tree could
match the criteria.
+ *
+ * Using the tree, reduces the search time from O(N) iterating through all the
intervals, to roughly O(log2(N)).
+ * Furthermore, a value can be associated with each interval, which is also
returned in the search result.
+ *
+ *
+ * The tree is a binary search tree sorted by interval start time. The
intervals are stored as nodes in the tree.
+ * Additional state containing the minimum and maximum interval bounds of the
entire subtree under a node is also
+ * stored in each node. This helps speed up the search for matching intervals
by skipping unsuitable subtrees that will
+ * not contain a matching candidate interval.
+ *
+ * To optimize the balancing cost w.r.t the operation time, the tree is not
balanced on every modification operation.
+ * Rather, a configurable imbalance tolerance from the theoretical ideal
height of log2(N) is allowed, breaching which
+ * triggers the rebalance.
+ *
+ * Not thread safe.
+ *
+ */
+public class IntervalTree extends AbstractMap implements
NavigableMap
+{
+ // The compartor for comparing the interval start timnes
+ Comparator startComparator;
+ // The comparator for comparing interval end times
+ Comparator endComparator;
+
+ @VisibleForTesting
+ Node root;
+ int size;
+
+ // Deviation allowed from ideal height for the maximum height on either side
of the tree, expressed as a
+ // percentage of ideal height
+ int imbalanceTolerance = 50;
+
+ EntrySet entrySet = new EntrySet();
+
+ public IntervalTree(Comparator startComparator,
Comparator endComparator)
+ {
+this.startComparator = startComparator;
+this.endComparator = endComparator;
+ }
+
+ public int getImbalanceTolerance()
+ {
+return imbalanceTolerance;
+ }
+
+ public void setImbalanceTolerance(int imbalanceTolerance)
+ {
+this.imbalanceTolerance = imbalanceTolerance;
+ }
+
+ static class Node implements Map.Entry
+ {
+Interval interval;
+T value;
+int height;
+// The full interval range of the subtree formed by this Node
+Interval range;
+Node parent;
+Node left;
+Node right;
+
+private static final String PRINT_FORMAT = "{\n"
++ "%sinterval = %s\n"
++ "%svalue = %s\n"
++ "%sheight = %d\n"
++ "%srange = %s\n"
++ "%sleft = %s\n"
++ "%sright = %s\n"
++ "%s}";
+
+public String print(int level)
+{
+ String prefix = "\t".repeat(level);
+ Stri
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r3197042308
##
processing/src/main/java/org/apache/druid/timeline/VersionedIntervalTimeline.java:
##
@@ -747,21 +795,38 @@ private List> lookup(Interval inte
timeline = completePartitionsTimeline;
}
-for (Entry entry : timeline.entrySet()) {
- Interval timelineInterval = entry.getKey();
- TimelineEntry val = entry.getValue();
-
- // exclude empty partition holders (i.e. tombstones) since they do not
add value
- // for higher level code...they have no data rows...
- if ((!skipObjectsWithNoData || val.partitionHolder.hasData()) &&
timelineInterval.overlaps(interval)) {
-retVal.add(
-new TimelineObjectHolder<>(
-timelineInterval,
-val.getTrueInterval(),
-val.getVersion(),
-
PartitionHolder.copyWithOnlyVisibleChunks(val.getPartitionHolder())
-)
-);
+if (fastIntervalSearch) {
Review Comment:
Parameterized the tests to exercise fastIntervalSearch true as well
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
FrankChen021 commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r3173375286
##
processing/src/main/java/org/apache/druid/timeline/VersionedIntervalTimeline.java:
##
@@ -747,21 +795,38 @@ private List> lookup(Interval inte
timeline = completePartitionsTimeline;
}
-for (Entry entry : timeline.entrySet()) {
- Interval timelineInterval = entry.getKey();
- TimelineEntry val = entry.getValue();
-
- // exclude empty partition holders (i.e. tombstones) since they do not
add value
- // for higher level code...they have no data rows...
- if ((!skipObjectsWithNoData || val.partitionHolder.hasData()) &&
timelineInterval.overlaps(interval)) {
-retVal.add(
-new TimelineObjectHolder<>(
-timelineInterval,
-val.getTrueInterval(),
-val.getVersion(),
-
PartitionHolder.copyWithOnlyVisibleChunks(val.getPartitionHolder())
-)
-);
+if (fastIntervalSearch) {
Review Comment:
Thanks. Yes, that is the remaining concern: please run the existing
VersionedIntervalTimeline coverage against fastIntervalSearch=true as well,
since the IntervalTree tests don't exercise VIT's interval
splitting/overshadowing behavior.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r3163820714
##
processing/src/main/java/org/apache/druid/timeline/VersionedIntervalTimeline.java:
##
@@ -747,21 +795,38 @@ private List> lookup(Interval inte
timeline = completePartitionsTimeline;
}
-for (Entry entry : timeline.entrySet()) {
- Interval timelineInterval = entry.getKey();
- TimelineEntry val = entry.getValue();
-
- // exclude empty partition holders (i.e. tombstones) since they do not
add value
- // for higher level code...they have no data rows...
- if ((!skipObjectsWithNoData || val.partitionHolder.hasData()) &&
timelineInterval.overlaps(interval)) {
-retVal.add(
-new TimelineObjectHolder<>(
-timelineInterval,
-val.getTrueInterval(),
-val.getVersion(),
-
PartitionHolder.copyWithOnlyVisibleChunks(val.getPartitionHolder())
-)
-);
+if (fastIntervalSearch) {
Review Comment:
Yes, was waiting for feedback on whether this configuration approach is
acceptable before making changes at all the places. Sounds like it is, will
propagate the changes.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r3163820714
##
processing/src/main/java/org/apache/druid/timeline/VersionedIntervalTimeline.java:
##
@@ -747,21 +795,38 @@ private List> lookup(Interval inte
timeline = completePartitionsTimeline;
}
-for (Entry entry : timeline.entrySet()) {
- Interval timelineInterval = entry.getKey();
- TimelineEntry val = entry.getValue();
-
- // exclude empty partition holders (i.e. tombstones) since they do not
add value
- // for higher level code...they have no data rows...
- if ((!skipObjectsWithNoData || val.partitionHolder.hasData()) &&
timelineInterval.overlaps(interval)) {
-retVal.add(
-new TimelineObjectHolder<>(
-timelineInterval,
-val.getTrueInterval(),
-val.getVersion(),
-
PartitionHolder.copyWithOnlyVisibleChunks(val.getPartitionHolder())
-)
-);
+if (fastIntervalSearch) {
Review Comment:
Yes, was waiting for feedback on whether this configuration approach is
acceptable before making changes at all the places.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
FrankChen021 commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r3141585621
##
processing/src/main/java/org/apache/druid/timeline/VersionedIntervalTimeline.java:
##
@@ -747,21 +795,38 @@ private List> lookup(Interval inte
timeline = completePartitionsTimeline;
}
-for (Entry entry : timeline.entrySet()) {
- Interval timelineInterval = entry.getKey();
- TimelineEntry val = entry.getValue();
-
- // exclude empty partition holders (i.e. tombstones) since they do not
add value
- // for higher level code...they have no data rows...
- if ((!skipObjectsWithNoData || val.partitionHolder.hasData()) &&
timelineInterval.overlaps(interval)) {
-retVal.add(
-new TimelineObjectHolder<>(
-timelineInterval,
-val.getTrueInterval(),
-val.getVersion(),
-
PartitionHolder.copyWithOnlyVisibleChunks(val.getPartitionHolder())
-)
-);
+if (fastIntervalSearch) {
Review Comment:
P2 Fast timeline path is not covered by existing VIT tests
The new fastIntervalSearch branch changes
lookup/findChunk/remove/overshadowing behavior, but the existing
VersionedIntervalTimeline test factory still constructs only the default false
path. IntervalTree unit tests do not cover VIT's adjusted interval splitting
and overshadowing semantics, so this can regress query segment selection when
the new config is enabled. Please parameterize the existing VIT tests to run
with fastIntervalSearch=true as well.
##
processing/src/main/java/org/apache/druid/timeline/IntervalTree.java:
##
@@ -0,0 +1,797 @@
+/*
+ * 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;
+
+import com.google.common.base.Predicate;
+import org.apache.druid.java.util.common.StringUtils;
+import org.jetbrains.annotations.NotNull;
+import org.jetbrains.annotations.VisibleForTesting;
+import org.joda.time.Interval;
+
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NavigableMap;
+import java.util.NavigableSet;
+import java.util.Set;
+import java.util.SortedMap;
+import java.util.function.BiConsumer;
+
+/**
+ * A variation of Interval Trees (https://en.wikipedia.org/wiki/Interval_tree)
+ * Custom optimizations for faster interval search and additional support for
specific joda Interval comparator
+ * arithmetic used in the project
+ *
+ *
+ * Multiple different intervals can be added to the tree. It can then be
searched to find all intervals matching a given
+ * interval. The user specifies the match condition, such as encompassing the
given interval, overlapping, etc. The
+ * search can return multiple results as multiple intervals in the tree could
match the criteria.
+ *
+ * Using the tree, reduces the search time from O(N) iterating through all the
intervals, to roughly O(log2(N)).
+ * Furthermore, a value can be associated with each interval, which is also
returned in the search result.
+ *
+ *
+ * The tree is a binary search tree sorted by interval start time. The
intervals are stored as nodes in the tree.
+ * Additional state containing the minimum and maximum interval bounds of the
entire subtree under a node is also
+ * stored in each node. This helps speed up the search for matching intervals
by skipping unsuitable subtrees that will
+ * not contain a matching candidate interval.
+ *
+ * To optimize the balancing cost w.r.t the operation time, the tree is not
balanced on every modification operation.
+ * Rather, a configurable imbalance tolerance from the theoretical ideal
height of log2(N) is allowed, breaching which
+ * triggers the rebalance.
+ *
+ * Not thread safe.
+ *
+ */
+public class IntervalTree extends AbstractMap implements
NavigableMap
+{
+ // The compartor for comparing the interval start timnes
+ Comparator startComparator;
+ // The comparator for comparing interval end times
+ Comparator endComparator;
+
+ @VisibleForTesting
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on PR #19138: URL: https://github.com/apache/druid/pull/19138#issuecomment-4308227433 Please see commend above on pushed config related changes @kfaraz -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] - To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r3127250027
##
processing/src/main/java/org/apache/druid/timeline/VersionedIntervalTimeline.java:
##
@@ -74,28 +75,77 @@
public class VersionedIntervalTimeline>
implements TimelineLookup
{
+ private static final Logger logger = new
Logger(VersionedIntervalTimeline.class);
private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock(true);
// Below timelines stores only *visible* timelineEntries
// adjusted interval -> timelineEntry
- private final NavigableMap
completePartitionsTimeline = new TreeMap<>(
- Comparators.intervalsByStartThenEnd()
- );
+ private final NavigableMap
completePartitionsTimeline;
// IncompletePartitionsTimeline also includes completePartitionsTimeline
// adjusted interval -> timelineEntry
@VisibleForTesting
- final NavigableMap incompletePartitionsTimeline =
new TreeMap<>(
- Comparators.intervalsByStartThenEnd()
- );
+ final NavigableMap incompletePartitionsTimeline;
// true interval -> version -> timelineEntry
private final Map>
allTimelineEntries = new HashMap<>();
+ private final IntervalTree>
allTimeIntervals = new IntervalTree<>(Comparators.intervalsByStart(),
Comparators.intervalsByEnd());
private final AtomicInteger numObjects = new AtomicInteger();
private final Comparator versionComparator;
// Set this to true if the client needs to skip tombstones upon lookup (like
the broker)
private final boolean skipObjectsWithNoData;
+ // 0 Legacy functionality
+ // 1 Use IntervalTree only for basic segment timeline
+ // 2 Use IntervalTree for querying segments as well
+ private enum IntervalTreeMatchMode
+ {
+NONE,
+ENTRIES_ONLY(Capability.ENTRIES),
+ALL(Capability.ENTRIES, Capability.QUERY);
+
+private enum Capability
+{
+ ENTRIES, QUERY
+}
+
+final Set capabilities;
+
+IntervalTreeMatchMode(Capability... capabilities)
+{
+ this.capabilities = Set.of(capabilities);
+}
+
+public boolean isEnabled(Capability capability)
+{
+ return capabilities.contains(capability);
+}
+ }
+
+ private static IntervalTreeMatchMode intervalTreeMatchMode =
IntervalTreeMatchMode.NONE;
+
+ static {
+String mode =
System.getProperty("experimental.timeline.intervalTreeMatchMode");
Review Comment:
@kfaraz please see if the modifications in the new commit are the way you
see this parameter should be configured. I wanted to get a feedback on this,
before making the modifications to pass in the parameter for all the classes
that use the timeline (directly or through layers of indirection), including
test classes and there are quite a few of them.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on PR #19138: URL: https://github.com/apache/druid/pull/19138#issuecomment-4299075820 @jtuglu1 thanks for the patience, submitting updates today. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] - To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
jtuglu1 commented on PR #19138: URL: https://github.com/apache/druid/pull/19138#issuecomment-4293378977 @pirvtech any updates here? I'm happy to get this merged if you're busy -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] - To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r3075353356
##
processing/src/main/java/org/apache/druid/timeline/VersionedIntervalTimeline.java:
##
@@ -74,28 +75,77 @@
public class VersionedIntervalTimeline>
implements TimelineLookup
{
+ private static final Logger logger = new
Logger(VersionedIntervalTimeline.class);
private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock(true);
// Below timelines stores only *visible* timelineEntries
// adjusted interval -> timelineEntry
- private final NavigableMap
completePartitionsTimeline = new TreeMap<>(
- Comparators.intervalsByStartThenEnd()
- );
+ private final NavigableMap
completePartitionsTimeline;
// IncompletePartitionsTimeline also includes completePartitionsTimeline
// adjusted interval -> timelineEntry
@VisibleForTesting
- final NavigableMap incompletePartitionsTimeline =
new TreeMap<>(
- Comparators.intervalsByStartThenEnd()
- );
+ final NavigableMap incompletePartitionsTimeline;
// true interval -> version -> timelineEntry
private final Map>
allTimelineEntries = new HashMap<>();
+ private final IntervalTree>
allTimeIntervals = new IntervalTree<>(Comparators.intervalsByStart(),
Comparators.intervalsByEnd());
private final AtomicInteger numObjects = new AtomicInteger();
private final Comparator versionComparator;
// Set this to true if the client needs to skip tombstones upon lookup (like
the broker)
private final boolean skipObjectsWithNoData;
+ // 0 Legacy functionality
+ // 1 Use IntervalTree only for basic segment timeline
+ // 2 Use IntervalTree for querying segments as well
+ private enum IntervalTreeMatchMode
+ {
+NONE,
+ENTRIES_ONLY(Capability.ENTRIES),
Review Comment:
Agree
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r3075350442
##
processing/src/main/java/org/apache/druid/timeline/VersionedIntervalTimeline.java:
##
@@ -74,28 +75,77 @@
public class VersionedIntervalTimeline>
implements TimelineLookup
{
+ private static final Logger logger = new
Logger(VersionedIntervalTimeline.class);
private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock(true);
// Below timelines stores only *visible* timelineEntries
// adjusted interval -> timelineEntry
- private final NavigableMap
completePartitionsTimeline = new TreeMap<>(
- Comparators.intervalsByStartThenEnd()
- );
+ private final NavigableMap
completePartitionsTimeline;
// IncompletePartitionsTimeline also includes completePartitionsTimeline
// adjusted interval -> timelineEntry
@VisibleForTesting
- final NavigableMap incompletePartitionsTimeline =
new TreeMap<>(
- Comparators.intervalsByStartThenEnd()
- );
+ final NavigableMap incompletePartitionsTimeline;
// true interval -> version -> timelineEntry
private final Map>
allTimelineEntries = new HashMap<>();
+ private final IntervalTree>
allTimeIntervals = new IntervalTree<>(Comparators.intervalsByStart(),
Comparators.intervalsByEnd());
private final AtomicInteger numObjects = new AtomicInteger();
private final Comparator versionComparator;
// Set this to true if the client needs to skip tombstones upon lookup (like
the broker)
private final boolean skipObjectsWithNoData;
+ // 0 Legacy functionality
+ // 1 Use IntervalTree only for basic segment timeline
+ // 2 Use IntervalTree for querying segments as well
+ private enum IntervalTreeMatchMode
+ {
+NONE,
+ENTRIES_ONLY(Capability.ENTRIES),
+ALL(Capability.ENTRIES, Capability.QUERY);
+
+private enum Capability
+{
+ ENTRIES, QUERY
+}
+
+final Set capabilities;
+
+IntervalTreeMatchMode(Capability... capabilities)
+{
+ this.capabilities = Set.of(capabilities);
+}
+
+public boolean isEnabled(Capability capability)
+{
+ return capabilities.contains(capability);
+}
+ }
+
+ private static IntervalTreeMatchMode intervalTreeMatchMode =
IntervalTreeMatchMode.NONE;
+
+ static {
+String mode =
System.getProperty("experimental.timeline.intervalTreeMatchMode");
Review Comment:
Agree. The mode was more for easing in this feature into the production
deployment with ability to fall back in case things didn't work out as planned.
A single binary feature flag maybe sufficient and coming from a configuration
like you suggested. I will make the change.
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
-
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on code in PR #19138: URL: https://github.com/apache/druid/pull/19138#discussion_r3075340491 ## processing/src/main/java/org/apache/druid/java/util/common/guava/Comparators.java: ## @@ -119,6 +119,34 @@ public int compare(Interval lhs, Interval rhs) } }; + private static final Comparator INTERVAL_BY_START = new Comparator<>() Review Comment: In IntervalTree we need a separate start and end comparators as we need to compare start and end times of intervals independently in different situations. Unfortunately INTERVAL_BY_START_THEN_END for example, compares end time when start times match and that leads to wrong results. I did initially try to use the existing comparators. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] - To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
jtuglu1 commented on PR #19138: URL: https://github.com/apache/druid/pull/19138#issuecomment-4238776858 > > @pirvtech – are you still working on this patch? We'd love to get this in and experimenting on Broker-side to fix some issues we've run into with large #s of intervals in the VIT. Happy to pick this up otherwise. > > @jtuglu1 yes was planning to send out updates to review comments this week. Let me know if you have any feedback as well. Feel free to use my benchmarks in https://github.com/apache/druid/pull/19278. I think it'd be great to extend on those to summarize/benchmark the common operations with a variable size of intervals to ensure we're seeing the expected throughput/latency. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] - To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on PR #19138: URL: https://github.com/apache/druid/pull/19138#issuecomment-4238710933 > @pirvtech – are you still working on this patch? We'd love to get this in and experimenting on Broker-side to fix some issues we've run into with large #s of intervals in the VIT. Happy to pick this up otherwise. @jtuglu1 yes was planning to send out updates to review comments this week. Let me know if you have any feedback as well. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] - To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
jtuglu1 commented on PR #19138: URL: https://github.com/apache/druid/pull/19138#issuecomment-4238193408 > Thanks for the clarification, @jtuglu1 ! Could you share an estimate of the typical number of intervals that causes the slowness? Were you able to capture flamegraphs? > > Regardless, I agree that this feature would be generally useful. We just need to clean up the changes a bit. I can get a flamegraph, but see the description of https://github.com/apache/druid/pull/19278 for explanation. Basically for a full year of MINUTE granularity you get ~500k intervals. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] - To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
kfaraz commented on PR #19138: URL: https://github.com/apache/druid/pull/19138#issuecomment-4227849090 Thanks for the clarification, @jtuglu1 ! Could you share an estimate of the typical number of intervals that causes the slowness? Were you able to capture flamegraphs? Regardless, I agree that this feature would be generally useful. We just need to clean up the changes a bit. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] - To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
jtuglu1 commented on PR #19138: URL: https://github.com/apache/druid/pull/19138#issuecomment-4210044419 @pirvtech – have you made any progress on this patch? We'd love to get this in and experimenting on Broker-side to fix some issues we've run into with large #s of intervals in the VIT. Happy to pick this up otherwise. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] - To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
jtuglu1 commented on PR #19138: URL: https://github.com/apache/druid/pull/19138#issuecomment-4209842873 @kfaraz I think this PR will have much more impact than just Historical. See https://github.com/apache/druid/pull/19278. Broker timeline operations become terribly slow under high # of intervals. We can use the interval tree here to speed up those operations drastically. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] - To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on PR #19138: URL: https://github.com/apache/druid/pull/19138#issuecomment-4084877434 @kfaraz thanks for the comments. We were facing a scenario where the number of segments were in the order of millions, due to the amount of parallelization we have in ingestion tasks, the time spread of data being ingested, and relative time offset when a time interval gets compacted. This change helped our historicals be able to load and serve segments faster. I had made another change to make the scanning and loading of local on-disk segments during historical startup multi-threaded from a single threa that it was, but looks like someone beat us to the punch in submission :). I will review your code feedback and provide my responses. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] - To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
kfaraz commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r2922543595
##
processing/src/main/java/org/apache/druid/java/util/common/guava/Comparators.java:
##
@@ -119,6 +119,34 @@ public int compare(Interval lhs, Interval rhs)
}
};
+ private static final Comparator INTERVAL_BY_START = new
Comparator<>()
Review Comment:
Can't we just reuse the existing comparators `INTERVAL_BY_START_THEN_END`
and `INTERVAL_BY_END_THEN_START`?
##
processing/src/main/java/org/apache/druid/timeline/VersionedIntervalTimeline.java:
##
@@ -74,28 +75,77 @@
public class VersionedIntervalTimeline>
implements TimelineLookup
{
+ private static final Logger logger = new
Logger(VersionedIntervalTimeline.class);
private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock(true);
// Below timelines stores only *visible* timelineEntries
// adjusted interval -> timelineEntry
- private final NavigableMap
completePartitionsTimeline = new TreeMap<>(
- Comparators.intervalsByStartThenEnd()
- );
+ private final NavigableMap
completePartitionsTimeline;
// IncompletePartitionsTimeline also includes completePartitionsTimeline
// adjusted interval -> timelineEntry
@VisibleForTesting
- final NavigableMap incompletePartitionsTimeline =
new TreeMap<>(
- Comparators.intervalsByStartThenEnd()
- );
+ final NavigableMap incompletePartitionsTimeline;
// true interval -> version -> timelineEntry
private final Map>
allTimelineEntries = new HashMap<>();
+ private final IntervalTree>
allTimeIntervals = new IntervalTree<>(Comparators.intervalsByStart(),
Comparators.intervalsByEnd());
private final AtomicInteger numObjects = new AtomicInteger();
private final Comparator versionComparator;
// Set this to true if the client needs to skip tombstones upon lookup (like
the broker)
private final boolean skipObjectsWithNoData;
+ // 0 Legacy functionality
+ // 1 Use IntervalTree only for basic segment timeline
+ // 2 Use IntervalTree for querying segments as well
+ private enum IntervalTreeMatchMode
+ {
+NONE,
+ENTRIES_ONLY(Capability.ENTRIES),
+ALL(Capability.ENTRIES, Capability.QUERY);
+
+private enum Capability
+{
+ ENTRIES, QUERY
+}
+
+final Set capabilities;
+
+IntervalTreeMatchMode(Capability... capabilities)
+{
+ this.capabilities = Set.of(capabilities);
+}
+
+public boolean isEnabled(Capability capability)
+{
+ return capabilities.contains(capability);
+}
+ }
+
+ private static IntervalTreeMatchMode intervalTreeMatchMode =
IntervalTreeMatchMode.NONE;
+
+ static {
+String mode =
System.getProperty("experimental.timeline.intervalTreeMatchMode");
Review Comment:
- Please don't use system properties here directly. Instead pass a flag into
the constructor of `VersionedIntervalTimeline` indicating whether the improved
datastructures should be used or not.
- Property name should be more like
`druid.segment.timeline.fastIntervalSearch` with possible values `true` and
`false`. (I don't think we need 3 modes).
- The class creating the timeline should pass in the correct value for the
flag.
##
processing/src/main/java/org/apache/druid/timeline/VersionedIntervalTimeline.java:
##
@@ -74,28 +75,77 @@
public class VersionedIntervalTimeline>
implements TimelineLookup
{
+ private static final Logger logger = new
Logger(VersionedIntervalTimeline.class);
private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock(true);
// Below timelines stores only *visible* timelineEntries
// adjusted interval -> timelineEntry
- private final NavigableMap
completePartitionsTimeline = new TreeMap<>(
- Comparators.intervalsByStartThenEnd()
- );
+ private final NavigableMap
completePartitionsTimeline;
// IncompletePartitionsTimeline also includes completePartitionsTimeline
// adjusted interval -> timelineEntry
@VisibleForTesting
- final NavigableMap incompletePartitionsTimeline =
new TreeMap<>(
- Comparators.intervalsByStartThenEnd()
- );
+ final NavigableMap incompletePartitionsTimeline;
// true interval -> version -> timelineEntry
private final Map>
allTimelineEntries = new HashMap<>();
+ private final IntervalTree>
allTimeIntervals = new IntervalTree<>(Comparators.intervalsByStart(),
Comparators.intervalsByEnd());
private final AtomicInteger numObjects = new AtomicInteger();
private final Comparator versionComparator;
// Set this to true if the client needs to skip tombstones upon lookup (like
the broker)
private final boolean skipObjectsWithNoData;
+ // 0 Legacy functionality
+ // 1 Use IntervalTree only for basic segment timeline
+ // 2 Use IntervalTree for querying segments as well
+ private enum IntervalTreeMatchMode
+ {
+NONE,
+ENTRIES_ONLY(Capability.ENTRIES),
Review Comment:
Is there a specifi
Re: [PR] Interval tree for managing segment metadata in memory (druid)
pirvtech commented on PR #19138: URL: https://github.com/apache/druid/pull/19138#issuecomment-4042784686 > Hi – thanks. Do you have benchmarks for this? I will add the benchmarks. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] - To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
Re: [PR] Interval tree for managing segment metadata in memory (druid)
github-advanced-security[bot] commented on code in PR #19138:
URL: https://github.com/apache/druid/pull/19138#discussion_r2921346381
##
processing/src/main/java/org/apache/druid/timeline/IntervalTree.java:
##
@@ -0,0 +1,797 @@
+/*
+ * 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;
+
+import com.google.common.base.Predicate;
+import org.apache.druid.java.util.common.StringUtils;
+import org.jetbrains.annotations.NotNull;
+import org.jetbrains.annotations.VisibleForTesting;
+import org.joda.time.Interval;
+
+import java.util.AbstractMap;
+import java.util.AbstractSet;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.NavigableMap;
+import java.util.NavigableSet;
+import java.util.Set;
+import java.util.SortedMap;
+import java.util.function.BiConsumer;
+
+/**
+ * A variation of Interval Trees (https://en.wikipedia.org/wiki/Interval_tree)
+ * Custom optimizations for faster interval search and additional support for
specific joda Interval comparator
+ * arithmetic used in the project
+ *
+ *
+ * Multiple different intervals can be added to the tree. It can then be
searched to find all intervals matching a given
+ * interval. The user specifies the match condition, such as encompassing the
given interval, overlapping, etc. The
+ * search can return multiple results as multiple intervals in the tree could
match the criteria.
+ *
+ * Using the tree, reduces the search time from O(N) iterating through all the
intervals, to roughly O(log2(N)).
+ * Furthermore, a value can be associated with each interval, which is also
returned in the search result.
+ *
+ *
+ * The tree is a binary search tree sorted by interval start time. The
intervals are stored as nodes in the tree.
+ * Additional state containing the minimum and maximum interval bounds of the
entire subtree under a node is also
+ * stored in each node. This helps speed up the search for matching intervals
by skipping unsuitable subtrees that will
+ * not contain a matching candidate interval.
+ *
+ * To optimize the balancing cost w.r.t the operation time, the tree is not
balanced on every modification operation.
+ * Rather, a configurable imbalance tolerance from the theoretical ideal
height of log2(N) is allowed, breaching which
+ * triggers the rebalance.
+ *
+ * Not thread safe.
+ *
+ */
+public class IntervalTree extends AbstractMap implements
NavigableMap
+{
+ // The compartor for comparing the interval start timnes
+ Comparator startComparator;
+ // The comparator for comparing interval end times
+ Comparator endComparator;
+
+ @VisibleForTesting
+ Node root;
+ int size;
+
+ // Deviation allowed from ideal height for the maximum height on either side
of the tree, expressed as a
+ // percentage of ideal height
+ int imbalanceTolerance = 50;
+
+ EntrySet entrySet = new EntrySet();
+
+ public IntervalTree(Comparator startComparator,
Comparator endComparator)
+ {
+this.startComparator = startComparator;
+this.endComparator = endComparator;
+ }
+
+ public int getImbalanceTolerance()
+ {
+return imbalanceTolerance;
+ }
+
+ public void setImbalanceTolerance(int imbalanceTolerance)
+ {
+this.imbalanceTolerance = imbalanceTolerance;
+ }
+
+ static class Node implements Map.Entry
+ {
+Interval interval;
+T value;
+int height;
+// The full interval range of the subtree formed by this Node
+Interval range;
+Node parent;
+Node left;
+Node right;
+
+private static final String PRINT_FORMAT = "{\n"
++ "%sinterval = %s\n"
++ "%svalue = %s\n"
++ "%sheight = %d\n"
++ "%srange = %s\n"
++ "%sleft = %s\n"
++ "%sright = %s\n"
++ "%s}";
+
+public String print(int level)
+{
+ String prefix = "\t".repea
Re: [PR] Interval tree for managing segment metadata in memory (druid)
jtuglu1 commented on PR #19138: URL: https://github.com/apache/druid/pull/19138#issuecomment-4042560579 Hi – do you have benchmarks for this? -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] - To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
