Re: Hierarchy Problems
From: Kevin Munro (kevin_at_c3amulet.com)
Date: 12/20/04
- Next message: Alejandro Mesa: "RE: Sql order by question"
- Previous message: Brandon Lilly: "RE: Search duplicated in a table"
- In reply to: Kevin Munro: "Re: Hierarchy Problems"
- Messages sorted by: [ date ] [ thread ]
Date: Mon, 20 Dec 2004 15:53:41 -0000
I now have a stored procedre and this creates the ancestry. Had to resort to
a cursor but it is fast enough.
Kevin.
CREATE FUNCTION ufn_GetAncestors(@ident AS int)
RETURNS @tree table
(
ident INT NOT NULL,
parent INT NULL,
lvl INT NOT NULL
)
AS
BEGIN
DECLARE @lvl AS INT
SET @lvl = 0
-- get given node
INSERT INTO @tree
SELECT ident, parent, @lvl
FROM container
WHERE ident = @ident
WHILE @@ROWCOUNT > 0
BEGIN
SET @lvl = @lvl + 1
-- get parent of prev level's node
INSERT INTO @tree
SELECT E.ident, E.parent, @lvl
FROM container AS E JOIN @tree AS T
ON E.ident = T.parent AND T.lvl = @lvl - 1
END
RETURN
END
GO
CREATE PROCEDURE amsp_InsertAncestors
@sessionid as varchar(8)
AS
-- Created 20th December 2004 - KM
declare @counter int
SET NOCOUNT ON
-- get all container rows into a temporary table
SELECT CONTAINERID INTO #tree FROM PQTSELECTION WHERE SESSIONID=@sessionid
-- set up the cursor
declare objects cursor
for
select containerid from #tree
declare @ident int
-- open the cursor and fetch the first row
open objects
fetch objects into @ident
while (@@fetch_status=0)
begin
-- insert into the container table and fetch the newxt row from the cursor
insert into pqtcontext select parent,@sessionid from
ufn_GetAncestors(@ident)
fetch objects into @ident
end
-- close and release memory
close objects
deallocate objects
-- drop temporary table
drop table #tree
GO
"Kevin Munro" <kevin@c3amulet.com> wrote in message
news:41c6e068$0$109$65c69314@mercury.nildram.net...
> Yes I was getting a table scan of 227,000 rows for each of query:
>
> This query was quick...
>
> select t.ident from container t join container x on x.hierarchy like
> t.hierarchy+'%'
> where x.ident=2560
>
> but when I go
>
> select t.ident from container t join container x on x.hierarchy like
> t.hierarchy+'%'
> where x.ident in (2560,2561,2562 etc) or
>
> select t.ident from container t join container x on x.hierarchy like
> t.hierarchy+'%'
> where x.ident in (select id from pqtselection)
>
> the time fairly multiplies out and soon I was doing a table scan over 16
> million records!
>
> So I've been playing with both of these suggestions and they are both
> interesting.
>
> To complicate matters somewhat I am really looking for the ancestors of a
> set of records and not just one. I have a table called pqtselection and I
> pass in the ident of the node and a unique session id.
>
> insert into pqtselection select parent,'999' from ufn_GetAncestors(4700)
> insert into pqtselection select parent,'999' from ufn_GetAncestors(4701)
> insert into pqtselection select parent,'999' from ufn_GetAncestors(4702)
> etc...
>
> Now I'm trying to get this into one query!
>
> Thanks, this is an interesting subject.
>
> Kevin.
>
>
> "Itzik Ben-Gan" <itzik@REMOVETHIS.SolidQualityLearning.com> wrote in
> message
> news:%23m8JKMp5EHA.1300@TK2MSFTNGP14.phx.gbl...
>> If you think about it, an index can be used when you look for all rows
>> with a path that starts with a constant ('constant%'), but not the other
>> way around.
>> You probably get a table scan when you look for the ancestors using the
>> LIKE predicate.
>> However, there is an efficient way to get ancestors using the path that
>> you already keep, using the unique index on ident. The path of the node
>> already contains all ancestor id's, so use a function to split the id's
>> into multiple rows, and join the result with the id's to the base table,
>> like so:
>>
>> -- Populate an auxiliary table of numbers
>> IF OBJECT_ID('Nums') IS NOT NULL
>> DROP TABLE Nums
>> GO
>> CREATE TABLE Nums(n INT NOT NULL PRIMARY KEY)
>> GO
>> SET NOCOUNT ON
>>
>> DECLARE
>> @max AS INT,
>> @rc AS INT
>>
>> SET @max = 10000
>> SET @rc = 1
>>
>> BEGIN TRAN
>> INSERT INTO Nums VALUES(1)
>>
>> WHILE @rc * 2 <= @max
>> BEGIN
>> INSERT INTO Nums
>> SELECT n + @rc FROM Nums
>>
>> SET @rc = @rc * 2
>> END
>>
>> INSERT INTO Nums
>> SELECT n + @rc FROM Nums
>> WHERE n + @rc <= @max
>> COMMIT TRAN
>> GO
>>
>> -- split function
>> CREATE FUNCTION fn_split(@str AS VARCHAR(8000)) RETURNS TABLE
>> AS
>> RETURN
>> SELECT
>> n - LEN(REPLACE(LEFT(string, n), '.', '')) AS pos,
>> CAST(SUBSTRING(string, n+1,
>> CHARINDEX('.', string, n+1) - (n+1))
>> AS INT) AS element
>> FROM (SELECT @str AS string) AS S
>> JOIN Nums
>> ON n < LEN(string)
>> AND SUBSTRING(string, n, 1) = '.'
>> GO
>>
>> -- test function
>> SELECT * FROM fn_split('.1.2.7.')
>>
>> pos element
>> ----------- -----------
>> 1 1
>> 2 2
>> 3 7
>>
>> -- Use split function to get ancestors of 7
>> DECLARE @path as VARCHAR(900)
>> SET @path = (SELECT path FROM Fred WHERE ident = 7)
>>
>> SELECT P.pos - 1 AS level, F.*
>> FROM fn_split(@path) AS P
>> JOIN Fred AS F
>> ON element = ident
>>
>> level ident n parent path
>> ----------- ----------- ---------- ----------- --------
>> 0 1 Root NULL .1.
>> 1 2 Fruit 1 .1.2.
>> 2 7 Orange 2 .1.2.7.
>>
>> You can examine the execution plan and see that there's a seek operation
>> in the index created on ident for each ancestor's ident value.
>>
>> --
>> BG, SQL Server MVP
>> www.SolidQualityLearning.com
>>
>>
>> "Kevin Munro" <kevin@c3amulet.com> wrote in message
>> news:41c6c1b0$0$105$65c69314@mercury.nildram.net...
>>> Itzik, thanks for this and I'll try it out on the main database.
>>>
>>> I've been using the ident string notation from your article and it works
>>> great when I want to query under a node.
>>>
>>> select t.ident from container t join container x on t.hierarchy like
>>> x.hierarchy+'%'
>>> where x.ident=2560
>>>
>>> But on my database of 250,000 containers if I want to query all rows
>>> above a container then the query takes over 20 seconds despite good
>>> indexes etc.
>>>
>>> select t.ident from container t join container x on x.hierarchy like
>>> t.hierarchy+'%'
>>> where x.ident=2560
>>>
>>> So I was hoping that I could use the existing parent/child relationship
>>> to get good performance going up through the ancestory - as I'm getting
>>> great performance with using the LIKE operator on the hierarchical
>>> string
>>> notation.
>>>
>>> Kevin.
>>>
>>>
>>> "Itzik Ben-Gan" <itzik@REMOVETHIS.SolidQualityLearning.com> wrote in
>>> message news:uJEDuoo5EHA.2876@TK2MSFTNGP12.phx.gbl...
>>>> Kevin, here's a function you can use:
>>>>
>>>> CREATE FUNCTION ufn_GetAncestors(@ident AS int)
>>>> RETURNS @tree table
>>>> (
>>>> ident INT NOT NULL,
>>>> parent INT NULL,
>>>> n VARCHAR(25) NOT NULL,
>>>> lvl INT NOT NULL
>>>> )
>>>> AS
>>>> BEGIN
>>>> DECLARE @lvl AS INT
>>>> SET @lvl = 0
>>>>
>>>> -- get given node
>>>> INSERT INTO @tree
>>>> SELECT ident, parent, n, @lvl
>>>> FROM Fred
>>>> WHERE ident = @ident
>>>>
>>>> WHILE @@ROWCOUNT > 0
>>>> BEGIN
>>>> SET @lvl = @lvl + 1
>>>>
>>>> -- get parent of prev level's node
>>>> INSERT INTO @tree
>>>> SELECT E.ident, E.parent, E.n, @lvl
>>>> FROM Fred AS E JOIN @tree AS T
>>>> ON E.ident = T.parent AND T.lvl = @lvl - 1
>>>> END
>>>>
>>>> RETURN
>>>> END
>>>> GO
>>>>
>>>> SELECT * FROM ufn_GetAncestors(7)
>>>>
>>>> ident parent n lvl
>>>> ----- ------ ------ -----------
>>>> 7 2 Orange 0
>>>> 2 1 Fruit 1
>>>> 1 NULL Root 2
>>>>
>>>> --
>>>> BG, SQL Server MVP
>>>> www.SolidQualityLearning.com
>>>>
>>>>
>>>> "Kevin Munro" <kevin@c3amulet.com> wrote in message
>>>> news:41c6b9f4$0$109$65c69314@mercury.nildram.net...
>>>>> Hello, I'm having a problem with hierarchies.
>>>>>
>>>>> I've got a simple parent child relationship as defined below and I'm
>>>>> wanting to return rows from a specified child to the root node.
>>>>>
>>>>> e.g. if I look at Orange I want three rows returned (with columns of
>>>>> ident and n)
>>>>>
>>>>> --7,Orange
>>>>> --2,Fruit
>>>>> --1,Root
>>>>>
>>>>> Thanks, Kevin.
>>>>>
>>>>> set nocount on
>>>>> drop table fred
>>>>> create table fred (ident int, n varchar(10),parent int)
>>>>> go
>>>>> insert into fred values (1,'Root',NULL)
>>>>> insert into fred values (2,'Fruit',1)
>>>>> insert into fred values (3,'Vegetables',1)
>>>>> insert into fred values (4,'Apple',2)
>>>>> insert into fred values (5,'Banana',2)
>>>>> insert into fred values (7,'Orange',2)
>>>>> insert into fred values (8,'Potato',3)
>>>>> insert into fred values (9,'Carrot',3)
>>>>>
>>>>> -- hierarchy is as follows
>>>>>
>>>>> --Root
>>>>> ----Fruit
>>>>> ------Apple
>>>>> ------Banana
>>>>> ------Orange
>>>>> ----Vegetables
>>>>> ------Potato
>>>>> ------Carrots
>>>>>
>>>>>
>>>>>
>>>>
>>>>
>>>
>>>
>>
>>
>
>
>
- Next message: Alejandro Mesa: "RE: Sql order by question"
- Previous message: Brandon Lilly: "RE: Search duplicated in a table"
- In reply to: Kevin Munro: "Re: Hierarchy Problems"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
