用SQL得到全排列
时间：2011-01-16 来源：DBFocus
此文一是为了温故而知新，另一个目的是为了在SQL Server 2008中验证各种方案的性能。
出乎意料的是部分实验结果与原文的分析与解释有些出入，有兴趣的朋友可以对照原文自己动手进行实验。
问题描述
在表Elements中存放了7个数，要得到这些数的全排列。
——什么是全排列？eg：有集合{1, 2, 3}，其全排列为：(1, 2, 3)，(1, 3, 2)，(2, 1, 3)，(2, 3, 1)，(3, 1, 2)，(3, 2, 1)
创建Elements表的脚本如下：
create table Elements
(
i int not null primary key
);
insert into Elements
values (1),(2),(3),(4),(5),(6),(7);
解决方案与性能比较
下文所有查询在SQL Server 2008中进行验证。
要对各种方案进行性能比较，我们可以观察查询的逻辑读数量和查询运行时间。
使用如下脚本来观察这些指标：
SET STATISTICS IO ON; SET STATISTICS TIME ON;
由于SQL Server 2008有缓存机制，故在每一次运行查询之前需要清除缓存，使用如下脚本：
DBCC FREEPROCCACHE;
DBCC DROPCLEANBUFFERS;
DBCC FREESYSTEMCACHE('ALL');
解决方案1
select
E1.i, E2.i, E3.i, E4.i, E5.i, E6.i, E7.i
from
Elements as E1,
Elements as E2,
Elements as E3,
Elements as E4,
Elements as E5,
Elements as E6,
Elements as E7
where
E1.i not in (E2.i, E3.i, E4.i, E5.i, E6.i, E7.i)
and
E2.i not in (E1.i, E3.i, E4.i, E5.i, E6.i, E7.i)
and
E3.i not in (E1.i, E2.i, E4.i, E5.i, E6.i, E7.i)
and
E4.i not in (E1.i, E2.i, E3.i, E5.i, E6.i, E7.i)
and
E5.i not in (E1.i, E2.i, E3.i, E4.i, E6.i, E7.i)
and
E6.i not in (E1.i, E2.i, E3.i, E4.i, E5.i, E7.i)
and
E7.i not in (E1.i, E2.i, E3.i, E4.i, E5.i, E6.i);
性能指标：
SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 62 ms.
(5040 row(s) affected)
Table 'Elements'. Scan count 7, logical reads 17326, 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 = 31 ms, elapsed time = 289 ms.
执行计划：
解决方案2
select
E1.i, E2.i, E3.i, E4.i, E5.i, E6.i, E7.i
from
Elements as E1,
Elements as E2,
Elements as E3,
Elements as E4,
Elements as E5,
Elements as E6,
Elements as E7
where
(E1.i + E2.i + E3.i + E4.i + E5.i + E6.i + E7.i) = 28
and
E1.i not in (E2.i, E3.i, E4.i, E5.i, E6.i, E7.i)
and
E2.i not in (E1.i, E3.i, E4.i, E5.i, E6.i, E7.i)
and
E3.i not in (E1.i, E2.i, E4.i, E5.i, E6.i, E7.i)
and
E4.i not in (E1.i, E2.i, E3.i, E5.i, E6.i, E7.i)
and
E5.i not in (E1.i, E2.i, E3.i, E4.i, E6.i, E7.i)
and
E6.i not in (E1.i, E2.i, E3.i, E4.i, E5.i, E7.i)
and
E7.i not in (E1.i, E2.i, E3.i, E4.i, E5.i, E6.i);
性能指标：
SQL Server parse and compile time:
CPU time = 16 ms, elapsed time = 54 ms.
(5040 row(s) affected)
Table 'Elements'. Scan count 7, logical reads 17326, 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 = 78 ms, elapsed time = 252 ms.
执行计划：
基本与解决方案1相似
解决方案2‘
select
E1.i, E2.i, E3.i, E4.i, E5.i, E6.i,
(28 - E1.i - E2.i - E3.i - E4.i - E5.i - E6.i) as i
from
Elements as E1,
Elements as E2,
Elements as E3,
Elements as E4,
Elements as E5,
Elements as E6
where
E1.i not in (E2.i, E3.i, E4.i, E5.i, E6.i)
and
E2.i not in (E1.i, E3.i, E4.i, E5.i, E6.i)
and
E3.i not in (E1.i, E2.i, E4.i, E5.i, E6.i)
and
E4.i not in (E1.i, E2.i, E3.i, E5.i, E6.i)
and
E5.i not in (E1.i, E2.i, E3.i, E4.i, E6.i)
and
E6.i not in (E1.i, E2.i, E3.i, E4.i, E5.i);
性能指标：
SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 37 ms.
(5040 row(s) affected)
Table 'Elements'. Scan count 6, logical reads 7245, 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 = 267 ms.
执行计划：
解决方案2’‘
select
E1.i, E2.i, E3.i, E4.i, E5.i, E6.i,
(28 - E1.i - E2.i - E3.i - E4.i - E5.i - E6.i) as i
from
Elements as E1,
Elements as E2,
Elements as E3,
Elements as E4,
Elements as E5,
Elements as E6
where
E2.i not in (E1.i)
and
E3.i not in (E1.i, E2.i)
and
E4.i not in (E1.i, E2.i, E3.i)
and
E5.i not in (E1.i, E2.i, E3.i, E4.i)
and
E6.i not in (E1.i, E2.i, E3.i, E4.i, E5.i);
性能指标：
SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 52 ms.
(5040 row(s) affected)
Table 'Elements'. Scan count 6, logical reads 7245, 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 = 47 ms, elapsed time = 272 ms.
执行计划：
基本与解决方案2‘相似
解决方案3
With ElementsWithWeight as
(
select
i,
power(2,(i-1)) as wgt
from
Elements
)
select
E1.i, E2.i, E3.i, E4.i, E5.i, E6.i, E7.i
from
ElementsWithWeight as E1,
ElementsWithWeight as E2,
ElementsWithWeight as E3,
ElementsWithWeight as E4,
ElementsWithWeight as E5,
ElementsWithWeight as E6,
ElementsWithWeight as E7
where
(E1.wgt + E2.wgt + E3.wgt + E4.wgt + E5.wgt + E6.wgt + E7.wgt) = 127;性能指标：
SQL Server parse and compile time:
CPU time = 31 ms, elapsed time = 47 ms.
(5040 row(s) affected)
Table 'Elements'. Scan count 13, logical reads 274526, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 0, logical reads 0, 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 = 1949 ms, elapsed time = 1259 ms.
执行计划：
解决方案3’
select
i,
power(2,(i-1)) as wgt
into
#Elements
from
Elements;
select
E1.i, E2.i, E3.i, E4.i, E5.i, E6.i, E7.i
from
#Elements as E1,
#Elements as E2,
#Elements as E3,
#Elements as E4,
#Elements as E5,
#Elements as E6,
#Elements as E7
where
(E1.wgt + E2.wgt + E3.wgt + E4.wgt + E5.wgt + E6.wgt + E7.wgt) = 127;
性能指标：
SQL Server parse and compile time:
CPU time = 15 ms, elapsed time = 58 ms.
(5040 row(s) affected)
Table '#Elements________________000000000002'. Scan count 13, logical reads 274514, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 0, logical reads 0, 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 = 905 ms, elapsed time = 650 ms.
执行计划：
解决方案4
select
a + c
from
(select
a + SUBSTRING(c, i, 1),
STUFF(c, i, 1, '')
from
Elements,
(select
a + SUBSTRING(c, i, 1),
STUFF(c, i, 1, '')
from
Elements,
(select
a + SUBSTRING(c, i, 1),
STUFF(c, i, 1, '')
from
Elements,
(select
a + SUBSTRING(c, i, 1),
STUFF(c, i, 1, '')
from
Elements,
(select
a + SUBSTRING(c, 1, 1),
STUFF(c, i, 1, '')
from
Elements,
(select
SUBSTRING('1234567', i, 1),
STUFF('1234567', i, 1, '')
from
Elements
where
i <= 7
) as T1(a,c)
where
i <= 6
) as T2(a,c)
where
i <= 5
) as T3(a,c)
where
i <= 4
) as T4(a,c)
where
i <= 3
) as T5(a,c)
where
i <= 2
) as T6(a,c);
性能指标：
SQL Server parse and compile time:
CPU time = 16 ms, elapsed time = 35 ms.
(5040 row(s) affected)
Table 'Elements'. Scan count 154, logical reads 1747, 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 = 31 ms, elapsed time = 209 ms.
执行计划：
解决方案4‘
select
SUBSTRING('1234567', a, 1)
+ SUBSTRING(STUFF('1234567', a, 1, ''), b, 1)
+ SUBSTRING(STUFF(STUFF('1234567', a, 1, ''), b, 1, ''), c, 1)
+ SUBSTRING(STUFF(STUFF(STUFF('1234567', a, 1, ''), b, 1, ''), c, 1, ''), d, 1)
+ SUBSTRING(STUFF(STUFF(STUFF(STUFF('1234567', a, 1, ''), b, 1, ''), c, 1, ''), d, 1, ''), e, 1)
+ SUBSTRING(STUFF(STUFF(STUFF(STUFF(STUFF('1234567', a, 1, ''), b, 1, ''), c, 1, ''), d, 1, ''), e, 1, ''), f, 1)
+ STUFF(STUFF(STUFF(STUFF(STUFF(STUFF('1234567', a, 1, ''), b, 1, ''), c, 1, ''), d, 1, ''), e, 1, ''), f, 1, '')
from
(select i as a from Elements where i<=7) as T1,
(select i as b from Elements where i<=6) as T2,
(select i as c from Elements where i<=5) as T3,
(select i as d from Elements where i<=4) as T4,
(select i as e from Elements where i<=3) as T5,
(select i as f from Elements where i<=2) as T6;
性能指标：
SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 40 ms.
(5040 row(s) affected)
Table 'Elements'. Scan count 154, logical reads 1747, 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 = 31 ms, elapsed time = 161 ms.
执行计划：
基本与解决方案4相似
总结
1. 本文最后两个方案是我在看原文之前怎么也想不到的，值得品味
2. 上例中我们是用7个数字来做全排列，大家可按照需要进行扩展
3. 我在对这些查询进行实验和性能比较后的感悟是：直觉和理论分析可能会有偏差，唯一的检验标准是实验。
相关阅读 更多 +
