Задача, которую мы будем рассматривать, известна как многовариантное разбиение множества чисел. Для данного множества чисел S, представляющего величины или веса, и числа требуемых разбиений, k, требуется разделить величины на k разбиений так, чтобы величины были распределены по разбиениям как можно ровнее.
Кола Черницки из компании Zopa — мой старый знакомый по работе с SQL. В его компании работает прекрасная команда специалистов по базам данных, которые знают толк в задачах по программированию. Кола предложил мне одну из задач, чтобы посмотреть, какой подход к ее решению я выберу в SQL Server. В данной статье будут описаны сама задача и решения на основе как T-SQL, так и CLR.
Задача и выбор алгоритма
Предложенная нам задача известна как многовариантное разбиение множества чисел (http://www.ijcai.org/Proceedings/09/Papers/096.pdf). Для Кола число разбиений было равно двум, но я опишу решения как для k = 2, так и для k >= 2. Кроме того, Кола не требовал, чтобы распределение было оптимальным. Он был бы удовлетворен решением, достаточно близким к оптимальному, при условии, что оно приносит хорошие результаты.
Эта задача относится к тому же семейству задач, что и задача об упаковке в контейнеры (https://en.wikipedia.org/wiki/Bin_packing_problem). Решения, которые гарантируют оптимальное распределение, довольно дорогостоящие и плохо масштабируются. Однако если вы можете частично поступиться оптимальностью распределения, то можно задействовать затратный алгоритм, известный также как метод первого подходящего, имеющий сложность O (n*log n), гораздо лучше, чем у альтернативных решений.
Алгоритм прост:
- просматривать элементы в порядке убывания величины;
- для каждого элемента назначить величину группе с наименьшим общим количеством или первой группе, если общее количество у всех одинаковое.
Согласно статье в Википедии (https://en.wikipedia.org/wiki/Partition_problem), при k = 2 этот затратный алгоритм обеспечивает приближение к оптимальному распределению 7/6. Таким образом, максимальное общее количество среди групп, полученных с помощью затратного алгоритма, меньше или равно максимальному общему количеству среди групп в оптимальном распределении.
Например, при данном множестве S = {7, 5, 6, 4, 8} и k = 2 затратный алгоритм выдает множества A = {4, 5, 8}, B = {6, 7}. Оптимальное распределение A = {4, 5, 6}, B = {7, 8}. Максимум сумм при затратном подходе 17, а в оптимальном случае 15. Действительно, 17 <= 15 * 7/6 (=17,5).
Я искал неитеративные решения с хорошей производительностью, в которых реализован затратный подход в T-SQL, но пока не преуспел. Поэтому в данной статье внимание будет сосредоточено на итеративных решениях с использованием как T-SQL, так и SQL CLR.
Тестовые данные и ожидаемые результаты
Я использую базу данных, именуемую mwaypart, для хранения тестовых данных этой статьи. Выполните следующий программный код, чтобы создать базу данных, если она еще не существует:
SET NOCOUNT ON; IF DB_ID (N'mwaypart') IS NULL CREATE DATABASE mwaypart; GO USE mwaypart;
Используйте программный код листинга 1, чтобы создать таблицу с именем T1, содержащую столбец, именуемый ID, в качестве ключевого и столбец qty для величины, и заполните его малым набором данных для проверки правильности решений.
Обратите внимание на индекс для столбцов qty DESC, id DESC. Индекс содержит величины в порядке, в котором их предполагается обрабатывать с использованием затратного алгоритма: сначала по количеству, по убыванию, затем по ID, по убыванию для разрешения конфликтов.
На рисунке 1 приведены ожидаемые результаты для разбиения на два подмножества, а на рисунке 2 — ожидаемые результаты для разбиения на три подмножества.
.jpg) |
| Рисунок 1. Ожидаемые результаты для разбиения на два подмножества |
.jpg) |
| Рисунок 2. Ожидаемые результаты для разбиения на три подмножества |
Чтобы протестировать ваши решения, необходим большой набор тестовых данных. Для начала выполните программный код листинга 2, чтобы создать вспомогательную функцию dbo.GetNums.
Затем выполните программный код листинга 3, чтобы записать 1 000 000 строк в таблицу T1.
В некоторых решениях, рассматриваемых в данной статье, используются оптимизированные в памяти табличные переменные. Выполните программный код из листинга 4, чтобы активировать выполняющуюся в памяти обработку транзакций в базе данных. Предполагается, что в файловой системе существует папка с именем C:\mwaypart\.
Разбиение на два подмножества с помощью решения на основе курсора
В программном коде листинга 5 реализовано решение разбиения на два подмножества с использованием затратного алгоритма с курсором T-SQL и табличной переменной на локальном диске.
Программный код использует переменную курсора, поэтому нет необходимости закрывать и освобождать его явно; закрытие и освобождение происходит автоматически, когда пакет завершается. Программный код извлекает строки из курсора по одной в локальные переменные в порядке qty, по убыванию, ID, по убыванию. На каждой итерации @sum1 содержит текущее общее количество для группы 1 и @sum2 для группы 2. Переменной @grp присваивается значение 1, если @sum1 меньше или равно @sum2, и значение 2 в противном случае. Если @grp равно 1, текущая величина добавляется к @sum1, в противном случае к @sum2. Это выполняется математически с помощью следующих назначений:
SELECT
@grp = CASE WHEN @sum1 <=
@sum2 THEN 1 ELSE 2 END,
@sum1 += (2 - @grp) * @qty,
@sum2 += (@grp - 1) * @qty;
Выражение 2 — @grp равно 1, когда @grp равно 1, и 0, когда @grp равно 2.
Выражение @grp — 1 равно 0, когда @grp равно 1, и 1, когда @grp равно 2.
Если эта логика кажется вам непонятной, ее можно заменить такой, как в листинге 6.
Затем программный код вставляет строку с текущим ID, количеством и группой в табличную переменную.
Ради повышения эффективности все вставки выполняются в рамках одной транзакции.
Наконец, к табличной переменной направляется запрос, чтобы получить окончательный результат.
Для выполнения этого решения с большим набором тестовых данных с 1 000 000 строк на моем компьютере потребовалось 17 секунд.
Один из способов оптимизировать решение, используя T-SQL, — заменить табличную переменную на локальном диске оптимизированной в памяти. Это позволяет уменьшить затраты на ввод-вывод и устраняет необходимость – в блокировке. Для этого нужно в первую очередь создать оптимизированный для обработки в памяти тип таблицы. Например, как в листинге 7.
Обратите внимание, что в программном коде листинга 7 хеш-индекс не применяется, но вы можете испытать решение с использованием двоичного древовидного индекса (в программном коде он закрыт знаками комментария). В листинге 8 приведено измененное решение, в котором задействована оптимизированная в памяти табличная переменная на основе только что созданного типа таблицы.
Это решение было выполнено на моем компьютере за 12 секунд с хеш-индексом и за 14 секунд с древовидным индексом. Это лучше, чем в первом решении, но преимущество небольшое.
Многовариантное разбиение с решением на основе курсора
Нереально обрабатывать разбиение множества чисел на k подмножеств, где k > 2, с использованием отдельных переменных, содержащих промежуточные величины групп. Одна возможность — использовать табличную переменную, содержащую для групп номер группы (столбец grp) и текущую величину группы (столбец sumqty). Следует индексировать таблицу по (sumqty, grp), чтобы 1 верхняя строка в порядке индекса всегда имела группу, с которой должна быть ассоциирована текущая величина. Ниже приводится программный код, который следует использовать, чтобы определить эту табличную переменную (сначала как таблицу на диске):
DECLARE @Groups AS TABLE ( grp INT NOT NULL, sumqty INT NOT NULL, INDEX idx_grp_sumqty UNIQUE CLUSTERED(sumqty, grp) );
Сначала заполните табличную переменную нулевым количеством для всех групп:
INSERT INTO @Groups(grp, sumqty) SELECT n AS grp, 0 AS sumqty FROM dbo.GetNums(1, @numgroups) AS Nums;
Затем на каждом выполнении цикла вы изменяете верхнюю строку в порядке (sumqty, grp), прибавляя текущую величину к значению sumqty, и записываете новую строку с текущим ID, qty и grp в табличную переменную @Result. Удивительно, но это можно сделать одной инструкцией с использованием CTE и инструкции UPDATE с предложением OUTPUT INTO, например, как в листинге 9.
В листинге 10 приведен полный программный код решения с числом групп 10.
Для выполнения этого решения на моем компьютере потребовалась 31 секунда. Указанное число групп было равно 10, использовался большой набор тестовых данных и табличные переменные на локальном диске.
Чтобы протестировать решение с оптимизированными в памяти табличными переменными, вам также потребуется тип таблицы для табличной переменной @Groups. В листинге 11 приводится программный код для создания такого типа таблицы.
В листинге 12 приведен измененный программный код решения, в котором обе табличные переменные на локальном диске заменены переменными, оптимизированными в памяти. Для выполнения этого программного кода на моем компьютере потребовалось 18 секунд.
Улучшения, достигаемые благодаря использованию оптимизированных в памяти табличных переменных, очевидны, но их нельзя назвать радикальными. По-прежнему остаются довольно значительные затраты, связанные с извлечением записей курсора и итерациями T-SQL. Чтобы получить значительное преимущество, необходимо обратиться к решению на основе CLR.
Решения на основе SQL CLR
Здесь будут представлены три определяемые пользователем функции CLR, возвращающие табличное значение: функция без параметров с именем PartitionTwoWays, которая выполняет разбиение множества чисел на два подмножества, и функции с именами PartitionMultipleWays и PartitionMultipleWays2, которые принимают параметр с именем numgroups с нужным количеством групп и выполняют многовариантное разбиение с использованием двух разных решений.
В листинге 13 приводится полный программный код, определяющий класс, именуемый MultiWayPartitioning, со всеми тремя функциями (в вашем коде следует задать параметр data source в соответствии с вашим экземпляром вместо data source=.\\sql2017).
Обратите внимание, что для передачи вызывающей стороне результирующих строк по мере их доступности используется конструкция yield return. Из-за программной ошибки (https://docs.microsoft.com/en-us/collaborate/connect-redirect) необходимо проинструктировать SQL Server не привязывать соединение в текущую транзакцию. Значит, SqlConnection («context connection=true») задействовать нельзя; вместо него используйте типичную явную клиентскую строку подключения и укажите enlist=false. Ваша полная строка подключения должна выглядеть следующим образом: SqlConnection («data source=
Сборка преобразуется в файл DLL. В листинге 14 приводятся код для его развертывания и три функции в базе данных mwaypart (при необходимости замените путь к файлу DLL).
Теперь несколько слов о программном коде, определяющем класс и функции. Класс начинается с определения структуры, именуемой ResultRow и представляющей результирующую строку, и метода заполнения строк с именем Partition_FillRow для заполнения результирующей строки. Все три функции используют этот метод заполнения строк и задают определение результирующей таблицы (атрибут TableDefinition) — «ID INT, qty INT, grp INT».
Все три функции определяют объект SqlConnection, именуемый conn, на основе указанной выше строки подключения, объект SqlCommand с именем comm на основе запроса SELECT id, qty FROM dbo.T1 ORDER BY qty DESC, id DESC и объект SqlDataReader с именем reader для прохода по строкам результата запроса команды по одной.
Функция PartitionTwoWays подготовлена с использованием кода. NET, но она реализует тот же самый алгоритм, что и решение T-SQL для разбиения множества на две части. Используйте следующий программный код для тестирования функции:
SELECT * FROM dbo.PartitionTwoWays ();
Напомню, что решение T-SQL выполняется в течение 18 секунд с табличной переменной на локальном диске и 12 секунд с оптимизацией в памяти при использовании большого набора тестовых данных на моем компьютере. А функция на основе CLR выполняется за 2 секунды!
В случае многовариантного разбиения функция PartitionMultipleWays определяет тестовый массив для хранения текущей общей величины для группы:
SqlInt32 [] groups = new SqlInt32 [numgroups.Value];
Функция сначала заполняет массив строкой для группы с количеством 0:
for (int i = 0; i < numgroups; i++) groups[i] = 0;
Затем для каждой исходной величины функция отыскивает группу с минимальным общим количеством, проходя по элементам массива, сопоставляя группу текущей строки группе с меньшим количеством, и добавляет текущую величину к общему количеству этой группы (листинг 15).
Используйте следующий программный код для тестирования функции с 10 группами:
SELECT * FROM dbo.PartitionMultipleWays (10);
Этот простой алгоритм для поиска группы с минимальным общим количеством хорошо работает с малым числом групп, но плохо масштабируется для большого числа групп. Для таблицы с 1 000 000 строк при различном числе групп я получил следующее время выполнения:
- 10 групп — 3 секунды;
- 100 групп — 5 секунд;
- 1000 групп — 44 секунд.
Если приходится иметь дело с большим числом групп, полезно заменить простой цикл по массиву, чтобы находить минимум с помощью оптимального альтернативного метода.
Функция PartitionMultipleWays2 обеспечивает оптимальную обработку большого числа групп с использованием объекта SortedList. Список содержит пары ключа (объект) и значения (объект), сортированные по ключу. Его можно использовать для хранения состояний групп с текущим общим количеством группы в качестве ключа и идентификатором группы в качестве значения. Таким образом, элемент в позиции 0 всегда будет группой с минимальным общим количеством — группой, с которой нужно связать следующую исходную величину. Но есть одна сложность: ключи должны быть уникальными и, очевидно, могут существовать состояния, в которых несколько групп имеют одинаковое общее количество. Возможное решение — сохранить в качестве ключа числовое значение в форме q.gggggggggg, где q — текущее общее количество для группы, а gggggggggg — идентификатор группы, разделенный на 10000000000.0. Например, элемент, представляющий общее количество 180 для группы 7, будет представлен ключом 180.0000000007. Таким образом, ключ гарантированно уникален, и вы даже применяете логику разрешения конфликтов для нескольких групп с одинаковым общим количеством, выбирая группу с наименьшим идентификатором.
Функция сначала заполняет список элементами, по одному на группу. Часть ключа, соответствующая общему количеству, изначально равна 0 (листинг 16).
Для каждой исходной величины функция назначает идентификатор группы текущей строки равным идентификатору в позиции 0 в списке:
resultRow.grp = (SqlInt32)sl.GetByIndex (0);
Затем программному коду следовало бы обновить общее количество элементов списка в позиции 0, добавив исходную величину, но объект SortedList не поддерживает обновления ключа; чтобы решить проблему, вы удаляете и добавляете элемент, как показано в листинге 17.
Итак, все готово. Воспользуйтесь следующим программным кодом, чтобы протестировать функцию с 1000 групп:
SELECT * FROM dbo.PartitionMultipleWays2 (1000);
На моем компьютере этот программный код был выполнен за 5 секунд — неплохо по сравнению с 44 секундами, которые потребовались функции PartitionMultipleWays для обработки такого числа групп.
К сожалению, несмотря на все усилия, я не смог найти хорошего неитеративного решения для задачи многовариантного разбиения множества чисел. Но это не означает, что решения не существует. Я продолжу поиски, и вам советую сделать то же самое. Если найдете что-нибудь, обязательно сообщите мне.
Производительность итеративных решений T-SQL на основе курсора ниже, чем у решений на основе CLR из-за больших затрат на выборку курсора и итерации в T-SQL. В SQL Server 2017 скомпилированные в собственном коде модули не поддерживают курсоры. Если поддержка когда-нибудь будет реализована, мы заново опробуем решения T-SQL, поскольку производительность в режиме компиляции в собственном коде, вероятно, станет намного выше.
DROP TABLE IF EXISTS dbo.T1; GO CREATE TABLE dbo.T1 ( id INT NOT NULL CONSTRAINT PK_T1 PRIMARY KEY, qty INT NOT NULL ); CREATE UNIQUE INDEX idx_qtyD_idD ON dbo.T1(qty DESC, id DESC); INSERT INTO dbo.T1(id, qty) VALUES (1, 6), (2, 4), (3, 8), (4, 5), (5, 7);
CREATE OR ALTER FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNS TABLE AS RETURN WITH L0 AS (SELECT c FROM (SELECT 1 UNION ALL SELECT 1) AS D(c)), L1 AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B), L2 AS (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B), L3 AS (SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B), L4 AS (SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B), L5 AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B), Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum FROM L5) SELECT TOP(@high - @low + 1) @low + rownum - 1 AS n FROM Nums ORDER BY rownum; GO
DROP TABLE IF EXISTS dbo.T1; GO DECLARE @numrows AS BIGINT = 1000000, @maxqty AS INT = 1000; CREATE TABLE dbo.T1 ( id INT NOT NULL, qty INT NOT NULL ); INSERT INTO dbo.T1 WITH (TABLOCK) (id, qty) SELECT n, ABS(CHECKSUM(NEWID())) % @maxqty + 1 AS qty FROM dbo.GetNums(1, @numrows); ALTER TABLE dbo.T1 ADD CONSTRAINT PK_T1 PRIMARY KEY(id); CREATE UNIQUE INDEX idx_qtyD_idD ON dbo.T1(qty DESC, id DESC);
ALTER DATABASE mwaypart ADD FILEGROUP mwaypart_MO CONTAINS MEMORY_OPTIMIZED_DATA; ALTER DATABASE mwaypart ADD FILE ( NAME = mwaypart_dir, FILENAME = 'C:\mwaypart\mwaypart_dir' ) TO FILEGROUP mwaypart_MO;
SET NOCOUNT ON; DECLARE @Result AS TABLE ( id INT NOT NULL, qty INT NOT NULL, grp INT NOT NULL, INDEX idx_qtyD_idD UNIQUE CLUSTERED(qty DESC, id DESC) ); DECLARE @id AS INT, @qty AS INT, @grp AS INT, @sum1 AS INT = 0, @sum2 AS INT = 0, @C AS cursor; SET @C = FORWARD_ONLY STATIC READ_ONLY FOR SELECT id, qty FROM dbo.T1 ORDER BY qty DESC, id DESC; OPEN @C; FETCH NEXT FROM @C INTO @id, @qty; BEGIN TRAN; WHILE @@FETCH_STATUS = 0 BEGIN SELECT @grp = CASE WHEN @sum1 <= @sum2 THEN 1 ELSE 2 END, @sum1 += (2 - @grp) * @qty, @sum2 += (@grp - 1) * @qty; INSERT INTO @Result(id, qty, grp) VALUES(@id, @qty, @grp); FETCH NEXT FROM @C INTO @id, @qty; END; COMMIT TRAN; SELECT id, qty, grp FROM @Result;
SET @grp = CASE WHEN @sum1 <= @sum2 THEN 1 ELSE 2 END; IF @grp = 1 SET @sum1 += @qty; ELSE SET @sum2 += @qty;
DROP TYPE IF EXISTS TYPE_mwaypart; GO CREATE TYPE dbo.TYPE_mwaypart AS TABLE ( id INT NOT NULL, qty INT NOT NULL, grp INT NOT NULL, -- INDEX idx_qtyD_idD UNIQUE NONCLUSTERED(qty DESC, id DESC) INDEX idx_id NONCLUSTERED HASH (id) WITH (BUCKET_COUNT = 1048576) ) WITH (MEMORY_OPTIMIZED = ON);
SET NOCOUNT ON; DECLARE @Result AS TYPE_mwaypart; DECLARE @id AS INT, @qty AS INT, @grp AS INT, @sum1 AS INT = 0, @sum2 AS INT = 0, @C AS cursor; SET @C = FORWARD_ONLY STATIC READ_ONLY FOR SELECT id, qty FROM dbo.T1 ORDER BY qty DESC, id DESC; OPEN @C; FETCH NEXT FROM @C INTO @id, @qty; BEGIN TRAN; WHILE @@FETCH_STATUS = 0 BEGIN SELECT @grp = CASE WHEN @sum1 <= @sum2 THEN 1 ELSE 2 END, @sum1 += (2 - @grp) * @qty, @sum2 += (@grp - 1) * @qty; INSERT INTO @Result(id, qty, grp) VALUES(@id, @qty, @grp); FETCH NEXT FROM @C INTO @id, @qty; END; COMMIT TRAN; SELECT id, qty, grp FROM @Result;
WITH C AS ( SELECT TOP (1) grp, sumqty FROM @Groups ORDER BY sumqty, grp ) UPDATE C SET sumqty += @qty OUTPUT @id, @qty, inserted.grp INTO @Result(id, qty, grp);
SET NOCOUNT ON; DECLARE @Groups AS TABLE ( grp INT NOT NULL, sumqty INT NOT NULL, INDEX idx_grp_sumqty UNIQUE CLUSTERED(sumqty, grp) ); DECLARE @Result AS TABLE ( id INT NOT NULL, qty INT NOT NULL, grp INT NOT NULL, INDEX idx_qtyD_idD UNIQUE CLUSTERED(qty DESC, id DESC) ); DECLARE @id AS INT, @qty AS INT, @numgroups AS INT = 10, @C AS cursor; INSERT INTO @Groups(grp, sumqty) SELECT n AS grp, 0 AS sumqty FROM dbo.GetNums(1, @numgroups) AS Nums; SET @C = FORWARD_ONLY STATIC READ_ONLY FOR SELECT id, qty FROM dbo.T1 ORDER BY qty DESC, id DESC; OPEN @C; FETCH NEXT FROM @C INTO @id, @qty; BEGIN TRAN; WHILE @@FETCH_STATUS = 0 BEGIN WITH C AS ( SELECT TOP (1) grp, sumqty FROM @Groups ORDER BY sumqty, grp ) UPDATE C SET sumqty += @qty OUTPUT @id, @qty, inserted.grp INTO @Result(id, qty, grp); FETCH NEXT FROM @C INTO @id, @qty; END; COMMIT TRAN; SELECT id, qty, grp FROM @Result;
DROP TYPE IF EXISTS TYPE_mwaygroups; GO CREATE TYPE dbo.TYPE_mwaygroups AS TABLE ( grp INT NOT NULL, sumqty INT NOT NULL, INDEX idx_grp_sumqty UNIQUE NONCLUSTERED(sumqty, grp) ) WITH (MEMORY_OPTIMIZED = ON);
SET NOCOUNT ON; DECLARE @Groups AS TYPE_mwaygroups, @Result AS TYPE_mwaypart; DECLARE @id AS INT, @qty AS INT, @numgroups AS INT = 10, @C AS cursor; INSERT INTO @Groups(grp, sumqty) SELECT n AS grp, 0 AS sumqty FROM dbo.GetNums(1, @numgroups) AS Nums; SET @C = FORWARD_ONLY STATIC READ_ONLY FOR SELECT id, qty FROM dbo.T1 ORDER BY qty DESC, id DESC; OPEN @C; FETCH NEXT FROM @C INTO @id, @qty; BEGIN TRAN; WHILE @@FETCH_STATUS = 0 BEGIN WITH C AS ( SELECT TOP (1) grp, sumqty FROM @Groups ORDER BY sumqty, grp ) UPDATE C SET sumqty += @qty OUTPUT @id, @qty, inserted.grp INTO @Result(id, qty, grp); FETCH NEXT FROM @C INTO @id, @qty; END; COMMIT TRAN; SELECT id, qty, grp FROM @Result;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Data;
using System.Data.SqlClient;
using System.Data.SqlTypes;
using Microsoft.SqlServer.Server;
public partial class MultiWayPartitioning
{
private struct ResultRow
{
public SqlInt32 id;
public SqlInt32 qty;
public SqlInt32 grp;
}
public static void Partition_FillRow(Object obj, out SqlInt32 id, out SqlInt32 qty, out SqlInt32 grp)
{
ResultRow resultRow = (ResultRow)obj;
id = resultRow.id;
qty = resultRow.qty;
grp = resultRow.grp;
}
[SqlFunction(
DataAccess = DataAccessKind.Read,
FillRowMethodName = "Partition_FillRow",
TableDefinition = "id INT, qty INT, grp INT")]
public static IEnumerable PartitionTwoWays()
{
using (SqlConnection conn = new SqlConnection("data source=.\\sql2017;initial catalog=mwaypart;integrated security=SSPI;enlist=false"))
{
SqlCommand comm = new SqlCommand();
comm.Connection = conn;
comm.CommandText = "SELECT id, qty FROM dbo.T1 ORDER BY qty DESC, id DESC;";
conn.Open();
SqlDataReader reader = comm.ExecuteReader();
ResultRow resultRow = new ResultRow();
SqlInt32 sum1 = 0;
SqlInt32 sum2 = 0;
while (reader.Read())
{
resultRow.id = reader.GetSqlInt32(0);
resultRow.qty = reader.GetSqlInt32(1);
resultRow.grp = sum1 <= sum2 ? 1 : 2;
sum1 += (2 - resultRow.grp) * resultRow.qty;
sum2 += (resultRow.grp - 1) * resultRow.qty;
yield return resultRow;
}
}
}
[SqlFunction(
DataAccess = DataAccessKind.Read,
FillRowMethodName = "Partition_FillRow",
TableDefinition = "id INT, qty INT, grp INT")]
public static IEnumerable PartitionMultipleWays(SqlInt32 numgroups)
{
SqlInt32[] groups = new SqlInt32[numgroups.Value];
for (int i = 0; i < numgroups; i++)
groups[i] = 0;
using (SqlConnection conn = new SqlConnection("data source=.\\sql2017;initial catalog=mwaypart;integrated security=SSPI;enlist=false"))
{
SqlCommand comm = new SqlCommand();
comm.Connection = conn;
comm.CommandText = "SELECT id, qty FROM dbo.T1 ORDER BY qty DESC, id DESC;";
conn.Open();
SqlDataReader reader = comm.ExecuteReader();
ResultRow resultRow = new ResultRow();
while (reader.Read())
{
resultRow.id = reader.GetSqlInt32(0);
resultRow.qty = reader.GetSqlInt32(1);
resultRow.grp = 1;
for (int i = 2; i <= numgroups; i++)
if (groups[i - 1] < groups[resultRow.grp.Value - 1])
resultRow.grp = i;
groups[resultRow.grp.Value - 1] += resultRow.qty;
yield return resultRow;
}
}
}
[SqlFunction(
DataAccess = DataAccessKind.Read,
FillRowMethodName = "Partition_FillRow",
TableDefinition = "id INT, qty INT, grp INT")]
public static IEnumerable PartitionMultipleWays2(SqlInt32 numgroups)
{
SortedList sl = new SortedList();
for (int i = 1; i <= numgroups; i++)
sl.Add((SqlDecimal)(i / 10000000000.0), (SqlInt32)i);
using (SqlConnection conn = new SqlConnection("data source=.\\sql2017;initial catalog=mwaypart;integrated security=SSPI;enlist=false"))
{
SqlCommand comm = new SqlCommand();
comm.Connection = conn;
comm.CommandText = "SELECT id, qty FROM dbo.T1 ORDER BY qty DESC, id DESC;";
conn.Open();
SqlDataReader reader = comm.ExecuteReader();
ResultRow resultRow = new ResultRow();
while (reader.Read())
{
resultRow.id = reader.GetSqlInt32(0);
resultRow.qty = reader.GetSqlInt32(1);
resultRow.grp = (SqlInt32)sl.GetByIndex(0);
SqlDecimal key = (SqlDecimal)sl.GetKey(0);
sl.RemoveAt(0);
sl.Add((SqlDecimal)(key + resultRow.qty), resultRow.grp);
yield return resultRow;
}
}
}
}
ALTER DATABASE mwaypart SET TRUSTWORTHY ON; DROP FUNCTION IF EXISTS dbo.PartitionTwoWays; DROP FUNCTION IF EXISTS dbo.PartitionMultipleWays; DROP FUNCTION IF EXISTS dbo.PartitionMultipleWays2; DROP ASSEMBLY IF EXISTS MultiWayPartitioning; CREATE ASSEMBLY MultiWayPartitioning FROM 'C:\MultiWayPartitioning\MultiWayPartitioning\bin\Debug\MultiWayPartitioning.dll' WITH PERMISSION_SET = EXTERNAL_ACCESS; GO CREATE FUNCTION dbo.PartitionTwoWays() RETURNS TABLE(id INT, qty INT, grp INT) AS EXTERNAL NAME MultiWayPartitioning.MultiWayPartitioning.PartitionTwoWays; GO CREATE FUNCTION dbo.PartitionMultipleWays(@numgroups AS INT) RETURNS TABLE(id INT, qty INT, grp INT) AS EXTERNAL NAME MultiWayPartitioning.MultiWayPartitioning.PartitionMultipleWays; GO CREATE FUNCTION dbo.PartitionMultipleWays2(@numgroups AS INT) RETURNS TABLE(id INT, qty INT, grp INT) AS EXTERNAL NAME MultiWayPartitioning.MultiWayPartitioning.PartitionMultipleWays2;
resultRow.grp = 1; for (int i = 2; i <= numgroups; i++) if (groups[i - 1] < groups[resultRow.grp.Value - 1]) resultRow.grp = i; groups[resultRow.grp.Value - 1] += resultRow.qty;
SortedList sl = new SortedList(); for (int i = 1; i <= numgroups; i++) sl.Add((SqlDecimal)(i / 10000000000.0), (SqlInt32)i);
SqlDecimal key = (SqlDecimal)sl.GetKey(0); sl.RemoveAt(0); sl.Add((SqlDecimal)(key + resultRow.qty), resultRow.grp);