Возвращение комбинаций
Используя таблицу чисел или генерирующий число 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 раза быстрее (как процессора, так и времени):
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.Для ясности, этот код выполняет подсчет количества установленных 1-битов в Num из таблицы Numbers.Это потому, что число используется как своего рода индексатор для выбора элементов набора в текущей комбинации, поэтому число 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);
Питер показал, что это "вертикальное перекрестное соединение" не так просто, как простая запись динамического 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
Экстраполируя, в конце концов мой запрос будет дешевле (хотя и с самого начала в reads), но ненадолго.Для использования 21 предмета в наборе уже требуется таблица чисел, доходящая до 2097152 ...
Вот комментарий, который я первоначально сделал, прежде чем понять, что мое решение будет работать значительно лучше с таблицей чисел на лету:
Мне нравятся решения таких проблем с помощью одного запроса, но если вы ищете лучшую производительность, лучше использовать фактическое перекрестное соединение, если только вы не начинаете работать с серьезно огромным количеством комбинаций,Но что же нужно кому-то с сотнями тысяч или даже миллионами строк?Даже растущее число операций чтения не кажется большой проблемой, хотя 6 миллионов - это много, и оно быстро увеличивается ...
В любом случае.Динамический SQL выигрывает.У меня все еще был красивый запрос.:)
Результаты производительности с таблицей чисел на лету
Когда я изначально писал этот ответ, я сказал:
Обратите внимание, что выможно было бы использовать таблицу чисел на лету , но я не пробовал.
Ну, я попробовал, и в результате получилось, что он работал намного лучше!Вот запрос, который я использовал:
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. Базовые данные для них находятся в другойответ на этой странице .Значения являются результатом 5 запусков каждого запроса при каждом значении K и N, после чего выбрасываются лучшие и худшие значения для каждой метрики и усредняются оставшиеся 3.
По сути, моя версия имеет «плечо»"(в крайнем левом углу диаграммы) при высоких значениях N и низких значениях K, которые делают его работу там хуже, чем у версии динамического SQL.Однако это остается довольно низким и постоянным, и центральный пик около N = 21 и K = 11 намного ниже для Duration, CPU и Reads, чем для динамической версии SQL.
Я включил диаграмму числастрок, которые должен возвращать каждый элемент, чтобы вы могли видеть, как выполняется запрос, сопоставленный с объемом работы.
Пожалуйста, смотрите мой дополнительный ответ на этой странице для полных результатов производительности.Я достиг предела количества сообщений и не смог включить его сюда.(Какие-нибудь идеи, куда еще это поместить?) Чтобы оценить ситуацию с точки зрения результатов моей первой версии, используется тот же формат, что и раньше:
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
Питер
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
Выводы
- Таблицы чисел на лету лучше, чем реальная таблица, содержащая строки, поскольку чтение одной таблицы на огромных счетчиках строк требуетмного ввода / вывода.Лучше использовать небольшой процессор.
- Мои первоначальные тесты не были достаточно широкими, чтобы действительно показать характеристики производительности двух версий.
- Версия Питера может быть улучшена, если каждый JOIN будет не только больше, чем предыдущий элемент, но и ограничит максимальное значение в зависимости от того, сколько еще элементов должно быть вписано в набор.Например, при 21 элементе, взятом по 21 элементу, имеется только один ответ из 21 строки (все 21 элемент по одному разу), но промежуточные наборы строк в динамической версии SQL, в начале плана выполнения, содержат такие комбинации, как "AU "на шаге 2, даже если это будет отброшено при следующем соединении, так как нет доступного значения выше, чем" U ".Точно так же промежуточный набор строк на шаге 5 будет содержать «ARSTU», но единственной допустимой комбинацией в этой точке является «ABCDE».Эта улучшенная версия не будет иметь более низкого пика в центре, поэтому, возможно, не улучшит его настолько, чтобы стать явным победителем, но она, по крайней мере, станет симметричной, так что графики не будут оставаться максимальными после середины региона, но откатятся назадпочти до 0, как моя версия (см. верхний угол пиков для каждого запроса).
Анализ продолжительности
- На самом деле нетзначительная разница между версиями по продолжительности (> 100 мс) до 14 пунктов, взятых по 12 за раз.До этого момента моя версия побеждала 30 раз, а динамическая версия SQL побеждает 43 раза.
- Начиная с 14 • 12, моя версия была быстрее в 65 раз (59> 100 мс), динамическая версия SQL в 64 раза (60> 100 мс).Тем не менее, все время, когда моя версия была быстрее, она сохраняла общую усредненную продолжительность в 256,5 секунд, а когда динамическая версия SQL была быстрее, она экономила 80,2 секунды.
- Общая усредненная продолжительность для всех испытаний составляла Эрик 270,3секунд, Питер 446,2 секунды.
- Если была создана справочная таблица, чтобы определить, какую версию использовать (выбирая более быструю для входов), все результаты могли быть выполнены за 188,7 секунды.Использование самого медленного каждый раз может занять 527,7 секунды.
Reads Analysis
Анализ продолжительности показал, что мой запрос выиграл в значительной, но не слишком большой сумме.Когда метрика переключается на чтение, появляется совсем другая картина - мой запрос использует в среднем 1/10 операций чтения.
- Нет действительно существенной разницы между версиями в чтениях (> 1000)до 9 предметов, взятых 9 одновременно.До этого момента моя версия выигрывала 30 раз, а динамическая версия SQL - 17 раз.
- Начиная с 9 • 9, моя версия использовала меньше операций чтения в 118 раз (113> 1000), а версия динамического SQL - в 69 раз (31> 1000).Тем не менее, все время, когда моя версия использовала меньше операций чтения, она в среднем сохраняла в среднем 75,9 млн операций чтения, а когда динамическая версия SQL работала быстрее, она сохраняла 380 тыс. Операций чтения.M, Peter 84M.
- Если была создана таблица поиска, чтобы определить, какую версию использовать (выбирая лучшую для входных данных), все результаты могут быть выполнены в 8M чтениях.Использование худшего значения каждый раз потребовало бы 84,3 млн. Чтений.
Мне было бы очень интересно увидеть результаты обновленной версии динамического 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))