Re: Performance problem in a "Connect-By" query over a DAG-edges table

From: Daniel Roy <danielroy10_at_hotmail.com>
Date: 14 May 2003 09:32:39 -0700
Message-ID: <1b061893.0305140832.72c9e431@posting.google.com>

Please provide:

- your Oracle version 
- OPTIMIZER_MODE value
- confirm that the table has been recently analyzed if you are using

cost-based optimization
- The execution plan

Daniel

olouidor_at_tx.technion.ac.il (Oren Louidor) wrote in message news:<39d6c4dc.0305112334.425c4e66_at_posting.google.com>...
> We're using an "Edges" table with records consisting of two fields:
> ParentID ChildID (actually, the table has some more columns, which
> are not important to the problem).
>
> This table describes a DAG-type graph, with each record being
> an edge between two vertices with IDs given in these two fields.
> Each vertex may have many parents and many childs.
>
> We want to get all the ancestors of a given vertex, using the
> following
> query:
> select ParentID from Edges
> start with ChildID = #####
> connect by prior ParentID = ChildID.
>
> When the table size is about 1000 records, this query doesn't stop. We
> know, that we don't have cycles in the our described graph. We think
> that the problem comes from the fact that, since the graph is a DAG,
> there are many ways to get to a certain ancestor of our vertex with
> the amount of ways increasing exponentially. We followed the execution
> of the query, by examining the output of ParentIDs and indeed, it
> seems that the query got to the same record many times.
>
> Is there a way to avoid this, or maybe there's a better way to get all
> the ancestors of our vertex.
>
> Thanks,
> Oren.
Received on Wed May 14 2003 - 11:32:39 CDT