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]