排序

Question

CREATE TABLE List(Id INT PRIMARY KEY,NextId INT UNIQUE)
INSERT List 
SELECT 1,4 UNION ALL 
SELECT 4,2 UNION ALL 
SELECT 3,1
GO 
DROP TABLE List--List 表存放的是一个链表，要求将其按照链接的顺序排序显示为如下效果
Id          NextId
----------- -----------
3           1
1           4
4           2建议用1万条数据测试，我现在用的方法是先找到链表的头，然后循环插入下一条到一个有自增列的表中，效率太低。

Answer 1

还没人？这可不是SQL版的风格

Answer 2

CREATE TABLE List(Id INT PRIMARY KEY,NextId INT UNIQUE) 
INSERT List 
SELECT 1,4 UNION ALL 
SELECT 4,2 UNION ALL 
SELECT 3,1 
GO 
create function f_getlevel(@id int)
returns int
as
begin
if not exists(select 1 from list where nextid = @id) 
return 0
declare @i int
    set @i = 0
    while exists(select 1 from list where nextid = @id)
    begin
        set @i = @i + 1
        select @id = id from list where nextid = @id    end
    return @i
end
goselect *
from list a
order by dbo.f_getlevel(id)
/*Id          NextId      
----------- ----------- -----------
3           1           0
1           4           1
4           2           2(3 行受影响)
*/
DROP TABLE List 
drop function f_getlevel

Answer 3

CREATE TABLE List(Id INT PRIMARY KEY,NextId INT UNIQUE) 
INSERT List 
SELECT 1,4 UNION ALL 
SELECT 4,2 UNION ALL 
SELECT 3,1 
GO with szx as
(
select id,nextid,lvl=0 from list a where not exists(select 1 from list where nextid=a.id)
union all
select a.id,a.nextid,b.lvl+1 from list a join szx b on a.id=b.nextid
)
select * from szx
/*
id          nextid      lvl
----------- ----------- -----------
3           1           0
1           4           1
4           2           2(3 行受影响)
*/

Answer 4

--这是我现在的写法
CREATE TABLE #Order(OrderId INT IDENTITY(1,1),Id INT UNIQUE,NextId INT UNIQUE,L INT)
DECLARE @l INT SET @l = 1 INSERT #Order(Id,NextId,L)
SELECT Id,NextId,@l FROM List WHERE Id NOT IN(SELECT NextId FROM List)WHILE @@ROWCOUNT > 0
BEGIN
SET @l = @l + 1
INSERT #Order(Id,NextId,L)
SELECT l.Id,l.NextId,@l
FROM List l 
JOIN #Order o ON o.NextId = l.Id
WHERE o.L = @l - 1 
END SELECT * FROM #Order
DROP TABLE #Order
GO 
DROP TABLE List 
DROP FUNCTION f_getlevel

Answer 5

CREATE TABLE List(Id INT PRIMARY KEY,NextId INT UNIQUE) 
INSERT List 
SELECT 1,4 UNION ALL 
SELECT 4,2 UNION ALL 
SELECT 3,1 
GO if object_id('getChain','tf') is not null
drop function getChain
go
create function getChain()
returns @tb table(iid int identity(1,1),id int,nextid int)
as
begin
declare @nextid int
insert @tb select a.id,a.nextid from list a where not exists(select 1 from list where nextid=a.id)
while @@rowcount>0
begin
select top 1 @nextid=nextid from @tb order by iid desc
insert @tb select id,nextid from list where id=@nextid
end
return
end
goselect id,nextid from dbo.getChain()
/*
id          nextid      lvl
----------- ----------- -----------
3           1           0
1           4           1
4           2           2(3 行受影响)
*/
DROP TABLE List 

Answer 6

晕，原来楼主的不是单链，如果节点的子节点比较多的话而且是SQL2005，用CTE递归吧，递归层数可以设为不限制，如果是SQL2000，只能按BOM的处理方式了。

Answer 7

14楼结果贴错了，没有lvl....
select id,nextid from dbo.getChain()
/*
id          nextid
----------- -----------
3           1
1           4
4           2(3 行受影响)
*/

Answer 8

谢谢大家，2005用CTE递归是最好的方法。2000还有更好的方法么？

Answer 9

join 的成本跟你的top desc的成本差不多.还是用事实说话吧.
CREATE TABLE List(Id INT PRIMARY KEY,NextId INT UNIQUE) 
INSERT List 
SELECT TOP 10000 ROW_NUMBER()OVER (ORDER BY a.[object_id]),ROW_NUMBER()OVER (ORDER BY a.[object_id]) +1 FROM sys.columns a,sys.columns b 
GO 
CREATE FUNCTION getChain()
RETURNS @tb TABLE(iid INT IDENTITY(1,1) PRIMARY KEY,Id INT UNIQUE,NextId INT UNIQUE )
AS
BEGIN
    DECLARE @NextId INT
    INSERT @tb SELECT a.Id,a.NextId FROM list a WHERE NOT EXISTS(SELECT 1 FROM list WHERE NextId=a.Id)
    WHILE @@rowcount>0
    BEGIN
        SELECT TOP 1 @NextId=NextId FROM @tb ORDER BY iid DESC
        INSERT @tb SELECT Id,NextId FROM list WHERE Id=@NextId
    END
    RETURN
END
go
CREATE FUNCTION getChain2()
RETURNS @Order TABLE (OrderId INT IDENTITY(1,1)PRIMARY KEY,Id INT UNIQUE,NextId INT UNIQUE,L INT)
AS 
BEGIN 
DECLARE @l INT SET @l = 1  INSERT @Order(Id,NextId,L)
SELECT Id,NextId,@l FROM List WHERE Id NOT IN(SELECT NextId FROM List) WHILE @@ROWCOUNT > 0
BEGIN
SET @l = @l + 1
INSERT @Order(Id,NextId,L)
SELECT l.Id,l.NextId,@l
FROM List l 
JOIN @Order o ON o.NextId = l.Id
WHERE o.L = @l - 1 
END
RETURN  
END 
GO 
SET STATISTICS IO ON 
GO 
SET STATISTICS TIME ON 
GO 
SELECT Id,NextId FROM dbo.getChain()
/*
SQL Server 分析和编译时间: 
   CPU 时间 = 0 毫秒，占用时间 = 1 毫秒。SQL Server 执行时间:
   CPU 时间 = 0 毫秒，占用时间 = 1 毫秒。
SQL Server 分析和编译时间: 
   CPU 时间 = 0 毫秒，占用时间 = 1 毫秒。(10000 行受影响)
表 '#1DE57479'。扫描计数 1，逻辑读取 28 次，物理读取 0 次，预读 8 次，lob 逻辑读取 0 次，lob 物理读取 0 次，lob 预读 0 次。(1 行受影响)SQL Server 执行时间:
   CPU 时间 = 17203 毫秒，占用时间 = 18470 毫秒。
SQL Server 分析和编译时间: 
   CPU 时间 = 0 毫秒，占用时间 = 1 毫秒。SQL Server 执行时间:
   CPU 时间 = 0 毫秒，占用时间 = 1 毫秒。
*/
SELECT Id,NextId FROM dbo.getChain2()
/*
SQL Server 分析和编译时间: 
   CPU 时间 = 0 毫秒，占用时间 = 1 毫秒。SQL Server 执行时间:
   CPU 时间 = 0 毫秒，占用时间 = 1 毫秒。
SQL Server 分析和编译时间: 
   CPU 时间 = 0 毫秒，占用时间 = 1 毫秒。(10000 行受影响)
表 '#22AA2996'。扫描计数 1，逻辑读取 33 次，物理读取 0 次，预读 0 次，lob 逻辑读取 0 次，lob 物理读取 0 次，lob 预读 0 次。(1 行受影响)SQL Server 执行时间:
   CPU 时间 = 15735 毫秒，占用时间 = 19521 毫秒。
SQL Server 分析和编译时间: 
   CPU 时间 = 0 毫秒，占用时间 = 1 毫秒。SQL Server 执行时间:
   CPU 时间 = 0 毫秒，占用时间 = 1 毫秒。*/
GO 
实际的执行计划显示成本为50%-50%

Answer 10

不对,还是我错了.多跑几次的话,会发现join还是比top desc成本高的.

Answer 11

--生成测试数据(11秒)
declare @t table (fId INT PRIMARY KEY,NextId INT UNIQUE) 
declare @rowcount int
set @rowcount=1
while @rowcount<=10000
begin
INSERT @t select @rowcount,@rowcount+1
set @rowcount=@rowcount+1
end
select *,0 orderid into #t from @t order by newid()
--排序(16秒)
declare @i int ,@nextid int
select @i=0,@nextid=nextid from #t t where not exists(select 1 from #t where nextid=t.fid)
while @@rowcount>0
update #t set orderid=@i,@nextid=nextid,@i=@i+1 from #t where fid=@nextid
select * from #t order by fiddrop table #t

Answer 12

CREATE FUNCTION getChain3()
RETURNS @tb TABLE(Id INT UNIQUE,NextId INT UNIQUE )
AS
BEGIN
    DECLARE @NextId INT
    INSERT @tb SELECT a.Id,a.NextId FROM list a WHERE NOT EXISTS(SELECT 1 FROM list WHERE NextId=a.Id)
    select @nextid = id from @tb 
    WHILE @@rowcount>0
    BEGIN
        SELECT @NextId=NextId FROM list where id = @nextid-- ORDER BY iid DESC
        INSERT @tb SELECT Id,NextId FROM list WHERE Id=@NextId
    END
    RETURN
END
goSELECT Id,NextId FROM dbo.getChain3()
/*
SQL Server 分析和编译时间: 
   CPU 时间 = 0 毫秒，占用时间 = 1 毫秒。(10000 行受影响)
表 '#2F10007B'。扫描计数 1，逻辑读取 23 次，物理读取 0 次，预读 0 次，lob 逻辑读取 0 次，lob 物理读取 0 次，lob 预读 0 次。SQL Server 执行时间:
   CPU 时间 = ＊＊＊＊ 毫秒，占用时间 = ＊＊＊＊ 毫秒。
*/

Answer 13

再改一下：
CREATE FUNCTION getChain3()
RETURNS @tb TABLE(Id INT PRIMARY KEY,NextId INT UNIQUE )
AS
BEGIN
    DECLARE @NextId INT
    INSERT @tb SELECT a.Id,a.NextId FROM list a WHERE NOT EXISTS(SELECT 1 FROM list WHERE NextId=a.Id)
    select @nextid = id from @tb 
    WHILE @@rowcount>0
    BEGIN
        SELECT @NextId=NextId FROM list where id = @nextid-- ORDER BY iid DESC
        INSERT @tb SELECT Id,NextId FROM list WHERE Id=@NextId
    END
    RETURN
END
go
SET STATISTICS IO ON 
GO 
SET STATISTICS TIME ON 
GO 
SELECT Id,NextId FROM dbo.getChain()
/*
SQL Server 分析和编译时间: 
   CPU 时间 = 0 毫秒，占用时间 = 252 毫秒。(10000 行受影响)
表 '#1B0907CE'。扫描计数 1，逻辑读取 28 次，物理读取 0 次，预读 0 次，lob 逻辑读取 0 次，lob 物理读取 0 次，lob 预读 0 次。SQL Server 执行时间:
   CPU 时间 = 40594 毫秒，占用时间 = 79591 毫秒。
*/
SELECT Id,NextId FROM dbo.getChain2()
/*
SQL Server 分析和编译时间: 
   CPU 时间 = 0 毫秒，占用时间 = 6 毫秒。(10000 行受影响)
表 '#1ED998B2'。扫描计数 1，逻辑读取 33 次，物理读取 0 次，预读 0 次，lob 逻辑读取 0 次，lob 物理读取 0 次，lob 预读 0 次。SQL Server 执行时间:
   CPU 时间 = 46485 毫秒，占用时间 = 105907 毫秒。*/
SELECT Id,NextId FROM dbo.getChain3()
/*
SQL Server 分析和编译时间: 
   CPU 时间 = 0 毫秒，占用时间 = 1 毫秒。(10000 行受影响)
表 '#34C8D9D1'。扫描计数 1，逻辑读取 20 次，物理读取 0 次，预读 0 次，lob 逻辑读取 0 次，lob 物理读取 0 次，lob 预读 0 次。SQL Server 执行时间:
   CPU 时间 = 35797 毫秒，占用时间 = 70906 毫秒。
*/

Answer 14

楼上的索引查找跟top 1 desc差不多.
但你不用自增列是无法保证插入顺续就是查询返回的顺续的.

Answer 15

28楼把27楼的unique改为primary key反而改错了,结果不对.

Answer 16

--没用主键，是慢了，用上主键，用时2秒
declare  @list  table(Id INT PRIMARY KEY,NextId INT UNIQUE,orderid int)
select top 10000 nextid=identity(int,2,1) into #t from dbo.sysobjects a,dbo.syscolumns b
insert @list select nextid-1,nextid,0 from #t order by newid()declare @i int ,@nextid int
select @i=0,@nextid=nextid from @list t where not exists(select 1 from @list where nextid=t.id)
while @@rowcount>0
    update @list set orderid=@i,@nextid=nextid,@i=@i+1  where id=@nextid
select * from @list order by orderiddrop table #t

Answer 17

谢谢楼上的朋友，到现在为止就两种方法
1.循环，无论是循环插入还是循环更新，效率基本一样。
2.CTE还有其他方法么？