using adjacency tables: finding leaves and dead ends

Please start any new threads on our new site at https://forums.sqlteam.com. We've got lots of great SQL Server experts to answer whatever question you can come up with.

All Forums

SQL Server 2000 Forums

SQL Server Development (2000)

using adjacency tables: finding leaves and dead ends

Author

Topic

AskSQLTeam
Ask SQLTeam Question

0 Posts

Posted - 2002-05-23 : 10:38:26

Steve writes "I've inherited a hierarchy modelled as an adjacency table. This stores a tree, and then stores documents linked to the nodes of that tree.


----tree table-----------     
id     label     parentid 
100    blah      0        
101    blah      100       
102    blah      101   
etc

And with that, what I thought would be simple is stumping me:

How do I get a list of all nodes that do not have further children? Eg for the above table, how do I return just 101 and 102?

I can find the nodes that have children quite easily:

select id, label from tree where id in (select parentid from tree) order by label

But when I reverse it ("where id not in") the query almost grinds to a halt. Any faster way to find this list

tia

Steve"

Page47
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2002-05-23 : 10:55:56


select
    id
from
    tree t
where
    not exists (
        select 1
        from
            tree
        where
            parentid = t.id)

<O>

Edited by - Page47 on 05/23/2002 10:56:20

stevep
Starting Member

17 Posts

Posted - 2002-05-23 : 22:15:44

page47,

ta for the suggestion. It is faster than mine, but not quite the huge improvement I need. For example, running the two queries, via ASP, on a tree with 1500 nodes (avg 10 kids per node), gives me the
following times:

35 secs = SELECT .... NOT IN..
33 secs = SELECT ...NOT EXISTS..
(The times are obviously comparative, more than absolute).

Anything above a second or two is a no go. Which means I now think the only way to get this data fast enough to be useful is to modify the table structure (add a flag to indicate if node has children or not)?

Steve

Lavos
Posting Yak Master

200 Posts

Posted - 2002-05-24 : 02:33:05

What indexes do you have defined on the table? What does the Execution Plan show in Query Analyzer when you cut and paste the code into it?

I'd also switch the NOT EXISTS sub-query to SELECT * instead of SELECT 1. It shouldn't make a difference to the optimizer, but it might.

----------------------
"O Theos mou! Echo ten labrida en te mou kephale!"

Page47
Master Smack Fu Yak Hacker

2878 Posts

Posted - 2002-05-24 : 07:59:17

15K records taking 30 seconds to run this query does smell a little funny . . . I hope there is some index tuning that can be done . . .

There are many things about the adjacency model that are a little...uhm...tedious. Have you looked at Rob's article on trees? However, this particular query is one of the few interactions with an adjacency hierarchy that is relatively simple.

<O>

Subscribe to SQLTeam.com

SQLTeam.com Articles via RSS

SQLTeam.com Weblog via RSS

- Advertisement -

Resources