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]