Derby
  1. Derby
  2. DERBY-4387

Infinite loop in PredicateList.joinClauseTransitiveClosure()

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: 10.0.2.1, 10.1.3.1, 10.2.2.0, 10.3.3.0, 10.4.2.0, 10.5.3.0, 10.6.1.0
    • Fix Version/s: 10.5.3.1, 10.6.1.0
    • Component/s: SQL
    • Labels:
      None
    • Issue & fix info:
      High Value Fix, Repro attached
    • Bug behavior facts:
      Crash

      Description

      This sequence of statements triggers an infinite loop in PredicateList.joinClauseTransitiveClosure() and never completes:

      create table c (a int, b int, c int);
      create table cc (aa int);

      select * from cc t1, c t2, cc t3 where t3.aa = t2.a and t3.aa = t2.b and t3.aa = t2.c;

      1. derby-4387.stat
        0.2 kB
        Dag H. Wanvik
      2. derby-4387.diff
        3 kB
        Dag H. Wanvik

        Issue Links

          Activity

          Hide
          Knut Anders Hatlen added a comment -

          Reassigning the issue to Dag who wrote the fix.

          Show
          Knut Anders Hatlen added a comment - Reassigning the issue to Dag who wrote the fix.
          Hide
          Dag H. Wanvik added a comment -

          The last official 10.5 release was 10.5.3.0 (August 21, 2009 / SVN 802917).
          The patch went in at 887249, so marking it as fixed in next release is fine. Thanks for catching that, Mike!

          Show
          Dag H. Wanvik added a comment - The last official 10.5 release was 10.5.3.0 (August 21, 2009 / SVN 802917). The patch went in at 887249, so marking it as fixed in next release is fine. Thanks for catching that, Mike!
          Hide
          Mike Matrigali added a comment -

          i am working on backporting this to 10.5.

          Show
          Mike Matrigali added a comment - i am working on backporting this to 10.5.
          Hide
          Mike Matrigali added a comment -

          Dag had already backported this issue to 10.5, but had not updated the fix in field. resolving it as fixed in 10.5. I am not sure what version of 10.5 it may have gone in, so just marking it as fixed in next release.

          Show
          Mike Matrigali added a comment - Dag had already backported this issue to 10.5, but had not updated the fix in field. resolving it as fixed in 10.5. I am not sure what version of 10.5 it may have gone in, so just marking it as fixed in next release.
          Hide
          Lily Wei added a comment -

          Reopen to 10.5 back port

          Show
          Lily Wei added a comment - Reopen to 10.5 back port
          Hide
          Knut Anders Hatlen added a comment -

          Verified that the statement does not loop infinitely on trunk. Closing.

          Show
          Knut Anders Hatlen added a comment - Verified that the statement does not loop infinitely on trunk. Closing.
          Hide
          Dag H. Wanvik added a comment -

          Bryan, I think the indentation is correct; but my new lines use blanks rather than tabs, I have given up
          on tabs entirely lately. (I used to try to keep tabs-only files that way, but there are very few of them left, most already have many changed lines with space indentation.)

          Show
          Dag H. Wanvik added a comment - Bryan, I think the indentation is correct; but my new lines use blanks rather than tabs, I have given up on tabs entirely lately. (I used to try to keep tabs-only files that way, but there are very few of them left, most already have many changed lines with space indentation.)
          Hide
          Dag H. Wanvik added a comment -

          Backported to 10.5 branch as svn 887249.

          Bryan, thanks for noticing, I'll fix it.

          Show
          Dag H. Wanvik added a comment - Backported to 10.5 branch as svn 887249. Bryan, thanks for noticing, I'll fix it.
          Hide
          Bryan Pendleton added a comment -

          Looks like the PredicateList.java change may have a tabs-versus-spaces format inconsistency.
          Sorry to be a bit late with this feedback.

          Show
          Bryan Pendleton added a comment - Looks like the PredicateList.java change may have a tabs-versus-spaces format inconsistency. Sorry to be a bit late with this feedback.
          Hide
          Dag H. Wanvik added a comment -

          Committed patch as svn 887246, resolving.

          Show
          Dag H. Wanvik added a comment - Committed patch as svn 887246, resolving.
          Hide
          Knut Anders Hatlen added a comment -

          The patch looks correct to me. I've also verified that it makes the query in the bug description return successfully. +1 to commit.

          Show
          Knut Anders Hatlen added a comment - The patch looks correct to me. I've also verified that it makes the query in the bug description return successfully. +1 to commit.
          Hide
          Dag H. Wanvik added a comment -

          Regressions passed OK.

          Show
          Dag H. Wanvik added a comment - Regressions passed OK.
          Hide
          Dag H. Wanvik added a comment -

          Uploading a patch which solves this case, and adds a test case to JoinTest.

          The problem here is that the computation of the transitive closure for
          the repro case, finds that closure predicates that apply for two
          columns in the same table. Cf the following snapshot of the fully
          computed joinClauses table (with the fix), where EC is equivalence
          class assigned, and a * denotes a predicate added by the closure
          computation. cf. PredicateList#joinClauseTransitiveClosure:

          [0]: (t1)
          [1]: (t2) i.e.
          [0]: 2.1 = 1.1 EC: 0 t3.aa == t2.a
          [1]: 1.1 = 1.3 EC: 0 t2.a == t2.c *
          [2]: 1.1 = 1.2 EC: 0 t2.a == t2.b *
          [3]: 2.1 = 1.2 EC: 0 t3.aa == t2.b
          [4]: 2.1 = 1.3 EC: 0 t3.aa == t2.c
          [2]: (t3)
          [0]: 2.1 = 1.1 EC: 0 t3.aa == t2.a
          [1]: 2.1 = 1.2 EC: 0 t3.aa == t2.b
          [2]: 2.1 = 1.3 EC: 0 t3.aa == t2.c

          Before the fix, the derived predicates (e.g. t2.a == t2.b) were
          added twice and caused an infinite loop. The patch makes sure to only
          add the derived predicate once (when outer and inner predicates list
          are the same, as they are here).

          Running regressions.

          Show
          Dag H. Wanvik added a comment - Uploading a patch which solves this case, and adds a test case to JoinTest. The problem here is that the computation of the transitive closure for the repro case, finds that closure predicates that apply for two columns in the same table . Cf the following snapshot of the fully computed joinClauses table (with the fix), where EC is equivalence class assigned, and a * denotes a predicate added by the closure computation. cf. PredicateList#joinClauseTransitiveClosure: [0] : (t1) [1] : (t2) i.e. [0] : 2.1 = 1.1 EC: 0 t3.aa == t2.a [1] : 1.1 = 1.3 EC: 0 t2.a == t2.c * [2] : 1.1 = 1.2 EC: 0 t2.a == t2.b * [3] : 2.1 = 1.2 EC: 0 t3.aa == t2.b [4] : 2.1 = 1.3 EC: 0 t3.aa == t2.c [2] : (t3) [0] : 2.1 = 1.1 EC: 0 t3.aa == t2.a [1] : 2.1 = 1.2 EC: 0 t3.aa == t2.b [2] : 2.1 = 1.3 EC: 0 t3.aa == t2.c Before the fix, the derived predicates (e.g. t2.a == t2.b) were added twice and caused an infinite loop. The patch makes sure to only add the derived predicate once (when outer and inner predicates list are the same, as they are here). Running regressions.
          Hide
          Knut Anders Hatlen added a comment -

          Thread dump when the statement has entered the infinite loop:

          "main" prio=3 tid=0x0806f400 nid=0x2 runnable [0xfe28e000]
          java.lang.Thread.State: RUNNABLE
          at org.apache.derby.impl.sql.compile.PredicateList.joinClauseTransitiveClosure(PredicateList.java:2071)
          at org.apache.derby.impl.sql.compile.SelectNode.performTransitiveClosure(SelectNode.java:1109)
          at org.apache.derby.impl.sql.compile.SelectNode.preprocess(SelectNode.java:954)
          at org.apache.derby.impl.sql.compile.DMLStatementNode.optimizeStatement(DMLStatementNode.java:318)
          at org.apache.derby.impl.sql.compile.CursorNode.optimizeStatement(CursorNode.java:573)
          at org.apache.derby.impl.sql.GenericStatement.prepMinion(GenericStatement.java:373)
          at org.apache.derby.impl.sql.GenericStatement.prepare(GenericStatement.java:88)
          at org.apache.derby.impl.sql.conn.GenericLanguageConnectionContext.prepareInternalStatement(GenericLanguageConnectionContext.java:824)
          at org.apache.derby.impl.jdbc.EmbedStatement.execute(EmbedStatement.java:606)

          • locked <0xbad3dc50> (a org.apache.derby.impl.jdbc.EmbedConnection40)
            at org.apache.derby.impl.jdbc.EmbedStatement.execute(EmbedStatement.java:555)
            at org.apache.derby.impl.tools.ij.ij.executeImmediate(ij.java:329)
            at org.apache.derby.impl.tools.ij.utilMain.doCatch(utilMain.java:521)
            at org.apache.derby.impl.tools.ij.utilMain.runScriptGuts(utilMain.java:366)
            at org.apache.derby.impl.tools.ij.utilMain.go(utilMain.java:261)
            at org.apache.derby.impl.tools.ij.Main.go(Main.java:229)
            at org.apache.derby.impl.tools.ij.Main.mainCore(Main.java:184)
            at org.apache.derby.impl.tools.ij.Main.main(Main.java:75)
            at org.apache.derby.tools.ij.main(ij.java:59)
            at org.apache.derby.iapi.tools.run.main(run.java:53)
          Show
          Knut Anders Hatlen added a comment - Thread dump when the statement has entered the infinite loop: "main" prio=3 tid=0x0806f400 nid=0x2 runnable [0xfe28e000] java.lang.Thread.State: RUNNABLE at org.apache.derby.impl.sql.compile.PredicateList.joinClauseTransitiveClosure(PredicateList.java:2071) at org.apache.derby.impl.sql.compile.SelectNode.performTransitiveClosure(SelectNode.java:1109) at org.apache.derby.impl.sql.compile.SelectNode.preprocess(SelectNode.java:954) at org.apache.derby.impl.sql.compile.DMLStatementNode.optimizeStatement(DMLStatementNode.java:318) at org.apache.derby.impl.sql.compile.CursorNode.optimizeStatement(CursorNode.java:573) at org.apache.derby.impl.sql.GenericStatement.prepMinion(GenericStatement.java:373) at org.apache.derby.impl.sql.GenericStatement.prepare(GenericStatement.java:88) at org.apache.derby.impl.sql.conn.GenericLanguageConnectionContext.prepareInternalStatement(GenericLanguageConnectionContext.java:824) at org.apache.derby.impl.jdbc.EmbedStatement.execute(EmbedStatement.java:606) locked <0xbad3dc50> (a org.apache.derby.impl.jdbc.EmbedConnection40) at org.apache.derby.impl.jdbc.EmbedStatement.execute(EmbedStatement.java:555) at org.apache.derby.impl.tools.ij.ij.executeImmediate(ij.java:329) at org.apache.derby.impl.tools.ij.utilMain.doCatch(utilMain.java:521) at org.apache.derby.impl.tools.ij.utilMain.runScriptGuts(utilMain.java:366) at org.apache.derby.impl.tools.ij.utilMain.go(utilMain.java:261) at org.apache.derby.impl.tools.ij.Main.go(Main.java:229) at org.apache.derby.impl.tools.ij.Main.mainCore(Main.java:184) at org.apache.derby.impl.tools.ij.Main.main(Main.java:75) at org.apache.derby.tools.ij.main(ij.java:59) at org.apache.derby.iapi.tools.run.main(run.java:53)

            People

            • Assignee:
              Dag H. Wanvik
              Reporter:
              Knut Anders Hatlen
            • Votes:
              1 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development