Обнаружение пересечений в интервалах

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

В моем примере используется таблица, именуемая Intervals, со столбцами keycol, low и high. В обоих предложенных решениях с успехом используется индекс (low, high, keycol). Low и high — целочисленные столбцы, представляющие собой разделители интервалов. На практике вы, вероятно, работаете в основном с разделителями даты и времени, а не с целыми числами, но предлагаемые решения будут работать в любом случае. Интервалы в моей таблице закрыто-открытые, то есть ограничитель low инклюзивный, а ограничитель high — эксклюзивный.

Наша задача заключается в том, чтобы подготовить запрос, который возвращает 1, если в данных существуют пересечения, и 0 — в противном случае. Пересечения существуют, если имеется хотя бы два интервала Iw и Iz, в которых Iw.low < Iz.high и Iw.high > Iz.low. Например, интервалы (10, 20) и (19, 21) пересекаются, как и (10, 20), (15, 15). Последний интервал называется вырожденным (low = high). Однако интервалы (10, 20) и (20, 30) не пересекаются.

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

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

Выполните программный код листинга 2, чтобы создать таблицу Intervals вместе с поддерживающим индексом.

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

Этот программный код заполняет таблицу сначала 10 000 интервалов, но вы можете протестировать решения с различными размерами таблиц. Используйте программный код, приведенный в листинге 4, чтобы запросить выборку из 10 строк из таблицы.

Этот программный код формирует выходные данные, показанные на экране 1.

Экран 1. Выходные данные запроса 10 строк

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

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

DELETE FROM dbo.Intervals WHERE
   keycol = 2147483647;

Традиционное решение

В традиционном решении (назовем его решением 1) используется два предиката EXISTS. Внутренний предикат EXISTS с вложенным запросом идентифицирует интервалы, пересекающиеся с другими интервалами. Внешний предикат EXISTS проверяет, возвращает ли внутренний запрос хотя бы один интервал, пересекающийся с другими интервалами. Программный код дает псевдоним I1 внешнему экземпляру таблицы Intervals и I2 — внутреннему экземпляру. Вложенный запрос фильтрует интервалы в I2, которые пересекаются с интервалом в I1, где 1.keycol < I2.keycol (чтобы убедиться, что мы не сравниваем интервал с самим собой) и I1.low < I2.high AND I1.high > I2.low. В листинге 6 приводится полный программный код решения.

План для этого запроса показан на экране 2 для тестовых данных размером 10 000 строк.

Экран 2. План исполнения для решения 1

Оператор Constant Scan определяет таблицу констант с одной строкой. Внешний оператор Nested Loops (Left Semi Join) завершает внутреннюю работу сразу после того, как обнаружена строка, что означает наличие по крайней мере одного интервала, пересекающегося с другими интервалами.

Внутренний оператор Nested Loops (Left Semi Join) завершает работу, в ходе которой выполняется поиск пересекающихся интервалов для данного интервала, как только обнаружен один случай пересечения.

Если пересечений не существует, завершения работы не происходит. Имеет место один полный проход для внешних входных данных внутреннего оператора Nested Loops плюс полный проход для данных в строке. Это означает, что для образца размером N строк число строк, сканируемых в соответствии с этим планом, равно N + N^2. Например, если в таблице только 10 000 строк, этот план сканирует 100 010 000 строк. Весьма неважно с точки зрения масштабирования решения.

На основе предположений, именуемых включением и вложением, оптимизатор выбирает сканирование, а не поиск в индексе, так как предполагается, что если вы ищете что-то, то этот объект существует. Если пересечения нет, это приводит к полному сканированию индекса по строкам. Кроме того, отсутствует предварительная фильтрация строк подсистемой хранилища.

Для выполнения этого запроса на моем компьютере потребовалось 14 секунд, а в таблице насчитывалось всего 10 000 строк.

Производительность можно повысить, принудив SQL Server выполнять поиск в индексе на основе предиката диапазона, задействующего начальный ключ индекса (I2.low < I1.high) с использованием оператора FORCESEEK. Таким образом достигаются два преимущества. Одно из них состоит в том, что, хотя вам придется выполнить поиск, чтобы добраться до конечного объекта строки, вы будете сканировать примерно половину строки для каждой строки (1 для первой, 2 для второй, N для N-ной). Поэтому получаем (N + N^2)/2 плюс дополнительный проход для внешних входных данных соединения, что дает в итоге N + (N + N^2)/2. Другое преимущество состоит в том, что такой план должен обеспечить передачу фильтрации остаточных предикатов (помимо предиката поиска) в подсистему хранилища. Предварительная фильтрация в подсистеме хранилища более эффективна, чем последующая фильтрация обработчиком запросов.

В листинге 7 приводится решение 1 с указанием FORCESEEK.

План для этого решения показан на экране 3.

Экран 3. План исполнения для решения 1 с указанием FORCESEEK

Вы можете увидеть как предикат поиска, основанный на предикате диапазона для начального ключа индекса, так и предварительную фильтрацию, выполняемую подсистемой хранилища для обработки остаточных предикатов, в свойствах нижнего оператора Index Seek. Как уже отмечалось, в дополнение к стоимости поисков, которые доходят до конечного элемента индекса каждой строки, этот план обрабатывает примерно N + (N + N^2)/2 строк (50 015 000 для набора тестовых данных из 10 000 строк), по сравнению с вдвое большим количеством в предыдущем решении. Это обстоятельство в сочетании с предварительной фильтрацией подсистемой хранилища приводит к тому, что запрос выполняется за 2 секунды для таблицы с 10 000 строк, по сравнению с 14 секундами без указания FORCESEEK. Читатель Адам Механик предложил совет для диагностики: вы можете заставить оптимизатор заменить остаточный предикат фильтром обработчика запросов, добавив флаг трассировки запроса 9130 (добавьте OPTION (QUERYTRACEON 9130) в конце запроса). Время выполнения последнего запроса с флагом трассировки увеличится в несколько раз.

К сожалению, даже с улучшением FORCESEEK сложность этого решения при масштабировании увеличивается по квадратичному закону. Я приведу результаты тестов производительности, чтобы сравнить различные решения с разными объемами данных, но вы можете представить, насколько плохо масштабируется усовершенствованное решение: для его выполнения на моем компьютере с 10 000 000 строк тестовых данных потребовалось бы немногим более 20 дней!

Новое решение

С помощью комбинации некоторых логических, математических и оконных функций можно добиться гораздо лучших результатов, чем при использовании классического решения. В основе нового решения (назовем его решение 2) лежит предположение, что если имеется хотя бы один случай пересекающихся интервалов, то существует по крайней мере одно событие двух последовательных интервалов Iw <= Iz (на основе порядка low, high, keycol), которые пересекаются.

Доказательство

1. Рассмотрим пример только с одним случаем пересекающихся интервалов Iw и Iz, с порядком Iw <= Iz.

Поскольку это пересекающиеся интервалы, Iw.low < Iz.high и Iw.high > Iz.low.

Покажем, что если существует только один случай пересекающихся интервалов, как в (1), то они должны быть последовательными.

2. Если бы Iw и Iz были непоследовательны, то существовал бы по крайней мере еще один интервал Ix, где Iw <= Ix <= Iz.

3. В соответствии с (1), Ix не пересекается с Iw и Iz, поэтому Iw.high <= Ix.low <= Ix.high <= Iz.low, следовательно, Iw.high <= Iz.low.

Вывод из (3) о том, что Iw.high <= Iz.low, противоречит одному из результатов (1), в соответствии с которым Iw.high > Iz.low. Поэтому если существует только один случай пересекающихся интервалов, то они должны быть последовательными.

Аналогично доказывается, что, если добавить интервал Iy между двумя пересекающимися интервалами Iw и Iz, он должен пересекаться с Iw, Iz или обоими. Потому что в противном случае вы будете иметь: Iw.high <= Iy.low <= Iy.high <= Iz.low, а это означает, что Iw.high <= Iz.low.

Это противоречит результату (1), в соответствии с которым Iw.high > Iz.low.

Поэтому, если есть по крайней мере один случай пересекающихся интервалов, то существует по крайней мере один случай последовательных интервалов, которые пересекаются. Что и требовалось доказать.

На основе этого вывода можно использовать пару функций LEAD, чтобы возвратить для каждого текущего интервала разделители следующего интервала (в порядке low, high, keycol) и проверить, пересекаются ли они. Предикат EXISTS может завершить работу, если существует одно пересечение. В листинге 8 приводится новое решение (решение 2) на основе этой логики.

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

На основе Iw <= Iz, если Iw.high > Iz.low, значит, должно быть Iw.low < Iz.high, и потому Iw и Iz пересекаются.

Доказательство

Известно, что Iw.low <= Iz.low <= Iz.high, поэтому Iw.low <= Iz.high. Единственный случай, когда Iw.low = Iz.high, будет, если оба интервала вырожденные (low = high). Если в действительности Iw.high > Iz.low, то оба интервала не могут быть вырожденными. Поэтому Iw.low < Iz.high. Что и требовалось доказать.

В листинге 9 приводится запрос, реализующий решение 2 после упрощения. План для этого запроса показан на экране 4.

Экран 4. План исполнения для решения 2 в строковом режиме

Обратите внимание, что выполняется только один обход данных (когда не существует пересечений), на основе индекса; поэтому явной сортировки для поддержки вычисления функции LEAD не требуется. Если существуют пересечения, оператор Left Semi Join завершает сканирование сразу же после обнаружения первого пересечения. Это решение выполняется за 23 миллисекунды при 10 000 строках на моем компьютере и масштабируется линейно. Оно неплохое, но, верьте или нет, пользователи SQL Server 2016 и более новых версий могут еще улучшить его. Создавая фильтрованный некластеризованный индекс dummy columnstore, вы включаете пакетную обработку с помощью нового оператора пакетного режима Window Aggregate. Подробнее об этом приеме можно прочитать в серии статей об агрегатном оконном операторе пакетного режима в SQL Server 2016, начиная с части 1 (опубликована в Windows IT Pro/RE № 9 за 2016 год).

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

Экран 5. План исполнения для решения 2 в пакетном режиме

Здесь вы вновь видите единственный упорядоченный проход индекса, но на этот раз оператор пакетного режима Window Aggregate выполняет вычисление оконной функции LEAD вместо первоначальных шести операторов построчного режима в преды­дущем плане. Это решение выполняется за 12 миллисекунд с 10 000 строками на моем компьютере и масштабируется линейно. Снижение времени с 14 секунд до 12 миллисекунд — неплохой результат. Учтите, что таблица очень невелика. Масштабирование классического решения происходит по квадратичному закону, а нового решения — линейно, поэтому по мере роста таблицы различие существенно увеличивается. В следующем разделе приведены результаты тестов производительности.

Тест производительности

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

Чтобы отключить пакетную обработку, используйте DBCC TRACEON (9453) или запустите новое решение без индекса dummy columnstore.

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

Например, вспомните, что сложность усовершенствованного классического решения — N + (N + N^2)/2. Поэтому я выполнил его с тестовым набором 50 000 строк и получил результат 44,514 секунды. Я подсчитал среднее время обработки одной строки, отталкиваясь от сложности с помощью вычислений в листинге 12.

Полученный результат — 3,51978881267124 E-08 секунд на строку.

Я могу прогнозировать время выполнения запроса для таблицы любого размера, вставив время выполнения строки в формулу сложности решения:

DECLARE @perrow AS FLOAT =
   3.51978881267124 E-08,
   @numrows AS INT = 1000000;
SELECT (@numrows + (@numrows +
    SQUARE (@numrows))/2) * @perrow;

На экране 6 показаны результаты теста производительности при сравнении нового решения (решения 2) в строковом режиме и в пакетном режиме. На экране 7 приведено сравнение усовершенствованного классического решения (решение 1) с новым решением (решение 2) в пакетном режиме.

Экран 6. Результаты теста производительности при сравнении решения 2 в строковом режиме и в пакетном режиме

Экран 7. Сравнение усовершенствованного решения 1 с решением 2 в пакетном режиме

Как мы видим, в пакетном режиме время выполнения решения 2 составляет примерно одну треть в сравнении со строковым режимом на моем тестовом компьютере.

При 10 000 000 строк для выполнения усовершенствованного решения 1 на моем компьютере потребуется немногим более 20 дней, по сравнению с решением 2 в пакетном режиме, которое занимает 6 секунд.

Итого 20 дней и 6 секунд — что вы выбираете?

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

И наконец, позвольте вам представить виртуальную доску, которую я использовал при работе с логикой, поддерживающей новое решение (см. рисунок).

Рисунок. Схема логики, поддерживающей новое решение

SET NOCOUNT ON;
USE tempdb;

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.Intervals', N'U') IS NOT NULL DROP TABLE dbo.Intervals;
GO

CREATE TABLE dbo.Intervals
(
  keycol INT NOT NULL
    CONSTRAINT PK_Intervals PRIMARY KEY,
  low    INT NOT NULL,
  high   INT NOT NULL,
  CONSTRAINT CHK_Intervals_high_gteq_low CHECK(high >= low),
  INDEX idx_low_high_keycol NONCLUSTERED(low, high, keycol)
);

DECLARE @numintervals AS INT = 10000; -- измените в соответствии со своими предпочтениями
TRUNCATE TABLE dbo.Intervals ;

INSERT INTO dbo.Intervals WITH (TABLOCK) (keycol, low, high)
  SELECT n, (n - 1) * 10 + 1 AS low, n * 10 AS high
  FROM dbo.GetNums(1, @numintervals) AS Nums;

SELECT TOP (10) keycol, low, high
FROM dbo.Intervals
ORDER BY low, high, keycol;

INSERT INTO dbo.Intervals(keycol, low, high)
  SELECT TOP (1) 2147483647 AS keycol, low, high
  FROM dbo.Intervals
  ORDER BY low DESC, high DESC, keycol DESC;

SELECT
  CASE
    WHEN EXISTS
        ( SELECT *
          FROM dbo.Intervals AS I1
          WHERE EXISTS
            ( SELECT *
              FROM dbo.Intervals AS I2
              WHERE I1.keycol < I2.keycol
                AND I1.low < I2.high
                AND I1.high > I2.low ) )
      THEN 1
    ELSE 0
  END AS intersectionsexist;

SELECT
  CASE
    WHEN EXISTS
        ( SELECT *
          FROM dbo.Intervals AS I1
          WHERE EXISTS
            ( SELECT *
              FROM dbo.Intervals AS I2 WITH (FORCESEEK)
              WHERE I1.keycol < I2.keycol
                AND I1.low < I2.high
                AND I1.high > I2.low ) )
      THEN 1
    ELSE 0
  END AS intersectionsexist;

SELECT
  CASE
    WHEN EXISTS
        ( SELECT *
          FROM ( SELECT keycol, low AS curlow, high AS curhigh,
                   LEAD(low) OVER(ORDER BY low, high, keycol) AS nextlow,
                   LEAD(high) OVER(ORDER BY low, high, keycol) AS nexthigh
                 FROM dbo.Intervals ) AS D
          WHERE curlow < nexthigh
            AND curhigh > nextlow )
      THEN 1
    ELSE 0
  END AS intersectionsexist;

SELECT
  CASE
    WHEN EXISTS
        ( SELECT *
          FROM ( SELECT keycol, low AS curlow, high AS curhigh,
                   LEAD(low) OVER(ORDER BY low, high, keycol) AS nextlow
                 FROM dbo.Intervals ) AS D
          WHERE curhigh > nextlow )
      THEN 1
    ELSE 0
  END AS intersectionsexist;

CREATE NONCLUSTERED COLUMNSTORE INDEX idx_cs_dummy
  ON dbo.Intervals(keycol) WHERE keycol = -1 AND keycol = -2;

SET NOCOUNT ON;
USE tempdb;

DECLARE @numintervals AS INT = 10000;

TRUNCATE TABLE dbo.Intervals ;

INSERT INTO dbo.Intervals WITH (TABLOCK) (keycol, low, high)
  SELECT n, (n - 1) * 10 + 1 AS low, n * 10 AS high
  FROM dbo.GetNums(1, @numintervals) AS Nums;
GO

DECLARE @start AS DATETIME2 = SYSDATETIME();
DECLARE @intersectionsexist AS INT =
  CASE
    WHEN EXISTS
        ( SELECT *
          FROM dbo.Intervals AS I1
          WHERE EXISTS
            ( SELECT *
              FROM dbo.Intervals AS I2 WITH (FORCESEEK)
              WHERE I1.keycol < I2.keycol
                AND I1.low < I2.high
                AND I1.high > I2.low ) )
      THEN 1
    ELSE 0
  END;
PRINT 'Solution 1 duration: ' + STR(DATEDIFF(ms, @start, SYSDATETIME()) / 1000., 10, 3) + ' seconds.';
GO

DECLARE @start AS DATETIME2 = SYSDATETIME();

DECLARE @intersectionsexist AS INT =
  CASE
    WHEN EXISTS
        ( SELECT *
          FROM ( SELECT keycol, low AS curlow, high AS curhigh,
                   LEAD(low) OVER(ORDER BY low, high, keycol) AS nextlow
                 FROM dbo.Intervals ) AS D
          WHERE curhigh > nextlow )
      THEN 1
    ELSE 0
  END;

PRINT ‘Solution 2 duration: ‘ + STR(DATEDIFF(ms, @start, SYSDATETIME()) / 1000., 10, 3) + ‘ seconds.’;

DECLARE @numrows AS INT = 50000, @runtimems AS INT = 44.514;
SELECT @runtimems / (@numrows + (@numrows + SQUARE(@numrows)) / 2);