Интервалы и счетчики, часть 1. Определяем дискретные интервалы и число перекрывающихся исходных интервалов

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

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

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

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

Во всех задачах, рассматриваемых в статьях этой серии, используется один набор тестовых данных. В данные входит таблица с именем Sessions, в которой содержатся сеансы, сопоставляемые различным приложениям. Столбец app представляет приложение (назовем его элементом секционирования), а столбцы starttime и endtime представляют точки начала и завершения интервала сеанса, соответственно. В столбцах starttime и endtime используется тип DATETIME2(0) с точностью до одной секунды.

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

Индекс с именем idx_start определен на списке ключей (app, starttime, keycol), а индекс с именем idx_end определен на списке ключей (app, endtime, keycol).

С помощью программного кода в листинге 2 заполним таблицу Sessions малым набором тестовых данных.

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

Рисунок 1. Интервалы

Для генерации большого набора тестовых данных понадобится вспомогательная функция GetNums, которая принимает на вход параметры @low и @high и возвращает последовательность целых чисел в нужном диапазоне. Код функции GetNums приведен в листинге 3.

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

Можно управлять числом приложений и общим число строк в тестовых данных, задавая параметры @numapps и @numrows, соответственно. Программный код в листинге 4 вносит в таблицу Apps 100 приложений, а в таблицу Sessions - 2 000 000 строк.

Задача: подсчет для дискретных интервалов

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

Рисунок 2. Подсчет по дискретным интервалам

На рисунке 3 показан желаемый выход запроса.

Рисунок 3. Подсчет перекрывающихся интервалов во время каждого дискретного интервала

В желаемом результате на рисунке 3 предполагается, что пользователь не заинтересован в интервалах, для которых результат подсчета равен нулю. Например, между 8:45 и 9:00 зарегистрировано 0 активных сеансов с подключением к app2. Иногда по каким-то причинам бывает полезно получить сведения о таких интервалах, и в этом случае в решении необходимо предусмотреть соответствующие меры.

Решение на основе агрегатов PIVOT, LEAD и SUM для окна

Первый шаг - составить одну последовательность начальных событий и событий завершения, отмечая начальные события типом события +1 (увеличивает число активных сеансов), а события завершения - -1 (число уменьшается). Чтобы сформировать такую последовательность событий, следует объединить результаты двух запросов - возвращающего начальные события и возвращающего события завершения. Например:

SELECT app, starttime AS ts, +1 AS type FROM dbo.Sessions UNION ALL SELECT app, endtime AS ts, -1 AS type FROM dbo.Sessions ORDER BY app, ts;

На рисунке 4 показан выход этого запроса.

Рисунок 4. Последовательность событий

Затем необходимо сгруппировать последовательность по приложениям и значениям в столбце ts, выполняя сведение количества событий по типу (помните, 1 для начала и -1 для завершения). Получается одна строка для каждого отдельного приложения и метки времени со столбцом, содержащим [1] для начальных событий и [-1] для событий завершения. Эта временная метка указывает на начало дискретного интервала. Затем вы применяете функцию LEAD, чтобы получить следующее значение ts, отмечающее завершение дискретного интервала. Число сеансов, перекрывающихся с текущим интервалом, представляет собой нарастающую итоговую сумму начальных событий за вычетом событий завершения. После того, как определено обобщенное табличное выражение (CTE) с именем C1 на основе предшествующего запроса, внешний запрос выглядит следующим образом:

SELECT app, ts AS starttime, LEAD(ts) OVER(PARTITION BY app ORDER BY ts) AS endtime, SUM([1]-[-1]) OVER(PARTITION BY app ORDER BY ts ROWS UNBOUNDED PRECEDING) AS cnt FROM C1 PIVOT(COUNT(type) FOR type IN([1],[-1])) AS P;

Код в листинге 5 объединяет запросы.

На рисунке 5 показан результат, формируемый программным кодом в листинге 5.

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

Обратите внимание, что в результат входят интервалы с подсчетом, равным нулю, а также интервал со значением starttime, равным последнему событию завершения, и NULL в столбце endtime. Естественно, желательно удалить строки со значением NULL в столбце endtime. Для этого можно определить CTE на основе внешнего запроса (с именем C2) и применить фильтр endtime IS NOT NULL в запросе к C2. Если нужно удалить интервалы с подсчетом, равным 0, используйте фильтр cnt > 0, который также удаляет строки со значением NULL в столбце endtime, так как подсчет здесь всегда нулевой. В листинге 6 приводится полное решение (предполагается, что нужно сохранить только интервалы с перекрывающимися сеансами).

Это решение сформировало план, показанный на рисунке 6, на моем компьютере для большого набора данных. Время выполнения составило 37 секунд.

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

Самая интересная особенность этого решения заключается в том, что два взаимосвязанных индекса idx_start и idx_end проверяются по очереди, но во всем плане нет ни одного явного оператора сортировки. Группирование, сведение, функции LEAD и SUM для окна и даже предложение ORDER BY - выполнение всех операций зависит от сохранения порядка данных.

Решение на основе агрегатов LEAD и ROW_NUMBER для окна

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

• порядковый номер для начальных событий (обозначается s) запроса начала;
• порядковый номер для событий завершения (обозначается e) запроса завершения;
• порядковый номер для событий начала или завершения (обозначается se) объединенного начала-завершения.

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

WITH C1 AS ( SELECT app, starttime AS ts, +1 AS type, keycol, ROW_NUMBER() OVER(PARTITION BY app ORDER BY starttime, keycol) AS s, - start ordinal NULL AS e FROM dbo.Sessions UNION ALL SELECT app, endtime, -1 AS type, keycol, NULL AS s, ROW_NUMBER() OVER(PARTITION BY app ORDER BY endtime, keycol) AS e - end ordinal FROM dbo.Sessions ) SELECT *, ROW_NUMBER() OVER(PARTITION BY app ORDER BY ts, type, keycol) AS se - start or end ordinal FROM C1;

На рисунке 7 показан результат этого запроса.

Рисунок 7. Последовательность событий с порядковыми номерами

Затем вычисляется число активных сеансов после каждого события. Обратите внимание (рисунок 7), что для событий начала имеется порядковый номер начала (s) и порядковые номера начала и завершения (se). Можно вычислить, сколько событий завершения произошло до этой точки, e = se - s. Затем можно вычислить число активных сеансов как cnt = s - e, или более полно как cnt = s - (se - s). Аналогично можно провести подсчет после событий завершения с использованием se и e: cnt = (se - e) - e. Чтобы получить подсчет после событий начала и завершения в одном целевом столбце, используйте формулу cnt = COALESCE(s - (se - s), s - (se - s)). Также можно возвращать вместе с каждым событием метку времени следующего события. Это достигается с помощью функции LEAD. Предположим, CTE с именем C2 определено на основе внешнего запроса в предыдущем образце программного кода. В этом случае можно задействовать следующий запрос к C2, чтобы выполнить подсчет и определить следующую метку времени:

SELECT *, (COALESCE( s - (se - s), - count of active intervals after start event (se - e) - e) - count of active intervals after end event ) AS cnt, LEAD(ts) OVER(PARTITION BY app ORDER BY ts, type, keycol) AS nextts FROM C2

Обратите внимание на список ORDER BY функции LEAD. Благодаря ему начальные события располагаются после событий завершения. Для разрешения конфликтов используется keycol. Точки, в которых ts отличается от nextts, представляют дискретные интервалы, и подсчеты, связанные с этими точками, охватывают все события в этих точках (то есть представляют подсчеты перекрывающихся сеансов с этими интервалами). Завершающий шаг - определить CTE на основе последнего запроса (с именем C3) и обеспечить фильтрацию с использованием внешнего запроса событий, для которых ts <> nextts. Если вы не заинтересованы в интервалах с нулевыми подсчетами, удалите их. Вот внешний запрос к C3:

SELECT app, ts AS starttime, nextts AS endtime, cnt FROM C3 WHERE ts <> nextts AND cnt > 0;

Листинг 7 содержит полное решение.

На рисунке 8 показан план для данного решения.

Рисунок 8. План запроса в листинге 7

Этот план более эффективен, чем план в предыдущем решении, благодаря двум особенностям. Он не связан с группированием и уменьшает число операторов Window Spool. На моем компьютере этот запрос выполнялся в течение 22 секунд (почти вдвое быстрее, чем первое решение).

Продолжение следует

Это первая из нескольких статей, в которых рассматриваются проблемы, связанные с интервалами, в том числе с различными подсчетами. Мы разобрали способы идентификации дискретных интервалов и подсчеты перекрывающихся исходных интервалов. В статье показано одно решение с использованием агрегатов PIVOT, LEAD и SUM для окна, а также более эффективное решение с применением функций ROW_NUMBER и LEAD. В следующий раз я продолжу исследование этой задачи, речь пойдет о дальнейших улучшениях и различных ее вариантах.