This is an automated email from the ASF dual-hosted git repository.
xingtanzjr pushed a commit to branch overlap_check_tool
in repository https://gitbox.apache.org/repos/asf/iotdb.git
The following commit(s) were added to refs/heads/overlap_check_tool by this
push:
new 3d230df45d4 Time range tool (#10808)
3d230df45d4 is described below
commit 3d230df45d4a0dd75cccac820ab14e17ff1ca1da
Author: Zhijia Cao <[email protected]>
AuthorDate: Tue Aug 8 10:38:33 2023 +0800
Time range tool (#10808)
* feat ListTimeRangeImpl
* feat OverlapStatisticTool
* add ut
---
.../dataregion/compaction/tool/Interval.java | 11 +++
.../compaction/tool/ListTimeRangeImpl.java | 52 +++++++++++-
.../compaction/tool/OverlapStatisticTool.java | 1 -
.../compaction/tool/UnseqSpaceStatistics.java | 22 ++++-
.../compaction/tools/ListTimeRangeImplTest.java | 94 ++++++++++++++++++++++
.../compaction/tools/UnseqSpaceStatisticsTest.java | 39 +++++++++
6 files changed, 212 insertions(+), 7 deletions(-)
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/Interval.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/Interval.java
index 7402ff34d20..8f2a2da301d 100644
---
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/Interval.java
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/Interval.java
@@ -26,6 +26,9 @@ public class Interval {
public Interval(long start, long end) {
this.start = start;
this.end = end;
+ if (end < start) {
+ throw new IllegalArgumentException("end must greater than start");
+ }
}
public long getStart() {
@@ -35,4 +38,12 @@ public class Interval {
public long getEnd() {
return end;
}
+
+ public void setStart(long start) {
+ this.start = start;
+ }
+
+ public void setEnd(long end) {
+ this.end = end;
+ }
}
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/ListTimeRangeImpl.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/ListTimeRangeImpl.java
index 8ff15fd02ca..12a3b490b22 100644
---
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/ListTimeRangeImpl.java
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/ListTimeRangeImpl.java
@@ -19,8 +19,7 @@
package org.apache.iotdb.db.storageengine.dataregion.compaction.tool;
-import java.util.LinkedList;
-import java.util.List;
+import java.util.*;
public class ListTimeRangeImpl implements ITimeRange {
@@ -30,10 +29,57 @@ public class ListTimeRangeImpl implements ITimeRange {
// 0-10. 20-70
@Override
- public void addInterval(Interval interval) {}
+ public void addInterval(Interval interval) {
+ List<Interval> mergedIntervals = new ArrayList<>();
+ int index = 0;
+ // 1. elements that do not overlap with the newly added element are placed
directly in the
+ // result
+ while (index < intervalList.size() && intervalList.get(index).getEnd() <
interval.getStart()) {
+ mergedIntervals.add(intervalList.get(index));
+ index++;
+ }
+
+ // 2. if the element overlaps with an existing element, start equals the
minimum value of the
+ // overlap and end equals the maximum value of the overlap
+ while (index < intervalList.size() && intervalList.get(index).getStart()
<= interval.getEnd()) {
+ interval.setStart(Math.min(intervalList.get(index).getStart(),
interval.getStart()));
+ interval.setEnd(Math.max(intervalList.get(index).getEnd(),
interval.getEnd()));
+ index++;
+ }
+ mergedIntervals.add(interval);
+
+ // 3. add the remaining elements to the result set
+ while (index < intervalList.size()) {
+ mergedIntervals.add(intervalList.get(index));
+ index++;
+ }
+
+ intervalList.clear();
+ intervalList.addAll(mergedIntervals);
+ }
+
+ public List<Interval> getIntervalList() {
+ return intervalList;
+ }
+
+ /**
+ * case 1: interval.getStart() <= currentInterval.getEnd()
+ *
+ * <p>currentInterval: [5,10], interval: [6,15],[1,7],[0,5],[10,15]
+ *
+ * <p>case 2: interval.getEnd() <= currentInterval.getEnd()
+ *
+ * <p>currentInterval: [5,10], interval:[1,9],[0,9],[1,10]
+ */
@Override
public boolean isOverlapped(Interval interval) {
+ for (Interval currentInterval : intervalList) {
+ if (interval.getStart() <= currentInterval.getEnd()
+ || interval.getEnd() <= currentInterval.getEnd()) {
+ return true;
+ }
+ }
return false;
}
}
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/OverlapStatisticTool.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/OverlapStatisticTool.java
index ca8523cb5d0..7a05ba9c9a4 100644
---
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/OverlapStatisticTool.java
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/OverlapStatisticTool.java
@@ -85,7 +85,6 @@ public class OverlapStatisticTool {
throw new RuntimeException(e);
}
}
-
return overlapStatistic;
}
diff --git
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/UnseqSpaceStatistics.java
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/UnseqSpaceStatistics.java
index 57bfb054fa8..0028ea452cb 100644
---
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/UnseqSpaceStatistics.java
+++
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tool/UnseqSpaceStatistics.java
@@ -19,16 +19,32 @@
package org.apache.iotdb.db.storageengine.dataregion.compaction.tool;
+import java.util.HashMap;
import java.util.Map;
public class UnseqSpaceStatistics {
// 设备 -> 序列 -> 时间范围
- private Map<String, Map<String, ITimeRange>> deviceStatisticMap;
+ private Map<String, Map<String, ITimeRange>> deviceStatisticMap = new
HashMap<>();
// 更新某个设备的某个序列的时间范围
- public void update(String device, String measurementUID, Interval interval)
{}
+ public void update(String device, String measurementUID, Interval interval) {
+ deviceStatisticMap
+ .computeIfAbsent(device, key -> new HashMap<>())
+ .computeIfAbsent(measurementUID, key -> new ListTimeRangeImpl())
+ .addInterval(interval);
+ }
public boolean hasOverlap(String device, String measurementUID, Interval
interval) {
- return false;
+ if (!deviceStatisticMap.containsKey(device)) {
+ return false;
+ }
+ if (!deviceStatisticMap.get(device).containsKey(measurementUID)) {
+ return false;
+ }
+ return
deviceStatisticMap.get(device).get(measurementUID).isOverlapped(interval);
+ }
+
+ public Map<String, Map<String, ITimeRange>> getDeviceStatisticMap() {
+ return deviceStatisticMap;
}
}
diff --git
a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tools/ListTimeRangeImplTest.java
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tools/ListTimeRangeImplTest.java
new file mode 100644
index 00000000000..62044ec39e0
--- /dev/null
+++
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tools/ListTimeRangeImplTest.java
@@ -0,0 +1,94 @@
+/*
+ * 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.iotdb.db.storageengine.dataregion.compaction.tools;
+
+import org.apache.iotdb.db.storageengine.dataregion.compaction.tool.Interval;
+import
org.apache.iotdb.db.storageengine.dataregion.compaction.tool.ListTimeRangeImpl;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+public class ListTimeRangeImplTest {
+
+ ListTimeRangeImpl listTimeRange = new ListTimeRangeImpl();
+
+ @Test
+ public void test01() {
+ listTimeRange.addInterval(new Interval(30, 40));
+ Assert.assertEquals(1, listTimeRange.getIntervalList().size());
+ Assert.assertEquals(30, listTimeRange.getIntervalList().get(0).getStart());
+ Assert.assertEquals(40, listTimeRange.getIntervalList().get(0).getEnd());
+ }
+
+ @Test
+ public void test02() {
+ listTimeRange.addInterval(new Interval(30, 40));
+ listTimeRange.addInterval(new Interval(10, 20));
+ listTimeRange.addInterval(new Interval(15, 20));
+ listTimeRange.addInterval(new Interval(50, 60));
+ Assert.assertEquals(3, listTimeRange.getIntervalList().size());
+ }
+
+ @Test
+ public void test03() {
+ listTimeRange.addInterval(new Interval(30, 40));
+ listTimeRange.addInterval(new Interval(10, 20));
+ listTimeRange.addInterval(new Interval(15, 20));
+ listTimeRange.addInterval(new Interval(50, 60));
+ listTimeRange.addInterval(new Interval(1, 100));
+ Assert.assertEquals(1, listTimeRange.getIntervalList().size());
+ Assert.assertEquals(1, listTimeRange.getIntervalList().get(0).getStart());
+ Assert.assertEquals(100, listTimeRange.getIntervalList().get(0).getEnd());
+ }
+
+ @Test
+ public void test04() {
+ listTimeRange.addInterval(new Interval(30, 40));
+ listTimeRange.addInterval(new Interval(10, 20));
+ listTimeRange.addInterval(new Interval(15, 20));
+ listTimeRange.addInterval(new Interval(50, 60));
+ listTimeRange.addInterval(new Interval(5, 100));
+ Assert.assertTrue(listTimeRange.isOverlapped(new Interval(1, 1)));
+ Assert.assertFalse(listTimeRange.isOverlapped(new Interval(101, 103)));
+ }
+
+ @Test
+ public void test05() {
+ listTimeRange.addInterval(new Interval(30, 40));
+ listTimeRange.addInterval(new Interval(10, 20));
+ listTimeRange.addInterval(new Interval(20, 30));
+ Assert.assertEquals(1, listTimeRange.getIntervalList().size());
+ }
+
+ @Test
+ public void test06() {
+ listTimeRange.addInterval(new Interval(1, 100));
+ listTimeRange.addInterval(new Interval(1, 2000));
+ Assert.assertEquals(1, listTimeRange.getIntervalList().size());
+ }
+
+ @Test
+ public void test07() {
+ listTimeRange.addInterval(new Interval(1, 10));
+ listTimeRange.addInterval(new Interval(60, 70));
+ listTimeRange.addInterval(new Interval(51, 55));
+ Assert.assertEquals(51, listTimeRange.getIntervalList().get(1).getStart());
+ }
+}
diff --git
a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tools/UnseqSpaceStatisticsTest.java
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tools/UnseqSpaceStatisticsTest.java
new file mode 100644
index 00000000000..af7213cac7a
--- /dev/null
+++
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/storageengine/dataregion/compaction/tools/UnseqSpaceStatisticsTest.java
@@ -0,0 +1,39 @@
+package org.apache.iotdb.db.storageengine.dataregion.compaction.tools;
+
+import org.apache.iotdb.db.storageengine.dataregion.compaction.tool.Interval;
+import
org.apache.iotdb.db.storageengine.dataregion.compaction.tool.UnseqSpaceStatistics;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+public class UnseqSpaceStatisticsTest {
+
+ @Test
+ public void test01() {
+ UnseqSpaceStatistics unseqSpaceStatistics = new UnseqSpaceStatistics();
+ unseqSpaceStatistics.update("root.db.d1", "s1", new Interval(1, 10));
+ unseqSpaceStatistics.update("root.db.d1", "s1", new Interval(5, 15));
+ unseqSpaceStatistics.update("root.db.d1", "s2", new Interval(1, 10));
+ unseqSpaceStatistics.update("root.db.d2", "s2", new Interval(1, 10));
+
+ Assert.assertEquals(2,
unseqSpaceStatistics.getDeviceStatisticMap().size());
+ Assert.assertEquals(2,
unseqSpaceStatistics.getDeviceStatisticMap().get("root.db.d1").size());
+ Assert.assertEquals(1,
unseqSpaceStatistics.getDeviceStatisticMap().get("root.db.d2").size());
+ }
+
+ @Test
+ public void test02() {
+ UnseqSpaceStatistics unseqSpaceStatistics = new UnseqSpaceStatistics();
+ unseqSpaceStatistics.update("root.db.d1", "s1", new Interval(1, 10));
+ unseqSpaceStatistics.update("root.db.d1", "s1", new Interval(5, 15));
+ unseqSpaceStatistics.update("root.db.d1", "s2", new Interval(1, 10));
+ unseqSpaceStatistics.update("root.db.d2", "s2", new Interval(1, 10));
+
+ Assert.assertTrue(unseqSpaceStatistics.hasOverlap("root.db.d1", "s1", new
Interval(1, 10)));
+ Assert.assertFalse(unseqSpaceStatistics.hasOverlap("root.db.d1", "s4", new
Interval(1, 10)));
+ Assert.assertFalse(unseqSpaceStatistics.hasOverlap("root.db.d2", "s1", new
Interval(1, 10)));
+
+ Assert.assertFalse(unseqSpaceStatistics.hasOverlap("root.db.d3", "s1", new
Interval(1, 10)));
+ Assert.assertFalse(unseqSpaceStatistics.hasOverlap("root.db.d1", "s1", new
Interval(21, 30)));
+ }
+}
