Generate all combinations in SQL
The CUBE extension to a group by clause represents all combinations of the given list. E.g, the following will give all 3-combinations of a 4-element set.
select concat(a,b,c,d)
from (select 'a','b','c','d') as t(a,b,c,d)
group by cube(a,b,c,d)
having len(concat(a,b,c,d)) = 3
Please forgive this extra answer. I ran into the post character limit in my original answer.
Here are the complete averaged numeric performance results for the charts in my answer.
| Erik | Peter
N K | CPU Duration Reads Writes | CPU Duration Reads Writes
-- -- - ----- -------- ------ ------ - ----- -------- ------- ------
1 1 | 0 0 7 0 | 0 0 7 0
2 1 | 0 0 10 0 | 0 0 7 0
2 2 | 0 0 7 0 | 0 0 11 0
3 1 | 0 0 12 0 | 0 0 7 0
3 2 | 0 0 12 0 | 0 0 13 0
3 3 | 5 0 7 0 | 0 0 19 0
4 1 | 0 0 14 0 | 0 0 7 0
4 2 | 0 0 18 0 | 0 0 15 0
4 3 | 0 0 14 0 | 5 0 27 0
4 4 | 0 0 7 0 | 0 0 35 0
5 1 | 5 0 16 0 | 5 0 7 0
5 2 | 0 0 26 0 | 0 0 17 0
5 3 | 0 0 26 0 | 0 0 37 0
5 4 | 0 0 16 0 | 0 0 57 0
5 5 | 0 0 7 0 | 0 0 67 0
6 1 | 0 0 18 0 | 0 0 7 0
6 2 | 5 0 36 0 | 0 0 19 0
6 3 | 0 0 46 0 | 0 0 49 0
6 4 | 0 0 36 0 | 0 0 89 0
6 5 | 5 0 18 0 | 5 0 119 0
6 6 | 0 0 7 0 | 0 0 131 0
7 1 | 5 0 20 0 | 0 0 7 0
7 2 | 0 0 48 0 | 0 0 21 0
7 3 | 0 0 76 0 | 0 0 63 0
7 4 | 0 0 76 0 | 0 0 133 0
7 5 | 0 1 48 0 | 0 1 203 0
7 6 | 5 0 20 0 | 0 1 245 0
7 7 | 5 0 7 0 | 0 3 259 0
8 1 | 5 2 22 0 | 0 4 7 0
8 2 | 0 1 62 0 | 0 0 23 0
8 3 | 0 1 118 0 | 0 0 79 0
8 4 | 0 1 146 0 | 0 1 191 0
8 5 | 5 3 118 0 | 0 1 331 0
8 6 | 5 1 62 0 | 5 2 443 0
8 7 | 0 0 22 0 | 5 3 499 0
8 8 | 0 0 7 0 | 5 3 515 0
9 1 | 0 2 24 0 | 0 0 7 0
9 2 | 5 3 78 0 | 0 0 25 0
9 3 | 5 3 174 0 | 0 1 97 0
9 4 | 5 5 258 0 | 0 2 265 0
9 5 | 5 7 258 0 | 10 4 517 0
9 6 | 5 5 174 0 | 5 5 769 0
9 7 | 0 3 78 0 | 10 4 937 0
9 8 | 0 0 24 0 | 0 3 1009 0
9 9 | 0 1 7 0 | 0 4 1027 0
10 1 | 10 4 26 0 | 0 0 7 0
10 2 | 5 5 96 0 | 0 0 27 0
10 3 | 5 2 246 0 | 0 0 117 0
10 4 | 10 10 426 0 | 10 4 357 0
10 5 | 15 12 510 0 | 5 8 777 0
10 6 | 15 16 426 0 | 10 9 1281 0
10 7 | 10 4 246 0 | 10 9 1701 0
10 8 | 10 5 96 0 | 10 5 1941 0
10 9 | 5 4 26 0 | 10 7 2031 0
10 10 | 5 0 7 0 | 10 7 2051 0
11 1 | 10 8 28 0 | 0 0 7 0
11 2 | 15 11 116 0 | 0 0 29 0
11 3 | 21 24 336 0 | 10 3 139 0
11 4 | 21 18 666 0 | 5 2 469 0
11 5 | 21 20 930 0 | 5 3 1129 0
11 6 | 26 35 930 0 | 15 12 2053 0
11 7 | 20 14 666 0 | 5 25 2977 0
11 8 | 15 9 336 0 | 20 14 3637 0
11 9 | 10 7 116 0 | 21 27 3967 0
11 10 | 10 8 28 0 | 36 34 4086 0
11 11 | 5 8 7 0 | 15 15 4109 0
12 1 | 16 18 30 0 | 5 0 7 0
12 2 | 31 32 138 0 | 0 0 31 0
12 3 | 31 26 446 0 | 10 2 163 0
12 4 | 47 40 996 0 | 10 7 603 0
12 5 | 47 46 1590 0 | 21 17 1593 0
12 6 | 57 53 1854 0 | 31 30 3177 0
12 7 | 41 39 1590 0 | 31 30 5025 0
12 8 | 41 42 996 0 | 42 43 6609 0
12 9 | 31 26 446 0 | 52 52 7607 0
12 10 | 20 19 138 0 | 57 62 8048 0
12 11 | 15 17 30 0 | 72 64 8181 0
12 12 | 15 10 7 0 | 67 38 8217 0
13 1 | 31 32 32 0 | 0 0 7 0
13 2 | 21 25 162 0 | 0 0 33 0
13 3 | 36 34 578 0 | 5 2 189 0
13 4 | 57 65 1436 0 | 10 5 761 0
13 5 | 41 40 2580 0 | 10 10 2191 0
13 6 | 62 56 3438 0 | 31 32 4765 0
13 7 | 62 62 3438 0 | 57 53 8251 0
13 8 | 52 64 2580 0 | 52 47 11710 0
13 9 | 26 28 1436 0 | 93 96 14311 0
13 10 | 31 29 578 0 | 161 104 15891 0
13 11 | 36 35 162 0 | 129 99 16525 0
13 12 | 21 22 32 0 | 156 96 16383 0
13 13 | 26 30 7 0 | 166 98 16411 0
14 1 | 57 53 34 0 | 0 0 7 0
14 2 | 52 50 188 0 | 0 0 35 0
14 3 | 57 60 734 0 | 10 4 217 0
14 4 | 78 76 2008 0 | 15 8 945 0
14 5 | 99 97 4010 0 | 36 34 2947 0
14 6 | 120 125 6012 0 | 41 47 6951 0
14 7 | 125 119 6870 0 | 93 94 12957 0
14 8 | 135 138 6012 0 | 88 98 19821 0
14 9 | 78 153 4010 0 | 234 156 26099 0
14 10 | 94 92 2008 0 | 229 133 30169 0
14 11 | 83 90 734 0 | 239 136 32237 0
14 12 | 47 46 188 0 | 281 176 33031 0
14 13 | 52 53 34 0 | 260 167 32767 0
14 14 | 46 47 7 0 | 203 149 32797 0
15 1 | 83 83 36 0 | 0 0 7 0
15 2 | 145 139 216 0 | 0 2 37 0
15 3 | 104 98 916 0 | 0 2 247 0
15 4 | 135 135 2736 0 | 15 17 1157 0
15 5 | 94 97 6012 0 | 26 27 3887 0
15 6 | 192 188 10016 0 | 57 53 9893 0
15 7 | 187 192 12876 0 | 73 73 19903 0
15 8 | 286 296 12876 0 | 338 230 33123 0
15 9 | 208 207 10016 0 | 354 223 46063 0
15 10 | 140 143 6012 0 | 443 334 56143 0
15 11 | 88 86 2736 0 | 391 273 62219 0
15 12 | 73 72 916 0 | 432 269 65019 0
15 13 | 109 117 216 0 | 317 210 65999 0
15 14 | 156 187 36 0 | 411 277 66279 0
15 15 | 140 142 7 0 | 354 209 65567 0
16 1 | 281 281 38 0 | 0 0 7 0
16 2 | 141 146 246 0 | 0 0 39 0
16 3 | 208 206 1126 0 | 10 4 279 0
16 4 | 187 189 3646 0 | 15 13 1399 0
16 5 | 234 234 8742 0 | 42 42 5039 0
16 6 | 333 337 16022 0 | 83 85 13775 0
16 7 | 672 742 22886 0 | 395 235 30087 0
16 8 | 510 510 25746 0 | 479 305 53041 0
16 9 | 672 675 22886 0 | 671 489 78855 0
16 10 | 489 492 16022 0 | 859 578 101809 0
16 11 | 250 258 8742 0 | 719 487 117899 0
16 12 | 198 202 3646 0 | 745 483 126709 0
16 13 | 119 119 1126 0 | 770 506 130423 0
16 14 | 291 327 246 0 | 770 531 131617 0
16 15 | 156 156 38 0 | 713 451 131931 0
16 16 | 125 139 7 0 | 895 631 132037 0
17 1 | 406 437 40 0 | 0 0 7 0
17 2 | 307 320 278 0 | 0 0 41 0
17 3 | 281 290 1366 0 | 0 3 313 0
17 4 | 307 317 4766 0 | 31 28 1673 0
17 5 | 354 378 12382 0 | 41 45 6433 0
17 6 | 583 582 24758 0 | 130 127 18809 0
17 7 | 839 859 38902 0 | 693 449 43873 0
17 8 | 1177 1183 48626 0 | 916 679 82847 0
17 9 | 1031 1054 48626 0 | 1270 944 131545 0
17 10 | 828 832 38902 0 | 1469 1105 180243 0
17 11 | 672 668 24758 0 | 1535 1114 219217 0
17 12 | 422 422 12382 0 | 1494 991 244047 0
17 13 | 474 482 4766 0 | 1615 1165 256501 0
17 14 | 599 607 1366 0 | 1500 1042 261339 0
17 15 | 223 218 278 0 | 1401 1065 262777 0
17 16 | 229 228 40 0 | 1390 918 263127 0
17 17 | 541 554 7 0 | 1562 1045 263239 0
18 1 | 401 405 42 0 | 0 0 7 0
18 2 | 401 397 312 0 | 0 0 43 0
18 3 | 458 493 1638 0 | 5 6 349 0
18 4 | 583 581 6126 0 | 16 13 1981 0
18 5 | 697 700 17142 0 | 83 130 8101 0
18 6 | 792 799 37134 0 | 156 162 25237 0
18 7 | 1672 1727 63654 0 | 1098 751 62693 0
18 8 | 1598 1601 87522 0 | 1416 1007 126423 0
18 9 | 1849 1893 97246 0 | 2051 1522 214021 0
18 10 | 1963 2083 87522 0 | 2734 2103 311343 0
18 11 | 1411 1428 63654 0 | 2849 2352 398941 0
18 12 | 1042 1048 37134 0 | 3021 2332 462671 0
18 13 | 942 985 17142 0 | 3036 2314 499881 0
18 14 | 656 666 6126 0 | 3052 2177 517099 0
18 15 | 526 532 1638 0 | 2910 2021 523301 0
18 16 | 614 621 312 0 | 3083 2108 525015 0
18 17 | 536 551 42 0 | 2921 2031 525403 0
18 18 | 682 680 7 0 | 3141 2098 525521 0
19 1 | 885 909 44 0 | 0 0 7 0
19 2 | 1411 1498 348 0 | 0 0 45 0
19 3 | 880 887 1944 0 | 5 4 387 0
19 4 | 1119 1139 7758 0 | 26 25 2325 0
19 5 | 1120 1127 23262 0 | 73 72 10077 0
19 6 | 1395 1462 54270 0 | 453 387 33591 0
19 7 | 1875 1929 100782 0 | 1197 838 87941 0
19 8 | 2656 2723 151170 0 | 2255 1616 188803 0
19 9 | 3046 3092 184762 0 | 3317 2568 340053 0
19 10 | 3635 3803 184762 0 | 5171 4041 524895 0
19 11 | 2739 2774 151170 0 | 5577 4574 709737 0
19 12 | 3203 3348 100782 0 | 6182 5194 860987 0
19 13 | 1672 1750 54270 0 | 6458 5561 961849 0
19 14 | 1760 1835 23262 0 | 6177 4964 1016199 0
19 15 | 968 1006 7758 0 | 6266 4331 1039541 0
19 16 | 1099 1134 1944 0 | 6208 4254 1047379 0
19 17 | 995 1037 348 0 | 6385 4366 1049403 0
19 18 | 916 964 44 0 | 6036 4268 1049831 0
19 19 | 1135 1138 7 0 | 6234 4320 1049955 0
20 1 | 1797 1821 46 0 | 0 0 7 0
20 2 | 2000 2029 386 0 | 0 0 47 0
20 3 | 2031 2071 2286 0 | 10 6 427 0
20 4 | 1942 2036 9696 0 | 31 34 2707 0
20 5 | 2104 2161 31014 0 | 88 85 12397 0
20 6 | 2880 2958 77526 0 | 860 554 43675 0
20 7 | 3791 3940 155046 0 | 2026 1405 121285 0
20 8 | 5130 5307 251946 0 | 3823 2731 276415 0
20 9 | 6547 6845 335926 0 | 5380 4148 528445 0
20 10 | 7119 7357 369518 0 | 8271 6685 864455 0
20 11 | 5692 5803 335926 0 | 9557 8029 1234057 0
20 12 | 4734 4850 251946 0 | 11114 9504 1570067 0
20 13 | 3604 3641 155046 0 | 11551 10434 1822097 0
20 14 | 2911 2999 77526 0 | 12317 10822 1977227 0
20 15 | 2115 2134 31014 0 | 12806 10679 2054837 0
20 16 | 2041 2095 9696 0 | 13062 9115 2085935 0
20 17 | 2390 2465 2286 0 | 12807 9002 2095715 0
20 18 | 1765 1788 386 0 | 12598 8601 2098085 0
20 19 | 2067 2143 46 0 | 12578 8626 2098555 0
20 20 | 1640 1663 7 0 | 12932 9064 2098685 0
21 1 | 3374 3425 48 0 | 0 0 7 0
21 2 | 4031 4157 426 0 | 0 1 49 0
21 3 | 3218 3250 2666 0 | 10 5 469 0
21 4 | 3687 3734 11976 0 | 21 25 3129 0
21 5 | 3692 3735 40704 0 | 115 114 15099 0
21 6 | 4859 4943 108534 0 | 963 661 56079 0
21 7 | 6114 6218 232566 0 | 2620 1880 164701 0
21 8 | 8573 8745 406986 0 | 4999 3693 397355 0
21 9 | 11880 12186 587866 0 | 9047 6863 804429 0
21 10 | 13255 13582 705438 0 | 14358 11436 1392383 0
21 11 | 13531 13807 705438 0 | 18823 15502 2097909 0
21 12 | 12244 12400 587866 0 | 21834 18760 2803435 0
21 13 | 9406 9528 406986 0 | 23771 21274 3391389 0
21 14 | 7114 7180 232566 0 | 26677 24296 3798463 0
21 15 | 4869 4961 108534 0 | 26479 23998 4031117 0
21 16 | 4416 4521 40704 0 | 26536 22976 4139739 0
21 17 | 4380 4443 11976 0 | 26490 19107 4180531 0
21 18 | 3265 3334 2666 0 | 25979 17995 4192595 0
21 19 | 3640 3768 426 0 | 26186 17891 4195349 0
21 20 | 3234 3295 48 0 | 25688 17653 4195863 0
21 21 | 3156 3219 7 0 | 26140 17838 4195999 0
Returning Combinations
Using a numbers table or number-generating CTE, select 0 through 2^n - 1. Using the bit positions containing 1s in these numbers to indicate the presence or absence of the relative members in the combination, and eliminating those that don't have the correct number of values, you should be able to return a result set with all the combinations you desire.
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;
This query performs pretty well, but I thought of a way to optimize it, cribbing from the Nifty Parallel Bit Count to first get the right number of items taken at a time. This performs 3 to 3.5 times faster (both CPU and time):
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;
I went and read the bit-counting page and think that this could perform better if I don't do the % 255 but go all the way with bit arithmetic. When I get a chance I'll try that and see how it stacks up.
My performance claims are based on the queries run without the ORDER BY clause. For clarity, what this code is doing is counting the number of set 1-bits in Num from the Numbers table. That's because the number is being used as a sort of indexer to choose which elements of the set are in the current combination, so the number of 1-bits will be the same.
I hope you like it!
For the record, this technique of using the bit pattern of integers to select members of a set is what I've coined the "Vertical Cross Join." It effectively results in the cross join of multiple sets of data, where the number of sets & cross joins is arbitrary. Here, the number of sets is the number of items taken at a time.
Actually cross joining in the usual horizontal sense (of adding more columns to the existing list of columns with each join) would look something like this:
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'
My queries above effectively "cross join" as many times as necessary with only one join. The results are unpivoted compared to actual cross joins, sure, but that's a minor matter.
Critique of Your Code
First, may I suggest this change to your Factorial UDF:
ALTER FUNCTION dbo.Factorial (
@x bigint
)
RETURNS bigint
AS
BEGIN
IF @x <= 1 RETURN 1
RETURN @x * dbo.Factorial(@x - 1)
END
Now you can calculate much larger sets of combinations, plus it's more efficient. You might even consider using decimal(38, 0) to allow larger intermediate calculations in your combination calculations.
Second, your given query does not return the correct results. For example, using my test data from the performance testing below, set 1 is the same as set 18. It looks like your query takes a sliding stripe that wraps around: each set is always 5 adjacent members, looking something like this (I pivoted to make it easier to see):
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
Compare the pattern from my queries:
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
...
Just to drive the bit-pattern -> index of combination thing home for anyone interested, notice that 31 in binary = 11111 and the pattern is ABCDE. 121 in binary is 1111001 and the pattern is A__DEFG (backwards mapped).
Performance Results With A Real Numbers Table
I ran some performance testing with big sets on my second query above. I do not have a record at this time of the server version used. Here's my test data:
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 showed that this "vertical cross join" doesn't perform as well as simply writing dynamic SQL to actually do the CROSS JOINs it avoids. At the trivial cost of a few more reads, his solution has metrics between 10 and 17 times better. The performance of his query decreases faster than mine as the amount of work increases, but not fast enough to stop anyone from using it.
The second set of numbers below is the factor as divided by the first row in the table, just to show how it scales.
Erik
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
Peter
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, eventually my query will be cheaper (though it is from the start in reads), but not for a long time. To use 21 items in the set already requires a numbers table going up to 2097152...
Here is a comment I originally made before realizing that my solution would perform drastically better with an on-the-fly numbers table:
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. :)
Performance Results with an On-The-Fly Numbers Table
When I originally wrote this answer, I said:
Note that you could use an on-the-fly numbers table, but I haven't tried it.
Well, I tried it, and the results were that it performed much better! Here is the query I used:
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;
Note that I selected the values into variables to reduce the time and memory needed to test everything. The server still does all the same work. I modified Peter's version to be similar, and removed unnecessary extras so they were both as lean as possible. The server version used for these tests is 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) running on a VM.
Below are charts showing the performance curves for values of N and K up to 21. The base data for them is in another answer on this page. The values are the result of 5 runs of each query at each K and N value, followed by throwing out the best and worst values for each metric and averaging the remaining 3.
Basically, my version has a "shoulder" (in the leftmost corner of the chart) at high values of N and low values of K that make it perform worse there than the dynamic SQL version. However, this stays fairly low and constant, and the central peak around N = 21 and K = 11 is much lower for Duration, CPU, and Reads than the dynamic SQL version.
I included a chart of the number of rows each item is expected to return so you can see how the query performs stacked up against how big a job it has to do.
Please see my additional answer on this page for the complete performance results. I hit the post character limit and could not include it here. (Any ideas where else to put it?) To put things in perspective against my first version's performance results, here's the same format as before:
Erik
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
Peter
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
Conclusions
- On-the-fly numbers tables are better than a real table containing rows, since reading one at huge rowcounts requires a lot of I/O. It is better to use a little CPU.
- My initial tests weren't broad enough to really show the performance characteristics of the two versions.
- Peter's version could be improved by making each JOIN not only be greater than the prior item, but also restrict the maximum value based on how many more items have to be fit into the set. For example, at 21 items taken 21 at a time, there is only one answer of 21 rows (all 21 items, one time), but the intermediate rowsets in the dynamic SQL version, early in the execution plan, contain combinations such as "AU" at step 2 even though this will be discarded at the next join since there is no value higher than "U" available. Similarly, an intermediate rowset at step 5 will contain "ARSTU" but the only valid combo at this point is "ABCDE". This improved version would not have a lower peak at the center, so possibly not improving it enough to become the clear winner, but it would at least become symmetrical so that the charts would not stay maxed past the middle of the region but would fall back to near 0 as my version does (see the top corner of the peaks for each query).
Duration Analysis
- There is no really significant difference between the versions in duration (>100ms) until 14 items taken 12 at a time. Up to this point, my version wins 30 times and the dynamic SQL version wins 43 times.
- Starting at 14•12, my version was faster 65 times (59 >100ms), the dynamic SQL version 64 times (60 >100ms). However, all the times my version was faster, it saved a total averaged duration of 256.5 seconds, and when the dynamic SQL version was faster, it saved 80.2 seconds.
- The total averaged duration for all trials was Erik 270.3 seconds, Peter 446.2 seconds.
- If a lookup table were created to determine which version to use (picking the faster one for the inputs), all the results could be performed in 188.7 seconds. Using the slowest one each time would take 527.7 seconds.
Reads Analysis
The duration analysis showed my query winning by significant but not overly large amount. When the metric is switched to reads, a very different picture emerges--my query uses on average 1/10th the reads.
- There is no really significant difference between the versions in reads (>1000) until 9 items taken 9 at a time. Up to this point, my version wins 30 times and the dynamic SQL version wins 17 times.
- Starting at 9•9, my version used fewer reads 118 times (113 >1000), the dynamic SQL version 69 times (31 >1000). However, all the times my version used fewer reads, it saved a total averaged 75.9M reads, and when the dynamic SQL version was faster, it saved 380K reads.
- The total averaged reads for all trials was Erik 8.4M, Peter 84M.
- If a lookup table were created to determine which version to use (picking the best one for the inputs), all the results could be performed in 8M reads. Using the worst one each time would take 84.3M reads.
I would be very interested to see the results of an updated dynamic SQL version that puts the extra upper limit on the items chosen at each step as I described above.
Addendum
The following version of my query achieves an improvement of about 2.25% over the performance results listed above. I used MIT's HAKMEM bit-counting method, and added a Convert(int) on the result of row_number() since it returns a bigint. Of course I wish this is the version I had used with for all the performance testing and charts and data above, but it is unlikely I will ever redo it as it was labor-intensive.
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
And I could not resist showing one more version that does a lookup to get the count of bits. It may even be faster than other versions:
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))