/*CREATE FUNCTION dbo.Factorial ( @x int )
RETURNS int
AS
BEGIN
DECLARE @value int
IF @x <= 1
SET @value = 1
ELSE
SET @value = @x * dbo.Factorial( @x - 1 )
RETURN @value
END
GO*/
SET NOCOUNT ON;
DECLARE @k int = 5,@n int;
DECLARE @set table ( [value] varchar(24) );
DECLARE @com table ( [index] int );
INSERT @set VALUES ('1'),('2'),('3'),('4'),('5'),('6');
SELECT @n = COUNT(*) FROM @set;
DECLARE @combinations int = dbo.Factorial(@n) / (dbo.Factorial(@k) * dbo.Factorial(@n - @k));
PRINT CAST(@combinations as varchar(max)) + ' combinations';
DECLARE @index int = 1;
WHILE @index <= @combinations
BEGIN
INSERT @com VALUES (@index)
SET @index = @index + 1
END;
WITH [set] as (
SELECT
[value],ROW_NUMBER() OVER ( ORDER BY [value] ) as [index]
FROM @set
)
SELECT
[values].[value],[index].[index] as [combination]
FROM [set] [values]
CROSS JOIN @com [index]
WHERE ([index].[index] + [values].[index] - 1) % (@n) BETWEEN 1 AND @k
ORDER BY
[index].[index];
解决方法
使用数字表或数字生成CTE,选择0到2 ^ n – 1.使用这些数字中包含1的位位置表示组合中存在或不存在相对成员,并消除那些没有正确的数值,你应该能够返回一个结果集与所有你想要的组合.
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开始,首先获得一次所需的正确数量.这样可以快3到3.5倍(cpu和时间)：
WITH Nums AS ( SELECT Num,P1 = (Num & 0x55555555) + ((Num / 2) & 0x55555555) FROM dbo.Numbers WHERE Num BETWEEN 0 AND POWER(2,Nums2 AS ( SELECT Num,P2 = (P1 & 0x33333333) + ((P1 / 4) & 0x33333333) FROM Nums ),Nums3 AS ( SELECT Num,P3 = (P2 & 0x0f0f0f0f) + ((P2 / 16) & 0x0f0f0f0f) FROM Nums2 ),* 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,但是通过比特算术,这可能会更好.当我有机会尝试一下,看看它堆叠起来.
我的性能声明是基于没有ORDER BY子句运行的查询.为了清楚起见,这个代码正在从Numbers表中计数Num中的1位的数目.这是因为该数字被用作一种索引器来选择当前组合中的哪些元素,因此1位的数量将是相同的.
我希望你喜欢它！
为了记录,使用整数的位模式来选择一组的成员的技术是我创造了“垂直交叉连接”.它有效地导致多组数据的交叉连接,其中集合&交叉连接是任意的.这里,套数是一次拍摄的物品数量.
实际上交叉加入通常的横向意义(每个连接添加更多的列到现有的列列表)将看起来像这样：
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'
我上面的查询有效地“交叉连接”多次,只需要一个连接.与实际的交叉连接相比,结果是不受欢迎的,但这是一个小问题.
批评你的代码
首先,我可以建议你对这个UDF的这个修改：
ALTER FUNCTION dbo.Factorial ( @x bigint ) RETURNS bigint AS BEGIN IF @x <= 1 RETURN 1 RETURN @x * dbo.Factorial(@x - 1) END
现在你可以计算出更大的组合,加上更有效率.您甚至可以考虑使用十进制(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,模式是A__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);
彼得表示,这个“垂直交叉连接”并不像简单地编写动态sql那样做,实际上它可以避免CROSS JOIN.他的解决方案以轻微的成本读取更多的10到17倍.随着工作量的增加,他的查询的性能下降速度比我的速度快,但是速度不足以阻止任何人使用它.
下面的第二组数字是除以表中第一行的因子,只是为了显示它如何缩放.
埃里克
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
Extrapolating,最终我的查询将会更便宜(虽然它是从开始读),但不是很长时间.要使用集合中的21个项目已经需要一个数字表,最多可以达到2097152 …
这是我最初发表的一个意见,意识到我的解决方案会在一个动态的数字表格上表现得更好：
I love single-query solutions to problems like this,but if you’re looking for the best performance,an actual cross-join is best,unless you start dealing with serIoUsly huge numbers of combination. But what does anyone want with hundreds of thousands or even millions of rows? Even the growing number of reads don’t seem too much of a problem,though 6 million is a lot and it’s getting bigger fast…
Anyway. Dynamic sql wins. I still had a beautiful query. 原文链接：https://www.f2er.com/mssql/81770.html
