sql - 生成SQL中的所有组合

Question

我需要在给定的大小@k中生成大小为@n的所有组合。有人可以复习以下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];

Answer 1

返回组合
使用数字表或生成数字的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, @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而是使用位算术一直走下去，这可能会更好。如果有机会，我会尝试一下，看看它如何堆积。
我的性能声明基于没有ORDER BY子句运行的查询。为了清楚起见，此代码正在执行的操作是计算 Num表中 Numbers中设置的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

现在，您可以计算出更大的组合集，而且效率更高。您甚至可以考虑使用 decimal(38, 0)在组合计算中允许更大的中间计算。
其次，您给定的查询未返回正确的结果。例如，使用下面的性能测试中的测试数据，集合1与集合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);

Peter证明了这种“垂直交叉联接”的性能不如简单地编写动态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

推断，最终我的查询会便宜一些（尽管从一开始就是读取），但是不会很长一段时间。要使用集合中的21个项目，已经需要一个数字表，最高可达2097152 ...
这是我最初提出的评论，后来才意识到我的解决方案可以通过实时数字表大幅提高性能：

我喜欢单查询解决方案来解决此类问题，但是，如果您要寻找最佳性能，那么实际的交叉联接是最好的，除非您开始认真处理大量的组合。但是，拥有数十万甚至数百万行的人想要什么？甚至不断增长的读取次数似乎也不是什么大问题，尽管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;

请注意，我将这些值选择为变量以减少测试所有内容所需的时间和内存。服务器仍然执行所有相同的工作。我修改了Peter的版本，使其相似，并删除了不必要的额外内容，因此它们都尽可能地精简。用于这些测试的服务器版本是在VM上运行的 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版本差。但是，它保持相当低且恒定，并且持续时间，CPU和读取次数在N = 21和K = 11附近的中心峰比动态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

结论

动态数字表比包含行的实际表要好，因为要读取大量行数需要大量I / O。最好使用一点CPU。
我的最初测试不够广泛，无法真正显示这两个版本的性能特征。
可以通过使每个JOIN不仅大于前一个项目，而且根据必须容纳多少个项目来限制最大值来改进Peter的版本。例如，一次21个项目中有21个项目，那么21行中只有一个答案（一次所有21个项目），但是在执行计划的早期，动态SQL版本中的中间行集包含诸如“即使没有任何值比“ U”高，第2步中的“ AU”也将在下一个连接处被丢弃。同样，步骤5的中间行集将包含“ ARSTU”，但此时唯一有效的组合是“ ABCDE”。改进后的版本不会在中心出现较低的峰值，因此可能无法将其改善到足以成为明显的赢家，但它至少会变得对称，以使图表不会超过该区域中间的最大值，而会回落接近我的版本的0（请参阅每个查询的峰值的右上角）。

持续时间分析

持续时间（> 100ms）之间的版本之间没有真正的显着差异，直到14项同时获取12项为止。到目前为止，我的版本赢得了30次，而动态SQL版本赢得了43次。
从14•12开始，我的版本速度提高了65倍（59> 100ms），动态SQL版本提高了64倍（60> 100ms）。但是，我的版本一直都比较快，它平均节省了256.5秒的平均时间，而动态SQL版本更快时，节省了80.2秒。
所有试验的平均总持续时间为Erik 270.3秒，Peter 446.2秒。
如果创建了一个查找表来确定要使用哪个版本（为输入选择更快的版本），则所有结果都可以在188.7秒内执行。每次使用最慢的一个将花费527.7秒。

读取分析
持续时间分析显示我的查询赢得了很大但不是太大。当指标切换为读取时，会出现一个截然不同的图景-我的查询平均使用读取的1/10。

在一次读取9项中的9项之前，读取的版本（> 1000）之间没有真正的显着差异。到目前为止，我的版本赢得了30次，而动态SQL版本赢得了17次。
从9•9开始，我的版本使用的读取次数减少了118次（113> 1000），而动态SQL版本使用的读取次数减少了69次（31> 1000）。但是，我的版本一直使用更少的读取次数，平均节省了7590万次读取，而动态SQL版本更快时，则节省了38万次读取。
所有试验的平均总读数为Erik 840万，Peter 84M。
如果创建了一个查找表来确定要使用哪个版本（为输入选择最佳版本），则所有结果都可以在8M次读取中执行。每次使用最差的一次将需要8430万次读取。

我将非常有兴趣看到更新的动态SQL版本的结果，该版本将额外的上限置于如上所述的每个步骤中选择的项目。
附录
我的查询的以下版本比上面列出的性能结果提高了约2.25％。我使用了MIT的HAKMEM位计数方法，并在 Convert(int)的结果上添加了 row_number()，因为它返回了bigint。当然，我希望这是我用于上面所有性能测试以及图表和数据的版本，但是由于它是劳动密集型的，因此我不太可能重做它。

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))