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

В первой части статьи, опубликованной в Windows IT Pro/RE № 2 за 2014 год, была представлена задача, связанная с определением местоположения подпоследовательности внутри последовательности. Были рассмотрены три итеративных решения: с использованием рекурсивного запроса, цикл с одной временной таблицей и цикл с двумя временными таблицами (алгоритм «Halloween — разделяй и властвуй»). Производительность трех итеративных решений составила соответственно 11, 7 и 3,5 секунды. Я надеялся отыскать более эффективные решения на основе наборов, но мне удалось добиться успеха лишь отчасти. В этой статье речь пойдет о трех решениях на основе наборов и их производительности. Два решения выполняются медленнее, чем самое быстрое итеративное решение, а одно — с такой же скоростью.

Задача

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

В таблице T1 содержатся последовательность значений в столбце val; порядок элементов определяется в столбце keycol. Предположим, что имеется входная последовательность в форме табличной переменной, например:

— Входная табличная переменная @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);

Задача состоит в том, чтобы подготовить программный код, который возвращает начальную и конечную позиции (в значениях keycol) входной последовательности @p.val в последовательности T1.val.

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

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

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

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

Таблица заполняется 10 000 000 строк с произвольными значениями в диапазоне от 1 до 10. Это означает, что статистически последовательность из одного значения будет обнаружена в 1/10 случаев, двух значений — в 1/100 случаев и n значений — в 1/10^n случаев. Например, при входной последовательности с четырьмя значениями будет около 1000 совпадений (1/10000 x 10 000 000).

Вероятно, вы сможете предложить собственные решения. Я же здесь расскажу о трех своих.

Решение 1. FOR XML PATH

В листинге 3 содержится первое рассматриваемое решение; на рисунке 3 показан план запроса. Главная тема решения — использование параметра FOR XML PATH для сцепления и сравнения последовательности в @P.val с подпоследовательностью в T1.val.

Рисунок 3. План запроса листинга 3

Производная таблица M во внешнем предложении FROM запроса вычисляет значение cnt, представляющее число элементов во входной последовательности в @P. С помощью CROSS JOIN выполняется сопоставление одной строки в M со строками в других таблицах в предложении FROM. В результате cnt доступна в последующих предикатах.

Следующая часть — соединение T1 и @P (с псевдонимом P) на основе предиката:

P.keycol = 1 AND P.val = T1.val

Этот предикат фильтрует только значения в T1.val, которые потенциально являются начальными во входной подпоследовательности (такое же, как первое значение в @P.val). При статистической вероятности 1/10 совпадений эта часть должна просмотреть и возвратить около 1 000 000 строк из индекса T1.UNQ_T1_val_keycol. Эта работа представлена в плане начиная с третьего нижнего оператора справа вверху. Обратите внимание, что оператор возвращает 1 000 545 строк в плане, полученном на моем компьютере. Число может быть и другим, так как в программном коде, используемом для формирования тестовых данных, применяется рандомизация.

Следующий предикат в предложении FROM сравнивает результаты двух подзапросов, каждый из которых конструирует объединенную строку из оставшихся элементов соответствующей последовательности. Первый подзапрос конструирует строку из второй до последних элементов в @P.val. Второй подзапрос конструирует строку для каждого потенциального начала последовательности в T1.val и следующих cnt-1 элементов. Если две строки одинаковы, то имеет место совпадение. Функция ISNULL используется в случае, если последовательность состоит только из одного элемента. В этом случае оба подзапроса возвращают NULL и функция ISNULL заменяет NULL пустой строкой, чтобы сравнение все же было возможным.

На второй подзапрос приходится основная часть работы в этом плане. Работа, связанная с ним, представлена нижней правой ветвью в Clustered Index Seek индекса T1.PK_T1 и оператора XML UDX. Эта ветвь выполняется 1 000 545 раз. После того, как поиск достигает конечного объекта индекса, проверка диапазона фильтрует первые cnt-1 строк (в нашем случае — три) из обнаруженных (отсюда общее число строк 3 001 635). Затем оператор XML UDX объединяет эти значения cnt-1 в одну строку (поэтому общее число строк становится 1 000 545).

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

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

Листинг 4 содержит второе решение на основе наборов; на рисунке 4 показан план выполнения. Первая часть решения очень похожа на предыдущее решение. Сначала определяется производная таблица с именем M с расчетом столбца, именуемого cnt, представляющего число элементов в подпоследовательности в @P. Затем с помощью перекрестного объединения строка в M сопоставляется с остальными таблицами в предложении FROM. Таким образом, столбец cnt становится доступным для выражений в последующих предикатах.

Рисунок 4. План запроса листинга 4

Как в предыдущем решении, T1 и @P объединяются на основе предиката P.keycol = 1 AND P.val = T1.val. Помните, что этот предикат фильтрует только значения в T1.val, которые являются потенциальными началами входной последовательности. Эта часть плана представлена оператором Index Seek, работающим с индексом T1.UNQ_T1_val_keycol, возвращая 1 000 545 совпадений. И опять же ваши числа могут быть иными, поскольку в программном коде, используемом для заполнения таблицы, применяется рандомизация.

Следующая часть этого решения отличается от продолжения предыдущего. Программный код сравнивает cnt с 1 плюс число строк, возвращенное объединением между @P (псевдоним P2) и T1 (псевдоним T1B) на основе следующего предиката:

P2.keycol > 1
AND T1B.keycol = T1.keycol + P2.keycol — 1
AND T1B.val = P2.val

В сущности, этот предикат фильтрует элементы со второго до последнего из P2, сопоставляя их с элементами, занимающими соответствующие позиции в T1B после потенциальных начальных значений последовательности. Помимо сопоставления соответствующих позиций предикат сопоставляет значения. Если число строк в результате объединения плюс 1 равно cnt, то имеет место совпадение.

Проблема с последней частью — работа, связанная с вычислениями. Она представлена нижней ветвью на плане. Clustered Index Seek в @P выполняется 1 000 545 раз, при этом возвращается 3 001 635 строк. Затем в поисках совпадений Index Seek применительно к T1.UNQ_T1_val_keycol выполняется 3 001 635 раз! Общее число логических чтений в этом плане — 11 миллионов логических чтений, и для выполнения запроса на моем компьютере потребовалось 9 секунд. Это решение менее эффективное, чем предыдущее.

Решение 3. Использование NOT EXISTS x 2

В листинге 5 дано третье решение на основе наборов; на рисунке 5 показан план запроса. Как и в предыдущем решении, сначала выполняется фильтрация потенциальных начальных значений подпоследовательности в последовательности путем объединения @P (псевдоним P) с T1 на основе предиката P.keycol = 1 AND P.val = T1.val. Как и прежде, это достигается с помощью оператора Index Seek, применяемого к индексу T1.UNQ_T1_val_keycol. Возвращается 1 000 545 совпадений.

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

То же самое объединение имеет дополнительный предикат, применяющий подход с двойным отрицанием:

AND NOT EXISTS
(SELECT *
FROM @P AS P2
WHERE P2.keycol > 1
AND NOT EXISTS
(SELECT *
FROM dbo.T1 AS T1B
WHERE T1B.keycol = T1.keycol + P2.keycol — 1
AND T1B.val = P2.val))

Логика этого предиката следующая: выдать совпадение, если не удается найти элемент после первого в @P, для которого нельзя найти элемент с таким же значением в соответствующей позиции в T1. Таким образом, если в @P нет элементов, которым не сопоставлен соответствующий элемент в T1, то все элементы в @P совпадают с соответствующими в T1. Достоинство метода — в использовании предиката в плане.

Для каждой из 1 000 545 строк, возвращенных предыдущим действием, план выполняет операцию поиска в кластеризованном индексе в @P, чтобы получить элементы со второго по последний во входной подпоследовательности. Однако, поскольку элементы со второго по последний просматриваются в @P, план выполняет поиск в T1.UNQ_T1_val_keycol, чтобы проверить, нельзя ли обнаружить совпадающий элемент в соответствующей позиции в T1. Как только для элемента не удается найти совпадения, выполнение прекращается, так как нет необходимости применять поиск в T1 для остальных элементов в @P. Поэтому число действий поиска для T1.UNQ_T1_val_keycol составляет 1 110 338, а не более 3 миллионов.

Общее число операций логического чтения составляет около 5 миллионов, но при этом нет дополнительных затрат, как в других решениях на основе наборов, связанных с объединением строк на основе XML и сравнений строк или статистических выражений подсчета. На моем компьютере решение было выполнено за 3 секунды. Это уже удовлетворительный результат!

Лучшее из лучшего

В первой и второй частях этой статьи я представил задачу определения местонахождения подпоследовательности внутри последовательности. В первой части были показаны три итеративных решения; самое эффективное из них было выполнено за 3,5 секунды. В данной статье отражена попытка найти решение на основе наборов, столь же удачное или более быстрое, чем оптимизированное итеративное решение. Рассмотрены три различных подхода. Скорость самого быстрого решения была близка к самому удачному итеративному решению — 3 секунды. Однако реляционное решение лучше, так как в дополнение к высокому быстродействию исходный текст этого элегантного решения гораздо короче, чем у итеративного решения.

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 dbo.GetNums(1, 10000000) AS Nums;

SELECT
T1.keycol AS minkey,
T1.keycol + M.cnt — 1 AS maxkey
FROM (SELECT MAX(keycol) AS cnt FROM @P) AS M
CROSS JOIN dbo.T1
INNER JOIN @P AS P
ON P.keycol = 1
AND P.val = T1.val
AND (SELECT P2.val AS [data()]
FROM @P AS P2
WHERE P2.keycol > 1
ORDER BY P2.keycol
FOR XML PATH('')) =
(SELECT T1B.val AS [data()]
FROM dbo.T1 AS T1B
WHERE T1B.keycol BETWEEN T1.keycol + 1 AND T1.keycol + M.cnt — 1
ORDER BY T1B.keycol
FOR XML PATH(''));

SELECT
T1.keycol AS minkey,
T1.keycol + M.cnt — 1 AS maxkey
FROM (SELECT MAX(keycol) AS cnt FROM @P) AS M
CROSS JOIN dbo.T1
INNER JOIN @P AS P
ON P.keycol = 1
AND P.val = T1.val
AND M.cnt =
(SELECT COUNT(*)
FROM @P AS P2
INNER JOIN dbo.T1 AS T1B
ON P2.keycol > 1
AND T1B.keycol = T1.keycol + P2.keycol — 1
AND T1B.val = P2.val) + 1;

SELECT
T1.keycol AS minkey,
T1.keycol + (SELECT MAX(keycol) FROM @P) — 1 AS maxkey
FROM dbo.T1
INNER JOIN @P AS P
ON P.keycol = 1
AND P.val = T1.val
AND NOT EXISTS
(SELECT *
FROM @P AS P2
WHERE P2.keycol > 1
AND NOT EXISTS
(SELECT *
FROM dbo.T1 AS T1B
WHERE T1B.keycol = T1.keycol + P2.keycol — 1
AND T1B.val = P2.val));