db-derby-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Dag H. Wanvik (JIRA)" <j...@apache.org>
Subject [jira] Updated: (DERBY-4387) Infinite loop in PredicateList.joinClauseTransitiveClosure()
Date Thu, 26 Nov 2009 18:02:39 GMT

     [ https://issues.apache.org/jira/browse/DERBY-4387?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Dag H. Wanvik updated DERBY-4387:
---------------------------------

    Attachment: derby-4387.stat
                derby-4387.diff

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.

> Infinite loop in PredicateList.joinClauseTransitiveClosure()
> ------------------------------------------------------------
>
>                 Key: DERBY-4387
>                 URL: https://issues.apache.org/jira/browse/DERBY-4387
>             Project: Derby
>          Issue Type: Bug
>          Components: SQL
>    Affects Versions: 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.0.0
>            Reporter: Knut Anders Hatlen
>         Attachments: derby-4387.diff, derby-4387.stat
>
>
> 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;

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


Mime
View raw message