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


##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/ParallelizeGrouping.java:
##########
@@ -166,19 +202,23 @@ public PlanNode visitGroup(GroupNode node, Context 
context) {
             false);
       }
 
-      checkPrefixMatch(
-          context, node.getOrderingScheme().getOrderBy().subList(0, 
node.getPartitionKeyCount()));
+      // Decide the group's own fate first: the claim it makes to its 
ancestors depends on
+      // whether it survives as a partitioned group or degrades to one 
globally ordered sort.
       Context newContext = new Context(node.getOrderingScheme(), 
node.getPartitionKeyCount());
       PlanNode child = node.getChild().accept(this, newContext);
-      switch (newContext.canOptimized) {
-        case ENABLE_PARALLEL:
-          GroupNode newNode = (GroupNode) node.clone();
-          newNode.addChild(child);
-          return newNode;
-        case TO_SORT:
-        default:
-          return new SortNode(node.getPlanNodeId(), child, 
node.getOrderingScheme(), false, false);
+      if (newContext.canOptimized == ENABLE_PARALLEL) {
+        // The group survives and its output is only per-instance partitioned. 
When the ancestor's
+        // claim cannot reuse it, TO_SORT is recorded on its context and the 
ancestor sorts this
+        // group's output itself.
+        checkPartitionKeysMatch(
+            context, node.getOrderingScheme().getOrderBy().subList(0, 
node.getPartitionKeyCount()));
+        GroupNode newNode = (GroupNode) node.clone();
+        newNode.addChild(child);
+        return newNode;
       }
+      // The group degrades to a sort, so its output is one stream ordered by 
the full scheme.
+      checkPrefixMatch(context, node.getOrderingScheme().getOrderBy());

Review Comment:
   This branch tells the ancestor that the degraded group is "one stream 
ordered by the full scheme". That stops being true in distribution planning 
when the consumer is a `RowNumberNode` or `TopKRankingNode`: 
`TableDistributedPlanGenerator.visitRowNumber` and `visitTopKRanking` drop a 
`SortNode` child with `node.setChild(((SortNode) node.getChild()).getChild())` 
(around L3759 and L3825). `RowNumber` then emits rows in input order, and 
`TopKRanking` emits groups in the order it first sees them. An outer strict 
prefix therefore still runs as a `GroupNode` (`TableStreamSortOperator`) over 
unclustered input.
   
   Repro on the `t2` from `IoTDBWindowTVFRegionsIT` (one device, 6000 rows, 4 
DataRegions), PR head:
   
   ```sql
   SELECT s1, cnt, count(*) AS n, max(rn) AS mrn FROM (
     SELECT s1, rn, count(*) OVER (PARTITION BY s1) AS cnt FROM (
       SELECT s1, s3, row_number() OVER (PARTITION BY s1, s3) AS rn FROM t2))
   GROUP BY s1, cnt ORDER BY s1, cnt
   ```
   
   Expected 3 rows (`0,1980,1980,1`, `1,2013,2013,1`, `2,2007,2007,1`). Actual: 
18 rows. Each `s1` comes back as 6 separate partitions of 265-384 rows. The 
merge base returns the same 18 rows. The plan is `WindowFunction(s1) > 
GroupNode[s1] > Project > RowNumber(s1, s3) > DeviceTableScan`; the `Sort` 
below `RowNumber` is gone.
   
   The `TopKRanking` form fails the same way. I gave `t2` an extra INT32 field 
`s2`, filled with a second pseudo-random value in 0..4. On both the PR and the 
merge base, this returns 20 rows instead of 3:
   
   ```sql
   SELECT s1, cnt, count(*) AS n, count(s2) AS c2, count(s3) AS c3 FROM (
     SELECT s1, s2, s3, count(*) OVER (PARTITION BY s1) AS cnt FROM (
       SELECT s1, s2, s3 FROM (
         SELECT s1, s2, s3, row_number() OVER (PARTITION BY s1, s3 ORDER BY s2) 
AS rn FROM t2)
       WHERE rn <= 1))
   GROUP BY s1, cnt ORDER BY s1, cnt
   ```
   
   The plan is `WindowFunction(s1) > GroupNode[s1] > Project > TopKRanking(s1, 
s3) > DeviceTableScan`. When the input spans several regions, a `Collect` ends 
up under the ranking node and `groupingInvalidatedByCollect` happens to catch 
both shapes. When the input comes from a single region (here: one device), 
nothing does. (Variants that order by `time` keep a pruning `Project` between 
the `Filter` and the `Window`. They stay a `Window` over a kept `Sort`, and are 
correct.)
   
   Suggestion: treat `RowNumberNode` and `TopKRankingNode` like table functions 
and pattern recognition. Add `visitRowNumber` / `visitTopKRanking` that call 
`checkPartitionKeysMatch(context, node.getPartitionBy())`, so the ancestor's 
context never reaches a `SortNode` that will be dropped. I also checked one 
case that is correct today: outer keys that extend into `TopKRanking`'s ORDER 
BY (`PARTITION BY (s1, s2)` over `PARTITION BY s1 ORDER BY s2`), because groups 
are drained in rank order. That case could stay allowed.



##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/ParallelizeGrouping.java:
##########
@@ -120,17 +134,13 @@ public PlanNode visitUnion(UnionNode node, Context 
context) {
     }
 
     /**
-     * We need to make sure: context#partitionKey can be satisfied by the 
prefix of childOrder.
+     * Whether the child's single ordered stream satisfies the required 
partition prefix.
      *
-     * <p>When the child exposes exactly the partition keys, the prefix is 
compared as a column set:
-     * partition columns are identified by their values, so a different 
writing order still produces
-     * the same partitions. This lets nested set-semantic table functions 
reuse their input
-     * clustering when the same PARTITION BY columns are listed in a different 
order. The set
-     * comparison is deliberately limited to this case: for a strict subset 
the child's partitions
-     * are only a refinement of the required ones, and after a fan-in over 
unordered sources
-     * (multiple DataRegions, hash aggregation) the subset need not be 
contiguous in the input.
-     *
-     * <p>Otherwise the prefix is compared positionally, as before.
+     * <p>Used when the child reports a globally sorted stream ({@link 
SortNode}, {@link
+     * StreamSortNode}, {@link TopKNode}). Such a stream is clustered by every 
prefix of its sort
+     * keys, so the prefix matches positionally. A permutation of the same key 
set also matches:

Review Comment:
   This says a permutation of the same key set also matches, but `sameKeySet` 
below only accepts it when `partitionKeyCount == childOrder.size()`. The 
degraded-group branch now passes the full ordering (partition keys + ORDER BY 
keys), so a reordered key set over an inner window with an ORDER BY no longer 
matches.
   
   Example: `count(s1) OVER (PARTITION BY tag2, tag1)` over `sum(s1) OVER 
(PARTITION BY tag1, tag2 ORDER BY time)` was `WindowFunction > GroupNode[tag2, 
tag1] > MergeSort` on the base. It is now `WindowFunction > Sort > MergeSort`, 
an extra full sort. In one sorted stream, any permutation of the first `k` sort 
keys is clustered. Comparing `ImmutableSet.copyOf(requiredPrefix)` with 
`ImmutableSet.copyOf(childOrder.subList(0, k))` would be correct and would also 
match this Javadoc.



##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/ParallelizeGrouping.java:
##########
@@ -310,13 +350,26 @@ public PlanNode visitDeviceTableScan(DeviceTableScanNode 
node, Context context)
 
     @Override
     public PlanNode visitAggregation(AggregationNode node, Context context) {
-      checkPrefixMatch(context, node.getGroupingKeys());
+      if (!context.canSkip()) {
+        if (node.getPreGroupedSymbols().isEmpty()) {
+          // A hash aggregation's output is not clustered by its grouping keys.

Review Comment:
   A completed aggregation emits each full grouping key exactly once, whether 
it hashed its input or not. So when the required keys are exactly the grouping 
keys, every partition is a single row and is trivially clustered. 
`TableDistributedPlanGenerator.groupingInvalidatedByCollect` already relies on 
this ("A completed aggregation emits each full grouping key once, even when it 
hashes its input.", around L2209). Only strict subsets need `TO_SORT`, and 
`checkPartitionKeysMatch` already rejects those.
   
   As written, `SESSION(DATA => (SELECT s1, s2, max(time) AS time FROM table1 
GROUP BY s1, s2) PARTITION BY (s1, s2) ...)` goes from `TableFunctionProcessor 
> GroupNode[s1, s2] > Aggregation` on the base to `TableFunctionProcessor > 
Sort > Aggregation`, which buffers and fully sorts the aggregation output. I'd 
drop the `getPreGroupedSymbols().isEmpty()` branch (here and in 
`visitAggregationTableScan`) and keep only `checkPartitionKeysMatch`. The 
logical `preGroupedSymbols` is not final anyway: the distributed 
`visitAggregation` can still clear it.



##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/ParallelizeGrouping.java:
##########
@@ -310,13 +350,26 @@ public PlanNode visitDeviceTableScan(DeviceTableScanNode 
node, Context context)
 
     @Override
     public PlanNode visitAggregation(AggregationNode node, Context context) {
-      checkPrefixMatch(context, node.getGroupingKeys());
+      if (!context.canSkip()) {
+        if (node.getPreGroupedSymbols().isEmpty()) {
+          // A hash aggregation's output is not clustered by its grouping keys.
+          context.canOptimized = TO_SORT;
+        } else {
+          checkPartitionKeysMatch(context, node.getGroupingKeys());
+        }
+      }
       return visitPlan(node, context);
     }
 
     @Override
     public PlanNode visitAggregationTableScan(AggregationTableScanNode node, 
Context context) {
-      checkPrefixMatch(context, node.getGroupingKeys());
+      if (!context.canSkip()) {
+        if (node.getPreGroupedSymbols().isEmpty()) {
+          context.canOptimized = TO_SORT;
+        } else {
+          checkPartitionKeysMatch(context, node.getGroupingKeys());

Review Comment:
   Requiring the exact key set here (and in `visitAggregation` and the 
surviving-group branch) also rejects the strict prefixes that #19207 lists as 
safe: prefixes that still contain every TAG column. Such a partition cannot 
span devices, so it cannot span regions, and each region's stream is already 
ordered by device.
   
   The most visible case is a per-device window over time-bucketed aggregates. 
With 12 devices over 4 DataRegions (TAG columns `a`, `b`):
   
   ```sql
   SELECT a, b, h, m, lag(m) OVER (PARTITION BY a, b ORDER BY h) AS prev
   FROM (SELECT a, b, date_bin(1h, time) AS h, avg(s1) AS m FROM tm GROUP BY a, 
b, date_bin(1h, time))
   ```
   
   On the merge base, EXPLAIN shows one `WindowFunction` per region directly 
over its `AggregationTableScan`, with only a `Collect` on the coordinator. With 
this PR there is a single `WindowFunction` on the coordinator over a 
`MergeSort`, and the regions only scan. The results are the same, but this 
shape is very common: aggregate per device and time bucket, then apply a 
window, FORECAST or MATCH_RECOGNIZE. PlanTester shows the same loss for 
`count(s1) OVER (PARTITION BY tag1, tag2, tag3)` over `max(s1) OVER (PARTITION 
BY tag1, tag2, tag3, attr1)`: the outer window moves from the region fragments 
to a single instance.
   
   For `AggregationTableScanNode`, I think also accepting 
`ImmutableSet.copyOf(requiredKeys).equals(ImmutableSet.copyOf(node.getPreGroupedSymbols()))`
 would keep this case. Each region's output is ordered by the pre-grouped keys, 
which include every TAG whenever the scan runs per region. `AggregationNode` 
needs more care, because the distributed `visitAggregation` can still drop its 
pre-grouping. More generally, the decision needs the bottom-up property 
described in #19207. One sorted stream allows any prefix. Per-instance 
clustering allows the full key set, and also subsets that still contain every 
TAG when each instance is ordered by device.



##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/ParallelizeGrouping.java:
##########
@@ -73,10 +73,24 @@
  *     <li>GroupNode[PK={tag1,tag2}, OK={s1}] -> 
TopKNode[sort={tag1,tag2,tag3}]
  *     <li>GroupNode[PK={tag1,tag2}, OK={}] -> 
AggregationNode[group={tag1,tag2}]
  *     <li>GroupNode[PK={tag1,tag2}, OK={s1}] -> 
AggregationNode[group={tag1,tag2,s1}]

Review Comment:
   After this change, `GroupNode[PK={tag1,tag2}, OK={s1}] -> 
AggregationNode[group={tag1,tag2,s1}]` is no longer parallelized. 
`checkPartitionKeysMatch` requires the exact grouping key set, so this shape 
now becomes a `SortNode`; in PlanTester, `PARTITION BY tag1, tag2, tag3` over 
`GROUP BY tag1, tag2, tag3, s1` plans as `WindowFunction > Sort > Aggregation`. 
Please update or remove this example so the list matches the new rules.



##########
iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/analyzer/TableFunctionTest.java:
##########
@@ -323,6 +328,70 @@ public void 
testNestedSetSemanticReorderedSubsetFallsBackToSort() {
         sort(orderBy("tag2", "tag1", "time"), tableFunctionProcessor(inner, 
scanAllColumns())));
   }
 
+  @Test
+  public void testNestedSetSemanticSameOrderPrefixFallsBackToSort() {
+    PlanTester planTester = new PlanTester();
+    String sql =
+        "SELECT * FROM SESSION(DATA => (SELECT * FROM SESSION(DATA => table1 "
+            + "PARTITION BY (tag1, tag2, tag3) ORDER BY time, GAP => 1m)) "
+            + "PARTITION BY (tag1, tag2) ORDER BY time, GAP => 2m)";
+    planTester.createPlan(sql);
+    Consumer<TableFunctionProcessorMatcher.Builder> outer =
+        sessionMatcher("window_start", "window_end", 120_000L);
+    Consumer<TableFunctionProcessorMatcher.Builder> inner =
+        sessionMatcher("window_start_0", "window_end_1", 60_000L);
+    // A strict prefix in the same order has the same problem as a reordered 
one: one outer
+    // partition can span several inner ones, which a fan-in does not keep 
contiguous.
+    assertPlan(
+        planTester.getFragmentPlan(0),
+        output(
+            tableFunctionProcessor(
+                outer,
+                mergeSort(orderBy("tag1", "tag2", "time"), exchange(), 
exchange(), exchange()))));
+    assertPlan(
+        planTester.getFragmentPlan(1),
+        sort(orderBy("tag1", "tag2", "time"), tableFunctionProcessor(inner, 
scanAllColumns())));
+  }
+
+  @Test
+  public void testSessionOverGroupByPrefixFallsBackToSort() {
+    PlanTester planTester = new PlanTester();
+    String sql =
+        "SELECT * FROM SESSION(DATA => (SELECT tag1, tag2, tag3, max(time) AS 
time FROM table1 "
+            + "GROUP BY tag1, tag2, tag3) PARTITION BY (tag1, tag2) ORDER BY 
time, GAP => 1m)";
+    LogicalQueryPlan logicalPlan = planTester.createPlan(sql);
+    // A grouping is only clustered per instance; a strict prefix of the 
grouping keys must be
+    // re-sorted before one instance can consume it.
+    assertOuterFunctionDegradedToSort(logicalPlan);
+  }
+
+  @Test
+  public void testSessionOverHashAggregationFallsBackToSort() {
+    PlanTester planTester = new PlanTester();
+    // s1 and s2 are fields, so the aggregation cannot stream and hashes its 
input instead.
+    String sql =
+        "SELECT * FROM SESSION(DATA => (SELECT s1, s2, max(time) AS time FROM 
table1 "
+            + "GROUP BY s1, s2) PARTITION BY (s1, s2) ORDER BY time, GAP => 
1m)";
+    LogicalQueryPlan logicalPlan = planTester.createPlan(sql);
+    // The grouping keys are exactly the partition keys, but a hash 
aggregation's output is not

Review Comment:
   The reasoning here doesn't hold. Every row of a completed aggregation has a 
distinct grouping key, so with the partition keys equal to the grouping keys 
each partition is one row. The input is then clustered whether or not the 
aggregation hashed it (see `groupingInvalidatedByCollect` in 
`TableDistributedPlanGenerator`). As written, this test locks in an extra full 
sort. If the hash branch is dropped, I'd change this test to assert that the 
group is kept. A strict-subset variant (`PARTITION BY (s1)` over `GROUP BY s1, 
s2`) can stay as the case that must sort.



##########
integration-test/src/test/java/org/apache/iotdb/relational/it/db/it/IoTDBWindowTVFRegionsIT.java:
##########
@@ -86,6 +88,125 @@ private static void insertData() {
     }
   }
 
+  private static void insertHashAggregationData() {
+    try (Connection connection = EnvFactory.getEnv().getTableConnection();
+        Statement statement = connection.createStatement()) {
+      statement.execute("USE " + DATABASE_NAME);
+      statement.execute("CREATE TABLE t2(d STRING TAG, s1 INT32 FIELD, s3 
INT32 FIELD)");
+      for (int start = 0; start < HASH_AGGREGATION_ROW_NUM; start += 1000) {
+        StringBuilder sql = new StringBuilder("INSERT INTO t2(time, d, s1, s3) 
VALUES ");
+        for (int row = start; row < start + 1000; row++) {
+          // Pseudo-random s1 in {0, 1, 2}; s3 is unique.
+          int s1 = (int) ((((long) row * 0x9E3779B1L) & 0xFFFFFFFFL) >> 20) % 
3;
+          if (row > start) {
+            sql.append(", ");
+          }
+          sql.append('(')
+              .append(row + 1)
+              .append(", 'd1', ")
+              .append(s1)
+              .append(", ")
+              .append(row)
+              .append(')');
+        }
+        statement.execute(sql.toString());
+      }
+      statement.execute("FLUSH");
+    } catch (Exception e) {
+      e.printStackTrace();
+      fail(String.valueOf(e.getMessage()));
+    }
+  }
+
+  @Test
+  public void testSameOrderPrefixPartitionStaysSingleInstance() {
+    // The outer PARTITION BY (a, b) is a strict prefix of the inner one. One 
outer partition still
+    // spans every DataRegion, so the outer SESSION must stay single-instance.
+    tableResultSetEqualTest(
+        "SELECT window_start, window_end, count(*) AS cnt FROM SESSION(DATA => 
("
+            + "    SELECT window_start AS inner_start, window_end AS 
inner_end, time, a, b, c, s1 "
+            + "    FROM SESSION(DATA => t PARTITION BY (a, b, c) ORDER BY 
time, GAP => 1ms)"
+            + ") PARTITION BY (a, b) ORDER BY time, GAP => 100ms) "
+            + "GROUP BY window_start, window_end ORDER BY window_start",
+        new String[] {"window_start", "window_end", "cnt"},
+        new String[] {"1970-01-01T00:00:00.001Z,1970-01-01T00:00:00.040Z,40,"},
+        DATABASE_NAME);
+  }
+
+  @Test
+  public void testSameOrderPrefixWindowPartitionStaysSingleInstance() {
+    tableResultSetEqualTest(
+        "SELECT max(cnt) AS max_cnt, min(cnt) AS min_cnt FROM ("
+            + "    SELECT count(s1) OVER (PARTITION BY a, b) AS cnt "
+            + "    FROM SESSION(DATA => t PARTITION BY (a, b, c) ORDER BY 
time, GAP => 1ms))",
+        new String[] {"max_cnt", "min_cnt"},
+        new String[] {"40,40,"},
+        DATABASE_NAME);
+  }
+
+  @Test
+  public void testHashAggregationWindowKeepsPartitionsWhole() {
+    // A hash aggregation's output is not clustered by its grouping keys. The 
window on top must
+    // see every (s1, s3) row of a partition together, not blocks with mixed 
s1 values.
+    tableResultSetEqualTest(
+        "SELECT s1, cnt, count(*) AS n FROM ("
+            + "    SELECT s1, count(*) OVER (PARTITION BY s1) AS cnt "
+            + "    FROM (SELECT s1, s3 FROM t2 GROUP BY s1, s3)) "
+            + "GROUP BY s1, cnt ORDER BY s1, cnt",
+        new String[] {"s1", "cnt", "n"},
+        new String[] {"0,1980,1980,", "1,2013,2013,", "2,2007,2007,"},
+        DATABASE_NAME);
+  }
+
+  @Test
+  public void testHashAggregationSessionKeepsPartitionsWhole() {
+    tableResultSetEqualTest(
+        "SELECT s1, window_start, window_end, count(*) AS cnt FROM 
SESSION(DATA => ("
+            + "    SELECT s1, s3, max(time) AS time FROM t2 GROUP BY s1, s3"
+            + ") PARTITION BY (s1) ORDER BY time, GAP => 100000ms) "
+            + "GROUP BY s1, window_start, window_end ORDER BY s1, 
window_start",
+        new String[] {"s1", "window_start", "window_end", "cnt"},
+        new String[] {
+          "0,1970-01-01T00:00:00.001Z,1970-01-01T00:00:05.997Z,1980,",
+          "1,1970-01-01T00:00:00.005Z,1970-01-01T00:00:05.999Z,2013,",
+          "2,1970-01-01T00:00:00.002Z,1970-01-01T00:00:06.000Z,2007,"
+        },
+        DATABASE_NAME);
+  }
+
+  @Test
+  public void testSameOrderPrefixTopKRankingStaysSingleInstance() {

Review Comment:
   The new tests only check one direction: "must fall back to a sort". Two gaps:
   
   - The shapes from the comment on `ParallelizeGrouping` L220 are not covered. 
An outer `PARTITION BY s1` over `row_number() OVER (PARTITION BY s1, s3)`, with 
or without `ORDER BY ... WHERE rn <= 1`, still returns wrong results on this 
`t2`.
   - Nothing pins the safe cases that should keep their parallelism or their 
streaming group. One example would be a distributed-plan assertion for a window 
`PARTITION BY` all TAG columns over `GROUP BY` all TAG columns + `date_bin`.
   
   Without these, the regressions described on L370, L355 and L141 pass CI 
unnoticed.



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