You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iotdb.apache.org by qi...@apache.org on 2022/10/06 09:30:37 UTC
[iotdb] branch master updated: [IOTDB-4504] Add BackwardSort algorithm for disordered time series (#7410)
This is an automated email from the ASF dual-hosted git repository.
qiaojialin pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/iotdb.git
The following commit(s) were added to refs/heads/master by this push:
new 4643cc548a [IOTDB-4504] Add BackwardSort algorithm for disordered time series (#7410)
4643cc548a is described below
commit 4643cc548a3c0bad147bf039cb1cafca721d1458
Author: Little Health <39...@users.noreply.github.com>
AuthorDate: Thu Oct 6 17:30:31 2022 +0800
[IOTDB-4504] Add BackwardSort algorithm for disordered time series (#7410)
---
.../db/utils/datastructure/AlignedTVList.java | 40 +++++-
.../db/utils/datastructure/BackAlignedTVList.java | 93 ++++++++++++++
.../db/utils/datastructure/BackBinaryTVList.java | 90 ++++++++++++++
.../db/utils/datastructure/BackBooleanTVList.java | 89 ++++++++++++++
.../db/utils/datastructure/BackDoubleTVList.java | 89 ++++++++++++++
.../db/utils/datastructure/BackFloatTVList.java | 89 ++++++++++++++
.../db/utils/datastructure/BackIntTVList.java | 90 ++++++++++++++
.../db/utils/datastructure/BackLongTVList.java | 89 ++++++++++++++
.../iotdb/db/utils/datastructure/BackwardSort.java | 134 +++++++++++++++++++++
.../iotdb/db/utils/datastructure/BinaryTVList.java | 10 +-
.../db/utils/datastructure/BooleanTVList.java | 10 +-
.../iotdb/db/utils/datastructure/DoubleTVList.java | 10 +-
.../iotdb/db/utils/datastructure/FloatTVList.java | 10 +-
.../iotdb/db/utils/datastructure/IntTVList.java | 10 +-
.../iotdb/db/utils/datastructure/LongTVList.java | 10 +-
.../db/utils/datastructure/TimAlignedTVList.java | 32 -----
16 files changed, 842 insertions(+), 53 deletions(-)
diff --git a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/AlignedTVList.java b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/AlignedTVList.java
index 39cdabb43e..fff6a1cec6 100644
--- a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/AlignedTVList.java
+++ b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/AlignedTVList.java
@@ -89,10 +89,44 @@ public abstract class AlignedTVList extends TVList {
}
public static AlignedTVList newAlignedList(List<TSDataType> dataTypes) {
- if (TVLIST_SORT_ALGORITHM == TVListSortAlgorithm.QUICK) {
- return new QuickAlignedTVList(dataTypes);
+ switch (TVLIST_SORT_ALGORITHM) {
+ case QUICK:
+ return new QuickAlignedTVList(dataTypes);
+ case BACKWARD:
+ return new BackAlignedTVList(dataTypes);
+ default:
+ return new TimAlignedTVList(dataTypes);
+ }
+ }
+
+ @Override
+ public TVList getTvListByColumnIndex(List<Integer> columnIndex, List<TSDataType> dataTypeList) {
+ List<List<Object>> values = new ArrayList<>();
+ List<List<BitMap>> bitMaps = null;
+ for (int i = 0; i < columnIndex.size(); i++) {
+ // columnIndex == -1 means querying a non-exist column, add null column here
+ if (columnIndex.get(i) == -1) {
+ values.add(null);
+ } else {
+ values.add(this.values.get(columnIndex.get(i)));
+ if (this.bitMaps != null && this.bitMaps.get(columnIndex.get(i)) != null) {
+ if (bitMaps == null) {
+ bitMaps = new ArrayList<>(columnIndex.size());
+ for (int j = 0; j < columnIndex.size(); j++) {
+ bitMaps.add(null);
+ }
+ }
+ bitMaps.set(i, this.bitMaps.get(columnIndex.get(i)));
+ }
+ }
}
- return new TimAlignedTVList(dataTypes);
+ AlignedTVList alignedTvList = AlignedTVList.newAlignedList(dataTypeList);
+ alignedTvList.timestamps = this.timestamps;
+ alignedTvList.indices = this.indices;
+ alignedTvList.values = values;
+ alignedTvList.bitMaps = bitMaps;
+ alignedTvList.rowCount = this.rowCount;
+ return alignedTvList;
}
@Override
diff --git a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackAlignedTVList.java b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackAlignedTVList.java
new file mode 100644
index 0000000000..3b9e03c162
--- /dev/null
+++ b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackAlignedTVList.java
@@ -0,0 +1,93 @@
+/*
+ * 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.utils.datastructure;
+
+import org.apache.iotdb.db.rescon.PrimitiveArrayManager;
+import org.apache.iotdb.tsfile.file.metadata.enums.TSDataType;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import static org.apache.iotdb.db.rescon.PrimitiveArrayManager.ARRAY_SIZE;
+
+public class BackAlignedTVList extends QuickAlignedTVList implements BackwardSort {
+ private final List<long[]> tmpTimestamps = new ArrayList<>();
+ private final List<int[]> tmpIndices = new ArrayList<>();
+ private int tmpLength = 0;
+
+ BackAlignedTVList(List<TSDataType> types) {
+ super(types);
+ }
+
+ @Override
+ public void sort() {
+ if (!sorted) {
+ backwardSort(timestamps, rowCount);
+ clearTmp();
+ }
+ sorted = true;
+ }
+
+ @Override
+ public void setFromTmp(int src, int dest) {
+ set(
+ dest,
+ tmpTimestamps.get(src / ARRAY_SIZE)[src % ARRAY_SIZE],
+ tmpIndices.get(src / ARRAY_SIZE)[src % ARRAY_SIZE]);
+ }
+
+ @Override
+ public void setToTmp(int src, int dest) {
+ tmpTimestamps.get(dest / ARRAY_SIZE)[dest % ARRAY_SIZE] = getTime(src);
+ tmpIndices.get(dest / ARRAY_SIZE)[dest % ARRAY_SIZE] = getValueIndex(src);
+ }
+
+ @Override
+ public void backward_set(int src, int dest) {
+ set(src, dest);
+ }
+
+ @Override
+ public int compareTmp(int idx, int tmpIdx) {
+ long t1 = getTime(idx);
+ long t2 = tmpTimestamps.get(tmpIdx / ARRAY_SIZE)[tmpIdx % ARRAY_SIZE];
+ return Long.compare(t1, t2);
+ }
+
+ @Override
+ public void checkTmpLength(int len) {
+ while (len > tmpLength) {
+ tmpTimestamps.add((long[]) getPrimitiveArraysByType(TSDataType.INT64));
+ tmpIndices.add((int[]) getPrimitiveArraysByType(TSDataType.INT32));
+ tmpLength += ARRAY_SIZE;
+ }
+ }
+
+ @Override
+ public void clearTmp() {
+ for (long[] dataArray : tmpTimestamps) {
+ PrimitiveArrayManager.release(dataArray);
+ }
+ tmpTimestamps.clear();
+ for (int[] dataArray : tmpIndices) {
+ PrimitiveArrayManager.release(dataArray);
+ }
+ tmpIndices.clear();
+ }
+}
diff --git a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackBinaryTVList.java b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackBinaryTVList.java
new file mode 100644
index 0000000000..270dfa0a14
--- /dev/null
+++ b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackBinaryTVList.java
@@ -0,0 +1,90 @@
+/*
+ * 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.utils.datastructure;
+
+import org.apache.iotdb.db.rescon.PrimitiveArrayManager;
+import org.apache.iotdb.tsfile.file.metadata.enums.TSDataType;
+import org.apache.iotdb.tsfile.utils.Binary;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import static org.apache.iotdb.db.rescon.PrimitiveArrayManager.ARRAY_SIZE;
+
+public class BackBinaryTVList extends QuickBinaryTVList implements BackwardSort {
+ private final List<long[]> tmpTimestamps = new ArrayList<>();
+ private final List<Binary[]> tmpValues = new ArrayList<>();
+ private int tmpLength = 0;
+
+ @Override
+ public void sort() {
+ if (!sorted) {
+ backwardSort(timestamps, rowCount);
+ clearTmp();
+ }
+ sorted = true;
+ }
+
+ @Override
+ public void setFromTmp(int src, int dest) {
+ set(
+ dest,
+ tmpTimestamps.get(src / ARRAY_SIZE)[src % ARRAY_SIZE],
+ tmpValues.get(src / ARRAY_SIZE)[src % ARRAY_SIZE]);
+ }
+
+ @Override
+ public void setToTmp(int src, int dest) {
+ tmpTimestamps.get(dest / ARRAY_SIZE)[dest % ARRAY_SIZE] = getTime(src);
+ tmpValues.get(dest / ARRAY_SIZE)[dest % ARRAY_SIZE] = getBinary(src);
+ }
+
+ @Override
+ public void backward_set(int src, int dest) {
+ set(src, dest);
+ }
+
+ @Override
+ public int compareTmp(int idx, int tmpIdx) {
+ long t1 = getTime(idx);
+ long t2 = tmpTimestamps.get(tmpIdx / ARRAY_SIZE)[tmpIdx % ARRAY_SIZE];
+ return Long.compare(t1, t2);
+ }
+
+ @Override
+ public void checkTmpLength(int len) {
+ while (len > tmpLength) {
+ tmpTimestamps.add((long[]) getPrimitiveArraysByType(TSDataType.INT64));
+ tmpValues.add((Binary[]) getPrimitiveArraysByType(TSDataType.TEXT));
+ tmpLength += ARRAY_SIZE;
+ }
+ }
+
+ @Override
+ public void clearTmp() {
+ for (long[] dataArray : tmpTimestamps) {
+ PrimitiveArrayManager.release(dataArray);
+ }
+ tmpTimestamps.clear();
+ for (Binary[] dataArray : tmpValues) {
+ PrimitiveArrayManager.release(dataArray);
+ }
+ tmpValues.clear();
+ }
+}
diff --git a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackBooleanTVList.java b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackBooleanTVList.java
new file mode 100644
index 0000000000..6453ddbcbf
--- /dev/null
+++ b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackBooleanTVList.java
@@ -0,0 +1,89 @@
+/*
+ * 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.utils.datastructure;
+
+import org.apache.iotdb.db.rescon.PrimitiveArrayManager;
+import org.apache.iotdb.tsfile.file.metadata.enums.TSDataType;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import static org.apache.iotdb.db.rescon.PrimitiveArrayManager.ARRAY_SIZE;
+
+public class BackBooleanTVList extends QuickBooleanTVList implements BackwardSort {
+ private final List<long[]> tmpTimestamps = new ArrayList<>();
+ private final List<boolean[]> tmpValues = new ArrayList<>();
+ private int tmpLength = 0;
+
+ @Override
+ public void sort() {
+ if (!sorted) {
+ backwardSort(timestamps, rowCount);
+ clearTmp();
+ }
+ sorted = true;
+ }
+
+ @Override
+ public void setFromTmp(int src, int dest) {
+ set(
+ dest,
+ tmpTimestamps.get(src / ARRAY_SIZE)[src % ARRAY_SIZE],
+ tmpValues.get(src / ARRAY_SIZE)[src % ARRAY_SIZE]);
+ }
+
+ @Override
+ public void setToTmp(int src, int dest) {
+ tmpTimestamps.get(dest / ARRAY_SIZE)[dest % ARRAY_SIZE] = getTime(src);
+ tmpValues.get(dest / ARRAY_SIZE)[dest % ARRAY_SIZE] = getBoolean(src);
+ }
+
+ @Override
+ public void backward_set(int src, int dest) {
+ set(src, dest);
+ }
+
+ @Override
+ public int compareTmp(int idx, int tmpIdx) {
+ long t1 = getTime(idx);
+ long t2 = tmpTimestamps.get(tmpIdx / ARRAY_SIZE)[tmpIdx % ARRAY_SIZE];
+ return Long.compare(t1, t2);
+ }
+
+ @Override
+ public void checkTmpLength(int len) {
+ while (len > tmpLength) {
+ tmpTimestamps.add((long[]) getPrimitiveArraysByType(TSDataType.INT64));
+ tmpValues.add((boolean[]) getPrimitiveArraysByType(TSDataType.BOOLEAN));
+ tmpLength += ARRAY_SIZE;
+ }
+ }
+
+ @Override
+ public void clearTmp() {
+ for (long[] dataArray : tmpTimestamps) {
+ PrimitiveArrayManager.release(dataArray);
+ }
+ tmpTimestamps.clear();
+ for (boolean[] dataArray : tmpValues) {
+ PrimitiveArrayManager.release(dataArray);
+ }
+ tmpValues.clear();
+ }
+}
diff --git a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackDoubleTVList.java b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackDoubleTVList.java
new file mode 100644
index 0000000000..f2154b425f
--- /dev/null
+++ b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackDoubleTVList.java
@@ -0,0 +1,89 @@
+/*
+ * 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.utils.datastructure;
+
+import org.apache.iotdb.db.rescon.PrimitiveArrayManager;
+import org.apache.iotdb.tsfile.file.metadata.enums.TSDataType;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import static org.apache.iotdb.db.rescon.PrimitiveArrayManager.ARRAY_SIZE;
+
+public class BackDoubleTVList extends QuickDoubleTVList implements BackwardSort {
+ private final List<long[]> tmpTimestamps = new ArrayList<>();
+ private final List<double[]> tmpValues = new ArrayList<>();
+ private int tmpLength = 0;
+
+ @Override
+ public void sort() {
+ if (!sorted) {
+ backwardSort(timestamps, rowCount);
+ clearTmp();
+ }
+ sorted = true;
+ }
+
+ @Override
+ public void setFromTmp(int src, int dest) {
+ set(
+ dest,
+ tmpTimestamps.get(src / ARRAY_SIZE)[src % ARRAY_SIZE],
+ tmpValues.get(src / ARRAY_SIZE)[src % ARRAY_SIZE]);
+ }
+
+ @Override
+ public void setToTmp(int src, int dest) {
+ tmpTimestamps.get(dest / ARRAY_SIZE)[dest % ARRAY_SIZE] = getTime(src);
+ tmpValues.get(dest / ARRAY_SIZE)[dest % ARRAY_SIZE] = getDouble(src);
+ }
+
+ @Override
+ public void backward_set(int src, int dest) {
+ set(src, dest);
+ }
+
+ @Override
+ public int compareTmp(int idx, int tmpIdx) {
+ long t1 = getTime(idx);
+ long t2 = tmpTimestamps.get(tmpIdx / ARRAY_SIZE)[tmpIdx % ARRAY_SIZE];
+ return Long.compare(t1, t2);
+ }
+
+ @Override
+ public void checkTmpLength(int len) {
+ while (len > tmpLength) {
+ tmpTimestamps.add((long[]) getPrimitiveArraysByType(TSDataType.INT64));
+ tmpValues.add((double[]) getPrimitiveArraysByType(TSDataType.DOUBLE));
+ tmpLength += ARRAY_SIZE;
+ }
+ }
+
+ @Override
+ public void clearTmp() {
+ for (long[] dataArray : tmpTimestamps) {
+ PrimitiveArrayManager.release(dataArray);
+ }
+ tmpTimestamps.clear();
+ for (double[] dataArray : tmpValues) {
+ PrimitiveArrayManager.release(dataArray);
+ }
+ tmpValues.clear();
+ }
+}
diff --git a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackFloatTVList.java b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackFloatTVList.java
new file mode 100644
index 0000000000..6788fded03
--- /dev/null
+++ b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackFloatTVList.java
@@ -0,0 +1,89 @@
+/*
+ * 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.utils.datastructure;
+
+import org.apache.iotdb.db.rescon.PrimitiveArrayManager;
+import org.apache.iotdb.tsfile.file.metadata.enums.TSDataType;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import static org.apache.iotdb.db.rescon.PrimitiveArrayManager.ARRAY_SIZE;
+
+public class BackFloatTVList extends QuickFloatTVList implements BackwardSort {
+ private final List<long[]> tmpTimestamps = new ArrayList<>();
+ private final List<float[]> tmpValues = new ArrayList<>();
+ private int tmpLength = 0;
+
+ @Override
+ public void sort() {
+ if (!sorted) {
+ backwardSort(timestamps, rowCount);
+ clearTmp();
+ }
+ sorted = true;
+ }
+
+ @Override
+ public void setFromTmp(int src, int dest) {
+ set(
+ dest,
+ tmpTimestamps.get(src / ARRAY_SIZE)[src % ARRAY_SIZE],
+ tmpValues.get(src / ARRAY_SIZE)[src % ARRAY_SIZE]);
+ }
+
+ @Override
+ public void setToTmp(int src, int dest) {
+ tmpTimestamps.get(dest / ARRAY_SIZE)[dest % ARRAY_SIZE] = getTime(src);
+ tmpValues.get(dest / ARRAY_SIZE)[dest % ARRAY_SIZE] = getFloat(src);
+ }
+
+ @Override
+ public void backward_set(int src, int dest) {
+ set(src, dest);
+ }
+
+ @Override
+ public int compareTmp(int idx, int tmpIdx) {
+ long t1 = getTime(idx);
+ long t2 = tmpTimestamps.get(tmpIdx / ARRAY_SIZE)[tmpIdx % ARRAY_SIZE];
+ return Long.compare(t1, t2);
+ }
+
+ @Override
+ public void checkTmpLength(int len) {
+ while (len > tmpLength) {
+ tmpTimestamps.add((long[]) getPrimitiveArraysByType(TSDataType.INT64));
+ tmpValues.add((float[]) getPrimitiveArraysByType(TSDataType.FLOAT));
+ tmpLength += ARRAY_SIZE;
+ }
+ }
+
+ @Override
+ public void clearTmp() {
+ for (long[] dataArray : tmpTimestamps) {
+ PrimitiveArrayManager.release(dataArray);
+ }
+ tmpTimestamps.clear();
+ for (float[] dataArray : tmpValues) {
+ PrimitiveArrayManager.release(dataArray);
+ }
+ tmpValues.clear();
+ }
+}
diff --git a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackIntTVList.java b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackIntTVList.java
new file mode 100644
index 0000000000..68ec6e8158
--- /dev/null
+++ b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackIntTVList.java
@@ -0,0 +1,90 @@
+/*
+ * 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.utils.datastructure;
+
+import org.apache.iotdb.db.rescon.PrimitiveArrayManager;
+import org.apache.iotdb.tsfile.file.metadata.enums.TSDataType;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import static org.apache.iotdb.db.rescon.PrimitiveArrayManager.ARRAY_SIZE;
+
+public class BackIntTVList extends QuickIntTVList implements BackwardSort {
+
+ private final List<long[]> tmpTimestamps = new ArrayList<>();
+ private final List<int[]> tmpValues = new ArrayList<>();
+ private int tmpLength = 0;
+
+ @Override
+ public void sort() {
+ if (!sorted) {
+ backwardSort(timestamps, rowCount);
+ clearTmp();
+ }
+ sorted = true;
+ }
+
+ @Override
+ public void setFromTmp(int src, int dest) {
+ set(
+ dest,
+ tmpTimestamps.get(src / ARRAY_SIZE)[src % ARRAY_SIZE],
+ tmpValues.get(src / ARRAY_SIZE)[src % ARRAY_SIZE]);
+ }
+
+ @Override
+ public void setToTmp(int src, int dest) {
+ tmpTimestamps.get(dest / ARRAY_SIZE)[dest % ARRAY_SIZE] = getTime(src);
+ tmpValues.get(dest / ARRAY_SIZE)[dest % ARRAY_SIZE] = getInt(src);
+ }
+
+ @Override
+ public void backward_set(int src, int dest) {
+ set(src, dest);
+ }
+
+ @Override
+ public int compareTmp(int idx, int tmpIdx) {
+ long t1 = getTime(idx);
+ long t2 = tmpTimestamps.get(tmpIdx / ARRAY_SIZE)[tmpIdx % ARRAY_SIZE];
+ return Long.compare(t1, t2);
+ }
+
+ @Override
+ public void checkTmpLength(int len) {
+ while (len > tmpLength) {
+ tmpTimestamps.add((long[]) getPrimitiveArraysByType(TSDataType.INT64));
+ tmpValues.add((int[]) getPrimitiveArraysByType(TSDataType.INT32));
+ tmpLength += ARRAY_SIZE;
+ }
+ }
+
+ @Override
+ public void clearTmp() {
+ for (long[] dataArray : tmpTimestamps) {
+ PrimitiveArrayManager.release(dataArray);
+ }
+ tmpTimestamps.clear();
+ for (int[] dataArray : tmpValues) {
+ PrimitiveArrayManager.release(dataArray);
+ }
+ tmpValues.clear();
+ }
+}
diff --git a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackLongTVList.java b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackLongTVList.java
new file mode 100644
index 0000000000..5a3b4e2319
--- /dev/null
+++ b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackLongTVList.java
@@ -0,0 +1,89 @@
+/*
+ * 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.utils.datastructure;
+
+import org.apache.iotdb.db.rescon.PrimitiveArrayManager;
+import org.apache.iotdb.tsfile.file.metadata.enums.TSDataType;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import static org.apache.iotdb.db.rescon.PrimitiveArrayManager.ARRAY_SIZE;
+
+public class BackLongTVList extends QuickLongTVList implements BackwardSort {
+ private final List<long[]> tmpTimestamps = new ArrayList<>();
+ private final List<long[]> tmpValues = new ArrayList<>();
+ private int tmpLength = 0;
+
+ @Override
+ public void sort() {
+ if (!sorted) {
+ backwardSort(timestamps, rowCount);
+ clearTmp();
+ }
+ sorted = true;
+ }
+
+ @Override
+ public void setFromTmp(int src, int dest) {
+ set(
+ dest,
+ tmpTimestamps.get(src / ARRAY_SIZE)[src % ARRAY_SIZE],
+ tmpValues.get(src / ARRAY_SIZE)[src % ARRAY_SIZE]);
+ }
+
+ @Override
+ public void setToTmp(int src, int dest) {
+ tmpTimestamps.get(dest / ARRAY_SIZE)[dest % ARRAY_SIZE] = getTime(src);
+ tmpValues.get(dest / ARRAY_SIZE)[dest % ARRAY_SIZE] = getLong(src);
+ }
+
+ @Override
+ public void backward_set(int src, int dest) {
+ set(src, dest);
+ }
+
+ @Override
+ public int compareTmp(int idx, int tmpIdx) {
+ long t1 = getTime(idx);
+ long t2 = tmpTimestamps.get(tmpIdx / ARRAY_SIZE)[tmpIdx % ARRAY_SIZE];
+ return Long.compare(t1, t2);
+ }
+
+ @Override
+ public void checkTmpLength(int len) {
+ while (len > tmpLength) {
+ tmpTimestamps.add((long[]) getPrimitiveArraysByType(TSDataType.INT64));
+ tmpValues.add((long[]) getPrimitiveArraysByType(TSDataType.INT64));
+ tmpLength += ARRAY_SIZE;
+ }
+ }
+
+ @Override
+ public void clearTmp() {
+ for (long[] dataArray : tmpTimestamps) {
+ PrimitiveArrayManager.release(dataArray);
+ }
+ tmpTimestamps.clear();
+ for (long[] dataArray : tmpValues) {
+ PrimitiveArrayManager.release(dataArray);
+ }
+ tmpValues.clear();
+ }
+}
diff --git a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackwardSort.java b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackwardSort.java
new file mode 100644
index 0000000000..84d227d6e7
--- /dev/null
+++ b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BackwardSort.java
@@ -0,0 +1,134 @@
+/*
+ * 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.utils.datastructure;
+
+import java.util.List;
+
+import static org.apache.iotdb.db.rescon.PrimitiveArrayManager.ARRAY_SIZE;
+
+public interface BackwardSort extends QuickSort {
+
+ double INVERSION_RATIOS_THRESHOLD = 0.004;
+
+ void setFromTmp(int src, int dest);
+
+ void setToTmp(int src, int dest);
+
+ void backward_set(int src, int dest);
+
+ int compareTmp(int idx, int tmpIdx);
+
+ void checkTmpLength(int len);
+
+ void clearTmp();
+
+ default void backwardSort(List<long[]> timestamps, int rowCount) {
+ int block_size = setBlockLength(timestamps, 1);
+ // System.out.printf("rowCount=%d, block_size=%d\n",rowCount, block_size);
+ int B = rowCount / block_size + 1;
+ sortBlock((B - 1) * block_size, rowCount - 1);
+ for (int i = B - 2; i >= 0; i--) {
+ int lo = i * block_size, hi = lo + block_size - 1;
+ sortBlock(lo, hi);
+ backwardMergeBlocks(lo, hi, rowCount);
+ }
+ }
+
+ /**
+ * check block-inversions to find the proper block_size, which is a multiple of array_size. For
+ * totally ordered, the block_size will equals to array_size For totally reverse ordered, the
+ * block_size will equals to the rowCount. INVERSION_RATIOS_THRESHOLD=0.005 is a empiric value.
+ *
+ * @param timestamps
+ * @param step
+ * @return
+ */
+ default int setBlockLength(List<long[]> timestamps, int step) {
+ double overlap = 0;
+ long last_time = timestamps.get(0)[0];
+ int i = step, blocks = 0;
+ while (i < timestamps.size()) {
+ long cur_time = timestamps.get(i)[0];
+ if (last_time > cur_time) {
+ overlap += 1;
+ }
+ last_time = cur_time;
+ i += step;
+ blocks += 1;
+ }
+ double ratio = overlap / blocks;
+ int mul = (int) Math.ceil(ratio / INVERSION_RATIOS_THRESHOLD);
+ // System.out.printf("Overlap ratio=%.4f mul=%d, step=%d\n", ratio, mul, step);
+ // ensure inversion ratio < INVERSION_RATIOS_THRESHOLD
+ if (mul <= 1) {
+ return step * ARRAY_SIZE;
+ }
+ return setBlockLength(timestamps, mul * step);
+ }
+
+ /**
+ * Backward merge the blocks to reduce repetitive moves.
+ *
+ * @param lo
+ * @param hi
+ * @param rowCount
+ */
+ default void backwardMergeBlocks(int lo, int hi, int rowCount) {
+ int overlapIdx = hi + 1;
+ while (overlapIdx < rowCount && compare(hi, overlapIdx) == 1) {
+ overlapIdx++;
+ }
+ if (overlapIdx == hi + 1) return;
+
+ int tmpIdx = 0;
+ int len = overlapIdx - hi;
+ checkTmpLength(len);
+ for (int i = hi + 1; i < overlapIdx; i++) {
+ setToTmp(i, tmpIdx);
+ tmpIdx++;
+ }
+
+ int a = hi, b = tmpIdx - 1, idx = overlapIdx - 1;
+ while (a >= lo && b >= 0) {
+ if (compareTmp(a, b) == 1) {
+ backward_set(a, idx);
+ a--;
+ } else {
+ setFromTmp(b, idx);
+ b--;
+ }
+ idx--;
+ }
+ while (b >= 0) {
+ setFromTmp(b, idx);
+ b--;
+ idx--;
+ }
+ }
+
+ /**
+ * TODO: optional sort algorithms by inversion rates and block_size
+ *
+ * @param lo
+ * @param hi
+ */
+ default void sortBlock(int lo, int hi) {
+ qsort(lo, hi);
+ }
+}
diff --git a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BinaryTVList.java b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BinaryTVList.java
index d5c7e24331..5b017e57d8 100644
--- a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BinaryTVList.java
+++ b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BinaryTVList.java
@@ -55,10 +55,14 @@ public abstract class BinaryTVList extends TVList {
}
public static BinaryTVList newList() {
- if (TVLIST_SORT_ALGORITHM == TVListSortAlgorithm.QUICK) {
- return new QuickBinaryTVList();
+ switch (TVLIST_SORT_ALGORITHM) {
+ case QUICK:
+ return new QuickBinaryTVList();
+ case BACKWARD:
+ return new BackBinaryTVList();
+ default:
+ return new TimBinaryTVList();
}
- return new TimBinaryTVList();
}
@Override
diff --git a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BooleanTVList.java b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BooleanTVList.java
index 3d7bc39f48..5e6f7ea366 100644
--- a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BooleanTVList.java
+++ b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/BooleanTVList.java
@@ -49,10 +49,14 @@ public abstract class BooleanTVList extends TVList {
}
public static BooleanTVList newList() {
- if (TVLIST_SORT_ALGORITHM == TVListSortAlgorithm.QUICK) {
- return new QuickBooleanTVList();
+ switch (TVLIST_SORT_ALGORITHM) {
+ case QUICK:
+ return new QuickBooleanTVList();
+ case BACKWARD:
+ return new BackBooleanTVList();
+ default:
+ return new TimBooleanTVList();
}
- return new TimBooleanTVList();
}
@Override
diff --git a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/DoubleTVList.java b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/DoubleTVList.java
index c3c6960812..41ae89264c 100644
--- a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/DoubleTVList.java
+++ b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/DoubleTVList.java
@@ -49,10 +49,14 @@ public abstract class DoubleTVList extends TVList {
}
public static DoubleTVList newList() {
- if (TVLIST_SORT_ALGORITHM == TVListSortAlgorithm.QUICK) {
- return new QuickDoubleTVList();
+ switch (TVLIST_SORT_ALGORITHM) {
+ case QUICK:
+ return new QuickDoubleTVList();
+ case BACKWARD:
+ return new BackDoubleTVList();
+ default:
+ return new TimDoubleTVList();
}
- return new TimDoubleTVList();
}
@Override
diff --git a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/FloatTVList.java b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/FloatTVList.java
index b88ee76b2e..05e2b4289e 100644
--- a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/FloatTVList.java
+++ b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/FloatTVList.java
@@ -49,10 +49,14 @@ public abstract class FloatTVList extends TVList {
}
public static FloatTVList newList() {
- if (TVLIST_SORT_ALGORITHM == TVListSortAlgorithm.QUICK) {
- return new QuickFloatTVList();
+ switch (TVLIST_SORT_ALGORITHM) {
+ case QUICK:
+ return new QuickFloatTVList();
+ case BACKWARD:
+ return new BackFloatTVList();
+ default:
+ return new TimFloatTVList();
}
- return new TimFloatTVList();
}
@Override
diff --git a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/IntTVList.java b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/IntTVList.java
index 4ad55d9452..9ea657755c 100644
--- a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/IntTVList.java
+++ b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/IntTVList.java
@@ -48,10 +48,14 @@ public abstract class IntTVList extends TVList {
}
public static IntTVList newList() {
- if (TVLIST_SORT_ALGORITHM == TVListSortAlgorithm.QUICK) {
- return new QuickIntTVList();
+ switch (TVLIST_SORT_ALGORITHM) {
+ case QUICK:
+ return new QuickIntTVList();
+ case BACKWARD:
+ return new BackIntTVList();
+ default:
+ return new TimIntTVList();
}
- return new TimIntTVList();
}
@Override
diff --git a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/LongTVList.java b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/LongTVList.java
index cbc69b3ce9..41ce036ab7 100644
--- a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/LongTVList.java
+++ b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/LongTVList.java
@@ -48,10 +48,14 @@ public abstract class LongTVList extends TVList {
}
public static LongTVList newList() {
- if (TVLIST_SORT_ALGORITHM == TVListSortAlgorithm.QUICK) {
- return new QuickLongTVList();
+ switch (TVLIST_SORT_ALGORITHM) {
+ case QUICK:
+ return new QuickLongTVList();
+ case BACKWARD:
+ return new BackLongTVList();
+ default:
+ return new TimLongTVList();
}
- return new TimLongTVList();
}
@Override
diff --git a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/TimAlignedTVList.java b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/TimAlignedTVList.java
index 8d6a075fec..1fc284f48f 100644
--- a/server/src/main/java/org/apache/iotdb/db/utils/datastructure/TimAlignedTVList.java
+++ b/server/src/main/java/org/apache/iotdb/db/utils/datastructure/TimAlignedTVList.java
@@ -20,9 +20,7 @@ package org.apache.iotdb.db.utils.datastructure;
import org.apache.iotdb.db.rescon.PrimitiveArrayManager;
import org.apache.iotdb.tsfile.file.metadata.enums.TSDataType;
-import org.apache.iotdb.tsfile.utils.BitMap;
-import java.util.ArrayList;
import java.util.List;
import static org.apache.iotdb.db.rescon.PrimitiveArrayManager.ARRAY_SIZE;
@@ -39,36 +37,6 @@ public class TimAlignedTVList extends AlignedTVList implements TimSort {
super(types);
}
- @Override
- public TVList getTvListByColumnIndex(List<Integer> columnIndex, List<TSDataType> dataTypeList) {
- List<List<Object>> values = new ArrayList<>();
- List<List<BitMap>> bitMaps = null;
- for (int i = 0; i < columnIndex.size(); i++) {
- // columnIndex == -1 means querying a non-exist column, add null column here
- if (columnIndex.get(i) == -1) {
- values.add(null);
- } else {
- values.add(this.values.get(columnIndex.get(i)));
- if (this.bitMaps != null && this.bitMaps.get(columnIndex.get(i)) != null) {
- if (bitMaps == null) {
- bitMaps = new ArrayList<>(columnIndex.size());
- for (int j = 0; j < columnIndex.size(); j++) {
- bitMaps.add(null);
- }
- }
- bitMaps.set(i, this.bitMaps.get(columnIndex.get(i)));
- }
- }
- }
- TimAlignedTVList alignedTvList = new TimAlignedTVList(dataTypeList);
- alignedTvList.timestamps = this.timestamps;
- alignedTvList.indices = this.indices;
- alignedTvList.values = values;
- alignedTvList.bitMaps = bitMaps;
- alignedTvList.rowCount = this.rowCount;
- return alignedTvList;
- }
-
@Override
public void sort() {
if (sortedTimestamps == null