February 8, 2008 at 5:36 am
what is the required t-sql for getting all the child categories in a parent category?
my table is like this : id | name | parentid
February 8, 2008 at 6:58 am
assuming parentid refers to an id in the same table (self join), you would have to do it with some sort of recursion. here's my suggestion:
create table #vehicles
( id int, category varchar(20), parent int null )
insert into #vehicles values ( 1, 'car', null )
insert into #vehicles values ( 2, 'boat', null )
insert into #vehicles values ( 3, 'chevy', 1 )
insert into #vehicles values ( 4, 'pontiac', 1 )
insert into #vehicles values ( 5, 'searay', 2 )
insert into #vehicles values ( 6, 'honda', 1 )
insert into #vehicles values ( 7, 'accord', 6 )
insert into #vehicles values ( 8, 'cobalt', 3 )
insert into #vehicles values ( 9, 'corvette', 3 )
insert into #vehicles values ( 10, 'z06', 9 )
go
declare @id int, @rc int, @level int
set @id = 3
set @level = 1
select @id as id, @level as lev into #t
set @rc = @@rowcount
while @rc > 0
begin
insert into #t (id, lev)
select V.id, @level + 1
from #vehicles V
where V.parent in (select id from #t where lev = @level)
set @rc = @@rowcount
set @level = @level + 1
end
select V.id, V.category, V.parent, T.lev
from #vehicles V join #t T on V.id = T.id
February 8, 2008 at 7:15 am
Not to take anything away from Antonio's solution - that's an ITERATIVE process, not a recursive one.
I've seen someone post a RECURSIVE version (using a CTE to get there), but I'd stick with this one - from what I've seen - the iterative version tends to outperform the recursive version.
----------------------------------------------------------------------------------
Your lack of planning does not constitute an emergency on my part...unless you're my manager...or a director and above...or a really loud-spoken end-user..All right - what was my emergency again?
February 8, 2008 at 12:13 pm
the technique doesn't use recursive calls (a process/method calling itself) but it does use recursion and can be considered recursive by defintion.
from dictionary.com:
re·cur·sive –adjective
1. pertaining to or using a rule or procedure that can be applied repeatedly.
2. Mathematics, Computers. pertaining to or using the mathematical process of recursion: a recursive function; a recursive procedure.
re·cur·sion –noun
Mathematics, Computers. the process of defining a function or calculating a number by the repeated application of an algorithm.
re·cur·sion
n. Mathematics
1. An expression, such as a polynomial, each term of which is determined by application of a formula to preceding terms.
2. A formula that generates the successive terms of a recursion.
February 8, 2008 at 12:19 pm
..which is fine as the beginning of a definition, but not nearly complete (at least not for the technical definition). A recursive function is one that calls ITSELF to finish: this involves a change in scope (a function called within a function within a function). Something that does the same function a bunch of times in the same execution scope is called iterative.
----------------------------------------------------------------------------------
Your lack of planning does not constitute an emergency on my part...unless you're my manager...or a director and above...or a really loud-spoken end-user..All right - what was my emergency again?
February 8, 2008 at 12:48 pm
a (useful) recursive function uses it's calculation result as input to the recursive call. a recursive function is one technique to perform recursion, but not the only technique. also, any recursive technique is also iterative because iteration's simple definition is "the act of repeating".
my suggestion is an iterative process that uses a recursive algorithm since its calculation results are the input for subsequent processing by the same algorithm.
American Heritage Dictionary
re·cur·sion:
n. Mathematics
1. An expression, such as a polynomial, each term of which is determined by application of a formula to preceding terms.
2. A formula that generates the successive terms of a recursion.
American Heritage Dictionary
it·er·a·tion
n.
1. The act or an instance of iterating; repetition.
2. Mathematics A computational procedure in which a cycle of operations is repeated, often to approximate the desired result more closely.
3. Computer Science
a. The process of repeating a set of instructions a specified number of times or until a specific result is achieved.
b. One cycle of a set of instructions to be repeated: After ten iterations, the program exited the loop.
February 8, 2008 at 12:55 pm
Now we're cooking with grease. I'll buy that one for a dollar (to quote RoboCop)....
----------------------------------------------------------------------------------
Your lack of planning does not constitute an emergency on my part...unless you're my manager...or a director and above...or a really loud-spoken end-user..All right - what was my emergency again?
February 8, 2008 at 1:06 pm
I've had to solve this one numerous times.
A cursor is deadly slow.
A while loop is pretty fast.
A CTE is the fastest, but only by a small margin.
Here are some tests.
Set-up:
use ProofOfConcept
go
drop table hierarchy
go
create table Hierarchy (
ID int primary key,
ParentID int null references dbo.hierarchy(id))
go
insert into dbo.hierarchy (id, parentid)
select structureid, parentstructureid
from ...a real hierarchy table... -- I have an actual table with real hierarchies in it
go
create index IDX_HierarchyUp on dbo.hierarchy (parentid, id)
create index IDX_Hierarchy on dbo.hierarchy (id, parentid)
go
20427 rows in the table
set statistics time on
set statistics io on
declare @TopID_in int -- The top level we want to resolve children for
select @topid_in = 6368
declare @T1 table (
ID int,
ParentID int)
insert into @t1 (id)
select @topid_in
declare @Rows int
select @rows = 1
while @rows > 0
begin
insert into @t1 (id, parentid)
select id, parentid
from dbo.hierarchy with(nolock)
where parentid in
(select id
from @t1)
and id not in
(select id
from @t1)
select @rows = @@rowcount
end
select * from @t1
------------SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 1 ms.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
Table '#4CEB477C'. Scan count 0, logical reads 1, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
(1 row(s) affected)
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
Table '#4CEB477C'. Scan count 2, logical reads 7, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 1, logical reads 8, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Hierarchy'. Scan count 1, logical reads 2, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
(3 row(s) affected)
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
Table '#4CEB477C'. Scan count 2, logical reads 14, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 1, logical reads 12, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Hierarchy'. Scan count 4, logical reads 8, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
(5 row(s) affected)
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
Table '#4CEB477C'. Scan count 2, logical reads 21, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 1, logical reads 14, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Hierarchy'. Scan count 9, logical reads 18, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
(6 row(s) affected)
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
Table '#4CEB477C'. Scan count 2, logical reads 15, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 1, logical reads 2, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Hierarchy'. Scan count 15, logical reads 30, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 16 ms, elapsed time = 2 ms.
(0 row(s) affected)
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
(15 row(s) affected)
Table '#4CEB477C'. Scan count 1, logical reads 1, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
----------------
Returns 15 rows, and gets an accurate hierarchy.
set statistics time on
set statistics io on
declare @TopID_in int -- The top level we want to resolve children for
select @topid_in = 6368
;with HierarchyCTE (ID, ParentID) as
(select id, parentid
from dbo.hierarchy
where id = @topid_in
union all
select hierarchy.id, hierarchy.parentid
from dbo.hierarchy
inner join hierarchycte
on hierarchy.parentid = hierarchycte.id)
select *
from hierarchycte
----------------
SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 1 ms.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
(15 row(s) affected)
Table 'Worktable'. Scan count 2, logical reads 92, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Hierarchy'. Scan count 15, logical reads 32, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 1 ms.
--------------------
Since all the execution times are 1 ms, which can easily be a rounding error, the best measure is the scan counts. The CTE has a total of 15 for the hierarchy table, but the while loop has 32, as well as many more scans of the worktables.
I'm not going to include the cursor version I was handed when I started working with these. It consists of 2 procs and 2 functions. The first proc creates a cursor that calls the second proc, which creates a cursor that calls the first function. The first function calls the second function. The second function calls itself recursively. Resolving the exact hierarchy that I used in the above samples was taking so long that I killed the process after 8 minutes. (When the table only had a few dozen rows of test data, the cursor solution, I'm told, worked just fine and never took more than about 30 seconds to complete running. I seem to have a different definition for "worked just fine" than the person who was telling me this.)
- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread
"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
February 8, 2008 at 1:27 pm
the CTE route is really cool since it calls itself. i only discovered that CTEs are really treated as "expressions" a few days ago so the self-referencing CTE in the second UNION re-evaluates the CTE again and performs the recursion.
unfortunately, some DBMS don't allow self-referencing CTEs so i can't add this technique to my global bag of tricks.
February 11, 2008 at 1:29 am
antonio.collins (2/8/2008)
assuming parentid refers to an id in the same table (self join), you would have to do it with some sort of recursion. here's my suggestion:
create table #vehicles
( id int, category varchar(20), parent int null )
insert into #vehicles values ( 1, 'car', null )
insert into #vehicles values ( 2, 'boat', null )
insert into #vehicles values ( 3, 'chevy', 1 )
insert into #vehicles values ( 4, 'pontiac', 1 )
insert into #vehicles values ( 5, 'searay', 2 )
insert into #vehicles values ( 6, 'honda', 1 )
insert into #vehicles values ( 7, 'accord', 6 )
insert into #vehicles values ( 8, 'cobalt', 3 )
insert into #vehicles values ( 9, 'corvette', 3 )
insert into #vehicles values ( 10, 'z06', 9 )
go
declare @id int, @rc int, @level int
set @id = 3
set @level = 1
select @id as id, @level as lev into #t
set @rc = @@rowcount
while @rc > 0
begin
insert into #t (id, lev)
select V.id, @level + 1
from #vehicles V
where V.parent in (select id from #t where lev = @level)
set @rc = @@rowcount
set @level = @level + 1
end
select V.id, V.category, V.parent, T.lev
from #vehicles V join #t T on V.id = T.id
can you create it like a stored procedure, i want to pass catid as parameter and want to get all the childs in that category and the childs in its sub categories. i dont understand sql syntax much
February 11, 2008 at 12:49 pm
Please provide a copy of the table structure.
(Right click the table in Management Studio, select Script Table as -> CREATE to -> clipboard, then paste that into the forum here.)
If you do so, I can create a proc for it. Without that, I can't.
- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread
"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
February 12, 2008 at 12:20 am
GSquared (2/11/2008)
Please provide a copy of the table structure.(Right click the table in Management Studio, select Script Table as -> CREATE to -> clipboard, then paste that into the forum here.)
If you do so, I can create a proc for it. Without that, I can't.
Actually i want to create a custom control for asp.net, so i want to create three public fields for the control no matter what the rest of the columns are, the required public fields will be PKIDcolumnName, CategoryNameColumnName,ParentIDColumnName and then custom control will generate the endless treeview, and i am gonna add the required javascript to the custom control so that some insertion and deletion operation can be done. so i want to use self-referencing on one table, i want to display all the product categories in hierarchical way, i want to insert delete and update those categories in that view too, so i am going to create an asp.net custom control inherited from webcontrol class. all i want is one generic stored procedure
February 12, 2008 at 7:23 am
In that case, take the CTE example I provided earlier in this thread, or the one in Books Online, and modify it for your tables, and you'll have what you need.
- Gus "GSquared", RSVP, OODA, MAP, NMVP, FAQ, SAT, SQL, DNA, RNA, UOI, IOU, AM, PM, AD, BC, BCE, USA, UN, CF, ROFL, LOL, ETC
Property of The Thread
"Nobody knows the age of the human race, but everyone agrees it's old enough to know better." - Anon
February 13, 2008 at 7:06 am
GSquared (2/12/2008)
In that case, take the CTE example I provided earlier in this thread, or the one in Books Online, and modify it for your tables, and you'll have what you need.
Thank you very much man, how can i improve my t-sql as well as yours?
Viewing 14 posts - 1 through 13 (of 13 total)
You must be logged in to reply to this topic. Login to reply