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


##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/process/InsertTabletStatementGenerator.java:
##########
@@ -157,6 +161,64 @@ protected void processColumn(
         .write(sourceTypeConvertor, valueColumn, rowIndex, columns, rowCount);
   }
 
+  /**
+   * The storage layer assumes the rows of a tablet are sorted by time: the 
sequence/unsequence
+   * classification, the time boundaries of the tsfile resource, the ttl 
check, the time partition
+   * routing and the last value composition all rely on it. The child operator 
of an {@code INSERT
+   * INTO ... SELECT} does not guarantee that order, so restore it before the 
tablet leaves the
+   * engine.
+   */
+  private void sortRowsByTimeIfNeeded() {
+    boolean sorted = true;
+    for (int i = 1; i < rowCount; i++) {
+      if (times[i] < times[i - 1]) {
+        sorted = false;
+        break;
+      }
+    }
+    if (sorted) {
+      return;
+    }
+
+    Integer[] order = new Integer[rowCount];
+    for (int i = 0; i < rowCount; i++) {
+      order[i] = i;
+    }
+    // stable, so rows sharing a timestamp keep their relative order
+    Arrays.sort(order, Comparator.comparingLong(index -> times[index]));
+
+    int[] permutation = new int[rowCount];
+    long[] sortedTimes = new long[rowCount];
+    for (int i = 0; i < rowCount; i++) {
+      permutation[i] = order[i];
+      sortedTimes[i] = times[order[i]];
+    }
+    times = sortedTimes;
+    for (int i = 0; i < columns.length; i++) {
+      columns[i] = permuteColumn(columns[i], permutation);
+      bitMaps[i] = permuteBitMap(bitMaps[i], permutation);
+    }
+  }
+
+  private Object permuteColumn(Object column, int[] permutation) {
+    int length = Array.getLength(column);
+    Object sortedColumn = 
Array.newInstance(column.getClass().getComponentType(), length);
+    for (int i = 0; i < length; i++) {
+      Array.set(sortedColumn, i, Array.get(column, permutation[i]));

Review Comment:
   `Array.get` / `Array.set` box every primitive element and make a native call 
per element, so the unsorted path is much more expensive than it needs to be. 
Measured `constructInsertTabletStatement()` on the PR head (10,000-row batch, 
full-batch path):
   
   | columns | already sorted | unsorted (this PR) | same algorithm, typed copy 
loops |
   |---|---|---|---|
   | 1 tag + 10 DOUBLE | 0.004 ms | 14.0 ms | 0.56 ms |
   | 1 tag + 50 DOUBLE | 0.004 ms | 64.0 ms | 2.19 ms |
   
   The sort runs synchronously on the INTO operator's driver thread before the 
write is submitted, so it doesn't overlap with the write, and every batch 
coming from `ORDER BY time DESC`, a join, or a multi-device table scan takes 
this path.
   
   Could the copy switch on the column's `TSDataType` and use typed loops 
instead? The `Integer[]` index sort itself is cheap (the typed variant above 
still uses it); the reflective copy dominates. If you also want to drop the 
boxing, `Session#sortedIndex` has a stable primitive merge sort with a fast 
path for strictly descending input.



##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/process/InsertTabletStatementGenerator.java:
##########
@@ -157,6 +161,64 @@ protected void processColumn(
         .write(sourceTypeConvertor, valueColumn, rowIndex, columns, rowCount);
   }
 
+  /**
+   * The storage layer assumes the rows of a tablet are sorted by time: the 
sequence/unsequence
+   * classification, the time boundaries of the tsfile resource, the ttl 
check, the time partition
+   * routing and the last value composition all rely on it. The child operator 
of an {@code INSERT
+   * INTO ... SELECT} does not guarantee that order, so restore it before the 
tablet leaves the
+   * engine.
+   */
+  private void sortRowsByTimeIfNeeded() {
+    boolean sorted = true;
+    for (int i = 1; i < rowCount; i++) {
+      if (times[i] < times[i - 1]) {
+        sorted = false;
+        break;
+      }
+    }
+    if (sorted) {
+      return;
+    }
+
+    Integer[] order = new Integer[rowCount];
+    for (int i = 0; i < rowCount; i++) {
+      order[i] = i;
+    }
+    // stable, so rows sharing a timestamp keep their relative order
+    Arrays.sort(order, Comparator.comparingLong(index -> times[index]));

Review Comment:
   For the table model one generator covers the whole target table, so a tablet 
usually holds several devices. The child operator emits them grouped by device, 
each device already in ascending time order, which is what the storage layer 
actually relies on: `split`, the device time index and the last cache all work 
per device range. A global stable sort by time interleaves those devices, so 
`splitByDevice` goes from one segment per device to up to one segment per row.
   
   `DataRegion#insertTablet` alone, 10,000-row relational tablets, 
device-grouped (what master writes) vs. time-interleaved (what this PR writes):
   
   | devices × rows per device | device segments | grouped | interleaved |
   |---|---|---|---|
   | 1000 × 10 | 1000 → 10000 | 2.4 ms | 6.8–7.9 ms |
   | 100 × 100 | 100 → 10000 | 1.45 ms | 6.06 ms |
   | 10 × 1000 | 10 → 10000 | 1.22 ms | 5.6 ms |
   
   The coordinator side (`collectSplitRanges` / `generateOneSplitList`) and 
`updateLastCache` also scale with the number of segments and are not included 
above. Downsampling statements such as `INSERT INTO agg SELECT date_bin(1h, 
time), tag, avg(s) FROM src GROUP BY 1, tag` hit this on every batch.
   
   If the goal is only the out-of-order rows of a single device, sorting only 
when some device's rows go backwards (or sorting by `(device, time)`) would 
keep the grouping. There is a trade-off worth spelling out, though. From 
reading the code (not verified with a test), two consumers depend on a globally 
sorted tablet:
   
   - `PipeInsertNodeTabletInsertionEvent#mayEventTimeOverlappedWithTimeRange` 
only looks at the first and last timestamps.
   - The relational TTL check marks expired rows individually, but 
`splitAndInsert` writes with `noFailure = true`, which passes `null` results to 
the memtable, so those rows are not skipped.
   
   Both look wrong on master for device-grouped tablets, and the global sort 
happens to fix them. Could the PR either keep the device grouping and handle 
those two consumers, or keep the global sort and call out the extra write cost?



##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/process/InsertTabletStatementGenerator.java:
##########
@@ -157,6 +161,64 @@ protected void processColumn(
         .write(sourceTypeConvertor, valueColumn, rowIndex, columns, rowCount);
   }
 
+  /**
+   * The storage layer assumes the rows of a tablet are sorted by time: the 
sequence/unsequence
+   * classification, the time boundaries of the tsfile resource, the ttl 
check, the time partition
+   * routing and the last value composition all rely on it. The child operator 
of an {@code INSERT
+   * INTO ... SELECT} does not guarantee that order, so restore it before the 
tablet leaves the
+   * engine.
+   */
+  private void sortRowsByTimeIfNeeded() {

Review Comment:
   The datanode already has this: `new 
PipeTableModelTabletEventSorter(statement).sortByTimestampIfNecessary()` (used 
by `PipeTransferTabletRawReqV2`) does the same sortedness check, a stable sort 
by time, and a typed reorder of the values and bitmaps, including the handling 
of how DATE columns are stored. Could this reuse it, or move the core of 
`PipeInsertEventSorter` into a shared utility so the query engine doesn't 
depend on the pipe package? Otherwise the two copies have to stay consistent on 
stability, bitmaps and DATE columns.



##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/DataRegion.java:
##########
@@ -1368,17 +1379,17 @@ private void split(
         before = loc;
         beforeTimePartition = timePartitionId;
         isSequence = time > lastFlushTime;
-      } else if (!isSequence) {
+      } else if (!isSequence || !timeOrdered) {

Review Comment:
   This branch only moves rows that are not newer than the last flushed time 
into the unsequence space. Rows that are all newer than it, but out of order 
among themselves, still land in one sequence range, and 
`TsFileProcessor#insertTablet` takes the device start time from the first row 
of each range, so the file's time index is still wrong.
   
   Reproduced on the PR head: write 10..39 for a device and close the file 
(last flushed time 39), then write the unsorted tablet `[100, 50]` and close 
again. The second sequence file is indexed `[100, 100]` while its chunk 
statistics are `[50, 100]` with 2 points, and no unsequence file is created. A 
query with `WHERE time <= 60` is then pruned by the resource time index and 
misses the row at 50.
   
   Not every ingress sorts before reaching this point: the REST handlers 
(`StatementConstructionHandler` under `rest/protocol/table/v1` and 
`rest/protocol/v2`) and MQTT (`MPPPublishHandler`) build the 
`InsertTabletStatement` as received. For those paths the TTL prefix, the 
forward-only partition detection in `collectSplitRanges` / 
`getTimePartitionSlots`, and the last-row last cache are unchanged as well. So 
"Fixing it in the storage layer covers every ingress" in the description 
doesn't quite hold, and the description still lists sorting as an alternative 
not taken, while a later commit sorts in the generator.
   
   Would it be simpler to do the O(n) sortedness check, and the sort when 
needed, once at a common point for every `InsertTabletStatement` (e.g. during 
analysis, before the time partition slots are computed)? That would cover INTO, 
REST and MQTT in one place, and this branch could remain a safety net.



##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/execution/operator/process/InsertTabletStatementGenerator.java:
##########
@@ -112,6 +114,8 @@ public InsertTabletStatement 
constructInsertTabletStatement() {
       }
     }
 
+    sortRowsByTimeIfNeeded();

Review Comment:
   Minor: when `rowCount != rowLimit`, the arrays are first truncated by the 
copy above, and `sortRowsByTimeIfNeeded()` then allocates every column again. 
While an unsorted batch is sorted, two copies of the times, columns and bitmaps 
are alive, plus the boxed `Integer[]` index and the `int[]` / `long[]` buffers. 
None of that is in `ramBytesUsed()`, and the row limit derived from 
`into_operation_buffer_size_in_byte` assumes a single copy. For wide tables, 
applying the permutation while truncating would do both in one copy.



##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/storageengine/dataregion/DataRegion.java:
##########
@@ -1368,17 +1379,17 @@ private void split(
         before = loc;
         beforeTimePartition = timePartitionId;
         isSequence = time > lastFlushTime;
-      } else if (!isSequence) {
+      } else if (!isSequence || !timeOrdered) {
         lastFlushTime = getLastFlushTime(timePartitionId, 
insertTabletNode.getDeviceID(loc));
-        if (time > lastFlushTime) {
-          // the same partition and switch to sequence data
-          // insert previous range into unsequence
-          updateSplitInfo(splitInfo, beforeTimePartition, false, new int[] 
{before, loc});
+        boolean rowIsSequence = time > lastFlushTime;

Review Comment:
   Minor: once `timeOrdered` is false, every remaining row calls 
`getLastFlushTime(...)` (a `HashMap<Long, …>` lookup with boxing plus a device 
lookup) under the write lock. `split` is called per device range and the 
partition only changes in the first branch, so the value is constant until the 
partition changes. It could be looked up once per partition and reused, which 
would also help the existing `!isSequence` prefix. This only affects unsorted 
input.



##########
integration-test/src/test/java/org/apache/iotdb/relational/it/insertquery/IoTDBInsertQueryIT.java:
##########
@@ -87,7 +87,11 @@ public static void setUpClass() {
         .getConfig()
         .getCommonConfig()
         .setPartitionInterval(1000)
-        .setMemtableSizeThreshold(10000);
+        .setMemtableSizeThreshold(10000)
+        // The out-of-order tablet test needs a sequence file with several 
pages: when the earlier
+        // file only has one page, the read side merges the overlapping page 
before the earlier
+        // pages are emitted and the wrong order is masked.
+        .setMaxNumberOfPointsInPage(10);

Review Comment:
   The 10-point page is only needed so this test can fail on the unfixed code, 
but the cluster is shared, so `testSimple` and the other existing tests in this 
class now also run with 10-point pages, which changes their storage layout and 
coverage. Would a separate IT class for the new test be better, or a comment 
explaining why the whole class needs this setting?



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