Задача, которую мы будем рассматривать, известна как многовариантное разбиение множества чисел. Для данного множества чисел 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 — ожидаемые результаты для разбиения на три подмножества.

 

Ожидаемые результаты для разбиения на два подмножества
Рисунок 1. Ожидаемые результаты для разбиения на два подмножества

 

 

Ожидаемые результаты для разбиения на три подмножества
Рисунок 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=; initial catalog=; integrated security=SSPI; enlist=false»). Это также означает, что сборку необходимо создать с минимальным набором разрешений EXTERNAL_ACCESS. Следовательно, сборка должна быть доверенной (подписанной сертификатом или асимметричным ключом, который имеет соответствующее имя входа с нужными разрешениями или — новшество SQL Server 2017 — внесен в белый список с использованием процедуры sp_add_trusted_assembly). В данном случае я для простоты выбираю параметр базы данных TRUSTWORTHY.

Сборка преобразуется в файл 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, поскольку производительность в режиме компиляции в собственном коде, вероятно, станет намного выше.

Листинг 1. Создание таблицы с именем T1
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);
Листинг 2. Создание вспомогательной функции dbo.GetNums
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
Листинг 3. Запись миллиона строк в таблицу Т1
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);
Листинг 4. Включение In-Memory OLTP 
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;
Листинг 5. Решение с курсором
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;
Листинг 6. Распределение в группы
  SET @grp = CASE WHEN @sum1 <= @sum2 THEN 1 ELSE 2 END;
  IF @grp = 1
    SET @sum1 += @qty;
  ELSE
    SET @sum2 += @qty;
Листинг 7. Создание оптимизированной для обработки в памяти таблицы
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);
Листинг 8. Использование оптимизированной в памяти табличной переменной 
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;
Листинг 9. Суммирование величин
  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);
Листинг 10. Многовариантное разбиение с решением на основе курсора 
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;
Листинг 11. Создание типа таблицы для табличной переменной @Groups 
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);
Листинг 12. Измененный программный код решения с курсором
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;
Листинг 13. Решение на основе SQL CLR
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;
            }
        }
    }
}
Листинг 14. Развертывание файла DLL и трех функций в базе данных mwaypart 
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;
Листинг 15. Заполнение тестового массива
                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;
Листинг 16. Часть ключа, соответствующая общему количеству
        SortedList sl = new SortedList();
        for (int i = 1; i <= numgroups; i++)
            sl.Add((SqlDecimal)(i / 10000000000.0), (SqlInt32)i);
Листинг 17. Обновление общего количества элементов
                SqlDecimal key = (SqlDecimal)sl.GetKey(0);
                sl.RemoveAt(0);
                sl.Add((SqlDecimal)(key + resultRow.qty), resultRow.grp);
Купить номер с этой статьей в PDF