生成SQL中的所有组合
我需要在给定的一组@ @中生成size @k的所有组合.有人可以查看以下SQL,并首先确定以下逻辑是否返回预期结果,第二个如果有更好的方法？
/*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在二进制= 22222,模式是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 … 这是我最初发表的一个意见,意识到我的解决方案会在一个动态的数字表格上表现得更好：
|