Нашли ошибку или опечатку? Выделите текст и нажмите

Поменять цветовую

гамму сайта?

Поменять
Обновления сайта
и новые разделы

Рекомендовать в Google +1

Упаковка интервалов в T-SQL

86
Исходник базы данных

Упаковка интервалов подразумевает группировку каждого набора смежных интервалов так, чтобы никакой интервал группы не перекрывался и не соседствовал (не граничил) с каким-либо интервалом других групп, и возвращение минимального начала и максимального конца каждой группы. Часто задачи упаковки в SQL Server предусматривают элемент секционирования (например, по пользователю или приложению) — тогда упаковка выполняется для каждой секции независимо.

В сценарии, который я использую для демонстрации решений задачи упаковки интервалов, применяются пользовательские сеансы приложений или служб. Используйте следующий код для создания таблиц Users (пользователи) и Sessions (сеансы) и наполнения их тестовыми данными для проверки работы решений:

SET NOCOUNT ON;
USE TSQL2012;

IF OBJECT_ID('dbo.Sessions') IS NOT NULL DROP TABLE dbo.Sessions;
IF OBJECT_ID('dbo.Users') IS NOT NULL DROP TABLE dbo.Users;

CREATE TABLE dbo.Users
(
  username  VARCHAR(14)  NOT NULL,
  CONSTRAINT PK_Users PRIMARY KEY(username)
);
GO

INSERT INTO dbo.Users(username) VALUES('User1'), ('User2'), ('User3');

CREATE TABLE dbo.Sessions
(
  id        INT          NOT NULL IDENTITY(1, 1),
  username  VARCHAR(14)  NOT NULL,
  starttime DATETIME2(3) NOT NULL,
  endtime   DATETIME2(3) NOT NULL,
  CONSTRAINT PK_Sessions PRIMARY KEY(id),
  CONSTRAINT CHK_endtime_gteq_starttime
    CHECK (endtime >= starttime)
);
GO

INSERT INTO dbo.Sessions(username, starttime, endtime) VALUES
  ('User1', '20121201 08:00:00.000', '20121201 08:30:00.000'),
  ('User1', '20121201 08:30:00.000', '20121201 09:00:00.000'),
  ('User1', '20121201 09:00:00.000', '20121201 09:30:00.000'),
  ('User1', '20121201 10:00:00.000', '20121201 11:00:00.000'),
  ('User1', '20121201 10:30:00.000', '20121201 12:00:00.000'),
  ('User1', '20121201 11:30:00.000', '20121201 12:30:00.000'),
  ('User2', '20121201 08:00:00.000', '20121201 10:30:00.000'),
  ('User2', '20121201 08:30:00.000', '20121201 10:00:00.000'),
  ('User2', '20121201 09:00:00.000', '20121201 09:30:00.000'),
  ('User2', '20121201 11:00:00.000', '20121201 11:30:00.000'),
  ('User2', '20121201 11:32:00.000', '20121201 12:00:00.000'),
  ('User2', '20121201 12:04:00.000', '20121201 12:30:00.000'),
  ('User3', '20121201 08:00:00.000', '20121201 09:00:00.000'),
  ('User3', '20121201 08:00:00.000', '20121201 08:30:00.000'),
  ('User3', '20121201 08:30:00.000', '20121201 09:00:00.000'),
  ('User3', '20121201 09:30:00.000', '20121201 09:30:00.000');

Вот результат, который нужно получить на основе этих данных:

Результат запроса для вычисления интервалов

На рисунке ниже показаны как исходные интервалы из таблицы Sessions (полосы), так и упакованные интервалы (стрелки):

Неупакованные и упакованные интервалы

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

DECLARE 
  @num_users          AS INT          = 2000,
  @intervals_per_user AS INT          = 2500,
  @start_period       AS DATETIME2(3) = '20120101',
  @end_period         AS DATETIME2(3) = '20120107',
  @max_duration_in_ms AS INT  = 3600000; -- 60 minutes
  
TRUNCATE TABLE dbo.Sessions;
TRUNCATE TABLE dbo.Users;

INSERT INTO dbo.Users(username)
  SELECT 'User' + RIGHT('000000000' + CAST(U.n AS VARCHAR(10)), 10) AS username
  FROM dbo.GetNums(1, @num_users) AS U;

WITH C AS
(
  SELECT 'User' + RIGHT('000000000' + CAST(U.n AS VARCHAR(10)), 10) AS username,
      DATEADD(ms, ABS(CHECKSUM(NEWID())) % 86400000,
        DATEADD(day, ABS(CHECKSUM(NEWID())) % DATEDIFF(day, @start_period, @end_period), @start_period)) AS starttime
  FROM dbo.GetNums(1, @num_users) AS U
    CROSS JOIN dbo.GetNums(1, @intervals_per_user) AS I
)
INSERT INTO dbo.Sessions WITH (TABLOCK) (username, starttime, endtime)
  SELECT username, starttime,
    DATEADD(ms, ABS(CHECKSUM(NEWID())) % (@max_duration_in_ms + 1), starttime) AS endtime
  FROM C;

Этот код добавляет 5 млн строк в таблицу Sessions. Я заполнил таблицу данными 2000 пользователей с 2500 сеансами у каждого на протяжении недели, причем длительность сеанса меньше или равна часу. Но вы вправе задать свои параметры и заполнить таблицу другим объемом данных.

Традиционное решение на основе наборов

Первое решение — классический вариант, который выполняет задачу, но очень неэффективно. Для него нужны следующие два индекса:

CREATE INDEX idx_user_start_end ON dbo.Sessions(username, starttime, endtime);
CREATE INDEX idx_user_end_start ON dbo.Sessions(username, endtime, starttime);

Вот код решения:

WITH StartTimes AS
(
  SELECT DISTINCT username, starttime
  FROM dbo.Sessions AS S1
  WHERE NOT EXISTS
    (SELECT * FROM dbo.Sessions AS S2
     WHERE S2.username = S1.username
       AND S2.starttime < S1.starttime
       AND S2.endtime >= S1.starttime)
),
EndTimes AS
(
  SELECT DISTINCT username, endtime
  FROM dbo.Sessions AS S1
  WHERE NOT EXISTS
    (SELECT * FROM dbo.Sessions AS S2
     WHERE S2.username = S1.username
       AND S2.endtime > S1.endtime
       AND S2.starttime <= S1.endtime)
)
SELECT username, starttime,
  (SELECT MIN(endtime) FROM EndTimes AS E
   WHERE E.username = S.username
     AND endtime >= starttime) AS endtime
FROM StartTimes AS S;

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

Как я уже говорил, это решение очень неэффективно. Для обработки тестовых данных из 5 млн строк в таблице Sessions потребовалось несколько часов. Прежде чем продолжить надо удалить ранее созданные индексы:

DROP INDEX idx_user_start_end ON dbo.Sessions;
DROP INDEX idx_user_end_start ON dbo.Sessions;

Решения на основе оконных функций

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

CREATE UNIQUE INDEX idx_user_start_id ON dbo.Sessions(username, starttime, id);
CREATE UNIQUE INDEX idx_user_end_id ON dbo.Sessions(username, endtime, id);

В первом способе в основном задействована функция ROW_NUMBER. Полное решение приведено ниже. На моем ноутбуке оно обрабатывает 5 млн строк за 47 секунд:

WITH C1 AS
-- пусть e будет кол-вом событий начала, а s = завершения сеансов
(
  SELECT id, username, starttime AS ts, +1 AS type, NULL AS e,
    ROW_NUMBER() OVER(PARTITION BY username ORDER BY starttime, id) AS s
  FROM dbo.Sessions

  UNION ALL

  SELECT id, username, endtime AS ts, -1 AS type, 
    ROW_NUMBER() OVER(PARTITION BY username ORDER BY endtime, id) AS e,
    NULL AS s
  FROM dbo.Sessions
),
C2 AS
-- пусть se является кол-вом событий начала или завершения интервалов,
-- то есть числом событий (начала или завершения) до текущего момента
(
  SELECT C1.*, ROW_NUMBER() OVER(PARTITION BY username ORDER BY ts, type DESC, id) AS se
  FROM C1
),
C3 AS
-- Для событий начала выражение s - (se - s) - 1 показывает,
-- сколько сеансов были активны непосредственно перед текущим сеансом (hence - 1)
--
-- Для событий завершения выражение (se - e) - e показывает,
-- сколько сеансов были активны непосредственно после текущего сеанса
--
-- Эти два выражения точно равны 0 в моменты соответственно
-- начала и конца упакованных интервалов
--
-- После фильтрации только событий начала или конца упакованных интервалов
-- группируем отдельные пары соседних событий начала и завершения
(
  SELECT username, ts, 
    FLOOR((ROW_NUMBER() OVER(PARTITION BY username ORDER BY ts) - 1) / 2 + 1) AS grpnum
  FROM C2
  WHERE COALESCE(s - (se - s) - 1, (se - e) - e) = 0
)
SELECT username, MIN(ts) AS starttime, max(ts) AS endtime
FROM C3
GROUP BY username, grpnum;

Код CTE-выражения C1 унифицирует события начала и конца в одну хронологическую последовательность событий (начала или конца). События начата отмечаются типом события «+1», потому что в этом случае число активных сеансов увеличивается, а события конца отмечаются типом «-1», потому что они уменьшают число активных сеансов. На рисунке ниже показана хронологическая последовательность унифицированных событий, отсортированных по username, ts, type DESC, id, а столбцы справа показывают, сколько сеансов были активны до и после каждого события.

Расположенные в хронологическом порядке события начала и завершения

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

Заметьте, что код в CTE-выражении C1 вычисляет число событий начала (атрибут по имени s), при этом значения NULL используются как знаки подстановки в этот атрибут вместо событий завершения, а также вычисляет число событий завершения (атрибут по имени e), при этом значения NULL используются как знаки подстановки в этот атрибут вместо событий начала. Код CTE-выражения C2 просто суммирует число событий начала и завершения (атрибут по имени se), секционированных по username и сортированных по ts, type DESC, id. Ниже приводится результат работы C2, отсортированный по username, ts, type DESC, id:

Результат запроса CTE C2

Все самое важное происходит в коде CTE-выражения C3. Для каждого события начала известно, сколько сеансов началось до этого (s), а также мы знаем, сколько сеансов начались или закончились до этого (se). Поэтому можно легко вычислить, сколько сеансов закончились на данный момент (se - s). Заметьте, что мы знаем, сколько сеансов началось и сколько закончилось, поэтому можно определить, сколько сеансов активны после события начала: s - (se - s). Можно к этому отнестись как к вычислению, сколько человек в комнате, если в нее вошли x и вышли y человек. Наконец, чтобы определить, сколько сеансов были активны до данного события начала, просто отнимем единицу из полученной ранее величины: s - (se - s) - 1.

Аналогично определяется число активных сеансов после каждого события завершения. Имея число сеансов, завершившихся (e), а также начавшихся или завершившихся (se) до текущего момента, можно вычислить, сколько сеансов было начато: se - е. Тогда число активных сеансов равно (se - е) - е.

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

WHERE COALESCE(s - (se - s) - 1, (se - e) - e) = 0

После отбора получаем пары смежных событий начала и завершения, каждая из которых обозначает начало и конец упакованного интервала. Нужно назначить идентификатор группы каждой паре, чтобы можно было потом свести их в одну строку. Эту задачу можно решить, назначая номера строк (назовем это n) и вычисления (n - 1)/2 + 1, где деление выполняется нацело. Для значений n = 1,2,3,4,... получаем результат 1,1,2,2,....

В SQL Server арифметический оператор деления (/) обозначает целочисленное деление, в котором операндами являются целые числа, но в Oracle этот оператор означает десятичное деление. Я добавил функцию FLOOR, чтобы код работал корректно в обеих СУБД. Таким образом, код CTE-выражения C3 возвращает такой результат:

Результат запроса CTE C3

Внешнему запросу остается выполнить группировку строк, полученных из C3 по username и grpnum и вернуть минимальное значение ts в качестве начала и ts — в качестве конца упакованного интервала.

План, созданный оптимизатором SQL Server для этого запроса, исключительно эффективный при условии, что вы создали упомянутые выше индексы idx_user_start_id и idx_user_end_id. План показан на рисунке:

План решения с использованием номеров строк

Самое замечательное в этом плане то, что в нем применяются два упорядоченных просмотра индексов, созданных для поддержки этого решения (idx_user_start_id и idx_user_end_id), причем решение полагается на эти упорядоченные просмотры при выполнении (сделайте глубокий вдох) вычисления:

  • номеров строк для счетчиков событий начала (s);

  • соединения слиянием для унификации результатов;

  • количества событий начала и завершения (se) в унифицированных наборах

  • номеров строк, которые нужны для получения grpnum после фильтрации

И все это выполняется без единого оператора сортировки! Действительно радостно видеть, что оптимизатор так точно понимает принцип представления упорядочения. Наконец хеш-агрегат используется для группировки данных по grpnum (строк, оставшихся после фильтрации). Так как у большинства операций в этом плане линейная масштабируемость, все решение должно масштабироваться примерно линейно.

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

Чтобы задействовать параллелизм «по полной», нужно инкапсулировать логику решения из предыдущего примера в табличное выражение, которое работает с одним пользователем, а затем применить его к каждому пользователю. Здесь предполагается, что у вас есть таблица с уникальными пользователями, что вполне справедливо. После этого очень удобно инкапсулировать логику решения для одного пользователя во встроенную табличную функцию, как в этом коде:

IF OBJECT_ID('dbo.UserIntervals', 'IF') IS NOT NULL DROP FUNCTION dbo.UserIntervals;
GO

CREATE FUNCTION dbo.UserIntervals(@user AS VARCHAR(14)) RETURNS TABLE
AS
RETURN
  WITH C1 AS
  (
    SELECT id, starttime AS ts, +1 AS type, NULL AS e,
      ROW_NUMBER() OVER(ORDER BY starttime, id) AS s
    FROM dbo.Sessions
    WHERE username = @user

    UNION ALL

    SELECT id, endtime AS ts, -1 AS type, 
      ROW_NUMBER() OVER(ORDER BY endtime, id) AS e,
      NULL AS s
    FROM dbo.Sessions
    WHERE username = @user
  ),
  C2 AS
  (
    SELECT C1.*, ROW_NUMBER() OVER(ORDER BY ts, type DESC, id) AS se
    FROM C1
  ),
  C3 AS
  (
    SELECT ts, 
      FLOOR((ROW_NUMBER() OVER(ORDER BY ts) - 1) / 2 + 1) AS grpnum
    FROM C2
    WHERE COALESCE(s - (se - s) - 1, (se - e) - e) = 0
  )
  SELECT MIN(ts) AS starttime, max(ts) AS endtime
  FROM C3
  GROUP BY grpnum;

После этого можно использовать оператор CROSS APPLY для применения этой функции к каждому пользователю в таблице Users:

SELECT U.username, A.starttime, A.endtime
FROM dbo.Users AS U
  CROSS APPLY dbo.UserIntervals(U.username) AS A;

Для этого запроса SQL Server генерирует параллельный план, показанный на рисунке:

План решения с использованием APPLY и номеров строк

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

Второе решение на основе оконных функций показано в примере ниже. В нем используется оконная функция агрегирования SUM с использованием особенностей определения окна, появившихся в SQL Server 2012:

WITH C1 AS
(
  SELECT username, starttime AS ts, +1 AS type, 1 AS sub
  FROM dbo.Sessions

  UNION ALL

  SELECT username, endtime AS ts, -1 AS type, 0 AS sub
  FROM dbo.Sessions
),
C2 AS
(
  SELECT C1.*,
    SUM(type) OVER(PARTITION BY username ORDER BY ts, type DESC
                   ROWS BETWEEN UNBOUNDED PRECEDING
                            AND CURRENT ROW) - sub AS cnt
  FROM C1
),
C3 AS
(
  SELECT username, ts, 
    FLOOR((ROW_NUMBER() OVER(PARTITION BY username ORDER BY ts) - 1) / 2 + 1) AS grpnum
  FROM C2
  WHERE cnt = 0
)
SELECT username, MIN(ts) AS starttime, max(ts) AS endtime
FROM C3
GROUP BY username, grpnum;
План выполнения решения с использованием оконного агрегата

В этом решении применяются принципы, похожие на те, что используются в предыдущем решении, но вместо номеров строк для вычислении числа активных сеансов в каждый момент времени задействована оконная функция агрегирования SUM. Нарастающий итог типов (как вы помните, «+1» представляет событие начала сеанса, а «-1» - событие завершения) в хронологическом порядке, секционированным но username, является числом активных сеансов в каждым момент времени. А теперь вспомним, что для событий начала сеанса надо знать число активных сеансов до этих событий, а для событий завершения число активных сеансов после этих событий. Поэтому нужно отнять единицу от числа событий начала сеанса и ничего не вычитать из числа событий завершения. Это решение генерирует атрибут но имени sub, принимающий значение «1» для событий начала и «0» для событий завершения, после этого это значение вычитается из нарастающего итога с применением следующего выражения:

SUM(type) OVER(PARTITION BY username ORDER BY ts, type DESC
             ROWS BETWEEN UNBOUNDED PRECEDING
                 AND CURRENT ROW) - sub AS cnt

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

Примененный в предыдущем решении прием создания встроенной табличной функции для одного пользователя и применения оператора APPLY для вызова этой функции для каждого пользователя в таблице Users можно использовать и в решении на основе оконного агрегата SUM. Вот код определения встроенной функции:

IF OBJECT_ID('dbo.UserIntervals', 'IF') IS NOT NULL DROP FUNCTION dbo.UserIntervals;
GO

CREATE FUNCTION dbo.UserIntervals(@user AS VARCHAR(14)) RETURNS TABLE
AS
RETURN
  WITH C1 AS
  (
    SELECT starttime AS ts, +1 AS type, 1 AS sub
    FROM dbo.Sessions
    WHERE username = @user

    UNION ALL

    SELECT endtime AS ts, -1 AS type, 0 AS sub
    FROM dbo.Sessions
    WHERE username = @user
  ),
  C2 AS
  (
    SELECT C1.*,
      SUM(type) OVER(ORDER BY ts, type DESC
                     ROWS BETWEEN UNBOUNDED PRECEDING
                              AND CURRENT ROW) - sub AS cnt
    FROM C1
  ),
  C3 AS
  (
    SELECT ts, 
      FLOOR((ROW_NUMBER() OVER(ORDER BY ts) - 1) / 2 + 1) AS grpnum
    FROM C2
    WHERE cnt = 0
  )
  SELECT MIN(ts) AS starttime, max(ts) AS endtime
  FROM C3
  GROUP BY grpnum;

А вот запрос, который применяет эту функцию к каждому пользователю:

SELECT U.username, A.starttime, A.endtime
FROM dbo.Users AS U
  CROSS APPLY dbo.UserIntervals(U.username) AS A;

Для этого решения создается план, показанный на рисунке ниже, и оно выполняется на моем ноутбуке за 13 секунд:

План выполнения решения с использованием APPLY и оконного агрегата
Пройди тесты