Поиск паросочетаний графов с помощью T-SQL. Часть 2

В первой статье серии о паросочетаниях в графе мы рассмотрели основы теории графов. Если имеется двудольный граф G, например представляющий возможные отношения между соискателями работы и рабочими местами, паросочетание M в G представляет любое подмножество ребер в G, такое, что ни одна вершина не принадлежит более чем одному ребру. Это означает, что соискателю не разрешается занимать более одного рабочего места, а рабочее место может быть занято не более чем одним соискателем. Я использовал таблицу с именем G для представления графа, где столбец x представляет идентификатор соискателя, столбец y — идентификатор рабочего места и ключ, определенный на (x, y). Таблица с именем M использовалась для представления паросочетания в G с одним ключом, определенным на x, и другим, определенным на y.

Я решил подготовить хранимую процедуру с именем MaximalMatching, которая заполняет M с применением наибольшего паросочетания. То есть паросочетанием, которое не может быть расширено путем добавления дополнительных ребер из G. Напомню, что наибольшее паросочетание — не обязательно паросочетание максимальной мощности. Последнее — паросочетание с максимальным возможным числом ребер. На рисунке 1 показаны различные типы паросочетаний.

Рисунок 1. Примеры паросочетания в графе

Практическое применение поиска паросочетания максимальной мощности очевидно: например, максимальная рабочая загрузка агентов. Но каково практическое применение наибольшего паросочетания? Один из примеров — предварительный шаг в поиске паросочетания максимальной мощности. Вы начинаете с наибольшего паросочетания, что довольно просто и недорого, а затем, после нескольких приращений, преобразуете его в паросочетание максимальной мощности. Чем больше начальное наибольшее паросочетание, тем быстрее можно будет совершить преобразование в паросочетание максимальной мощности. Этот подход будет продемонстрирован в третьей статье серии.

А в данной статье мы сосредоточимся на различных решениях поиска наибольшего паросочетания. Очевидно, что чем быстрее работает решение, тем лучше. Кроме того, чем больше ребер будет найдено, тем лучше. В зависимости от времени выполнения следует предпочесть более медленное решение, которое находит более крупное наибольшее паросочетание. В конечном итоге, после того как вы объедините его с остальной работой, связанной с поиском паросочетания максимальной мощности, главным критерием будет общее время выполнения.

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

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

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

В случае с большим набором тестовых данных вы инициализируете @n с общим числом строк, которые должны присутствовать в G. Вы получите приблизительно это число на практике. Оно представляет собой сумму арифметической последовательности. Например, если инициализировать @n числом 10, это число представляет сумму арифметической последовательности 1 + 2 + 3 + 4. Назначение SET @n = SQRT (@n * 2) вычисляет количество членов последовательности (4 в нашем примере). Затем программный код заполняет таблицу значениями x от 1 до @n и сопоставляет различным значениям x значения @n, @n-1, @n-2, …, 1 y, выбранным произвольно из набора 1 — @n. Например, одно выполнение этого программного кода при инициализации @n числом 10 выдает такие строки в G, как показано на экране 1.

Экран 1. Пример результатов выполнения листинга 2

При инициализации @n числом 10 000 000 таблица G заполняется 10 001 628 строками — достаточное число для измерения производительности.

Решения

Я представлю несколько решений и укажу время выполнения, измеренное на моем компьютере, на большим наборе тестовых данных (~10 000 000 строк). Кроме того, я предоставлю обнаруженное число паросочетаний. Помните: чем быстрее, тем лучше, и чем больше паросочетаний, тем лучше.

Чтобы протестировать корректность решения, после запуска хранимой процедуры MaximalMatching вы можете убедиться, что в G нет ребер со свободными вершинами x и y (отсутствуют в M). Это достигается с помощью запроса, показанного в листинге 3.

Например, запустите этот запрос перед выполнением любой реализации хранимой процедуры MaximalMatching. Поскольку сейчас M пуста, это не наибольшее паросочетание в G. Вы получите выходные данные, аналогичные показанным на экране 2 (вероятно, с другим тестовым ребром, поскольку таблица заполнялась с использованием рандомизации плюс запрос TOP не упорядочен).

Экран 2. Результаты запуска листинга 3

Решение 1. IGNORE_DUP_KEY, одно предложение INSERT

Приступая к подготовке и тестированию Решения 1, я был уверен, что это будет одним из самых быстрых возможных решений. SQL Server поддерживает параметр IGNORE_DUP_KEY с уникальными индексами, поэтому предложения INSERT не отказывают полностью при попытке вставить повторяющиеся ключи, а просто игнорируют дубликаты. Поэтому я реализовал хранимую процедуру MaximalMatching, выполнив следующие шаги:

1. Объявил табличную переменную @M со столбцами x и y одним уникальным индексом с параметром IGNORE_DUP_KEY на x и другим на y.
2. Очистил таблицу M.
3. Вставил в @M все строки из G (игнорируя дубликаты).
4. Вставил в M все строки из @M.

В листинге 4 приводится полный программный код хранимой процедуры, реализующей Решение 1.

Используйте следующую команду для запуска хранимой процедуры:

EXEC dbo.MaximalMatching;

Для выполнения этой хранимой процедуры на моем компьютере потребовалось 11 секунд. Это неплохой результат для поиска наибольшего паросочетания в графе с 10 млн ребер. Но, к моему удивлению, выполнив проверочный запрос, приведенный выше, я обнаружил, что содержимое M не является наибольшим паросочетанием в G. В M присутствовало лишь несколько сотен строк, хотя при таком наборе тестовых данных их должно было быть несколько тысяч. Очевидно, применяемый в SQL Server способ вставки в таблицу с несколькими индексами с параметром IGNORE_DUP_KEY иной, нежели я предполагал.

Например, предположим, вы пытаетесь вставить в @M четыре строки, как в листинге 5.

Я полагал, что по крайней мере в случае с параметром IGNORE_DUP_KEY вставки обрабатываются последовательно, то есть как четыре вставки одиночных строк. Поэтому, в зависимости от порядка вставки, строки, в которых обнаружены дубликаты, исключаются. Для этих четырех строк, независимо от порядка, я предполагал, что будут вставлены две строки. Например, порядок вставки следующий:

('A', 1)

('A', 2)

('B', 1)

('B', 2)

Я ожидал, что будут вставлены ('A', 1) и ('B', 2).

Или порядок вставки следующий:

('A', 2)

('A', 1)

('B', 1)

('B', 2)

В этом случае я ожидал, что будут вставлены ('A', 2) и ('B', 1). Каким бы ни был порядок, вы должны вставить две строки. Но, к моему удивлению, запрос с SELECT показал, что содержимое @M возвращает всего одну строку (экран 3).

Экран 3. Результаты проверки вставки строк

Чтобы выяснить, что случилось, необходимо понимать, как SQL Server оптимизирует предложение INSERT для таблицы с индексами с параметром IGNORE_DUP_KEY. Крейг Фридман раскрывает проблему в своем блоге (https://blogs.msdn.microsoft.com/craigfr/2008/01/30/maintaining-unique-indexes-with-ignore_dup_key/). В применении к нашему случаю с малым примером из четырех строк SQL Server выдает план, показанный на рисунке 2 (https://www.sentryone.com/plan-explorer/).

Рисунок 2. План для инструкции INSERT

Выделенный синим набор операторов сортирует строки по y. Предположим, что выходные данные сортировки такие, как показано на экране 4.

Экран 4. Пример выходных данных сортировки

Оператор Left Semi Join вычисляет пробное значение, отмечая дубликаты ключами, уже присутствующими в индексе по y (перед вставкой). В нашем примере они отсутствуют, так как мы начали с очистки таблицы @M. Поэтому выходные данные этого шага такие, как показано на экране 5.

Экран 5. Результаты работы Left Semi Join

Оператор Assert удаляет строки с пробным значением, указывающим дубликат, возвращая данные (и вновь отсутствуют дубликаты с существующими строками), приведенные на экране 6.

Экран 6. Результаты работы Assert

Оператор Segment обрабатывает каждую группу y отдельно (экран 7).

Экран 7. Результаты работы Segment

Оператор Top сохраняет лишь первую строку в каждом сегменте. Таким образом, синий набор операторов выдает данные как на экране 8.

Экран 8. Результаты работы выделенного синим набора операторов на рисунке 2

Набор выделенных красным операторов затем выполняет аналогичную работу с оставшимися строками, но на этот раз выполняется сортировка по x, результаты показаны на экране 9.

Экран 9. Результаты работы выделенного красным набора операторов на рисунке 2

И вновь дубликатов с существующими ключами в индексе нет, поэтому оператору Assert нечего удалять. В потоке строк выше только один сегмент, и оператор Top, примененный к этому сегменту, приносит строку как на экране 10.

Экран 10. Окончательный результат

Стив Касс опубликовал запрос (https://connect.microsoft.com/SQLServer/feedback/details/342100/ignore-dup-key-fails-to-work-as-it-should-ignoring-too-many-rows), предполагая, что такое поведение является ошибкой, но, как следует из реакции Microsoft, специалисты компании так не считают. Поэтому, к сожалению, Решение 1 не действует, и потому от него следует отказаться.

Решение 2. IGNORE_DUP_KEY, несколько предложений INSERT с курсором

Решение 2 начинается аналогично Решению 1: объявляется табличная переменная с именем @M с одним уникальным индексом с параметром IGNORE_DUP_KEY по столбцу x и другим по столбцу y. Но вместо использования одного многострочного предложения INSERT для копирования строк из G в @M применяется курсор для обхода строк в G, с упорядочением по x, y. На каждом повторе программный код проверяет, превышает ли текущее значение x преды­дущее вставленное значение x. Если это так, предпринимается попытка вставить значения строки текущего курсора в @M. Если значение дублированное, вставка игнорируется; в противном случае она завершается успешно. После того как программный код заканчивает обработку всех строк курсора, он копирует строки из @M в M. В листинге 6 приводится полный исходный текст решения.

Это решение детерминированное, поскольку строки обрабатываются из G в порядке x, y. Для выполнения этого решения на моем компьютере потребовалось 235 секунд. Было обнаружено наибольшее паросочетание с 4415 паросочетаниями. Это довольно медленно, и остается пространство для повышения мощности наибольшего паросочетания.

Решение 3. Курсор, NOT EXISTS

Решение 3 концептуально похоже на Решение 2, но в нем не используется промежуточная табличная переменная с двумя индексами с параметром IGNORE_DUP_KEY. Однако при обходе строк курсора используются два предиката NOT EXISTS для M, чтобы увидеть, свободны ли обе вершины ребра в G. В этом случае строка добавляется в M. Аналогично Решению 2, сначала нужно убедиться, что значение x текущей строки больше предшествующего вставленного значения x, затем проверяется существование в M. В листинге 7 приводится полный программный код решения.

Это решение было выполнено на моем компьютере за 132 секунды, что почти вдвое меньше, чем время выполнения Решения 2. Строки обрабатываются в том же порядке, что и в Решении 2, поэтому. естественно, обнаруживается то же наибольшее паросочетание, что и в Решении 2, с 4415 паросочетаниями в моем случае, и оно также детерминированное.

Решение 4. Цикл, TOP с параметром NOT EXISTS, с упорядочением по x, y

Решение 4 довольно простое и очень эффективное. Оно начинается с использования запроса TOP (1) к G, с упорядочением по x, y и сохранением обнаруженных значений столбца первой строки в локальных переменных @x и @y. Затем запускается цикл для разового обхода для каждого обнаруженного неповторяющегося значения x, и на каждом проходе в M записывается новая строка со значениями из локальных переменных. Затем используется другой запрос TOP (1) для поиска следующей строки, где x больше, чем @x, и где y не существует в M. Соответствующие значения записываются в локальные переменные.

В листинге 8 приводится полный программный код решения.

Поскольку в этом решении строки обрабатываются в том же порядке, что и в решениях 2 и 3, будет обнаружено такое же наибольшее паросочетание. Оно такое же детерминированное, как и два других. Однако это решение гораздо более производительное. Для его выполнения на моем компьютере потребовалось всего 8 секунд! Это неплохо, учитывая, что G содержит около 10 000 000 строк. Но остается пространство для улучшения в поиске мощности паросочетания (4415 паросочетаний в моем случае).

Обратите внимание, что для оптимизации этого решения между столбцами x и y элементом итерации должен быть тот, который имеет более высокую плотность (меньше неповторяющихся значений). Если ожидаются близкие плотности, не имеет значения, какой из них будет выбран (в нашем примере используется x). Но, конечно, если плотность y существенно выше, лучше выполнять итерацию по y.

Решение 5. Цикл, TOP с параметром NOT EXISTS, упорядочение по мощности

Производительность Решения 4 очень высокая, но остается пространство для улучшения поиска мощности паросочетания. Не имея сведений о природе данных и основываясь на статистике, можно утверждать, что если обрабатывать меньшие группы x прежде групп x более крупного размера (предполагается, что плотности x и y близки), то велика вероятность, что будет найдено наибольшее паросочетание большей мощности. В этом основная логика Решения 5. Обратите внимание, что это решение вычисляет как агрегаты, так и рейтинг, и вы можете получить больший выигрыш в производительности благодаря пакетной обработке. Чтобы задействовать пакетную обработку, в таблице, к которой направляются запросы, должен быть столбчатый индекс columnstore, даже если он не используется. Задействуйте программный код листинга 9 для создания пустого фильтруемого индекса columnstore, чтобы включить пакетную обработку.

Полный программный код хранимой процедуры, реализующей Решение 5, приведен в листинге 10.

Программный код направляет запрос к G, подсчитывает число строк на группу x (присвоим результирующему столбцу имя cnt) и присваивает значения рейтинга плотности строкам, упорядоченным по cnt и x (присвоим результирующему столбцу имя n). Программный код заполняет временную таблицу с именем #G с n (мощность x), x и y, с кластеризованным индексом, определенным по n и y. Затем программный код заполняет временную таблицу с именем #G с n (мощность x), x и y, с кластеризованным индексом, определенным на n и y. Затем в программном коде используется логика, похожая на Решение 4, для одного прохода на отдельное значение x с использованием запроса TOP (1) в каждом цикле, только теперь обработка строк основывается на упорядочении n, y. Потребовалось 49 секунд, чтобы выполнить это решение на моем компьютере, то есть оно явно медленнее, чем Решение 4, но обнаружено наибольшее паросочетание с мощностью 4472 (вместо 4415 в Решении 4).

Убедитесь, что вы не отбросили пустой индекс columnstore, так как он полезен и для Решения 6.

Решение 6. Решение на основе произвольного порядка y

В Решении 6 используется цикл и на каждом проходе добавляется больше ребер из G в M. В каждом цикле используется запрос на основе набора с двумя обобщенными табличными выражениями (CTE) (C1 и C2) и внешней инструкцией INSERT. C1 фильтрует строки из G, где в M отсутствуют x и y (свободные вершины); назначает номера строкам, секционированным по x, и упорядочивает в случайном порядке внутри секции (результирующий столбец rnx). Затем C2 направляет запрос к строкам из C1, фильтрует только строки, где rnx равен 1, и вы получаете одну строку для каждого отдельного x. Строкам назначаются номера, секционированные по y без определенного порядка (результирующий столбец rny). Инструкция INSERT направляет запрос к C2 и фильтрует только строки из C2, где rny равно 1. Это решение обнаруживает подмножество подходящих паросочетаний в каждом цикле и добавляет их в M. Как только в текущем цикле не удается обнаружить новых паросочетаний, значит, паросочетание в M является наибольшим. В листинге 11 приводится полный программный код решения.

Это решение недетерминированное, поскольку использует случайный порядок выбора первой строки в каждой группе x, а затем выбирает первую в каждой группе y без определенного порядка.

Для его выполнения на моем компьютере потребовалось 53 секунды, было получено наибольшее паросочетание с мощностью 4468 (в отличие от 4415 в Решении 4 и 4472 в Решении 5). Поскольку оно недетерминированное, результатом каждого выполнения может быть различное наибольшее паросочетание с разной мощностью.

Решение 7. Подстроенное обновление

В Решении 7 используется подстроенное обновление (многостроковое пердложение UPDATE с заданием переменной). Объявляется переменная символьной строки с именем @s, инициализируемая разделителем '.'. Затем подстроенное обновление применяется к G, где для каждой строки проверяется, не содержит ли @s значений x и y; если нет, то к @s присоединяется текущее значение x, разделитель ',' и разделитель '.' После завершения обновления @s имеет одну строку с парами значений. x, y., представляющими наибольшее паросочетание. На следующем и последнем шаге запрос с использованием функции STRING_SPLIT разбивает строку в @s в набор строк с парами значений x, y, а предложение INSERT вставляет эти строки в M. В листинге 12 приводится полный программный код решения.

Это решение недетерминированное и, как оказалось, очень медленное. Для его выполнения потребовалось 17 секунд, при этом в G содержалось всего 100 000 строк. Напоминаю, что все остальные решения тестировались с 10 млн строк. Однако обдумывать его было интересно.

Следующее задание

Лучшими оказались решения 4, 5 и 6. Первое из них самое быстрое, но мощность полученного наибольшего паросочетания меньше.

Следующее задание — подготовить решение, которое заполняет M с паросочетанием максимальной мощности. Вспомните, что паросочетание максимальной мощности представляет собой наибольшее паросочетание с максимальной возможной мощностью (чтобы уяснить это, взгляните на рисунок 1).

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

«Выполнять повторяющийся поиск увеличивающегося пути M в G и обновлять M с использованием симметрической разности этого пути и M».

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

SET NOCOUNT ON;
USE tempdb;

-- Очистка
DROP TABLE IF EXISTS dbo.M, dbo.G, dbo.X, dbo.Y;
GO

-- Set X, e.g., Applicants
CREATE TABLE dbo.X
(
  x VARCHAR(10) NOT NULL CONSTRAINT PK_X PRIMARY KEY,
  moreonx VARCHAR(20) NOT NULL
);
INSERT INTO dbo.X(x, moreonx) VALUES
  ('A', 'Applicant A'),
  ('B', 'Applicant B'),
  ('C', 'Applicant C'),
  ('D', 'Applicant D');

-- Set Y, e.g., Jobs
CREATE TABLE dbo.Y
(
  y INT NOT NULL CONSTRAINT PK_Y PRIMARY KEY,
  moreony VARCHAR(20) NOT NULL
);

INSERT INTO dbo.Y(y, moreony) VALUES
  (1, 'Job 1'),
  (2, 'Job 2'),
  (3, 'Job 3'),
  (4, ‘Job 4’);

-- Граф G = (X, Y, E), например, возможные соединения соискатель-рабочее место
CREATE TABLE dbo.G
(
  x VARCHAR(10) NOT NULL
    CONSTRAINT FK_G_X FOREIGN KEY REFERENCES dbo.X,
  y INT NOT NULL
    CONSTRAINT FK_G_Y FOREIGN KEY REFERENCES dbo.Y,
  CONSTRAINT PK_G PRIMARY KEY (x, y)
);


INSERT INTO dbo.G(x, y) VALUES
  (‘A’, 1),
  (‘A’, 2),
  (‘B’, 1),
  (‘B’, 3),
  (‘C’, 3),
  (‘C’, 4),
  (‘D’, 3);
GO


-- M является паросочетанием в G
CREATE TABLE dbo.M
(
  x VARCHAR(10) NOT NULL
    CONSTRAINT UQ_M_x UNIQUE,
  y INT NOT NULL
    CONSTRAINT UQ_M_y UNIQUE,
  CONSTRAINT PK_M PRIMARY KEY (x, y),
  CONSTRAINT FK_M_G FOREIGN KEY (x, y) REFERENCES dbo.G(x, y)
);

-- Cleanup
SET NOCOUNT ON;
USE tempdb;

DROP TABLE IF EXISTS dbo.M, dbo.G, dbo.X, dbo.Y;
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

CREATE TABLE dbo.X
(
  x VARCHAR(10) NOT NULL CONSTRAINT PK_X PRIMARY KEY,
  moreonx VARCHAR(20) NOT NULL
);

CREATE TABLE dbo.Y
(
  y INT NOT NULL CONSTRAINT PK_Y PRIMARY KEY,
  moreony VARCHAR(20) NOT NULL
);

CREATE TABLE dbo.G
(
  x VARCHAR(10) NOT NULL
    CONSTRAINT FK_G_X FOREIGN KEY REFERENCES dbo.X,
  y INT NOT NULL
    CONSTRAINT FK_G_Y FOREIGN KEY REFERENCES dbo.Y,
  CONSTRAINT PK_G PRIMARY KEY (x, y)
);

CREATE TABLE dbo.M
(
  x VARCHAR(10) NOT NULL
    CONSTRAINT UQ_M_x UNIQUE,
  y INT NOT NULL
    CONSTRAINT UQ_M_y UNIQUE,
  CONSTRAINT PK_M PRIMARY KEY (x, y),
  CONSTRAINT FK_M_G FOREIGN KEY (x, y) REFERENCES dbo.G(x, y)
);
GO

DECLARE @n AS INT = 10000000; -- ~ общее число строк
SET @n = SQRT(@n * 2); -- число членов арифметической последовательности

INSERT INTO dbo.X(x, moreonx)
  SELECT
    RIGHT('000000000' + CAST(N.n AS VARCHAR(10)), 10) AS x,
    'Applicant ' + RIGHT('000000000' + CAST(N.n AS VARCHAR(10)), 10) AS moreonx
  FROM dbo.GetNums(1, @n) AS N;

INSERT INTO dbo.Y(y, moreony)
  SELECT
    N.n AS y,
    'Job ' + CAST(N.n AS VARCHAR(10)) AS moreonx
  FROM dbo.GetNums(1, @n) AS N;

INSERT INTO dbo.G WITH (TABLOCK) (x, y)
  SELECT RIGHT('000000000' + CAST(X.n AS VARCHAR(10)), 10) AS x, Y.n AS y
  FROM dbo.GetNums(1, @n) AS X
    CROSS APPLY (SELECT TOP (@n - X.n + 1) n
                 FROM dbo.GetNums(1, @n)
                 ORDER BY NEWID()) AS Y;

WITH C AS
(
  SELECT TOP (1) 0 AS sortcol,
    'Sorry, this is not a maximal matching. :('
    + ' For example, edge ('
    + x + ', ' + CAST(y AS VARCHAR(10))
    + ') from G could be added to M.' AS IsMaximalMatching
  FROM dbo.G
  WHERE NOT EXISTS ( SELECT * FROM dbo.M WHERE M.x = G.x )
    AND NOT EXISTS ( SELECT * FROM dbo.M WHERE M.y = G.y )
  
  UNION ALL

  SELECT 1 AS sortcol,
    'Congrats! This is a maximal matching. :)'
    + ' You found ' + CAST( (SELECT COUNT(*) FROM dbo.M) AS VARCHAR(10) )
    + ' matchings out of '
    + CAST( (SELECT COUNT(*) FROM dbo.G) AS VARCHAR(10) )
    + ' edges in G.' AS IsMaximalMatching
)
SELECT TOP (1) IsMaximalMatching
FROM C
ORDER BY sortcol;

CREATE OR ALTER PROC dbo.MaximalMatching
AS

SET NOCOUNT, XACT_ABORT ON;

DECLARE @M AS TABLE
(
  x VARCHAR(10) NOT NULL
    INDEX idx_x UNIQUE NONCLUSTERED WITH (IGNORE_DUP_KEY = ON),
  y INT NOT NULL
    INDEX idx_y UNIQUE NONCLUSTERED WITH (IGNORE_DUP_KEY = ON)
);

TRUNCATE TABLE dbo.M;

INSERT INTO @M(x, y) SELECT x, y FROM dbo.G;
INSERT INTO dbo.M(x, y) SELECT x, y FROM @M;
GO

DECLARE @M AS TABLE
(
  x VARCHAR(10) NOT NULL
    INDEX idx_x UNIQUE NONCLUSTERED WITH (IGNORE_DUP_KEY = ON),
  y INT NOT NULL
    INDEX idx_y UNIQUE NONCLUSTERED WITH (IGNORE_DUP_KEY = ON)
);

INSERT INTO @M(x, y) VALUES('A', 1),('A', 2),('B', 1),('B', 2);

SELECT * FROM @M;

CREATE OR ALTER PROC dbo.MaximalMatching
AS

SET NOCOUNT, XACT_ABORT ON;

DECLARE @x AS VARCHAR(10), @prevx AS VARCHAR(10) = '', @y AS INT, @C AS ;

DECLARE @M AS TABLE
(
  x VARCHAR(10) NOT NULL
    INDEX idx_x UNIQUE NONCLUSTERED WITH (IGNORE_DUP_KEY = ON),
  y INT NOT NULL
    INDEX idx_y UNIQUE NONCLUSTERED WITH (IGNORE_DUP_KEY = ON)
);

TRUNCATE TABLE dbo.M;

SET @C =  FORWARD_ONLY STATIC READ_ONLY FOR
  SELECT x, y FROM dbo.G ORDER BY x, y;

OPEN @C;

FETCH NEXT FROM @C INTO @x, @y;

WHILE @@FETCH_STATUS = 0
BEGIN
  IF @x > @prevx
  BEGIN
    INSERT INTO @M(x, y) VALUES(@x, @y);
    IF @@ROWCOUNT > 0
      SET @prevx = @x;
  END;

  FETCH NEXT FROM @C INTO @x, @y;
END;

INSERT INTO dbo.M(x, y) SELECT x, y FROM @M;
GO

CREATE OR ALTER PROC dbo.MaximalMatching
AS

SET NOCOUNT, XACT_ABORT ON;

DECLARE @x AS VARCHAR(10), @prevx AS VARCHAR(10) = '', @y AS INT, @C AS ;

TRUNCATE TABLE dbo.M;

SET @C =  FORWARD_ONLY STATIC READ_ONLY FOR
  SELECT x, y FROM dbo.G ORDER BY x, y;

OPEN @C;

FETCH NEXT FROM @C INTO @x, @y;

WHILE @@FETCH_STATUS = 0
BEGIN
  IF @x > @prevx
    IF NOT EXISTS ( SELECT * FROM dbo.M WHERE x = @x )
         AND NOT EXISTS ( SELECT * FROM dbo.M WHERE y = @y )
    BEGIN
      INSERT INTO dbo.M(x, y) VALUES(@x, @y);
      SET @prevx = @x;
    END;

  FETCH NEXT FROM @C INTO @x, @y;
END;
GO

CREATE OR ALTER PROC dbo.MaximalMatching
AS

SET NOCOUNT, XACT_ABORT ON;

DECLARE @x AS VARCHAR(10), @y AS INT;

TRUNCATE TABLE dbo.M;

SELECT TOP (1) @x = x, @y = y
FROM dbo.G
ORDER BY x, y;

WHILE @@ROWCOUNT > 0
BEGIN
  INSERT INTO dbo.M(x, y) VALUES(@x, @y);

  SELECT TOP (1) @x = x, @y = y
  FROM dbo.G
  WHERE x > @x
    AND NOT EXISTS ( SELECT * FROM dbo.M WHERE M.y = G.y )
  ORDER BY x, y;
END;
GO

CREATE NONCLUSTERED COLUMNSTORE INDEX idx_cs_dummy
  ON dbo.G(x)
  WHERE x = 'yes' AND x = 'no';

CREATE OR ALTER PROC dbo.MaximalMatching
AS

SET NOCOUNT, XACT_ABORT ON;

DECLARE @n AS BIGINT, @x AS VARCHAR(10), @y AS INT;

TRUNCATE TABLE dbo.M;

CREATE TABLE #G
(
  n BIGINT NOT NULL,
  x VARCHAR(10) NOT NULL,
  y INT NOT NULL,
  INDEX idx_n_y CLUSTERED(n, y)
);

WITH C AS
(
  SELECT x, y,
    COUNT(*) OVER(PARTITION BY x) AS cnt
  FROM dbo.G
)
INSERT INTO #G (n, x, y)
  SELECT DENSE_RANK() OVER(ORDER BY cnt, x) AS n, x, y
  FROM C;

SELECT TOP (1) @n = n, @x = x, @y = y
FROM #G
ORDER BY n, y;

WHILE @@ROWCOUNT > 0
BEGIN
  INSERT INTO dbo.M(x, y) VALUES(@x, @y);

  SELECT TOP (1) @n = n, @x = x, @y = y
  FROM #G AS G
  WHERE n > @n
    AND NOT EXISTS ( SELECT * FROM dbo.M WHERE M.y = G.y )
  ORDER BY n, y;
END;

DROP TABLE #G;
GO

CREATE OR ALTER PROC dbo.MaximalMatching
AS

SET NOCOUNT, XACT_ABORT ON;

TRUNCATE TABLE dbo.M;

WHILE 1 = 1
BEGIN
  WITH C1 AS
  (
    SELECT x, y,
      ROW_NUMBER() OVER(PARTITION BY x ORDER BY NEWID()) AS rnx
    FROM dbo.G
    WHERE NOT EXISTS ( SELECT * FROM dbo.M WHERE M.x = G.x )
      AND NOT EXISTS ( SELECT * FROM dbo.M WHERE M.y = G.y )
  ),
  C2 AS
  (
    SELECT x, y,
      ROW_NUMBER() OVER(PARTITION BY y ORDER BY (SELECT NULL)) AS rny
    FROM C1
    WHERE rnx = 1
  )
  INSERT INTO dbo.M(x, y)
    SELECT x, y
    FROM C2
    WHERE rny = 1;

  IF @@ROWCOUNT = 0 BREAK;
END;
GO

CREATE OR ALTER PROC dbo.MaximalMatching
AS
SET NOCOUNT, XACT_ABORT ON;
DECLARE @s AS VARCHAR(MAX) = '.';
TRUNCATE TABLE dbo.M;
SELECT
  @s +=
    CASE
      WHEN CHARINDEX('.' + x + ',', @s) > 0
           OR CHARINDEX(',' + CAST(y AS VARCHAR(20)) + '.', @s) > 0
        THEN ''
      ELSE x + ',' + CAST(y AS VARCHAR(20)) + '.'
    END
FROM dbo.G;

INSERT INTO dbo.M(x, y)
  SELECT
    LEFT(value, CHARINDEX(',', value) - 1) AS x,
    CAST(RIGHT(value, LEN(value) - CHARINDEX(',', value)) AS INT) AS y
  FROM STRING_SPLIT(CASE WHEN @s = '.' THEN NULL ELSE SUBSTRING(@s, 2, LEN(@s) - 2) END, '.');
GO