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

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

Doesn't stop thinking or doesn't stop printing output?

> know, that we don't have cycles in the our described graph. We think

Usually Oracle detects loops in Connect BY query and returns an error.

> 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.
>

I'd recommend to test this query on the small table and make sure (using level function) that result is what you actually want. Query conditions appear to be OK to me, but who knows. Also, it's a good idea to research problem analitically. Actually, you're building ascending tree in the DAG, it should be possible to estimate number of vertices and edges in the tree for some particular cases. Then compare estimated value with the number of records you're getting from the queries.

I can't give a better advice here, it would require detailed knowledge of your data.

> 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 Mon May 12 2003 - 10:39:53 CDT