ColinLeeo commented on code in PR #19035:
URL: https://github.com/apache/iotdb/pull/19035#discussion_r4478127007


##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/utils/sorter/InsertEventSorter.java:
##########
@@ -166,4 +168,57 @@ private int getLastNonnullIndex(
     }
     return index[lastNonnullIndex];
   }
+
+  /** Sort by time only, keeping the relative order of rows that share a 
timestamp. */
+  public void sortByTimestampIfNecessary() {
+    if (dataAdapter == null || dataAdapter.getRowSize() == 0) {
+      return;
+    }
+
+    final long[] timestamps = dataAdapter.getTimestamps();
+    final int rowSize = dataAdapter.getRowSize();
+    for (int i = 1; i < rowSize; ++i) {
+      if (timestamps[i] < timestamps[i - 1]) {
+        isSorted = false;
+        break;
+      }
+    }
+
+    if (isSorted) {
+      return;
+    }
+
+    index = new Integer[rowSize];
+    for (int i = 0; i < rowSize; i++) {
+      index[i] = i;
+    }
+    sortTimestamps();
+
+    deDuplicatedIndex = null;
+    deDuplicatedSize = rowSize;
+    sortAndMayDeduplicateValuesAndBitMaps();
+  }
+
+  /**
+   * The permutation the last sort applied: the row at position {@code i} came 
from row {@code
+   * permutation[i]} of the input. {@code null} when the rows were already in 
order and nothing was
+   * moved.
+   */
+  public int[] getRowPermutation() {
+    if (index == null) {
+      return null;
+    }
+    final int[] permutation = new int[index.length];
+    for (int i = 0; i < index.length; i++) {
+      permutation[i] = index[i];
+    }
+    return permutation;

Review Comment:
   `index` is an `Integer[]` (the stable sort needs a comparator over boxed 
values) while the permutation is an `int[]`, and 
`System.arraycopy`/`Arrays.copyOf` cannot unbox — `System.arraycopy` would 
throw `ArrayStoreException`. The loop performs the unboxing and only runs when 
a sort actually moved rows.
   
   



##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/utils/sorter/InsertEventSorter.java:
##########
@@ -166,4 +168,57 @@ private int getLastNonnullIndex(
     }
     return index[lastNonnullIndex];
   }
+
+  /** Sort by time only, keeping the relative order of rows that share a 
timestamp. */
+  public void sortByTimestampIfNecessary() {
+    if (dataAdapter == null || dataAdapter.getRowSize() == 0) {
+      return;
+    }
+
+    final long[] timestamps = dataAdapter.getTimestamps();
+    final int rowSize = dataAdapter.getRowSize();
+    for (int i = 1; i < rowSize; ++i) {
+      if (timestamps[i] < timestamps[i - 1]) {
+        isSorted = false;
+        break;
+      }
+    }
+
+    if (isSorted) {
+      return;
+    }
+
+    index = new Integer[rowSize];
+    for (int i = 0; i < rowSize; i++) {
+      index[i] = i;
+    }
+    sortTimestamps();
+
+    deDuplicatedIndex = null;
+    deDuplicatedSize = rowSize;
+    sortAndMayDeduplicateValuesAndBitMaps();
+  }
+
+  /**
+   * The permutation the last sort applied: the row at position {@code i} came 
from row {@code
+   * permutation[i]} of the input. {@code null} when the rows were already in 
order and nothing was
+   * moved.
+   */
+  public int[] getRowPermutation() {
+    if (index == null) {
+      return null;
+    }
+    final int[] permutation = new int[index.length];
+    for (int i = 0; i < index.length; i++) {
+      permutation[i] = index[i];
+    }
+    return permutation;
+  }
+
+  protected void sortTimestamps() {
+    // Index is sorted stably because it is Integer[]
+    Arrays.sort(this.index, 
Comparator.comparingLong(dataAdapter::getTimestamp));
+    final long[] timestamps = dataAdapter.getTimestamps();
+    Arrays.sort(timestamps, 0, dataAdapter.getRowSize());

Review Comment:
   Done in b4b58c0ca5: `sortTimestamps()` now rearranges the timestamps with 
the index it just computed (O(N)) instead of sorting them again (O(N log N)).
   



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

Reply via email to