Uploaded image for project: 'Calcite'
  1. Calcite
  2. CALCITE-3118

VolcanoRuleCall should look at RelSubset rather than RelSet when checking child ordinal of a parent operand

    XMLWordPrintableJSON

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 1.21.0
    • Component/s: None

      Description

      In VolcanoRuleCall.matchRecurse(), when ascending (child operand is matched, looking for parent operand match), we want to check that the matched parent indeed has the previously matched RelNode as a child with the expected child ordinal.

      However, there is a bug in this child ordinal check:

      333        if (ascending && operand.childPolicy != RelOptRuleOperandChildPolicy.UNORDERED) {
      334          // We know that the previous operand was *a* child of its parent,
      335          // but now check that it is the *correct* child.
      336          final RelSubset input =
      337              (RelSubset) rel.getInput(previousOperand.ordinalInParent);
      338          List<RelNode> inputRels = input.set.getRelsFromAllSubsets();
      339          if (!inputRels.contains(previous)) {
      340            continue;
      341          }
      342        }
      

      We intend to make sure that "previous" is in Subset "input". However line 338 looked at RelNodes from the entire RelSet, rather than RelNodes only in Subset "input". As a result, in some cases, incorrect parent is not skipped as expected and is matched incorrectly.

      The unit test case included is a case that triggers this bug, where a second child RelNode incorrectly get matched as the first child of the parent RelNode.

      --------------------------
      Here's a detailed explanation of the test case that triggers the bug

      We constructed a RelNode structure:

           PhysBiRel
            /     \
        Subset1   Subset2
          |          |
      leftPhy    rightPhy
      

      Where PhysBiRel has two inputs: leftPhy and rightPhy, both are logically equivalent, but with different traits (Convention in this test case), and thus are in different subsets.
      (Two Rels in two subsets in the same RelSet is a necessary condition to trigger this bug. )

      A rule AssertOperandsDifferentRule is constructed as follows:

      operand(PhysBiRel.class,
          operand(PhysLeafRel.class, any()),
          operand(PhysLeafRel.class, any()))
      

      Obviously the correct match would be:

           PhysBiRel
            /     \
      leftPhy    rightPhy
      

      However, with the bug, another match is also returned:

           PhysBiRel
            /     \
      rightPhy    rightPhy
      

      This is wrong because rightPhy is not PhysBiRel's first input at all, and should not match as parent operand's first child.

      ----------------------------
      Here's how the incorrect match occurs.
      1. When rightPhy of class PhysLeafRel is registered, we attempt to match it to both the left and right child operands of AssertOperandsDifferentRule above. This is expected. 
      2. When matched to the right child operand, it eventually leads to the correct match result above.
      3. When matched to the left child operand, it should have skipped/failed matching the parent operand to PhysBiRel because rightPhy is NOT PhysBiRel's first input. But because of the bug, the match succeeded. After parent is matched, then it attempt to match the right child operand, and again matched the rightPhy. As a result, both child operand end up matching the same RelNode rightPhy.

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                danny0405 Danny Chen
                Reporter:
                botong Botong Huang
              • Votes:
                0 Vote for this issue
                Watchers:
                5 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved:

                  Time Tracking

                  Estimated:
                  Original Estimate - Not Specified
                  Not Specified
                  Remaining:
                  Remaining Estimate - 0h
                  0h
                  Logged:
                  Time Spent - 2h 20m
                  2h 20m