Поиск внутри последовательности, часть 1

Недавно мне довелось поработать над задачей T-SQL, в процессе решения которой требовалось определить подпоследовательность внутри последовательности. Задача показалась мне интересной, и я решил рассмотреть ее в статье, состоящей из двух частей. В первой статье речь пойдет об итеративных решениях, а в следующей — о решениях на основе наборов. Как всегда, я рекомендую, прочитав условие задачи, попробовать справиться с ней самостоятельно, прежде чем знакомиться с моим решением.

Задача

Нам необходимо найти местонахождение подпоследовательности внутри последовательности. Например, существует последовательность 1, 1, 7, 5, 9, 1, 7, 1, 7, 5, 9 и подпоследовательность 1, 7, 5, 9. Подпоследовательность находится в позициях со 2 по 5 и с 8 по 11 в исходной последовательности.

Пример практического применения — поиск определенной подпоследовательности в последовательности ДНК, представляющей возможную мутацию. В этом случае четыре нуклеотидных основания ДНК (G, A, T и C) составляют элементы последовательности вместо целых чисел в моем примере, но принцип остается неизменным. Используйте программный код в листинге 1, чтобы построить таблицы с именем T1 и заполнить ее малым набором тестовых данных, представляющих полную последовательность.

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

— Входная табличная переменная @P

DECLARE @P AS TABLE
(
keycol INT NOT NULL
PRIMARY KEY,
val INT NOT NULL,
UNIQUE(val, keycol)
);

— тестовый ввод; попробуйте другие входные данные

INSERT INTO @P(keycol, val) VALUES
(1, 1),(2, 7),(3, 1),(4, 7);
--

Конечно, можно как угодно менять тестовый ввод, чтобы протестировать решения с разными подпоследовательностями. На рисунке 1 показан желаемый результат для малого набора тестовых данных для входной последовательности 1,7,1,7.

Рисунок 1. Желаемый результат для?малого набора тестовых данных и?входа 1, 7, 1, 7

На рисунке 2 показан желаемый результат для подпоследовательности 1,7,5,9. Обратите внимание, что при наличии нескольких экземпляров подпоследовательности необходимо определить их все.

Рисунок 2. Желаемый результат для?малого набора тестовых данных и?входа 1, 7, 5, 9

Используйте малый набор тестовых данных, чтобы проверить корректность решения. Чтобы протестировать производительность решения, необходимо заполнить таблицу более крупным набором тестовых данных. Для этой цели можно использовать исходный текст листинга 2.

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

Решение 1. Использование рекурсивного запроса

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

Первый запрос в тексте CTE представляет собой закрепленный элемент:

SELECT
T1.keycol AS minkey,
P.keycol AS P_keycol,
T1.keycol AS T1_keycol
FROM @P AS P
INNER JOIN dbo.T1
ON P.val = T1.val
WHERE P.keycol = 1

Запрос фильтрует только первый элемент из входной последовательности в табличной переменной @P, объединяя @P и T1, чтобы идентифицировать все вхождения первого значения подпоследовательности в последовательность. Ключ этого первого значения определяется как потенциальный минимальный ключ (с псевдонимом minkey). Ключи подпоследовательности и последовательности также возвращаются с псевдонимами P_keycol и T1_keycol, соответственно.

Второй запрос в тексте CTE представляет собой рекурсивный элемент:

SELECT
PRV.minkey,
P.keycol AS P_keycol,
T1.keycol AS T1_keycol
FROM C AS PRV
INNER JOIN @P AS P
ON P.keycol = PRV.P_keycol + 1
INNER JOIN dbo.T1
ON T1.keycol = PRV.T1_keycol + 1
AND P.val = T1.val

Этот запрос объединяет предыдущий результат (с псевдонимом PRV) с табличной переменной @P (с псевдонимом P) и таблицей T1. Цель этих объединений — определить следующее значение как в подпоследовательности, так и в последовательности и сообщить о совпадении, только если следующее значение в обоих случаях одинаковое (P.val = T1.val). Этот рекурсивный запрос выполняется повторно до тех пор, пока не будут найдены дополнительные совпадения.

Наконец, внешний запрос фильтрует только строки из CTE, представляющие последние оставшиеся элементы подпоследовательности (P_keycol равен максимальному ключу в @P). Это означает, что найдена вся подпоследовательность:

SELECT minkey, T1_keycol AS maxkey
FROM C
WHERE P_keycol = (SELECT MAX(keycol) FROM @P);

Это довольно простое решение, но, к сожалению, его эффективность невелика. Дело в том, что запрос выполняет много операций ввода-вывода с внутренней рабочей таблицы (буфером), формируемой для хранения промежуточных наборов результатов. У вас нет возможности повлиять на этот процесс, индексацию рабочей таблицы или любые другие аспекты. На моем компьютере выполнение данного решения заняло 11 секунд; при этом было совершено 13 миллионов операций логического считывания.

Решение 2. Использование цикла

Во втором решении реализован тот же подход, что и в первом, но вместо рекурсивного CTE используется явный цикл. В листинге 4 приведен полный исходный текст решения.

Исходный текст начинается с определения временной таблицы с именем #T для хранения промежуточных результатов. Затем объявляются и инициализируются две переменные: @i — счетчик итераций с начальным значением 1, которое увеличивается на 1 при каждом повторном выполнении цикла; @cnt — содержит число элементов в подпоследовательности.

Затем инструкция INSERT выполняет задачу, которая в предыдущем решении возлагалась на закрепленный элемент: фильтрует первый элемент в подпоследовательности и присоединяет к T1, чтобы обнаружить все значения в последовательности, представляющей возможное начало подпоследовательности. Результат сохраняется в #T.

Затем выполняется цикл, который не прекращается до тех пор, пока предыдущая инструкция INSERT возвращает строки. В каждой итерации INSERT выполняет задачу, которая предыдущем решении выполнялась рекурсивным членом, а именно, сопоставляет элементы предыдущего прохода со следующим элементом в последовательности, если это ожидаемый следующий элемент подпоследовательности.

Наконец, последний запрос возвращает ключи начала и конца для всех экземпляров подпоследовательности в последовательности (где P_keycol = @cnt).

При выполнении программного кода в листинге 4 в том виде, как он приведен (без параметра запроса RECOMPILE), я получил тот же план для всех исполнений INSERT в теле запроса. На рисунке 3 показан результирующий план.

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

Первый план был сформирован для примерно 1 миллиона совпадений; затем он использовался во всех последующих итерациях. Проблема в том, что все последующие итерации возвращают гораздо меньше совпадений, и данный план — не самый эффективный. На моем компьютере выполнение этого решения заняло 10 секунд; при этом было совершено 3,5 миллионов операций логического считывания.

Производительность решения можно повысить с помощью параметра запроса RECOMPILE в инструкции INSERT в теле цикла. Это заставляет SQL Server подготовить новый план для каждой итерации инструкции, более подходящий на основе новой оценки. Я снял знаки комментария параметра запроса RECOMPILE в листинге 4 и повторно выполнил программный код.

Я получил различные планы для первой итерации инструкции INSERT (подходит для большого числа совпадений) и для всех оставшихся итераций (подходит для малого числа совпадений), как показано на рисунке 4.

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

На этот раз запрос был выполнен за 7 секунд, а число логических считываний немного увеличилось (3,85 миллиона), но в целом производительность повысилась.

Решение 3. Принцип «Halloween — разделяй и властвуй»

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

В статье «Divide and Conquer Halloween» (http://sqlmag.com/t-sql/divide-and-conquer-halloween) рассмотрена общая форма итеративного алгоритма, используемого в данной статье – «разделяй и властвуй». Я объяснил необходимость в Halloween Protection, когда источник и место назначения итеративной инструкции INSERT совпадают. Было предложено решение, реализующее тот же алгоритм, но без необходимости в Halloween Protection. Просто использовались две временные таблицы вместо одной с переключением между ними. Таким образом на каждом проходе источник и место назначения различаются. Я назвал этот подход «Halloween — разделяй и властвуй». В листинге 5 приведен исходный текст решения, реализующего этот подход.

На рисунке 5 показаны планы для различных исполнений инструкций INSERT в теле цикла, без добавления специального кода для Halloween Protection.

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

На моем компьютере выполнение этого решения заняло 3,5 секунды; при этом было совершено всего 370 000 операций логического считывания.

В следующей статье

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

SET NOCOUNT ON;
USE tempdb;
GO
IF OBJECT_ID(N'dbo.T1', N'U') IS NOT NULL DROP TABLE dbo.T1;
GO
CREATE TABLE dbo.T1
(
keycol INT NOT NULL
CONSTRAINT PK_T1 PRIMARY KEY,
val INT NOT NULL,
CONSTRAINT UNQ_T1_val_keycol UNIQUE(val, keycol)
);
— Малый набор тестовых данных для проверки корректности
INSERT INTO dbo.T1(keycol, val) VALUES
(1, 1),(2, 1),(3, 7),(4, 5),(5, 9),(6, 1),(7, 7),(8, 1),(9, 7),(10, 5),(11, 9);

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
— Большой набор тестовых данных для проверки производительности
TRUNCATE TABLE dbo.T1;
INSERT INTO dbo.T1(keycol, val)
SELECT n AS keycol, ABS(CHECKSUM(NEWID())) % 10 + 1 AS val
FROM TSQL2012.dbo.GetNums(1, 10000000) AS Nums;

WITH C AS
(
SELECT
T1.keycol AS minkey,
P.keycol AS P_keycol,
T1.keycol AS T1_keycol
FROM @P AS P
INNER JOIN dbo.T1
ON P.val = T1.val
WHERE P.keycol = 1
UNION ALL
SELECT
PRV.minkey,
P.keycol AS P_keycol,
T1.keycol AS T1_keycol
FROM C AS PRV
INNER JOIN @P AS P
ON P.keycol = PRV.P_keycol + 1
INNER JOIN dbo.T1
ON T1.keycol = PRV.T1_keycol + 1
AND P.val = T1.val
)
SELECT minkey, T1_keycol AS maxkey
FROM C
WHERE P_keycol = (SELECT MAX(keycol) FROM @P);

CREATE TABLE #T
(
minkey INT NOT NULL,
P_keycol INT NOT NULL,
T1_keycol INT NOT NULL,
PRIMARY KEY(P_keycol, T1_keycol)
);
DECLARE
@i AS INT = 1,
@cnt AS INT = (SELECT MAX(keycol) FROM @P);
INSERT INTO #T(minkey, P_keycol, T1_keycol)
SELECT
T1.keycol AS minkey,
P.keycol AS P_keycol,
T1.keycol AS T1_keycol
FROM @P AS P
INNER JOIN dbo.T1
ON P.val = T1.val
WHERE P.keycol = 1;
WHILE @@rowcount > 0
BEGIN
SET @i += 1;
INSERT INTO #T(minkey, P_keycol, T1_keycol)
SELECT
PRV.minkey,
P.keycol AS P_keycol,
T1.keycol AS T1_keycol
FROM #T AS PRV
INNER JOIN @P AS P
ON P.keycol = PRV.P_keycol + 1
INNER JOIN dbo.T1
ON T1.keycol = PRV.T1_keycol + 1
AND P.val = T1.val
WHERE PRV.P_keycol = @i — 1
/* OPTION(RECOMPILE) */;
END;
SELECT minkey, T1_keycol AS maxkey
FROM #T
WHERE P_keycol = @cnt;
DROP TABLE #T;

CREATE TABLE #T1
(
minkey INT NOT NULL,
P_keycol INT NOT NULL,
T1_keycol INT NOT NULL,
PRIMARY KEY(P_keycol, T1_keycol)
);
CREATE TABLE #T2
(
minkey INT NOT NULL,
P_keycol INT NOT NULL,
T1_keycol INT NOT NULL,
PRIMARY KEY(P_keycol, T1_keycol)
);
DECLARE
@i AS INT = 1,
@cnt AS INT = (SELECT MAX(keycol) FROM @P);
INSERT INTO #T1(minkey, P_keycol, T1_keycol)
SELECT
T1.keycol AS minkey,
P.keycol AS P_keycol,
T1.keycol AS T1_keycol
FROM @P AS P
INNER JOIN dbo.T1
ON P.val = T1.val
WHERE P.keycol = 1;
WHILE @@rowcount > 0
BEGIN
SET @i += 1;
IF @i % 2 = 0
BEGIN
TRUNCATE TABLE #T2;
INSERT INTO #T2(minkey, P_keycol, T1_keycol)
SELECT
PRV.minkey,
P.keycol AS P_keycol,
T1.keycol AS T1_keycol
FROM #T1 AS PRV
INNER JOIN @P AS P
ON P.keycol = PRV.P_keycol + 1
INNER JOIN dbo.T1
ON T1.keycol = PRV.T1_keycol + 1
AND P.val = T1.val
OPTION(RECOMPILE);
END;
ELSE
BEGIN
TRUNCATE TABLE #T1;
INSERT INTO #T1(minkey, P_keycol, T1_keycol)
SELECT
PRV.minkey,
P.keycol AS P_keycol,
T1.keycol AS T1_keycol
FROM #T2 AS PRV
INNER JOIN @P AS P
ON P.keycol = PRV.P_keycol + 1
INNER JOIN dbo.T1
ON T1.keycol = PRV.T1_keycol + 1
AND P.val = T1.val
OPTION(RECOMPILE);
END;
END;
IF @i % 2 = 0
SELECT minkey, T1_keycol AS maxkey
FROM #T1
WHERE P_keycol = @cnt;
ELSE
SELECT minkey, T1_keycol AS maxkey
FROM #T2
WHERE P_keycol = @cnt;
DROP TABLE #T1, #T2;