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

Rules fail to match because of missing link to parent equivalence set

    Details

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

      Description

      There is no "parent link" in RelSubset, it is only for RelSet. However, RelSubset provides a "getParentRels()" link.

        public Collection<RelNode> getParentRels() {
          final Set<RelNode> list = new LinkedHashSet<RelNode>();
        parentLoop:
          for (RelNode parent : set.getParentRels()) {
            for (RelSubset rel : inputSubsets(parent)) {
              if (rel.set == set && rel.getTraitSet().equals(traitSet)) {
                list.add(parent);
                continue parentLoop;
              }
            }
          }
          return list;
        }
      

      Now that we have a RelNode P1 and its input subset is S1, and we have a rule that matches P1 and does the following:

      onMatch(RelOptRuleCall call) {
        RelNode P1 = call.rel(0);
        RelNode S1 = P1.getInput(0);
        RelTraitSet t1 = S1.getTraitSet();
        RelTraitSet t2 = t1.replace(tx);
        RelNode S2 = convert(S1, t2);
        RelNode P2 = P1.copy(P1.getCluster, P1.getTraitSet(), S2);
        call.transformTo(P2);
      }
      

      Note that t1 is NOT equal to t2. So right now we have two subsets, S1 and S2, in the same set; and their parents P1 and P2 in another set.

      P1            P2
      |             |
      S1(t1)        S2(t2)
      

      getParentRels(S1) would return P1, and getParentRels(S2) would return P2. This works fine except when t1 satisfies t2 (for instance, if tx is the empty collation trait) and as a result S2 subsumes S1. Thus the expression S2 = convert(S1, t2) would eventually turn into S1 after conversion, so P2 is also a parent of S1, and getParentRels(S1) should return P1, P2 instead.
      Suppose we have a second rule that should match P2 - R subsequently, R as some Rel in S1, it would NOT be fired since P2 is not returned in the parent list of S1. It would not match R in S2 either since it is in the form of P2 - AbstractConverter - R.

      1. CALCITE-926.patch
        0.6 kB
        Maryann Xue
      2. CALCITE-926_2.patch
        7 kB
        Maryann Xue

        Activity

        Hide
        maryannxue Maryann Xue added a comment - - edited

        Changing implementation of getParentRels() would also fix this problem, but I suspect it might add some redundancy.

        diff --git a/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java b/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
        index b3e6a5e..1adebbd 100644
        --- a/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
        +++ b/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java
        @@ -236,7 +236,7 @@ protected String computeDigest() {
           parentLoop:
             for (RelNode parent : set.getParentRels()) {
               for (RelSubset rel : inputSubsets(parent)) {
        -        if (rel.set == set && rel.getTraitSet().equals(traitSet)) {
        +        if (rel.set == set && traitSet.satisfies(rel.getTraitSet())) {
                   list.add(parent);
                   continue parentLoop;
                 }
        

        So I'm suggesting the fix in the patch, to return S1 for convert(S1, t2) directly instead of creating a new subset S2.

        Will follow up with a second patch once I have a test case. Will have to create some new rules for test purpose.

        Show
        maryannxue Maryann Xue added a comment - - edited Changing implementation of getParentRels() would also fix this problem, but I suspect it might add some redundancy. diff --git a/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java b/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java index b3e6a5e..1adebbd 100644 --- a/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java +++ b/core/src/main/java/org/apache/calcite/plan/volcano/RelSubset.java @@ -236,7 +236,7 @@ protected String computeDigest() { parentLoop: for (RelNode parent : set.getParentRels()) { for (RelSubset rel : inputSubsets(parent)) { - if (rel.set == set && rel.getTraitSet().equals(traitSet)) { + if (rel.set == set && traitSet.satisfies(rel.getTraitSet())) { list.add(parent); continue parentLoop; } So I'm suggesting the fix in the patch, to return S1 for convert(S1, t2) directly instead of creating a new subset S2 . Will follow up with a second patch once I have a test case. Will have to create some new rules for test purpose.
        Hide
        maryannxue Maryann Xue added a comment -

        Including a new test case: VolcanoPlannerTraitTest.testRuleMatchAfterConversion().
        Also switching back to the getParentRels() fix, for the fix in the first patch wouldn't solve the issue if part of the TraitSet does not satisfy.

        Show
        maryannxue Maryann Xue added a comment - Including a new test case: VolcanoPlannerTraitTest.testRuleMatchAfterConversion(). Also switching back to the getParentRels() fix, for the fix in the first patch wouldn't solve the issue if part of the TraitSet does not satisfy.
        Show
        julianhyde Julian Hyde added a comment - Fixed in http://git-wip-us.apache.org/repos/asf/incubator-calcite/commit/2c339be1 . Thanks for the patch, Maryann Xue !
        Hide
        jcamachorodriguez Jesus Camacho Rodriguez added a comment -

        Resolved in release 1.5.0 (2015-11-10)

        Show
        jcamachorodriguez Jesus Camacho Rodriguez added a comment - Resolved in release 1.5.0 (2015-11-10)

          People

          • Assignee:
            maryannxue Maryann Xue
            Reporter:
            maryannxue Maryann Xue
          • Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development