You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iotdb.apache.org by ja...@apache.org on 2022/11/25 09:47:05 UTC
[iotdb] branch IOTDB-4940 created (now fa3c5f7254)
This is an automated email from the ASF dual-hosted git repository.
jackietien pushed a change to branch IOTDB-4940
in repository https://gitbox.apache.org/repos/asf/iotdb.git
at fa3c5f7254 [IOTDB-4940] Optimize PartitonFetch Process in query
This branch includes the following new commits:
new fa3c5f7254 [IOTDB-4940] Optimize PartitonFetch Process in query
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
[iotdb] 01/01: [IOTDB-4940] Optimize PartitonFetch Process in query
Posted by ja...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
jackietien pushed a commit to branch IOTDB-4940
in repository https://gitbox.apache.org/repos/asf/iotdb.git
commit fa3c5f7254c9d894b33b7e89dee219edba5c2769
Author: JackieTien97 <ja...@gmail.com>
AuthorDate: Fri Nov 25 17:46:49 2022 +0800
[IOTDB-4940] Optimize PartitonFetch Process in query
---
.../commons/partition/DataPartitionQueryParam.java | 6 +
.../iotdb/db/mpp/plan/analyze/AnalyzeVisitor.java | 53 ++-
.../mpp/plan/analyze/QueryTimePartitionTest.java | 526 +++++++++++++++++++++
.../iotdb/tsfile/read/filter/GroupByFilter.java | 8 +
.../iotdb/tsfile/read/filter/TimeFilter.java | 84 ++++
.../iotdb/tsfile/read/filter/basic/Filter.java | 7 +
.../tsfile/read/filter/operator/AndFilter.java | 40 ++
.../tsfile/read/filter/operator/NotFilter.java | 27 ++
.../tsfile/read/filter/operator/OrFilter.java | 66 +++
9 files changed, 813 insertions(+), 4 deletions(-)
diff --git a/node-commons/src/main/java/org/apache/iotdb/commons/partition/DataPartitionQueryParam.java b/node-commons/src/main/java/org/apache/iotdb/commons/partition/DataPartitionQueryParam.java
index 8053a2e39b..83a7cdeb2c 100644
--- a/node-commons/src/main/java/org/apache/iotdb/commons/partition/DataPartitionQueryParam.java
+++ b/node-commons/src/main/java/org/apache/iotdb/commons/partition/DataPartitionQueryParam.java
@@ -28,6 +28,12 @@ public class DataPartitionQueryParam {
private String devicePath;
private List<TTimePartitionSlot> timePartitionSlotList = new ArrayList<>();
+ public DataPartitionQueryParam(
+ String devicePath, List<TTimePartitionSlot> timePartitionSlotList) {
+ this.devicePath = devicePath;
+ this.timePartitionSlotList = timePartitionSlotList;
+ }
+
public DataPartitionQueryParam() {}
public String getDevicePath() {
diff --git a/server/src/main/java/org/apache/iotdb/db/mpp/plan/analyze/AnalyzeVisitor.java b/server/src/main/java/org/apache/iotdb/db/mpp/plan/analyze/AnalyzeVisitor.java
index 9bd95df7b6..4e414ca69f 100644
--- a/server/src/main/java/org/apache/iotdb/db/mpp/plan/analyze/AnalyzeVisitor.java
+++ b/server/src/main/java/org/apache/iotdb/db/mpp/plan/analyze/AnalyzeVisitor.java
@@ -115,6 +115,7 @@ import org.apache.iotdb.tsfile.file.metadata.enums.CompressionType;
import org.apache.iotdb.tsfile.file.metadata.enums.TSDataType;
import org.apache.iotdb.tsfile.file.metadata.enums.TSEncoding;
import org.apache.iotdb.tsfile.read.TsFileSequenceReader;
+import org.apache.iotdb.tsfile.read.common.TimeRange;
import org.apache.iotdb.tsfile.read.filter.GroupByFilter;
import org.apache.iotdb.tsfile.read.filter.GroupByMonthFilter;
import org.apache.iotdb.tsfile.read.filter.basic.Filter;
@@ -1112,15 +1113,18 @@ public class AnalyzeVisitor extends StatementVisitor<Analysis, MPPQueryContext>
deviceSet.add(ExpressionAnalyzer.getDeviceNameInSourceExpression(expression));
}
}
- DataPartition dataPartition = fetchDataPartitionByDevices(deviceSet, schemaTree);
+ DataPartition dataPartition =
+ fetchDataPartitionByDevices(deviceSet, schemaTree, analysis.getGlobalTimeFilter());
analysis.setDataPartitionInfo(dataPartition);
}
- private DataPartition fetchDataPartitionByDevices(Set<String> deviceSet, ISchemaTree schemaTree) {
+ private DataPartition fetchDataPartitionByDevices(
+ Set<String> deviceSet, ISchemaTree schemaTree, Filter globalTimeFilter) {
+ List<TTimePartitionSlot> timePartitionSlotList = getTimePartitionSlotList(globalTimeFilter);
Map<String, List<DataPartitionQueryParam>> sgNameToQueryParamsMap = new HashMap<>();
for (String devicePath : deviceSet) {
- DataPartitionQueryParam queryParam = new DataPartitionQueryParam();
- queryParam.setDevicePath(devicePath);
+ DataPartitionQueryParam queryParam =
+ new DataPartitionQueryParam(devicePath, timePartitionSlotList);
sgNameToQueryParamsMap
.computeIfAbsent(schemaTree.getBelongedDatabase(devicePath), key -> new ArrayList<>())
.add(queryParam);
@@ -1128,6 +1132,47 @@ public class AnalyzeVisitor extends StatementVisitor<Analysis, MPPQueryContext>
return partitionFetcher.getDataPartition(sgNameToQueryParamsMap);
}
+ public static List<TTimePartitionSlot> getTimePartitionSlotList(Filter timeFilter) {
+ if (timeFilter == null) {
+ return Collections.emptyList();
+ }
+ List<TimeRange> timeRangeList = timeFilter.getTimeRanges();
+ if (timeRangeList.get(0).getMin() == Long.MIN_VALUE
+ || timeRangeList.get(timeRangeList.size() - 1).getMax() == Long.MAX_VALUE) {
+ return Collections.emptyList();
+ }
+
+ List<TTimePartitionSlot> result = new ArrayList<>();
+ long startTime =
+ (timeRangeList.get(0).getMin() / TimePartitionUtils.timePartitionInterval)
+ * TimePartitionUtils.timePartitionInterval; // included
+ long endTime = startTime + TimePartitionUtils.timePartitionInterval; // excluded
+ TTimePartitionSlot timePartitionSlot =
+ TimePartitionUtils.getTimePartition(timeRangeList.get(0).getMin());
+ int index = 0, size = timeRangeList.size();
+ while (index < size) {
+ long curLeft = timeRangeList.get(index).getMin();
+ long curRight = timeRangeList.get(index).getMax();
+ if (curLeft >= endTime) {
+ result.add(timePartitionSlot);
+ // next init
+ endTime =
+ (curLeft / TimePartitionUtils.timePartitionInterval + 1)
+ * TimePartitionUtils.timePartitionInterval;
+ timePartitionSlot = TimePartitionUtils.getTimePartition(curLeft);
+ } else if (curRight >= endTime) {
+ result.add(timePartitionSlot);
+ // next init
+ timePartitionSlot = new TTimePartitionSlot(endTime);
+ endTime = endTime + TimePartitionUtils.timePartitionInterval;
+ } else {
+ index++;
+ }
+ }
+ result.add(timePartitionSlot);
+ return result;
+ }
+
private void analyzeInto(
Analysis analysis,
QueryStatement queryStatement,
diff --git a/server/src/test/java/org/apache/iotdb/db/mpp/plan/analyze/QueryTimePartitionTest.java b/server/src/test/java/org/apache/iotdb/db/mpp/plan/analyze/QueryTimePartitionTest.java
new file mode 100644
index 0000000000..53607a13ef
--- /dev/null
+++ b/server/src/test/java/org/apache/iotdb/db/mpp/plan/analyze/QueryTimePartitionTest.java
@@ -0,0 +1,526 @@
+/*
+ * 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.mpp.plan.analyze;
+
+import org.apache.iotdb.common.rpc.thrift.TTimePartitionSlot;
+import org.apache.iotdb.db.conf.IoTDBDescriptor;
+import org.apache.iotdb.tsfile.read.common.TimeRange;
+import org.apache.iotdb.tsfile.read.filter.TimeFilter;
+import org.apache.iotdb.tsfile.read.filter.operator.AndFilter;
+import org.apache.iotdb.tsfile.read.filter.operator.NotFilter;
+import org.apache.iotdb.tsfile.read.filter.operator.OrFilter;
+
+import org.junit.Test;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
+import static org.apache.iotdb.db.mpp.plan.analyze.AnalyzeVisitor.getTimePartitionSlotList;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+
+public class QueryTimePartitionTest {
+
+ @Test
+ public void testAndTimeFilter() {
+ TimeFilter.TimeGt left = TimeFilter.gt(10);
+ TimeFilter.TimeLt right = TimeFilter.lt(20);
+
+ // time > 10 and time < 20
+ AndFilter andFilter = new AndFilter(left, right);
+ List<TimeRange> timeRangeList = andFilter.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(11, timeRangeList.get(0).getMin());
+ assertEquals(19, timeRangeList.get(0).getMax());
+
+ // time > 10 and time <= 20
+ andFilter = new AndFilter(left, TimeFilter.ltEq(20));
+ timeRangeList = andFilter.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(11, timeRangeList.get(0).getMin());
+ assertEquals(20, timeRangeList.get(0).getMax());
+
+ // time >= 10 and time <= 20
+ andFilter = new AndFilter(TimeFilter.gtEq(10), TimeFilter.ltEq(20));
+ timeRangeList = andFilter.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(10, timeRangeList.get(0).getMin());
+ assertEquals(20, timeRangeList.get(0).getMax());
+
+ // time <= 20 and time >= 10
+ andFilter = new AndFilter(TimeFilter.ltEq(20), TimeFilter.gtEq(10));
+ timeRangeList = andFilter.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(10, timeRangeList.get(0).getMin());
+ assertEquals(20, timeRangeList.get(0).getMax());
+
+ // time >= 20 and time <= 10
+ andFilter = new AndFilter(TimeFilter.gtEq(20), TimeFilter.ltEq(10));
+ timeRangeList = andFilter.getTimeRanges();
+ assertEquals(0, timeRangeList.size());
+
+ // time >= 20 and time < 20
+ andFilter = new AndFilter(TimeFilter.gtEq(20), TimeFilter.lt(20));
+ timeRangeList = andFilter.getTimeRanges();
+ assertEquals(0, timeRangeList.size());
+ }
+
+ @Test
+ public void testOrTimeFilter() {
+
+ // time < 10 or time > 20
+ OrFilter filter = new OrFilter(TimeFilter.lt(10), TimeFilter.gt(20));
+ List<TimeRange> timeRangeList = filter.getTimeRanges();
+ assertEquals(2, timeRangeList.size());
+ assertEquals(Long.MIN_VALUE, timeRangeList.get(0).getMin());
+ assertEquals(9, timeRangeList.get(0).getMax());
+ assertEquals(21, timeRangeList.get(1).getMin());
+ assertEquals(Long.MAX_VALUE, timeRangeList.get(1).getMax());
+
+ // time < 10 or time >= 20
+ filter = new OrFilter(TimeFilter.lt(10), TimeFilter.gtEq(20));
+ timeRangeList = filter.getTimeRanges();
+ assertEquals(2, timeRangeList.size());
+ assertEquals(Long.MIN_VALUE, timeRangeList.get(0).getMin());
+ assertEquals(9, timeRangeList.get(0).getMax());
+ assertEquals(20, timeRangeList.get(1).getMin());
+ assertEquals(Long.MAX_VALUE, timeRangeList.get(1).getMax());
+
+ // time <= 10 or time >= 20
+ filter = new OrFilter(TimeFilter.ltEq(10), TimeFilter.gtEq(20));
+ timeRangeList = filter.getTimeRanges();
+ assertEquals(2, timeRangeList.size());
+ assertEquals(Long.MIN_VALUE, timeRangeList.get(0).getMin());
+ assertEquals(10, timeRangeList.get(0).getMax());
+ assertEquals(20, timeRangeList.get(1).getMin());
+ assertEquals(Long.MAX_VALUE, timeRangeList.get(1).getMax());
+
+ // time >= 20 or time <= 10
+ filter = new OrFilter(TimeFilter.gtEq(20), TimeFilter.ltEq(10));
+ timeRangeList = filter.getTimeRanges();
+ assertEquals(2, timeRangeList.size());
+ assertEquals(Long.MIN_VALUE, timeRangeList.get(0).getMin());
+ assertEquals(10, timeRangeList.get(0).getMax());
+ assertEquals(20, timeRangeList.get(1).getMin());
+ assertEquals(Long.MAX_VALUE, timeRangeList.get(1).getMax());
+
+ // time >= 20 or time >= 10
+ filter = new OrFilter(TimeFilter.gtEq(20), TimeFilter.gtEq(10));
+ timeRangeList = filter.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(10, timeRangeList.get(0).getMin());
+ assertEquals(Long.MAX_VALUE, timeRangeList.get(0).getMax());
+
+ // time < 20 or time <= 10
+ filter = new OrFilter(TimeFilter.lt(20), TimeFilter.ltEq(10));
+ timeRangeList = filter.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(Long.MIN_VALUE, timeRangeList.get(0).getMin());
+ assertEquals(19, timeRangeList.get(0).getMax());
+ }
+
+ @Test
+ public void testAndOrTimeFilter() {
+
+ // (time >= 10 and time <= 20) or (time > 30)
+ OrFilter filter =
+ new OrFilter(new AndFilter(TimeFilter.gtEq(10), TimeFilter.ltEq(20)), TimeFilter.gt(30));
+ List<TimeRange> timeRangeList = filter.getTimeRanges();
+ assertEquals(2, timeRangeList.size());
+ assertEquals(10, timeRangeList.get(0).getMin());
+ assertEquals(20, timeRangeList.get(0).getMax());
+ assertEquals(31, timeRangeList.get(1).getMin());
+ assertEquals(Long.MAX_VALUE, timeRangeList.get(1).getMax());
+
+ // (time <= 10 or time > 20) and (time >= 30)
+ AndFilter filter1 =
+ new AndFilter(new OrFilter(TimeFilter.ltEq(10), TimeFilter.gt(20)), TimeFilter.gtEq(30));
+ timeRangeList = filter1.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(30, timeRangeList.get(0).getMin());
+ assertEquals(Long.MAX_VALUE, timeRangeList.get(0).getMax());
+
+ // (time <= 10 or time > 20) and (time <= 30)
+ filter1 =
+ new AndFilter(new OrFilter(TimeFilter.ltEq(10), TimeFilter.gt(20)), TimeFilter.ltEq(30));
+ timeRangeList = filter1.getTimeRanges();
+ assertEquals(2, timeRangeList.size());
+ assertEquals(Long.MIN_VALUE, timeRangeList.get(0).getMin());
+ assertEquals(10, timeRangeList.get(0).getMax());
+ assertEquals(21, timeRangeList.get(1).getMin());
+ assertEquals(30, timeRangeList.get(1).getMax());
+
+ // (time >= 10 and time <= 20) or (time < 99 and time > 30)
+ filter =
+ new OrFilter(
+ new AndFilter(TimeFilter.gtEq(10), TimeFilter.ltEq(20)),
+ new AndFilter(TimeFilter.lt(100), TimeFilter.gt(30)));
+ timeRangeList = filter.getTimeRanges();
+ assertEquals(2, timeRangeList.size());
+ assertEquals(10, timeRangeList.get(0).getMin());
+ assertEquals(20, timeRangeList.get(0).getMax());
+ assertEquals(31, timeRangeList.get(1).getMin());
+ assertEquals(99, timeRangeList.get(1).getMax());
+ }
+
+ @Test
+ public void testBetweenTimeFilter() {
+
+ // time between 10 and 20
+ TimeFilter.TimeBetween filter = TimeFilter.between(10, 20, false);
+ List<TimeRange> timeRangeList = filter.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(10, timeRangeList.get(0).getMin());
+ assertEquals(20, timeRangeList.get(0).getMax());
+
+ // time not between 10 and 20
+ filter = TimeFilter.between(10, 20, true);
+ timeRangeList = filter.getTimeRanges();
+ assertEquals(2, timeRangeList.size());
+ assertEquals(Long.MIN_VALUE, timeRangeList.get(0).getMin());
+ assertEquals(9, timeRangeList.get(0).getMax());
+ assertEquals(21, timeRangeList.get(1).getMin());
+ assertEquals(Long.MAX_VALUE, timeRangeList.get(1).getMax());
+
+ // time not between 10 and Long.MAX_VALUE
+ filter = TimeFilter.between(10, Long.MAX_VALUE, true);
+ timeRangeList = filter.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(Long.MIN_VALUE, timeRangeList.get(0).getMin());
+ assertEquals(9, timeRangeList.get(0).getMax());
+
+ // time not between Long.MIN_VALUE and 20
+ filter = TimeFilter.between(Long.MIN_VALUE, 20, true);
+ timeRangeList = filter.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(21, timeRangeList.get(0).getMin());
+ assertEquals(Long.MAX_VALUE, timeRangeList.get(0).getMax());
+ }
+
+ @Test
+ public void testNotTimeFilter() {
+
+ // !(time > 10 and time <= 20)
+ NotFilter filter = new NotFilter(new AndFilter(TimeFilter.gt(10), TimeFilter.ltEq(20)));
+ List<TimeRange> timeRangeList = filter.getTimeRanges();
+ assertEquals(2, timeRangeList.size());
+ assertEquals(Long.MIN_VALUE, timeRangeList.get(0).getMin());
+ assertEquals(10, timeRangeList.get(0).getMax());
+ assertEquals(21, timeRangeList.get(1).getMin());
+ assertEquals(Long.MAX_VALUE, timeRangeList.get(1).getMax());
+
+ // !(time > 20 or time <= 10)
+ filter = new NotFilter(new OrFilter(TimeFilter.gt(20), TimeFilter.ltEq(10)));
+ timeRangeList = filter.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(11, timeRangeList.get(0).getMin());
+ assertEquals(20, timeRangeList.get(0).getMax());
+ }
+
+ @Test
+ public void testTimeEqFilter() {
+
+ // time = 10
+ TimeFilter.TimeEq filter = TimeFilter.eq(10);
+ List<TimeRange> timeRangeList = filter.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(10, timeRangeList.get(0).getMin());
+ assertEquals(10, timeRangeList.get(0).getMax());
+
+ // !(time = 10)
+ NotFilter filter1 = new NotFilter(filter);
+ timeRangeList = filter1.getTimeRanges();
+ assertEquals(2, timeRangeList.size());
+ assertEquals(Long.MIN_VALUE, timeRangeList.get(0).getMin());
+ assertEquals(9, timeRangeList.get(0).getMax());
+ assertEquals(11, timeRangeList.get(1).getMin());
+ assertEquals(Long.MAX_VALUE, timeRangeList.get(1).getMax());
+ }
+
+ @Test
+ public void testTimeNotEqFilter() {
+
+ // time != 10
+ TimeFilter.TimeNotEq filter = TimeFilter.notEq(10);
+ List<TimeRange> timeRangeList = filter.getTimeRanges();
+ assertEquals(2, timeRangeList.size());
+ assertEquals(Long.MIN_VALUE, timeRangeList.get(0).getMin());
+ assertEquals(9, timeRangeList.get(0).getMax());
+ assertEquals(11, timeRangeList.get(1).getMin());
+ assertEquals(Long.MAX_VALUE, timeRangeList.get(1).getMax());
+
+ // !(time != 10)
+ NotFilter filter1 = new NotFilter(filter);
+ timeRangeList = filter1.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(10, timeRangeList.get(0).getMin());
+ assertEquals(10, timeRangeList.get(0).getMax());
+ }
+
+ @Test
+ public void testTimeGtFilter() {
+
+ // time > 10
+ TimeFilter.TimeGt filter = TimeFilter.gt(10);
+ List<TimeRange> timeRangeList = filter.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(11, timeRangeList.get(0).getMin());
+ assertEquals(Long.MAX_VALUE, timeRangeList.get(0).getMax());
+
+ // !(time > 10)
+ NotFilter filter1 = new NotFilter(filter);
+ timeRangeList = filter1.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(Long.MIN_VALUE, timeRangeList.get(0).getMin());
+ assertEquals(10, timeRangeList.get(0).getMax());
+ }
+
+ @Test
+ public void testTimeGtEqFilter() {
+
+ // time >= 10
+ TimeFilter.TimeGtEq filter = TimeFilter.gtEq(10);
+ List<TimeRange> timeRangeList = filter.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(10, timeRangeList.get(0).getMin());
+ assertEquals(Long.MAX_VALUE, timeRangeList.get(0).getMax());
+
+ // !(time >= 10)
+ NotFilter filter1 = new NotFilter(filter);
+ timeRangeList = filter1.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(Long.MIN_VALUE, timeRangeList.get(0).getMin());
+ assertEquals(9, timeRangeList.get(0).getMax());
+ }
+
+ @Test
+ public void testTimeLtFilter() {
+
+ // time < 10
+ TimeFilter.TimeLt filter = TimeFilter.lt(10);
+ List<TimeRange> timeRangeList = filter.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(Long.MIN_VALUE, timeRangeList.get(0).getMin());
+ assertEquals(9, timeRangeList.get(0).getMax());
+
+ // !(time < 10)
+ NotFilter filter1 = new NotFilter(filter);
+ timeRangeList = filter1.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(10, timeRangeList.get(0).getMin());
+ assertEquals(Long.MAX_VALUE, timeRangeList.get(0).getMax());
+ }
+
+ @Test
+ public void testTimeLtEqFilter() {
+
+ // time <= 10
+ TimeFilter.TimeLtEq filter = TimeFilter.ltEq(10);
+ List<TimeRange> timeRangeList = filter.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(Long.MIN_VALUE, timeRangeList.get(0).getMin());
+ assertEquals(10, timeRangeList.get(0).getMax());
+
+ // !(time <= 10)
+ NotFilter filter1 = new NotFilter(filter);
+ timeRangeList = filter1.getTimeRanges();
+ assertEquals(1, timeRangeList.size());
+ assertEquals(11, timeRangeList.get(0).getMin());
+ assertEquals(Long.MAX_VALUE, timeRangeList.get(0).getMax());
+ }
+
+ @Test
+ public void testGetTimePartitionSlotList() {
+ // time >= 10
+ List<TTimePartitionSlot> res = getTimePartitionSlotList(TimeFilter.gtEq(10));
+ assertTrue(res.isEmpty());
+
+ // time < 20
+ res = getTimePartitionSlotList(TimeFilter.lt(20));
+ assertTrue(res.isEmpty());
+
+ // time > 10 and time <= 20
+ res = getTimePartitionSlotList(new AndFilter(TimeFilter.gt(10), TimeFilter.ltEq(20)));
+ List<TTimePartitionSlot> expected = Collections.singletonList(new TTimePartitionSlot(0));
+ assertEquals(expected.size(), res.size());
+ for (int i = 0; i < expected.size(); i++) {
+ assertEquals(expected.get(i), res.get(i));
+ }
+
+ // time > 0 and time <= IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 3
+ // + 1
+ res =
+ getTimePartitionSlotList(
+ new AndFilter(
+ TimeFilter.gt(0),
+ TimeFilter.ltEq(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 3 + 1)));
+ expected =
+ Arrays.asList(
+ new TTimePartitionSlot(0),
+ new TTimePartitionSlot(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval()),
+ new TTimePartitionSlot(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 2),
+ new TTimePartitionSlot(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 3));
+ assertEquals(expected.size(), res.size());
+ for (int i = 0; i < expected.size(); i++) {
+ assertEquals(expected.get(i), res.get(i));
+ }
+
+ // time >= IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() - 1 and time <
+ // IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() + 1
+ res =
+ getTimePartitionSlotList(
+ new AndFilter(
+ TimeFilter.gtEq(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() - 1),
+ TimeFilter.lt(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() + 1)));
+ expected =
+ Arrays.asList(
+ new TTimePartitionSlot(0),
+ new TTimePartitionSlot(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval()));
+ assertEquals(expected.size(), res.size());
+ for (int i = 0; i < expected.size(); i++) {
+ assertEquals(expected.get(i), res.get(i));
+ }
+
+ // time between IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() - 1 and
+ // time < IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval()
+ res =
+ getTimePartitionSlotList(
+ TimeFilter.between(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() - 1,
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval(),
+ false));
+ expected =
+ Arrays.asList(
+ new TTimePartitionSlot(0),
+ new TTimePartitionSlot(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval()));
+ assertEquals(expected.size(), res.size());
+ for (int i = 0; i < expected.size(); i++) {
+ assertEquals(expected.get(i), res.get(i));
+ }
+
+ // time >= IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() and time <=
+ // IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() + 1
+ res =
+ getTimePartitionSlotList(
+ new AndFilter(
+ TimeFilter.gtEq(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval()),
+ TimeFilter.ltEq(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() + 1)));
+ expected =
+ Collections.singletonList(
+ new TTimePartitionSlot(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval()));
+ assertEquals(expected.size(), res.size());
+ for (int i = 0; i < expected.size(); i++) {
+ assertEquals(expected.get(i), res.get(i));
+ }
+
+ // time between IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() and time <=
+ // IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() + 1
+ res =
+ getTimePartitionSlotList(
+ TimeFilter.between(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval(),
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() + 1,
+ false));
+ expected =
+ Collections.singletonList(
+ new TTimePartitionSlot(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval()));
+ assertEquals(expected.size(), res.size());
+ for (int i = 0; i < expected.size(); i++) {
+ assertEquals(expected.get(i), res.get(i));
+ }
+
+ // (time >= 10 and time < IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval())
+ // or (time > IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() and time <
+ // IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 2 - 100)
+ // or (time > IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 2 - 50 and
+ // time <= IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 2 - 40)
+ // or (time > IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 2 - 20 and
+ // time <= IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 3 + 10)
+ // or (time > IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 5 + 1 and
+ // time < IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 5 + 10)
+
+ OrFilter orFilter1 =
+ new OrFilter(
+ new AndFilter(
+ TimeFilter.gtEq(10),
+ TimeFilter.lt(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval())),
+ new AndFilter(
+ TimeFilter.gt(IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval()),
+ TimeFilter.lt(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 2
+ - 100)));
+ OrFilter orFilter2 =
+ new OrFilter(
+ orFilter1,
+ new AndFilter(
+ TimeFilter.gt(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 2 - 50),
+ TimeFilter.ltEq(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 2
+ - 40)));
+ OrFilter orFilter3 =
+ new OrFilter(
+ orFilter2,
+ new AndFilter(
+ TimeFilter.gt(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 2 - 20),
+ TimeFilter.ltEq(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 3
+ + 10)));
+ OrFilter orFilter4 =
+ new OrFilter(
+ orFilter3,
+ new AndFilter(
+ TimeFilter.gt(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 5 + 1),
+ TimeFilter.lt(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 5
+ + 10)));
+
+ res = getTimePartitionSlotList(orFilter4);
+ expected =
+ Arrays.asList(
+ new TTimePartitionSlot(0),
+ new TTimePartitionSlot(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval()),
+ new TTimePartitionSlot(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 2),
+ new TTimePartitionSlot(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 3),
+ new TTimePartitionSlot(
+ IoTDBDescriptor.getInstance().getConfig().getTimePartitionInterval() * 5));
+ for (int i = 0; i < expected.size(); i++) {
+ assertEquals(expected.get(i), res.get(i));
+ }
+ }
+}
diff --git a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/GroupByFilter.java b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/GroupByFilter.java
index 236f7a4305..179f239f8d 100644
--- a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/GroupByFilter.java
+++ b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/GroupByFilter.java
@@ -19,6 +19,7 @@
package org.apache.iotdb.tsfile.read.filter;
import org.apache.iotdb.tsfile.file.metadata.statistics.Statistics;
+import org.apache.iotdb.tsfile.read.common.TimeRange;
import org.apache.iotdb.tsfile.read.filter.basic.Filter;
import org.apache.iotdb.tsfile.read.filter.factory.FilterSerializeId;
@@ -26,6 +27,8 @@ import java.io.DataOutputStream;
import java.io.IOException;
import java.io.Serializable;
import java.nio.ByteBuffer;
+import java.util.Collections;
+import java.util.List;
import java.util.Objects;
public class GroupByFilter implements Filter, Serializable {
@@ -151,4 +154,9 @@ public class GroupByFilter implements Filter, Serializable {
public long getEndTime() {
return endTime;
}
+
+ @Override
+ public List<TimeRange> getTimeRanges() {
+ return Collections.singletonList(new TimeRange(startTime, endTime - 1));
+ }
}
diff --git a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/TimeFilter.java b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/TimeFilter.java
index e5109bf46b..e33b617e60 100644
--- a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/TimeFilter.java
+++ b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/TimeFilter.java
@@ -18,6 +18,7 @@
*/
package org.apache.iotdb.tsfile.read.filter;
+import org.apache.iotdb.tsfile.read.common.TimeRange;
import org.apache.iotdb.tsfile.read.filter.basic.Filter;
import org.apache.iotdb.tsfile.read.filter.factory.FilterType;
import org.apache.iotdb.tsfile.read.filter.operator.Between;
@@ -30,7 +31,12 @@ import org.apache.iotdb.tsfile.read.filter.operator.LtEq;
import org.apache.iotdb.tsfile.read.filter.operator.NotEq;
import org.apache.iotdb.tsfile.read.filter.operator.NotFilter;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
import java.util.Set;
+import java.util.stream.Collectors;
public class TimeFilter {
@@ -77,6 +83,24 @@ public class TimeFilter {
private TimeBetween(long value1, long value2, boolean not) {
super(value1, value2, FilterType.TIME_FILTER, not);
}
+
+ @Override
+ public List<TimeRange> getTimeRanges() {
+ long left = (long) value1;
+ long right = (long) value2;
+ if (not) {
+ List<TimeRange> res = new ArrayList<>();
+ if (left != Long.MIN_VALUE) {
+ res.add(new TimeRange(Long.MIN_VALUE, left - 1));
+ }
+ if (right != Long.MAX_VALUE) {
+ res.add(new TimeRange(right + 1, Long.MAX_VALUE));
+ }
+ return res;
+ } else {
+ return Collections.singletonList(new TimeRange(left, right));
+ }
+ }
}
public static class TimeIn extends In {
@@ -84,6 +108,18 @@ public class TimeFilter {
private TimeIn(Set<Long> values, boolean not) {
super(values, FilterType.TIME_FILTER, not);
}
+
+ @Override
+ public List<TimeRange> getTimeRanges() {
+ return ((Set<Long>) values)
+ .stream()
+ .map(
+ l -> {
+ long time = l;
+ return new TimeRange(time, time);
+ })
+ .collect(Collectors.toList());
+ }
}
public static class TimeEq extends Eq {
@@ -91,6 +127,11 @@ public class TimeFilter {
private TimeEq(long value) {
super(value, FilterType.TIME_FILTER);
}
+
+ @Override
+ public List<TimeRange> getTimeRanges() {
+ return Collections.singletonList(new TimeRange((long) value, (long) value));
+ }
}
public static class TimeNotEq extends NotEq {
@@ -98,6 +139,19 @@ public class TimeFilter {
private TimeNotEq(long value) {
super(value, FilterType.TIME_FILTER);
}
+
+ @Override
+ public List<TimeRange> getTimeRanges() {
+ long time = (long) value;
+ if (time == Long.MIN_VALUE) {
+ return Collections.singletonList(new TimeRange(time + 1, Long.MAX_VALUE));
+ } else if (time == Long.MAX_VALUE) {
+ return Collections.singletonList(new TimeRange(Long.MIN_VALUE, time - 1));
+ } else {
+ return Arrays.asList(
+ new TimeRange(Long.MIN_VALUE, time - 1), new TimeRange(time + 1, Long.MAX_VALUE));
+ }
+ }
}
public static class TimeGt extends Gt {
@@ -105,6 +159,16 @@ public class TimeFilter {
private TimeGt(long value) {
super(value, FilterType.TIME_FILTER);
}
+
+ @Override
+ public List<TimeRange> getTimeRanges() {
+ long left = (long) value;
+ if (left != Long.MAX_VALUE) {
+ return Collections.singletonList(new TimeRange(left + 1, Long.MAX_VALUE));
+ } else {
+ return Collections.emptyList();
+ }
+ }
}
public static class TimeGtEq extends GtEq {
@@ -112,6 +176,11 @@ public class TimeFilter {
private TimeGtEq(long value) {
super(value, FilterType.TIME_FILTER);
}
+
+ @Override
+ public List<TimeRange> getTimeRanges() {
+ return Collections.singletonList(new TimeRange((long) value, Long.MAX_VALUE));
+ }
}
public static class TimeLt extends Lt {
@@ -119,6 +188,16 @@ public class TimeFilter {
private TimeLt(long value) {
super(value, FilterType.TIME_FILTER);
}
+
+ @Override
+ public List<TimeRange> getTimeRanges() {
+ long right = (long) value;
+ if (right != Long.MIN_VALUE) {
+ return Collections.singletonList(new TimeRange(Long.MIN_VALUE, right - 1));
+ } else {
+ return Collections.emptyList();
+ }
+ }
}
public static class TimeLtEq extends LtEq {
@@ -126,6 +205,11 @@ public class TimeFilter {
private TimeLtEq(long value) {
super(value, FilterType.TIME_FILTER);
}
+
+ @Override
+ public List<TimeRange> getTimeRanges() {
+ return Collections.singletonList(new TimeRange(Long.MIN_VALUE, (long) value));
+ }
}
public static class TimeNotFilter extends NotFilter {
diff --git a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/basic/Filter.java b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/basic/Filter.java
index 4fb987b3a2..dc0d479c83 100755
--- a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/basic/Filter.java
+++ b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/basic/Filter.java
@@ -19,11 +19,14 @@
package org.apache.iotdb.tsfile.read.filter.basic;
import org.apache.iotdb.tsfile.file.metadata.statistics.Statistics;
+import org.apache.iotdb.tsfile.read.common.TimeRange;
import org.apache.iotdb.tsfile.read.filter.factory.FilterSerializeId;
import java.io.ByteArrayOutputStream;
import java.io.DataOutputStream;
import java.nio.ByteBuffer;
+import java.util.Collections;
+import java.util.List;
/** Filter is a top level filter abstraction. */
public interface Filter {
@@ -73,4 +76,8 @@ public interface Filter {
void deserialize(ByteBuffer buffer);
FilterSerializeId getSerializeId();
+
+ default List<TimeRange> getTimeRanges() {
+ return Collections.emptyList();
+ }
}
diff --git a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/operator/AndFilter.java b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/operator/AndFilter.java
index 9fe6a6036b..6c5120a3f7 100755
--- a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/operator/AndFilter.java
+++ b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/operator/AndFilter.java
@@ -19,10 +19,14 @@
package org.apache.iotdb.tsfile.read.filter.operator;
import org.apache.iotdb.tsfile.file.metadata.statistics.Statistics;
+import org.apache.iotdb.tsfile.read.common.TimeRange;
import org.apache.iotdb.tsfile.read.filter.basic.BinaryFilter;
import org.apache.iotdb.tsfile.read.filter.basic.Filter;
import org.apache.iotdb.tsfile.read.filter.factory.FilterSerializeId;
+import java.util.ArrayList;
+import java.util.List;
+
/** Both the left and right operators of AndExpression must satisfy the condition. */
public class AndFilter extends BinaryFilter {
@@ -70,4 +74,40 @@ public class AndFilter extends BinaryFilter {
public FilterSerializeId getSerializeId() {
return FilterSerializeId.AND;
}
+
+ @Override
+ public List<TimeRange> getTimeRanges() {
+ List<TimeRange> result = new ArrayList<>();
+ List<TimeRange> leftTimeRanges = left.getTimeRanges();
+ List<TimeRange> rightTimeRanges = right.getTimeRanges();
+
+ int leftIndex = 0,
+ rightIndex = 0,
+ leftSize = leftTimeRanges.size(),
+ rightSize = rightTimeRanges.size();
+ while (leftIndex < leftSize && rightIndex < rightSize) {
+ TimeRange leftRange = leftTimeRanges.get(leftIndex);
+ TimeRange rightRange = rightTimeRanges.get(rightIndex);
+
+ if (leftRange.getMax() < rightRange.getMin()) {
+ leftIndex++;
+ } else if (rightRange.getMax() < leftRange.getMin()) {
+ rightIndex++;
+ } else {
+ TimeRange intersection =
+ new TimeRange(
+ Math.max(leftRange.getMin(), rightRange.getMin()),
+ Math.min(leftRange.getMax(), rightRange.getMax()));
+ result.add(intersection);
+ if (leftRange.getMax() <= intersection.getMax()) {
+ leftIndex++;
+ }
+ if (rightRange.getMax() <= intersection.getMax()) {
+ rightIndex++;
+ }
+ }
+ }
+
+ return result;
+ }
}
diff --git a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/operator/NotFilter.java b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/operator/NotFilter.java
index 5ed24a6308..cd983dc329 100755
--- a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/operator/NotFilter.java
+++ b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/operator/NotFilter.java
@@ -19,6 +19,7 @@
package org.apache.iotdb.tsfile.read.filter.operator;
import org.apache.iotdb.tsfile.file.metadata.statistics.Statistics;
+import org.apache.iotdb.tsfile.read.common.TimeRange;
import org.apache.iotdb.tsfile.read.filter.basic.Filter;
import org.apache.iotdb.tsfile.read.filter.factory.FilterFactory;
import org.apache.iotdb.tsfile.read.filter.factory.FilterSerializeId;
@@ -27,6 +28,8 @@ import java.io.DataOutputStream;
import java.io.IOException;
import java.io.Serializable;
import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.List;
import java.util.Objects;
/** NotFilter necessary. Use InvertExpressionVisitor */
@@ -112,4 +115,28 @@ public class NotFilter implements Filter, Serializable {
public int hashCode() {
return Objects.hash(that);
}
+
+ @Override
+ public List<TimeRange> getTimeRanges() {
+ List<TimeRange> list = that.getTimeRanges();
+ if (list.isEmpty()) {
+ return list;
+ }
+ List<TimeRange> res = new ArrayList<>();
+ if (list.get(0).getMin() != Long.MIN_VALUE) {
+ res.add(new TimeRange(Long.MIN_VALUE, list.get(0).getMin() - 1));
+ }
+ for (int i = 1, size = list.size(); i < size; i++) {
+ long left = list.get(i - 1).getMax() + 1;
+ long right = list.get(i).getMin() - 1;
+ if (left <= right) {
+ res.add(new TimeRange(left, right));
+ }
+ }
+
+ if (list.get(list.size() - 1).getMax() != Long.MAX_VALUE) {
+ res.add(new TimeRange(list.get(list.size() - 1).getMax() + 1, Long.MAX_VALUE));
+ }
+ return res;
+ }
}
diff --git a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/operator/OrFilter.java b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/operator/OrFilter.java
index 32e4593651..17b0935510 100755
--- a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/operator/OrFilter.java
+++ b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/filter/operator/OrFilter.java
@@ -19,11 +19,15 @@
package org.apache.iotdb.tsfile.read.filter.operator;
import org.apache.iotdb.tsfile.file.metadata.statistics.Statistics;
+import org.apache.iotdb.tsfile.read.common.TimeRange;
import org.apache.iotdb.tsfile.read.filter.basic.BinaryFilter;
import org.apache.iotdb.tsfile.read.filter.basic.Filter;
import org.apache.iotdb.tsfile.read.filter.factory.FilterSerializeId;
import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
/** Either of the left and right operators of AndExpression must satisfy the condition. */
public class OrFilter extends BinaryFilter implements Serializable {
@@ -72,4 +76,66 @@ public class OrFilter extends BinaryFilter implements Serializable {
public FilterSerializeId getSerializeId() {
return FilterSerializeId.OR;
}
+
+ @Override
+ public List<TimeRange> getTimeRanges() {
+ List<TimeRange> result = new ArrayList<>();
+ List<TimeRange> leftTimeRanges = left.getTimeRanges();
+ List<TimeRange> rightTimeRanges = right.getTimeRanges();
+
+ int leftIndex = 0,
+ rightIndex = 0,
+ leftSize = leftTimeRanges.size(),
+ rightSize = rightTimeRanges.size();
+ TimeRange range;
+ if (leftTimeRanges.isEmpty() && rightTimeRanges.isEmpty()) {
+ return Collections.emptyList();
+ } else if (leftTimeRanges.isEmpty()) {
+ return rightTimeRanges;
+ } else if (rightTimeRanges.isEmpty()) {
+ return leftTimeRanges;
+ } else {
+ TimeRange leftRange = leftTimeRanges.get(leftIndex);
+ TimeRange rightRange = rightTimeRanges.get(rightIndex);
+ if (leftRange.getMin() <= rightRange.getMin()) {
+ range = leftRange;
+ leftIndex++;
+ } else {
+ range = rightRange;
+ rightIndex++;
+ }
+ }
+
+ while (leftIndex < leftSize || rightIndex < rightSize) {
+ TimeRange chosenRange;
+ if (leftIndex < leftSize && rightIndex < rightSize) {
+ TimeRange leftRange = leftTimeRanges.get(leftIndex);
+ TimeRange rightRange = rightTimeRanges.get(rightIndex);
+ if (leftRange.getMin() <= rightRange.getMin()) {
+ chosenRange = leftRange;
+ leftIndex++;
+ } else {
+ chosenRange = rightRange;
+ rightIndex++;
+ }
+ } else if (leftIndex < leftSize) {
+ chosenRange = leftTimeRanges.get(leftIndex);
+ leftIndex++;
+ } else {
+ chosenRange = rightTimeRanges.get(rightIndex);
+ rightIndex++;
+ }
+
+ if (chosenRange.getMin() > range.getMax()) {
+ result.add(range);
+ range = chosenRange;
+ } else {
+ range.setMax(Math.max(range.getMax(), chosenRange.getMax()));
+ }
+ }
+
+ result.add(range);
+
+ return result;
+ }
}