Halloween - разделяй и властвуй

В соответствии с классическим принципом проектирования, известного как «разделяй и властвуй» (Divide and Conquer — D&C), задача упрощается путем разбиения на две или несколько малых задач рекурсивно-итерактивным методом. Вариант метода, именуемый «уменьшай и властвуй» (Decrease and Conquer), заключается в сведении исходной задачи к одной частичной задаче, также рекурсивно-итерактивным методом.

В SQL Server типовой рекурсивно-итерактивный метод используется для обработки задач, связанных с графами, которые можно рассматривать как основанные на алгоритме Decrease and Conquer. Примером таких задач может служить возвращение подграфа (поиск подчиненных руководителя или деталей в ведомости материалов). Типовой способ решения заключается в итеративном проходе по уровням графов и в поочередной обработке уровней по одному с помощью временной таблицы или табличной переменной.

Недавно я отметил, что планы запросов решений на основе этого метода содержат дополнительную работу, связанную с защитой Halloween. Для углубленного знакомства с темой рекомендую прочитать отличную серию статей Пола Уайта о защите Halloween (http://sqlblog.com/blogs/paul_white/archive/2013/02/21/halloween-protection-the-complete-series.aspx). Когда источник и место назначения изменения одинаковы и существует возможность, что некоторые строки будут обработаны два или несколько раз (например, обновлены несколько раз, многократно прочитаны и вставлены), то оптимизатор использует защиту Halloween, чтобы избежать проблем. Для такой защиты Halloween подчас требуется добавить к плану дополнительную работу, в которой в ином случае не было бы необходимости.

Я задумался, возможен ли альтернативный общий подход, устраняющий необходимость в защите Halloween, и сумел найти его. Я разделил обработку каждого уровня на две части, переключаясь между временными таблицами/табличными переменными. В результате источник и место назначения всегда различны. Прежде чем написать статью с объяснением метода, я описал его своей супруге и попросил совета, как назвать метод. Любопытно, что она ответила «разделяй и властвуй», хотя до этого не знала об алгоритме проектирования с таким названием. Мне понравилось ее предложение и я назвал свой метод «Halloween — разделяй и властвуй».

Задача

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

Выполните программный код в листинге 2, чтобы создать таблицу с именем Graph и заполнить ее 10 000 000 узлов. Степень графа (максимальная глубина) — 7.

Предположим, что требуется найти решение для запроса подграфа. При входном узле @root возвращаются узлы в подграфе @root. Для наших целей, чтобы избежать очень больших выводов, можно не возвращать все отдельные узлы в подграфе, а вычислить сумму значений в столбце val и их количество. Обратите внимание, что тестовые данные, которыми заполнена таблица Graph, представляет граф, являющийся деревом. Таким образом, только один путь может вести к каждому узлу; однако методы, описанные в этой статье, применимы и в более общем случае, известном как направленный ациклический граф (к узлу могут вести несколько путей). Типичный способ обработки таких запросов подграфа — использовать рекурсивный запрос, аналогичный показанному в листинге 3.

На рисунке 1 показан план выполнения для этого запроса. Здесь вы заметите, что SQL Server создает Index Spool (рабочую таблицу на основе B-дерева), где хранится промежуточный набор результатов. С помощью оператора Nested Loops план итеративно обрабатывает по одному уровню узлов за один прием. На каждой итерации выполняется чтение из очереди для сбора узлов из текущего уровня, присоединение к таблице Graph для получения узлов с текущего уровня и вставка этих узлов в очередь.

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

Проблема этого решения в том, что можно управлять только аспектами оптимизации пользовательской таблицы Graph в отношении индексации, статистики и т.д. Вы не можете влиять на индексацию и статистику рабочей таблицы или любой другой аспект ее обработки. В результате быстродействие решения низкое. Для выполнения решения на моем компьютере потребовалось 19 секунд для ввода @root = 5. Всего было выполнено 13 337 269 операций логического чтения (измерено в сеансе расширенных событий).

Рекурсивный запрос лаконичен, но, как правило, быстродействие того же алгоритма выше, если использовать цикл и временную таблицу или табличную переменную, как показано в листинге 4. SQL Server ведет статистику распространения (гистограммы) по временным таблицам, но не табличным переменным; поэтому оценки обычно лучше для временных таблиц.

На рисунке 2 показаны планы для запросов в решении.

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

Первый план представляет вставку первого узла во временную таблицу. Следующие семь планов представляют итеративные вставки «следующего уровня». Наконец, последний план представляет запрос, вычисляющий сумму и счетчик. Обратите внимание на выделенные операторы Table Spool (Eager Spool) в планах для первых шести итераций инструкции INSERT. Eager Spool — рабочая таблица, которая полностью обрабатывает все входные строки перед передачей их в оператор слева. Это блокирующий оператор (stop-and-go).

SQL Server использует блокирующий оператор для целей защиты Halloween, чтобы данные, прочитанные или записанные в таблицу, не были прочитаны более одного раза. Естественно, Eager Spool увеличивает число операций, в основном ввода-вывода в tempdb, кратковременные блокировки и т.д. Эти ресурсы часто бывают причиной конкуренции в SQL Server. План для седьмой итерации инструкции INSERT не содержит оператора Eager Spool для целей защиты Halloween. Это объясняется тем, что оператор the Hash Match — блокирующий оператор для конструктивного входного значения и поэтому уже обеспечивает необходимую защиту.

Для выполнения данного решения на моем компьютере потребовалось 8 секунд; было произведено 4 232 753 логических операций чтения. Несколько сотен тысяч операций чтения приходится на операторы Eager Spool для защиты Halloween. Меня заинтересовала возможность найти типовой метод решения для таких задач, такой, чтобы можно было отказаться от защиты Halloween и избежать связанных с ней затрат.

Решение: Halloween — разделяй и властвуй

Как уже отмечалось, возможность защиты Halloween существует лишь в том случае, если источник и место назначения одинаковы. Чтобы избежать необходимости в защите Halloween, я использовал две временные таблицы вместо одной, переключаясь между ними при каждой итерации цикла. По четности счетчика уровня (@lvl) определяется, какую из двух таблиц использовать в качестве источника, а какую — в качестве места назначения. Затем окончательный запрос, который вычисляет сумму и подсчет, просто применяет вычислительный алгоритм к объединенному набору из двух таблиц. В листинге 5 содержится полное решение.

На рисунке 3 показаны планы выполнения для запросов в этом решении. Обратите внимание, что защита Halloween с Eager Spool полностью устранена из всех планов. На моем компьютере выполнение этого решения заняло 6 секунд, а число логических чтений уменьшилось более чем на полмиллиона, до 3 651 072.

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

Избавляемся от лишних затрат

В этой статье описаны типовые приемы, используемые в итеративных решениях T-SQL для обработки различных задач, в том числе связанных с графами. Проблема состоит в том, что приходится выполнять итеративное чтение и запись в одну временную таблицу. Для этого в SQL Server приходится применять защитные меры Halloween, связанные с затратами ресурсов. Я предложил измененный алгоритм «Halloween — разделяй и властвуй» с переключением между двумя временными таблицами и использованием различных источника и места назначения при каждой итерации. В этом решении одна и та же таблица никогда не используется одновременно в качестве источника и места назначения, поэтому не требуется добавлять защиту Halloween и тем самым уменьшаются накладные расходы.

SET NOCOUNT ON;
USE tempdb;
GO
IF OBJECT_ID(N'dbo.GetNums', N'IF') IS NOT NULL DROP FUNCTION dbo.GetNums;
GO
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

IF OBJECT_ID(N'dbo.Graph', N'U') IS NOT NULL DROP TABLE dbo.Graph;
GO
CREATE TABLE dbo.Graph
(
nodeid INT NOT NULL,
parentid INT NULL,
val NUMERIC(12, 2)
);
INSERT INTO dbo.Graph WITH(TABLOCK) (nodeid, parentid, val)
SELECT
n AS nodeid,
NULLIF((n-1) / 10, 0) AS parentid,
CAST(1 + ABS(CHECKSUM(NEWID())) % 100 AS NUMERIC(12, 2)) AS val
FROM dbo.GetNums(1, 10000000) AS Nums;
CREATE UNIQUE CLUSTERED INDEX idx_pid_nid ON dbo.Graph(parentid, nodeid);
ALTER TABLE dbo.Graph ADD CONSTRAINT PK_Graph PRIMARY KEY NONCLUSTERED(nodeid);

DECLARE @root AS INT = 5;
WITH C AS
(
SELECT nodeid, parentid, val
FROM dbo.Graph
WHERE nodeid = @root
UNION ALL
SELECT CUR.nodeid, CUR.parentid, CUR.val
FROM C AS PRV
INNER JOIN dbo.Graph AS CUR
ON CUR.parentid = PRV.nodeid
)
SELECT COUNT(*) AS cnt, SUM(val) AS total_val
FROM C;

DECLARE @root AS INT = 5;
CREATE TABLE #T
(
lvl INT NOT NULL,
nodeid INT NOT NULL,
parentid INT NULL,
val NUMERIC(12, 2) NOT NULL,
UNIQUE CLUSTERED(lvl, nodeid)
);
DECLARE @lvl AS INT = 0;
— вставить корневой узел
INSERT INTO #T(lvl, nodeid, parentid, val)
SELECT @lvl, nodeid, parentid, val
FROM dbo.Graph
WHERE nodeid = @root;
WHILE @@ROWCOUNT > 0
BEGIN
SET @lvl += 1;
— вставить дочерей узлов на предыдущем уровне
INSERT INTO #T(lvl, nodeid, parentid, val)
SELECT @lvl, CUR.nodeid, CUR.parentid, CUR.val
FROM #T AS PRV
INNER JOIN dbo.Graph AS CUR
ON PRV.lvl = @lvl — 1
AND CUR.parentid = PRV.nodeid;
END
SELECT COUNT(*) AS cnt, SUM(val) AS total_val
FROM #T;
DROP TABLE #T;

DECLARE @root AS INT = 5;
CREATE TABLE #T1
(
lvl INT NOT NULL,
nodeid INT NOT NULL,
parentid INT NULL,
val NUMERIC(12, 2) NOT NULL,
UNIQUE CLUSTERED(lvl, nodeid)
);
CREATE TABLE #T2
(
lvl INT NOT NULL,
nodeid INT NOT NULL,
parentid INT NULL,
val NUMERIC(12, 2) NOT NULL,
UNIQUE CLUSTERED(lvl, nodeid)
);
DECLARE @lvl AS INT = 0;
— вставить корневой узел
INSERT INTO #T1(lvl, nodeid, parentid, val)
SELECT @lvl, nodeid, parentid, val
FROM dbo.Graph
WHERE nodeid = @root;
WHILE @@ROWCOUNT > 0
BEGIN
SET @lvl += 1;
— вставить дочерей узлов на предыдущем уровне
IF @lvl % 2 = 1
INSERT INTO #T2(lvl, nodeid, parentid, val)
SELECT @lvl, CUR.nodeid, CUR.parentid, CUR.val
FROM #T1 AS PRV
INNER JOIN dbo.Graph AS CUR
ON PRV.lvl = @lvl — 1
AND CUR.parentid = PRV.nodeid;
ELSE
INSERT INTO #T1(lvl, nodeid, parentid, val)
SELECT @lvl, CUR.nodeid, CUR.parentid, CUR.val
FROM #T2 AS PRV
INNER JOIN dbo.Graph AS CUR
ON PRV.lvl = @lvl — 1
AND CUR.parentid = PRV.nodeid;
END
SELECT COUNT(*) AS cnt, SUM(val) AS total_val
FROM (SELECT * FROM #T1 UNION ALL SELECT * FROM #T2) AS U;
DROP TABLE #T1, #T2;