Группирование связанных элементов в T-SQL

В этой статье я хочу представить вам интересную задачу, которую предложил мне мой друг, обладатель звания Data Platform MVP Дэвид Маури. Она была связана с конкретным приложением, важным для начинающей компании Sensoria, с которой Дэвид одно время работал, но проблема на самом деле гораздо шире. Мы рассмотрим задачу, в которой требуется группировать связанные элементы, и четыре различных решения T-SQL, в частности их производительность и возможности масштабирования. Решение CLR UDA с впечатляющей производительностью, предложенное Дэвидом, можно найти в его блоге (http://sqlblog.com/blogs/davide_mauri/archive/2017/11/12/lateral-thinking-transitive-closure-clustering-with-sql-server-uda-and-json.aspx).

Задача связана с ненаправленным циклическим графом, представляющим пары связанных узлов, между которыми существует некоторое отношение. В случае Дэвида каждый узел представляет сеанс («прогулку» или «пробежку»), а ребро, соединяющее два узла, означает, что существует определенная минимальная степень сходства между сеансами. Цель состоит в том, чтобы сгруппировать все узлы, связанные прямо или непрямо (транзитивно). Задача проиллюстрирована рисунком 1.

Рисунок 1. Группирование связанных элементов

Обратите внимание, что в этом примере нет прямого соединения между узлами 17 и 25, но они связаны непрямо, или транзитивно, через цепь 17-18-25, поэтому являются частью одной группы. Входной граф представлен таблицей (назовем ее T1) с ребрами. На экране 1 перечислены ребра графа, показанного на рисунке 1.

Экран 1. Ребра графа, показанного на рисунке 1

На выходе должны быть получены идентификаторы отдельных узлов, каждому из которых назначен общий идентификатор группы; например, можно использовать минимальный идентификатор узла в группе в качестве группового идентификатора. На экране 2 приводится предпочтительный вывод для графа, показанного на рисунке 1.

Экран 2. Желательный вывод для графа, показанного на рисунке 1

Другим примером использования может быть идентификация групп продуктов, приобретаемых вместе, чтобы оптимальным образом размещать их на полках магазинов.

Тестовые данные

Используйте код листинга 1 для создания таблицы T1 и заполните его малым набором тестовых данных, представляющим граф, показанный на рисунке 1.

Обратите внимание: ограничение CHECK позволяет убедиться, что id1 меньше, чем id2. Это связано с тем, что граф ненаправленный, и сделано во избежание избыточности. Ненаправленное ребро 17-18 представляет два направленных ребра, 17->18 и 18->17, поэтому нет необходимости хранить в таблице оба. Если вы хотите разрешить вставку строк, где id2 > id1, но все же сохранять их с id1, имеющим меньшее значение, и id2, имеющим большее значение, чтобы исключить дубликаты, то можете поменять местами идентификаторы с помощью триггера INSTEAD OF (листинг 2).

Используйте малый набор тестовых данных для проверки логики и правильности решений. Для проверки производительности и масштабирования решений потребуется больший набор тестовых данных.

Задействуйте программный код листинга 3 для создания вспомогательной функции GetNums, которая возвращает последовательность целых чисел в требуемом диапазоне.

Используйте программный код листинга 4 для заполнения таблицы необходимым минимальным числом групп и строк на группу.

Назначьте собственные значения переменным @minnumgroups и @rowspergroup. Например, чтобы протестировать масштабируемость решения относительно количества групп, испытайте его с различными значениями @minnumgroups при неизменном @rowspergroup. Чтобы проверить масштабируемость решения относительно размера группы, испытайте его с различными значениями @rowspergroup при неизменном @minnumgroups.

И если вам нравятся задачи T-SQL, вы можете попытаться найти собственные решения, прежде чем знакомиться с моими. Желаю вам успеха!

Решение 1. Транзитивное закрытие с табличной переменной

Первое решение заключается в вычислении транзитивного закрытия нашего входного графа. При данном входном графе G (представленном таблицей T1) транзитивное закрытие G — новый направленный граф TC, содержащий ребро для каждой пары узлов, между которыми находится цепь, прямая или транзитивная. На рисунке 2 показано транзитивное закрытие нашего тестового входного графа. Красные стрелки представляют направленные ребра транзитивного закрытия.

Рисунок 2. Транзитивное закрытие

Сначала будет представлено решение для подготовки транзитивного закрытия графа, хранимого в T1, а затем я покажу, как выполнить нашу задачу группирования связанных элементов на его основе.

Приведенный в листинге 5 программный код создает функцию TVF с несколькими инструкциями, именуемую T1TC, которая возвращает табличную переменную (@T1TC) с транзитивным закрытием T1.

Сначала программный код записывает в @T1TC ребро для каждой прямой цепи между двумя узлами из T1. Одна инструкция INSERT записывает все ребра, представляющие цепи id1->id2, а вторая инструкция INSERT записывает все ребра, представляющие цепи id2->id1. Затем начинается выполнение цикла, продолжающееся до тех пор, пока на последнем шаге не будет найдено по крайне мере одно новое ребро. На каждом проходе цикла используйте одну инструкцию INSERT, чтобы добавить к @T1TC новые ребра (x, z), где (x, y) присутствуют в @T1TC, а (y, z) присутствует в T1, и другую инструкцию INSERT, чтобы добавить к @T1TC новые ребра (x, z), где (x, y) присутствует в @T1TC, а (z, y) присутствует в T1. Эти две инструкции обеспечивают обход графа как в правом, так и в левом направлении для поиска новых транзитивных соединений: @T1TC.id1->@T1TC.id2=T1.id1->T1.id2, поэтому @T1TC.id1->T1.id2, и @T1 TC.id1->@T1TC.id2=T1.id2->T1.id1, поэтому @T1TC.id1->T1.id1.

Выполните следующий программный код, чтобы протестировать функцию с малым набором тестовых данных:

SELECT id1, id2
FROM dbo.T1 TC ();

Вы получите выходные данные как на экране 3, представляющие транзитивное закрытие графа в T1.

Экран 3. Транзитивное закрытие графа в T1

Для любого узла x транзитивное закрытие будет иметь ребро (x,) для любого другого узла, который является частью той же группы. К ней, конечно же, относится ребро (x,). Исключение — для x = транзитивное закрытие не имеет ребра (x, x). Поэтому чтобы получить идентификатор группы, нужно сгруппировать данные по id1 и возвратить id1 как идентификатор, а в качестве идентификатора группы — меньшее из значений id1 и MIN (id2). Эта логика реализована в запросе в листинге 6.

Данный запрос формирует предпочтительные выходные данные, показанные на экране 4.

Экран 4. Вывод идентификатора группы

Всегда приятно видеть, что ваше решение возвращает правильный результат. К сожалению, его производительность не очень высокая. При запуске решения после заполнения T1 одной группы со 100 строками (@minnumgroups = 1, @rowspergroup = 100) для его выполнения потребовалось 40 секунд на моем ноутбуке. Это крошечная таблица, почему же такая низкая производительность? Причиной неэффективности стало то обстоятельство, что программный код использует табличную переменную в функции TVF с несколькими инструкциями, и отсутствие векторов плотности и статистики распределения приводит к неудачным оценкам числа элементов и влечет за собой неоптимальные шаги. На рисунке 3 показано сравнение оценки с действительными планами (с использованием обозревателя планов SentryOne) на последней итерации внутреннего запроса 1 в теле цикла, а на рисунке 4 — для внутреннего запроса 2.

Рисунок 3. План для внутреннего запроса 1 Решения 1

Рисунок 4. План для внутреннего запроса 2 Решения 1

Обратите внимание на неточности в оценке количества элементов в обоих случаях. Например, алгоритм вложенных циклов полезен как для соединения между @T1TC и T1, так и для оператора anti-semi join, обрабатывающего предикат NOT EXISTS, только если задействовано очень малое количество строк. Это предполагается оценкой, но на практике дело обстоит иначе. Когда число строк довольно велико, алгоритм хеш-соединения оказывается гораздо более удачным в обоих случаях. Кроме того, обратите внимание, что во втором запросе цикл, выполняющий оператор anti-semi join, просматривает в целом десятки миллионов строк из @T1TC вследствие многочисленных повторных просмотров табличной переменной. Одним словом, решение на основе табличной переменной — неудачный вариант для этого алгоритма.

Решение 2. Транзитивное закрытие с таблицей temp

В Решении 2 реализован тот же алгоритм, что и в Решении 1, но вместо табличной переменной @T1TC используется временная таблица с именем #T1TC. Определяемые пользователем функции не поддерживают временные таблицы, поэтому необходимо реализовать решение в хранимой процедуре или как специальный пакет. Программный код листинга 7 демонстрирует второй вариант.

Время выполнения для Решения 2 значительно лучше, чем для Решения 1. Например, при одной группе со 100 строками Решение 2 завершается менее чем за секунду, в отличие от 40 секунд для Решения 1. На рисунках 5 и 6 приведено сравнение оценочного и действительного планов запроса для последнего выполнения внутренних запросов 1 и 2 цикла соответственно.

Рисунок 5. План для внутреннего запроса 1 Решения 2

Рисунок 6. План для внутреннего запроса 2 Решения 2

Обратите внимание, насколько точнее оценки количества элементов на этот раз, а также на то обстоятельство, что оптимизатор выбрал хеш-соединения вместо оператора Loop Join как для соединений между временной таблицей и T1, так и для оператора anti-semi join, используемого для обработки предиката NOT EXISTS.

Решение 2 действительно гораздо эффективнее, чем Решение 1, но ему свойственны недостатки производительности. Имея группу из N элементов, транзитивное закрытие такой группы имеет (1 + 2 + … + N-1) x 2 = N^2 — N ребер. Например, при наличии 10 элементов транзитивное закрытие имеет 90 ребер. При 100 элементах — 9900. При 1000 элементов — 999 000 ребер. Другими словами, количество ребер увеличивается экспоненциально в соответствии с количеством элементов. Это означает, что решение масштабируется слабо. На рисунке 7 показано время выполнения данного решения в секундах для одной группы с числом строк, увеличивающимся от 100 до 1000.

Рисунок 7. Производительность Решения 2 относительно размера группы

Поэтому, если вы не имеете дела с очень малым количеством групп, Решение 2 нельзя назвать удачным вариантом.

Решение 3. Развертывание связанных узлов

В Решении 2 сначала развернуты все возможные соединения между парами узлов в группе путем создания транзитивного закрытия, а затем оно свертывает их для вычисления идентификатора группы. Результатом становится экспоненциальное масштабирование. В Решении 3 подход с развертыванием-свертыванием не применяется. Вместо этого группы обрабатываются по одной, начиная с одной пары (TOP (1) для необработанной пары ORDER BY id1, id2), а затем развертываются соединения, подобно тому как развертывается иерархия «родитель-потомок» как в левом, так и в правом направлении. Значение id1 из первой пары группы используется как идентификатор группы. Решение записывает обнаруженные узлы с идентификатором группы (значение id1 из первой пары) во временной таблице с именем #G, используя предикат NOT EXISTS для проверки, добавляются ли только необработанные узлы. В листинге 8 приведен полный программный код решения.

На рисунке 8 показана производительность этого решения в зависимости от размера группы. Как мы видим, это решение линейно масштабируется в зависимости от размера группы и может обрабатывать гораздо более многочисленные группы по сравнению с Решением 2.

Рисунок 8. Производительность Решения 3 относительно размера группы

Однако, если увеличить количество групп, сохраняя размеры группы неизменными, время выполнения круто идет вверх линейным образом (детальный график производительности приведен на рисунке 11). Например, вот как выглядит время выполнения для трех прогонов Решения 3 с тремя различными количествами групп:

100 групп со 100 строками в каждой — 1 секунда;
500 групп со 100 строками в каждой — 18 секунд;
1000 групп со 100 строками в каждой — 71 секунда.

После выполнения Решения 3 с большим количеством групп обратитесь к разделу Recent Expensive Queries («Последние ресурсоемкие запросы») в мониторе активности. На рисунке 9 показан снимок экрана этого раздела на моем компьютере.

Рисунок 9. Монитор активности — последние ресурсоемкие запросы

Больше всего ресурсов потребляет, похоже, выделенный запрос TOP (1). Это не первый запрос TOP (1) из Решения 3; в действительности это элемент в конце внешнего цикла. Первый запрос TOP (1) идентифицирует первую пару в первой группе (на основе упорядочения id1, id2). В ней отсутствует предложение WHERE, поскольку пока не обработано ни одного узла. Ресурсоемкость этого запроса очень мала. Запрос TOP (1) в конце внешнего цикла (идентифицированного как ресурсоемкий в мониторе активности) должен найти первую пару следующей необработанной группы и поэтому использует предикат NOT EXISTS, чтобы проверять только строки, где id1 не присутствует в #G. Проблема в том, что по мере продвижения по группе просматривается нарастающее число строк в T1, пока не будет найден первый необработанный элемент. Щелкните правой кнопкой мыши на запросе TOP (1) в мониторе активности, выберите в контекстном меню пункт Show Execution Plan («Показать план выполнения»), а затем откройте этот план в обозревателе планов SentryOne. Полученный мною план показан на рисунке 10.

Рисунок 10. План для запроса TOP (1) в Решении 3

Рисунок 11. Влияние количества групп на производительность Решений 3 и 4

Обозреватель планов предупреждает, что, хотя от запроса ожидается возвращение только одной строки, операция может привести к остаточному вводу-выводу с прочтением приблизительно 100 000 строк. Это число, конечно, зависит от количества групп и размера групп, используемых в процессе тестирования. Главное, что это решение плохо масштабируется при увеличении числа групп.

Решение 4. Развертывание связанных узлов с удалением обработанных ребер

Чтобы обойти недостаток Решения 3 и избежать остаточного ввода-вывода, в Решении 4 сначала выполняется копирование содержимого T1 во временную таблицу с именем #T1, и на каждом проходе обработанные пары удаляются. Для обработки пар текущего прохода, представляющих соединения слева или справа, инструкция DELETE удаляет их из #T1 и использует предложение OUTPUT для записи идентификаторов в табличную переменную с именем @CurIDs. Идентификаторы из @CurIDs, которые пока не существуют в #G, затем записываются в #G с групповым идентификатором текущей группы. Это означает, что запрос TOP (1) в конце внешнего цикла, который идентифицирует первую строку в следующей группе, не нуждается в предложении WHERE и затрагивает только одну строку. Остаточный ввод-вывод отсутствует. Полный программный код решения приведен в листинге 9.

На рисунке 11 сравнивается производительность Решений 3 и 4 и видно, как оба решения масштабируются в зависимости от количества групп.

Итак, победитель очевиден.

В заключение я хочу сказать, что задачи, связанные с графами, часто оказываются сложными, так как легко напасть на плохо масштабируемое решение. Это в полной мере относится и к рассмотренной в данной статье задаче группирования связанных элементов. Производительность Решения 1, основанного на транзитивном закрытии и табличной переменной, очень низкая даже с небольшими объемами данных. Решение 2 на основе транзитивного закрытия и временной таблицы имеет более высокую производительность, но все же масштабируется экспоненциально. Решение 3 обрабатывает группы по одной, начиная с первой пары и развертывая соединения подобно развертыванию иерархий «родитель-потомок». Оно прекрасно масштабируется относительно размера группы, но не так хорошо относительно количества групп, из-за того что запрос, отыскивающий первую пару в группе, должен просмотреть и обработать нарастающее число строк. Решение 4 добавляет измерение в Решение 3, работая с копией данных во временной таблице и удаляя все обработанные строки на каждом проходе. Таким образом значительно улучшается масштабирование относительно количества групп. На рисунке 12 приведен сводный график производительности решений (Решение 1 не показано на графике, так как оно слишком медленное).

Рисунок 12. Сводка производительности (логарифмическая шкала)

Листинг 1. Создание таблицы T1 и заполнение ее данными

SET NOCOUNT ON;
USE tempdb;

DROP TABLE IF EXISTS dbo.T1;
GO
CREATE TABLE dbo.T1
(
  id1 INT NOT NULL,
  id2 INT NOT NULL,
  CONSTRAINT PK_T1 PRIMARY KEY (id1, id2),
  CONSTRAINT CHK_T1_id1_LT_id2 CHECK (id1 < id2) -- since graph is undirected no need to keep both (x, y) and (y, x)
);
-- необходим индекс для производительности некоторых решений
CREATE UNIQUE NONCLUSTERED INDEX idx_id2_id1 ON dbo.T1(id2, id1);
GO
-- Малый набор тестовых данных
TRUNCATE TABLE dbo.T1;
INSERT INTO dbo.T1 VALUES
(24, 25),
(89, 90),
(17, 24),
(18, 24),
(18, 25),
(17, 18);

Листинг 2. Разрешение вставки строк с id2 > id1

DROP TRIGGER IF EXISTS trg_T1_IOINS_id1_LT_id2;
GO
CREATE OR ALTER TRIGGER trg_T1_IOINS_id1_LT_id2 ON dbo.T1 INSTEAD OF INSERT
AS
IF @@ROWCOUNT = 0 RETURN;
SET NOCOUNT ON;
INSERT INTO dbo.T1(id1, id2)
  SELECT
    CASE WHEN id1 < id2 THEN id1 ELSE id2 END AS id1,
    CASE WHEN id1 < id2 THEN id2 ELSE id1 END AS id2
  FROM inserted;
GO
TRUNCATE TABLE dbo.T1;
INSERT INTO dbo.T1 VALUES
(25, 24), -- будет замена
(90, 89), -- будет замена
(17, 24),
(18, 24),
(18, 25),
(18, 17); -- будет замена

Листинг 3. Вспомогательная функция GetNums

DROP FUNCTION IF EXISTS dbo.GetNums;
GO
-- Вспомогательная функция dbo.GetNums
CREATE 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

Листинг 4. Заполнение таблицы необходимым минимальным числом групп и строк на группу

TRUNCATE TABLE dbo.T1;
-- num rows = @minnumgroups * @rowspergroup
DECLARE @minnumgroups AS INT = 1000, @rowspergroup AS INT = 100;

INSERT INTO dbo.T1(id1, id2)
  SELECT id1,
    id1 + ABS(CHECKSUM(NEWID())) % (@rowspergroup + 1 - R.n) + 1 AS id2
  FROM dbo.GetNums(1, @minnumgroups) AS G
    CROSS JOIN dbo.GetNums(1, @rowspergroup) AS R
    CROSS APPLY ( VALUES( (G.n - 1) * (@rowspergroup + 1) + R.n ) ) AS D(id1);

Листинг 5. Создание функции T1TC

DROP FUNCTION IF EXISTS dbo.T1TC;
GO
CREATE OR ALTER FUNCTION dbo.T1TC() RETURNS @T1TC TABLE
(
  id1 INT NOT NULL,
  id2 INT NOT NULL,
  PRIMARY KEY (id1, id2)
)
AS
BEGIN
  DECLARE @added as INT;
  INSERT INTO @T1TC(id1, id2)
    SELECT id1, id2 FROM dbo.T1;
  SET @added = @@ROWCOUNT;
  INSERT INTO @T1TC(id1, id2)
    SELECT id2, id1 FROM dbo.T1
  SET @added += @@ROWCOUNT;
  WHILE @added > 0 BEGIN
    INSERT INTO @T1TC(id1, id2)
      SELECT DISTINCT TC.id1, T1.id2
      FROM @T1TC AS TC
        INNER JOIN dbo.T1
          ON T1.id1 = TC.id2
      WHERE NOT EXISTS
        (SELECT * FROM @T1TC AS TC2
         WHERE TC2.id1 = TC.id1
           AND TC2.id2 = T1.id2)
        AND TC.id1 <> T1.id2;
    SET @added = @@ROWCOUNT;
    INSERT INTO @T1TC(id1, id2)
      SELECT DISTINCT TC.id1, T1.id1
      FROM @T1TC AS TC
        INNER JOIN dbo.T1
          ON T1.id2 = TC.id2
      WHERE NOT EXISTS
        (SELECT * FROM @T1TC AS TC2
         WHERE TC2.id1 = TC.id1
           AND TC2.id2 = T1.id1)
        AND TC.id1 <> T1.id1;
    SET @added += @@ROWCOUNT;
  END
  RETURN;
END
GO

Листинг 6. Получение идентификатора группы

SELECT id1 AS id,
  (SELECT MIN(id) FROM ( VALUES(id1),(MIN(id2)) ) AS D(id)) AS grp
FROM dbo.T1TC()
GROUP BY id1;

Листинг 7. Второй вариант решения

SET NOCOUNT ON;
USE tempdb;
GO
CREATE TABLE #T1TC
(
  id1 INT NOT NULL,
  id2 INT NOT NULL,
  PRIMARY KEY (id1, id2)
)
DECLARE @added as INT;
INSERT INTO #T1TC(id1, id2)
  SELECT id1, id2 FROM dbo.T1;
SET @added = @@ROWCOUNT;
INSERT INTO #T1TC(id1, id2)
  SELECT id2, id1 FROM dbo.T1
SET @added = @added + @@ROWCOUNT;
WHILE @added > 0 BEGIN
  INSERT INTO #T1TC(id1, id2)
    SELECT DISTINCT TC.id1, T1.id2
    FROM #T1TC AS TC
      INNER JOIN dbo.T1
        ON T1.id1 = TC.id2
    WHERE NOT EXISTS
      (SELECT * FROM #T1TC AS TC2
       WHERE TC2.id1 = TC.id1
         AND TC2.id2 = T1.id2)
      AND TC.id1 <> T1.id2;
  SET @added = @@ROWCOUNT;
  INSERT INTO #T1TC(id1, id2)
    SELECT DISTINCT TC.id1, T1.id1
    FROM #T1TC AS TC
      INNER JOIN dbo.T1
        ON T1.id2 = TC.id2
    WHERE NOT EXISTS
      (SELECT * FROM #T1TC AS TC2
       WHERE TC2.id1 = TC.id1
         AND TC2.id2 = T1.id1)
      AND TC.id1 <> T1.id1;
  SET @added = @added + @@ROWCOUNT;
END
SELECT id1 AS id,
  (SELECT MIN(id) FROM ( VALUES(id1),(MIN(id2)) ) AS D(id)) AS grp
FROM #T1TC
GROUP BY id1;
DROP TABLE #T1TC;

Листинг 8. Код решения 3

SET NOCOUNT ON;
USE tempdb;
GO
CREATE TABLE #G
(
  id INT NOT NULL,
  grp INT NOT NULL,
  lvl INT NOT NULL,
  PRIMARY KEY NONCLUSTERED (id),
  UNIQUE CLUSTERED(lvl, id)
);
DECLARE @lvl AS INT = 1, @added AS INT;
INSERT INTO #G(id, grp, lvl)
  SELECT A.id, A.grp, @lvl AS lvl
  FROM ( SELECT TOP (1) id1, id2
         FROM dbo.T1
         ORDER BY id1, id2 ) AS D
    CROSS APPLY ( VALUES(id1, id1),(id2, id1) ) AS A(id, grp);
SET @added = @@ROWCOUNT;
WHILE @added > 0
BEGIN
  WHILE @added > 0
  BEGIN
    SET @lvl += 1;

    INSERT INTO #G(id, grp, lvl)
      SELECT DISTINCT T1.id2 AS id, G.grp, @lvl AS lvl
      FROM #G AS G
        INNER JOIN dbo.T1
          ON G.id = T1.id1
      WHERE lvl = @lvl - 1
        AND NOT EXISTS
          ( SELECT * FROM #G AS G
            WHERE G.id = T1.id2 )


    SET @added = @@ROWCOUNT;
    INSERT INTO #G(id, grp, lvl)
      SELECT DISTINCT T1.id1 AS id, G.grp, @lvl AS lvl
      FROM #G AS G
        INNER JOIN dbo.T1
          ON G.id = T1.id2
      WHERE lvl = @lvl - 1
        AND NOT EXISTS
          ( SELECT * FROM #G AS G
            WHERE G.id = T1.id1 );
    SET @added += @@ROWCOUNT;
  END;
  INSERT INTO #G(id, grp, lvl)
    SELECT A.id, A.grp, @lvl AS lvl
    FROM ( SELECT TOP (1) id1, id2
           FROM dbo.T1
           WHERE NOT EXISTS
             ( SELECT * FROM #G AS G
               WHERE G.id = T1.id1 )
           ORDER BY id1, id2 ) AS D
      CROSS APPLY ( VALUES(id1, id1),(id2, id1) ) AS A(id, grp);
  SET @added = @@ROWCOUNT;
END;
SELECT id, grp
FROM #G;
DROP TABLE #G;

Листинг 9. Код решения 4

SET NOCOUNT ON;
USE tempdb;
GO
SELECT id1, id2
INTO #T1
FROM dbo.T1;
CREATE UNIQUE CLUSTERED INDEX idx_id1_id2 ON #T1(id1, id2);
CREATE UNIQUE NONCLUSTERED INDEX idx_id2_id1 ON #T1(id2, id1);
CREATE TABLE #G
(
  id INT NOT NULL,
  grp INT NOT NULL,
  lvl INT NOT NULL,
  PRIMARY KEY NONCLUSTERED (id),
  UNIQUE CLUSTERED(lvl, id)
);
DECLARE @lvl AS INT = 1, @added AS INT, @id1 AS INT, @id2 AS INT;
DECLARE @CurIds AS TABLE(id INT NOT NULL);
SELECT TOP (1) @id1 = id1, @id2 = id2
FROM #T1
ORDER BY id1, id2;
SET @added = @@ROWCOUNT;
WHILE @added > 0
BEGIN
  INSERT INTO #G(id, grp, lvl) VALUES
    (@id1, @id1, @lvl),
    (@id2, @id1, @lvl);
  DELETE FROM #T1 WHERE id1 = @id1 AND id2 = @id2;
  WHILE @added > 0
  BEGIN
    SET @lvl += 1;
    DELETE FROM @CurIds;
    DELETE FROM T1
      OUTPUT deleted.id2 AS id INTO @CurIds(id)
    FROM #G AS G
      INNER JOIN #T1 AS T1
        ON G.id = T1.id1
    WHERE lvl = @lvl - 1;
    INSERT INTO #G(id, grp, lvl)
      SELECT DISTINCT id, @id1 AS grp, @lvl AS lvl
      FROM @CurIds AS C
      WHERE NOT EXISTS
          ( SELECT * FROM #G AS G
            WHERE G.id = C.id );
    SET @added = @@ROWCOUNT;
    DELETE FROM @CurIds;
    DELETE FROM T1
      OUTPUT deleted.id1 AS id INTO @CurIds(id)
    FROM #G AS G
      INNER JOIN #T1 AS T1
        ON G.id = T1.id2
    WHERE lvl = @lvl - 1;
    INSERT INTO #G(id, grp, lvl)
      SELECT DISTINCT id, @id1 AS grp, @lvl AS lvl
      FROM @CurIds AS C
      WHERE NOT EXISTS
          ( SELECT * FROM #G AS G
            WHERE G.id = C.id );
    SET @added += @@ROWCOUNT;
  END;
  SELECT TOP (1) @id1 = id1, @id2 = id2
  FROM #T1
  ORDER BY id1, id2;
  SET @added = @@ROWCOUNT;
END;
SELECT id, grp
FROM #G;
DROP TABLE #G, #T1;