返回组合
WITH Nums (Num) AS (
SELECT Num
FROM Numbers
WHERE Num BETWEEN 0 AND POWER(2, @n) - 1
), BaseSet AS (
SELECT ind = Power(2, Row_Number() OVER (ORDER BY Value) - 1), *
FROM @set
), Combos AS (
SELECT
ComboID = N.Num,
S.Value,
Cnt = Count(*) OVER (PARTITION BY N.Num)
FROM
Nums N
INNER JOIN BaseSet S ON N.Num & S.ind <> 0
)
SELECT
ComboID,
Value
FROM Combos
WHERE Cnt = @k
ORDER BY ComboID, Value;
这个查询执行得很好,但是我想到了一种优化它的方法,从
Nifty Parallel Bit Count
WITH Nums AS (
SELECT Num, P1 = (Num & 0x55555555) + ((Num / 2) & 0x55555555)
FROM dbo.Numbers
WHERE Num BETWEEN 0 AND POWER(2, @n) - 1
), Nums2 AS (
SELECT Num, P2 = (P1 & 0x33333333) + ((P1 / 4) & 0x33333333)
FROM Nums
), Nums3 AS (
SELECT Num, P3 = (P2 & 0x0f0f0f0f) + ((P2 / 16) & 0x0f0f0f0f)
FROM Nums2
), BaseSet AS (
SELECT ind = Power(2, Row_Number() OVER (ORDER BY Value) - 1), *
FROM @set
)
SELECT
ComboID = N.Num,
S.Value
FROM
Nums3 N
INNER JOIN BaseSet S ON N.Num & S.ind <> 0
WHERE P3 % 255 = @k
ORDER BY ComboID, Value;
我去看了位计数页,认为如果我不做%255,而是一直用位运算,这个性能会更好。当我有机会的时候,我会尝试一下,看看它有多好。
我的性能声明是基于在没有orderby子句的情况下运行的查询。为清楚起见,这段代码所做的是计算中设置的1位的数量
Num
从
Numbers
作为记录,这种使用整数的位模式来选择集合成员的技术就是我创造的“垂直交叉连接”。它有效地导致多组数据的交叉连接,其中集合和交叉连接的数量是任意的。这里,集合的数量是一次获取的项目数。
实际上,通常水平意义上的交叉连接(即使用每个连接将更多列添加到现有列列表中)如下所示:
SELECT
A.Value,
B.Value,
C.Value
FROM
@Set A
CROSS JOIN @Set B
CROSS JOIN @Set C
WHERE
A.Value = 'A'
AND B.Value = 'B'
AND C.Value = 'C'
我上面的查询有效地“交叉连接”了很多次,只需要一个连接。当然,与实际的交叉连接相比,结果是不精确的,但这只是一个小问题。
ALTER FUNCTION dbo.Factorial (
@x bigint
)
RETURNS bigint
AS
BEGIN
IF @x <= 1 RETURN 1
RETURN @x * dbo.Factorial(@x - 1)
END
现在你可以计算更大的组合,而且效率更高。你甚至可以考虑使用
decimal(38, 0)
其次,给定的查询没有返回正确的结果。例如,使用下面性能测试中的测试数据,set 1与set 18相同。看起来您的查询采用了一个环绕的滑动条带:每个集合总是5个相邻的成员,看起来是这样的(我旋转以使其更易于查看):
1 ABCDE
2 ABCD Q
3 ABC PQ
4 AB OPQ
5 A NOPQ
6 MNOPQ
7 LMNOP
8 KLMNO
9 JKLMN
10 IJKLM
11 HIJKL
12 GHIJK
13 FGHIJ
14 EFGHI
15 DEFGH
16 CDEFG
17 BCDEF
18 ABCDE
19 ABCD Q
31 ABCDE
47 ABCD F
55 ABC EF
59 AB DEF
61 A CDEF
62 BCDEF
79 ABCD G
87 ABC E G
91 AB DE G
93 A CDE G
94 BCDE G
103 ABC FG
107 AB D FG
109 A CD FG
110 BCD FG
115 AB EFG
117 A C EFG
118 BC EFG
121 A DEFG
...
为了让感兴趣的人了解位模式->组合事物索引,请注意二进制中的31=11111,模式是ABCDE。二进制中的121是1111001,模式是\uu DEFG(向后映射)。
实数表的性能结果
我在上面的第二个查询中用大集合进行了一些性能测试。我目前没有所用服务器版本的记录。以下是我的测试数据:
DECLARE
@k int,
@n int;
DECLARE @set TABLE (value varchar(24));
INSERT @set VALUES ('A'),('B'),('C'),('D'),('E'),('F'),('G'),('H'),('I'),('J'),('K'),('L'),('M'),('N'),('O'),('P'),('Q');
SET @n = @@RowCount;
SET @k = 5;
DECLARE @combinations bigint = dbo.Factorial(@n) / (dbo.Factorial(@k) * dbo.Factorial(@n - @k));
SELECT CAST(@combinations as varchar(max)) + ' combinations', MaxNumUsedFromNumbersTable = POWER(2, @n);
下面的第二组数字是除以表中第一行的系数,只是为了说明它是如何缩放的。
埃里克
Items CPU Writes Reads Duration | CPU Writes Reads Duration
----- ------ ------ ------- -------- | ----- ------ ------ --------
17â¢5 7344 0 3861 8531 |
18â¢9 17141 0 7748 18536 | 2.3 2.0 2.2
20â¢10 76657 0 34078 84614 | 10.4 8.8 9.9
21â¢11 163859 0 73426 176969 | 22.3 19.0 20.7
21â¢20 142172 0 71198 154441 | 19.4 18.4 18.1
Items CPU Writes Reads Duration | CPU Writes Reads Duration
----- ------ ------ ------- -------- | ----- ------ ------ --------
17â¢5 422 70 10263 794 |
18â¢9 6046 980 219180 11148 | 14.3 14.0 21.4 14.0
20â¢10 24422 4126 901172 46106 | 57.9 58.9 87.8 58.1
21â¢11 58266 8560 2295116 104210 | 138.1 122.3 223.6 131.3
21â¢20 51391 5 6291273 55169 | 121.8 0.1 613.0 69.5
在意识到我的解决方案在使用动态数字表时会表现得更好之前,我最初做了一个评论:
我喜欢这种问题的单查询解决方案,但是如果您希望获得最佳性能,那么实际的交叉连接是最好的,除非您开始处理大量的组合。但是,有人想要几十万甚至数百万排的队伍做什么呢?即使是不断增长的阅读量似乎也不是太大的问题,尽管600万是一个很大的数字,而且它正在迅速变大。。。
不管怎样。动态SQL获胜。我还有一个漂亮的问题。:)
动态数字表的性能结果
当我最初写这个答案时,我说:
on-the-fly numbers table
,但我没试过。
嗯,我试过了,结果是它的表现好多了!以下是我使用的查询:
DECLARE @N int = 16, @K int = 12;
CREATE TABLE #Set (Value char(1) PRIMARY KEY CLUSTERED);
CREATE TABLE #Items (Num int);
INSERT #Items VALUES (@K);
INSERT #Set
SELECT TOP (@N) V
FROM
(VALUES ('A'),('B'),('C'),('D'),('E'),('F'),('G'),('H'),('I'),('J'),('K'),('L'),('M'),('N'),('O'),('P'),('Q'),('R'),('S'),('T'),('U'),('V'),('W'),('X'),('Y'),('Z')) X (V);
GO
DECLARE
@N int = (SELECT Count(*) FROM #Set),
@K int = (SELECT TOP 1 Num FROM #Items);
DECLARE @combination int, @value char(1);
WITH L0 AS (SELECT 1 N UNION ALL SELECT 1),
L1 AS (SELECT 1 N FROM L0, L0 B),
L2 AS (SELECT 1 N FROM L1, L1 B),
L3 AS (SELECT 1 N FROM L2, L2 B),
L4 AS (SELECT 1 N FROM L3, L3 B),
L5 AS (SELECT 1 N FROM L4, L4 B),
Nums AS (SELECT Row_Number() OVER(ORDER BY (SELECT 1)) Num FROM L5),
Nums1 AS (
SELECT Num, P1 = (Num & 0x55555555) + ((Num / 2) & 0x55555555)
FROM Nums
WHERE Num BETWEEN 0 AND Power(2, @N) - 1
), Nums2 AS (
SELECT Num, P2 = (P1 & 0x33333333) + ((P1 / 4) & 0x33333333)
FROM Nums1
), Nums3 AS (
SELECT Num, P3 = (P2 & 0x0F0F0F0F) + ((P2 / 16) & 0x0F0F0F0F)
FROM Nums2
), BaseSet AS (
SELECT Ind = Power(2, Row_Number() OVER (ORDER BY Value) - 1), *
FROM #Set
)
SELECT
@Combination = N.Num,
@Value = S.Value
FROM
Nums3 N
INNER JOIN BaseSet S
ON N.Num & S.Ind <> 0
WHERE P3 % 255 = @K;
Microsoft SQL Server 2008 (RTM) - 10.0.1600.22 (Intel X86) Standard Edition on Windows NT 5.2 <X86> (Build 3790: Service Pack 2) (VM)
在虚拟机上运行。
下面的图表显示了N和K值到21的性能曲线。它们的基础数据在
another answer on this page
. 这些值是在每个K和N值处对每个查询运行5次的结果,然后抛出每个度量的最佳值和最差值,并对剩余的3次进行平均。
基本上,我的版本在高值N和低值K处有一个“肩部”(在图表的最左角),这使得它的性能比动态SQL版本差。但是,这保持了相当低的值和常数,并且N=21和K=11附近的中心峰值在持续时间、CPU和读取方面比动态SQL版本低得多。
请看
my additional answer on this page
完整的性能结果。我达到了后字符限制,不能在这里包括它。(还有其他的想法吗?)为了对比我的第一个版本的性能结果,这里的格式与之前相同:
Items CPU Duration Reads Writes | CPU Duration Reads
----- ----- -------- ------- ------ | ----- -------- -------
17â¢5 354 378 12382 0 |
18â¢9 1849 1893 97246 0 | 5.2 5.0 7.9
20â¢10 7119 7357 369518 0 | 20.1 19.5 29.8
21â¢11 13531 13807 705438 0 | 38.2 36.5 57.0
21â¢20 3234 3295 48 0 | 9.1 8.7 0.0
彼得
Items CPU Duration Reads Writes | CPU Duration Reads
----- ----- -------- ------- ------ | ----- -------- -------
17â¢5 41 45 6433 0 |
18â¢9 2051 1522 214021 0 | 50.0 33.8 33.3
20â¢10 8271 6685 864455 0 | 201.7 148.6 134.4
21â¢11 18823 15502 2097909 0 | 459.1 344.5 326.1
21â¢20 25688 17653 4195863 0 | 626.5 392.3 652.2
结论
-
-
我最初的测试不够广泛,无法真正显示这两个版本的性能特征。
-
工期分析
-
-
从1412开始,我的版本快了65倍(59>100ms),动态SQL版本快了64倍(60>100ms)。然而,在我的版本快的时候,它节省了256.5秒的总平均持续时间,而当动态SQL版本快的时候,它节省了80.2秒。
-
所有试验的总平均持续时间为Erik 270.3秒,Peter 446.2秒。
-
如果创建一个查找表来确定要使用哪个版本(为输入选择更快的版本),那么所有结果都可以在188.7秒内执行。每次使用最慢的一个需要527.7秒。
阅读分析
-
在每次读取9个项目之前,不同版本的读取量没有显著差异(>1000)。到目前为止,我的版本赢了30次,动态SQL版本赢了17次。
-
-
所有试验的总平均阅读量为埃里克840万,彼得840万。
-
如果创建一个查找表来确定要使用哪个版本(为输入选择最佳版本),那么所有结果都可以在8M次读取中执行。每次使用最差的一个需要8430万次阅读。
我非常希望看到一个更新的动态SQL版本的结果,这个版本为我上面描述的每个步骤中选择的项设置了额外的上限。
附录
Convert(int)
关于
row_number()
WITH L0 AS (SELECT 1 N UNION ALL SELECT 1),
L1 AS (SELECT 1 N FROM L0, L0 B),
L2 AS (SELECT 1 N FROM L1, L1 B),
L3 AS (SELECT 1 N FROM L2, L2 B),
L4 AS (SELECT 1 N FROM L3, L3 B),
L5 AS (SELECT 1 N FROM L4, L4 B),
Nums AS (SELECT Row_Number() OVER(ORDER BY (SELECT 1)) Num FROM L5),
Nums1 AS (
SELECT Convert(int, Num) Num
FROM Nums
WHERE Num BETWEEN 1 AND Power(2, @N) - 1
), Nums2 AS (
SELECT
Num,
P1 = Num - ((Num / 2) & 0xDB6DB6DB) - ((Num / 4) & 0x49249249)
FROM Nums1
),
Nums3 AS (SELECT Num, Bits = ((P1 + P1 / 8) & 0xC71C71C7) % 63 FROM Nums2),
BaseSet AS (SELECT Ind = Power(2, Row_Number() OVER (ORDER BY Value) - 1), * FROM #Set)
SELECT
N.Num,
S.Value
FROM
Nums3 N
INNER JOIN BaseSet S
ON N.Num & S.Ind <> 0
WHERE
Bits = @K
我忍不住又展示了一个版本,它通过查找来获取位的计数。它甚至可能比其他版本更快:
DECLARE @BitCounts binary(255) =
0x01010201020203010202030203030401020203020303040203030403040405
+ 0x0102020302030304020303040304040502030304030404050304040504050506
+ 0x0102020302030304020303040304040502030304030404050304040504050506
+ 0x0203030403040405030404050405050603040405040505060405050605060607
+ 0x0102020302030304020303040304040502030304030404050304040504050506
+ 0x0203030403040405030404050405050603040405040505060405050605060607
+ 0x0203030403040405030404050405050603040405040505060405050605060607
+ 0x0304040504050506040505060506060704050506050606070506060706070708;
WITH L0 AS (SELECT 1 N UNION ALL SELECT 1),
L1 AS (SELECT 1 N FROM L0, L0 B),
L2 AS (SELECT 1 N FROM L1, L1 B),
L3 AS (SELECT 1 N FROM L2, L2 B),
L4 AS (SELECT 1 N FROM L3, L3 B),
L5 AS (SELECT 1 N FROM L4, L4 B),
Nums AS (SELECT Row_Number() OVER(ORDER BY (SELECT 1)) Num FROM L5),
Nums1 AS (SELECT Convert(int, Num) Num FROM Nums WHERE Num BETWEEN 1 AND Power(2, @N) - 1),
BaseSet AS (SELECT Ind = Power(2, Row_Number() OVER (ORDER BY Value) - 1), * FROM ComboSet)
SELECT
@Combination = N.Num,
@Value = S.Value
FROM
Nums1 N
INNER JOIN BaseSet S
ON N.Num & S.Ind <> 0
WHERE
@K =
Convert(int, Substring(@BitCounts, N.Num & 0xFF, 1))
+ Convert(int, Substring(@BitCounts, N.Num / 256 & 0xFF, 1))
+ Convert(int, Substring(@BitCounts, N.Num / 65536 & 0xFF, 1))
+ Convert(int, Substring(@BitCounts, N.Num / 16777216, 1))
