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


##########
iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/distribute/TableDistributedPlanGenerator.java:
##########
@@ -320,8 +324,113 @@ public List<PlanNode> visitInto(final IntoNode node, 
final PlanContext context)
   public List<PlanNode> visitFill(FillNode node, PlanContext context) {
     if (!(node instanceof ValueFillNode)) {
       context.clearExpectedOrderingScheme();
+      List<PlanNode> result = dealWithPlainSingleChildNode(node, context);
+      nodeOrderingMap.remove(node.getPlanNodeId());

Review Comment:
   **Perf regression: `ORDER BY <group keys>, time` over `FILL METHOD PREVIOUS 
| NEXT | LINEAR ... FILL_GROUP` now gets an extra blocking sort above the fill**
   
   The non-constant branch of `visitFill` now drops the fill's ordering 
unconditionally (this line). With `FILL_GROUP`, `QueryPlanner.fillGroup` 
already sorts the fill input by `(group keys, TIME_COLUMN)`, so on master an 
outer `ORDER BY <group keys>, time` is eliminated. With this PR it becomes a 
full `SortNode` in the root fragment, which buffers the whole result (and may 
spill) before emitting anything, for the common "fill per device, return per 
device" query:
   
   ```sql
   SELECT time, tag1, tag2, tag3, s1 FROM table1
   FILL METHOD PREVIOUS TIME_COLUMN 1 FILL_GROUP 2,3,4
   ORDER BY tag1, tag2, tag3, time
   ```
   
   ```text
   master (and with the change below)        this PR (20d7b00)
   Output                                    Output
     PreviousFill                              Sort [tag1, tag2, tag3, time]   
<-- new
       MergeSort [tag1, tag2, tag3, time]        PreviousFill
         DeviceTableScan x 3 regions               MergeSort [tag1, tag2, tag3, 
time]
                                                     DeviceTableScan x 3 regions
   ```
   
   Same pattern for these shapes (distributed plans from `PlanTester`, 3 
regions):
   
   | Shape | master | this PR | with the change below |
   |---|---|---|---|
   | `LINEAR TIME_COLUMN 1 FILL_GROUP 2,3,4` or `NEXT TIME_COLUMN 1 FILL_GROUP 
2,3,4`, `ORDER BY tag1, tag2, tag3, time` | no sort above the fill | + full 
Sort | as master |
   | `PREVIOUS TIME_BOUND 1h TIME_COLUMN 1 FILL_GROUP 2,3,4`, same `ORDER BY` | 
no sort above the fill | + full Sort | as master |
   | `PREVIOUS TIME_COLUMN 1 FILL_GROUP 2,3,4 ORDER BY tag1, tag2, tag3` | no 
sort above the fill | + full Sort | as master |
   | `SELECT time, tag1, s1 ... FILL_GROUP 2 ORDER BY tag1, time` | no sort 
above the fill | + full Sort | as master |
   | `PREVIOUS ... FILL_GROUP 2,3,4` over `HOP(DATA => table1, ...)` | no sort 
above the fill | + full Sort | as master |
   | `PREVIOUS ... FILL_GROUP 2,3,4` with `lag(s1) OVER (PARTITION BY tag1, 
tag2, tag3 ORDER BY time)` in the select list | StreamSort below the fill | + 
full Sort above the fill | no sort at all |
   | `date_bin_gapfill(...)` or `date_bin(...)` aggregation + `FILL ... 
FILL_GROUP 2,3,4 ORDER BY tag1, tag2, tag3, t` | 1 Sort (below the fill) | 2 
Sorts | still 2 Sorts (see the end) |
   
   Dropping the ordering is right for sort keys the fill can rewrite, and it 
fixes a real master bug: master eliminates the outer sort in `SELECT * FROM 
(SELECT * FROM table1 ORDER BY s1, s2 LIMIT 10) FILL METHOD PREVIOUS ORDER BY 
s1, s2` (also with `NEXT` / `LINEAR`), although PREVIOUS turns `(5, 1), (5, 9), 
(NULL, 2)` into `(5, 1), (5, 9), (5, 2)`. But part of the child ordering 
provably survives a PREVIOUS / NEXT / LINEAR fill:
   
   - the fill only writes NULL positions and emits rows in input order;
   - it resets at every FILL_GROUP boundary, and all rows of a group share 
their group-key values, so a group key is never rewritten (a NULL key has no 
non-NULL value in its group to copy);
   - non-NULL columns (native time, tags / attributes that are non-null for 
every device) are never rewritten; `getNonNullSymbols` already proves this for 
the constant fill.
   
   So the fill can keep the prefix of its child's ordering that consists of 
FILL_GROUP keys and provably non-null columns. As in the constant-fill branch, 
`getNonNullSymbols` (which may read the coordinator's spilled device entries) 
only runs when an ancestor requests an ordering; the group keys alone need no 
metadata.
   
   ```diff
   --- 
a/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/distribute/TableDistributedPlanGenerator.java
   +++ 
b/iotdb-core/datanode/src/main/java/org/apache/iotdb/db/queryengine/plan/relational/planner/distribute/TableDistributedPlanGenerator.java
   @@ -52,11 +52,14 @@
    import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.GroupNode;
    import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.JoinNode;
    import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.LimitNode;
   +import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.LinearFillNode;
    import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.MarkDistinctNode;
    import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.MergeSortNode;
   +import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.NextFillNode;
    import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.OffsetNode;
    import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.OutputNode;
    import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.PatternRecognitionNode;
   +import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.PreviousFillNode;
    import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.ProjectNode;
    import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.RowNumberNode;
    import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.SemiJoinNode;
   @@ -323,9 +326,24 @@
      @Override
      public List<PlanNode> visitFill(FillNode node, PlanContext context) {
        if (!(node instanceof ValueFillNode)) {
   +      boolean hasExpectedOutputOrdering = context.hasSortProperty;
          context.clearExpectedOrderingScheme();
   +      // PREVIOUS/NEXT/LINEAR fill only replaces NULLs, keeps the row order 
and resets at every
   +      // FILL_GROUP boundary. Group keys are constant within a group and 
non-null columns are never
   +      // rewritten, so a child ordering prefix made of such columns still 
holds after the fill.
   +      Set<Symbol> unchanged = new HashSet<>(getFillGroupingKeys(node));
   +      if (hasExpectedOutputOrdering) {
   +        unchanged.addAll(getNonNullSymbols(node.getChild()));
   +      }
          List<PlanNode> result = dealWithPlainSingleChildNode(node, context);
   -      nodeOrderingMap.remove(node.getPlanNodeId());
   +      OrderingScheme ordering =
   +          TableFunctionOrdering.retainOrderingPrefix(
   +              nodeOrderingMap.get(node.getPlanNodeId()), unchanged);
   +      if (ordering == null) {
   +        nodeOrderingMap.remove(node.getPlanNodeId());
   +      } else {
   +        nodeOrderingMap.put(node.getPlanNodeId(), ordering);
   +      }
          return result;
        }
        // Inspect metadata before distribution consumes a spilled device data 
set. No data rows need
   @@ -354,6 +372,18 @@
        return Collections.singletonList(node);
      }
    
   +  private static List<Symbol> getFillGroupingKeys(FillNode node) {
   +    Optional<List<Symbol>> groupingKeys = Optional.empty();
   +    if (node instanceof PreviousFillNode) {
   +      groupingKeys = ((PreviousFillNode) node).getGroupingKeys();
   +    } else if (node instanceof NextFillNode) {
   +      groupingKeys = ((NextFillNode) node).getGroupingKeys();
   +    } else if (node instanceof LinearFillNode) {
   +      groupingKeys = ((LinearFillNode) node).getGroupingKeys();
   +    }
   +    return groupingKeys.orElse(Collections.emptyList());
   +  }
   +
      private Set<Symbol> getNonNullSymbols(PlanNode node) {
        Set<Symbol> cached = nonNullSymbols.get(node.getPlanNodeId());
        if (cached != null) {
   ```
   
   <details>
   <summary>Regression tests 
(<code>OrderingPropertyPropagationTest</code>)</summary>
   
   ```diff
   --- 
a/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/OrderingPropertyPropagationTest.java
   +++ 
b/iotdb-core/datanode/src/test/java/org/apache/iotdb/db/queryengine/plan/relational/planner/optimizations/OrderingPropertyPropagationTest.java
   @@ -23,6 +23,7 @@
    import org.apache.iotdb.commons.queryengine.plan.relational.planner.Symbol;
    import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.AggregationNode;
    import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.CollectNode;
   +import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.FillNode;
    import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.PatternRecognitionNode;
    import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.RowNumberNode;
    import 
org.apache.iotdb.commons.queryengine.plan.relational.planner.node.SortNode;
   @@ -296,6 +297,48 @@
      }
    
      @Test
   +  public void testFillGroupKeepsGroupKeyAndTimeOrdering() {
   +    String window = ", lag(s1) OVER (PARTITION BY " + TAGS + " ORDER BY 
time) AS lg";
   +    for (String extraColumn : List.of("", window)) {
   +      for (String method :
   +          List.of(
   +              "PREVIOUS TIME_COLUMN 1",
   +              "PREVIOUS TIME_BOUND 1h TIME_COLUMN 1",
   +              "NEXT TIME_COLUMN 1",
   +              "LINEAR TIME_COLUMN 1")) {
   +        for (String[] group : new String[][] {{"2,3,4", TAGS}, {"2", 
"tag1"}}) {
   +          String sql =
   +              "SELECT time, "
   +                  + TAGS
   +                  + ", s1"
   +                  + extraColumn
   +                  + " FROM table1 FILL METHOD "
   +                  + method
   +                  + " FILL_GROUP "
   +                  + group[0]
   +                  + " ORDER BY "
   +                  + group[1]
   +                  + ", time";
   +          PlanTester tester = plan(sql);
   +          assertFalse(sql, findNodes(tester, FillNode.class).isEmpty());
   +          // FILL_GROUP already orders the input by its keys and time, and 
the fill changes neither.
   +          assertTrue(sql, sortsAbove(tester, FillNode.class).isEmpty());
   +        }
   +      }
   +    }
   +  }
   +
   +  @Test
   +  public void testFillKeepsSortOnFilledNullableKeys() {
   +    // PREVIOUS can turn (5, 1), (5, 9), (NULL, 2) into (5, 1), (5, 9), (5, 
2), so an ordering on
   +    // nullable columns that are not FILL_GROUP keys must not survive the 
fill.
   +    String sql =
   +        "SELECT * FROM (SELECT * FROM table1 ORDER BY s1, s2 LIMIT 10)"
   +            + " FILL METHOD PREVIOUS ORDER BY s1, s2";
   +    assertFalse(sql, sortsAbove(plan(sql), FillNode.class).isEmpty());
   +  }
   +
   +  @Test
      public void testUnorderedQueriesKeepUnorderedCollection() {
        for (String sql :
            List.of(
   ```
   
   </details>
   
   Checked locally on top of 20d7b00:
   
   - `testFillGroupKeepsGroupKeyAndTimeOrdering` fails on 20d7b00 (Sort above 
the fill) and passes with the change. `testFillKeepsSortOnFilledNullableKeys` 
passes on both, so the master bug above stays fixed.
   - Of 149 distributed-plan probes (TVF / window / TopK / fill / aggregation / 
LIMIT / JOIN / UNION / single-device shapes), only the 8 FILL_GROUP shapes 
above that the change fixes differ from 20d7b00; the other 141 plans are 
identical.
   - All unit tests under `org/apache/iotdb/db/queryengine/plan/relational` 
pass (493 run) except `CteMaterializerTest` / `CteSubqueryTest`, which error 
locally on JDK 21 with or without the change.
   
   Not covered: gapfill + `FILL_GROUP` and `date_bin` aggregation + 
`FILL_GROUP` still sort twice. There the bucket column comes out of an 
aggregation, which `getNonNullSymbols` does not model, and 
`AbstractGapFillOperator` explicitly passes NULL buckets through, so I did not 
assume it is non-NULL. Covering these needs a separate argument about how NULLs 
in the key right after the group keys get filled; I'd leave that for a 
follow-up.
   



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