Новое решение задачи упаковки интервалов

Упаковка интервалов — классическая задача T-SQL, для решения которой требуется упаковать группы пересекающихся интервалов в соответствующие непрерывные интервалы. Я попытался отыскать изящное решение, в котором использовались бы только один индекс и один обход данных, и мне удалось это сделать. Ранее я уже писал о такой задаче и двух ее решениях. Два прежних решения достаточно эффективны, но для них требовалось создать два вспомогательных индекса и дважды просмотреть данные. Я попытался найти решение с единственным индексом. В этой статье я представляю новое решение и сравниваю его с двумя предшествующими.

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

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

Как мы видим, каждый сеанс был активен в течение временного интервала с временем начала и конца, хранящимся в столбцах starttime и endtime соответственно. Задача — упаковать группы пересекающихся интервалов для каждой учетной записи. Таким образом, для каждой группы пересекающихся интервалов предполагается вернуть один непрерывный интервал; в качестве начального и конечного времени упакованного интервала предполагается использовать минимальное начальное время и максимальное конечное время в группе соответственно. Для тестовых данных в листинге 1 желаемый результат показан в таблице 4.

Для проверки производительности решений необходимы более крупные наборы тестовых данных. Используйте программный код листинга 2 для заполнения таблицы Accounts 5 тысячами учетных записей, а таблицы Sessions — двумя сотнями сеансов для каждой учетной записи (всего 1 млн сеансов). Вы можете изменить эти значения, чтобы протестировать решения с другим числом строк по вашему выбору.

Новое решение с использованием оконных агрегатов

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

CREATE UNIQUE INDEX idx_start_end
    ON dbo.Sessions(actid, starttime,
    endtime, sessionid);

Следующий программный код реализует первый шаг решения:

SELECT *,
  MAX(endtime) OVER(PARTITION BY actid
                    ORDER BY starttime,
                    endtime, sessionid
                    ROWS BETWEEN UNBOUNDED
                        PRECEDING AND 1 PRECEDING)
                       AS prvend
FROM dbo.Sessions;

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

Таблица 1. Выходные данные шага 1

Естественно, первый сеанс учетной записи не имеет соответствующего предыдущего сеанса, поэтому значение prvend для первого сеанса равно NULL.

Цель второго шага — выяснить, начинается ли новый упакованный интервал с текущего интервала. На этом шаге реализована важная часть решения, поэтому обязательно разберитесь в его логике. Интервалы I1 и I2 пересекаются, если выполняются два условия: I2.endtime >= I1.starttime AND I2.starttime <= I1.endtime. Очевидно, в сеансах вплоть до предшествующего текущему для последнего упакованного интервала в качестве времени завершения будет использоваться значение prvend. Благодаря оконному предложению порядка в вычислении prvend по определению время завершения текущего сеанса больше или равно времени начала последнего упакованного интервала. Это объясняется тем, что время начала текущего сеанса больше или равно времени начала любого предшествующего сеанса, а время завершения текущего сеанса больше или равно времени начала текущего сеанса. Другими словами, одно из условий пересечения между текущим сеансом и последним упакованным интервалом всегда подразумевается. Поэтому остается явно проверить лишь другое условие. А именно, если время начала текущего сеанса меньше или равно значению prvend, то оно не начинает новый упакованный интервал; в противном случае — начинает. На основе этой логики в следующем программном коде рассчитывается флаг с именем isstart, которому присваивается значение NULL, если текущий сеанс не начинает новый упакованный интервал, и значение 1, если начинает:

WITH C1 AS
(
  SELECT *,
    MAX(endtime) OVER(PARTITION BY actid
                      ORDER BY starttime, endtime,
                      sessionid
                      ROWS BETWEEN UNBOUNDED
                      PRECEDING AND 1 PRECEDING)
                      AS prvend
  FROM dbo.Sessions
)
SELECT *
FROM C1
  CROSS APPLY ( VALUES(CASE WHEN
  starttime <= prvend THEN NULL ELSE 1
  END) ) AS A(isstart);

В таблице 2 приведены выходные данные шага 2.

Таблица 2. Выходные данные шага 2

Третий шаг решения — формирование группового идентификатора упакованных интервалов (назовем его grp) с вычислением простой суммы нарастающим итогом флага isstart от начала раздела до текущей строки. Ниже приводится программный код, реализующий этот шаг:

WITH C1 AS
(
  SELECT *,
    MAX(endtime) OVER(PARTITION BY actid
                      ORDER BY starttime, endtime,
                      sessionid
                      ROWS BETWEEN UNBOUNDED
                      PRECEDING AND 1 PRECEDING)
                      AS prvend
  FROM dbo.Sessions
)
SELECT *,
  SUM(isstart) OVER(PARTITION BY actid
                    ORDER BY starttime,
                    endtime, sessionid
                    ROWS UNBOUNDED
                    PRECEDING) AS grp
FROM C1
  CROSS APPLY ( VALUES(CASE WHEN
  starttime <= prvend THEN NULL ELSE 1
  END) ) AS A(isstart);

Таблица 3 содержит выходные данные шага 3.

Таблица 3. Выходные данные шага 3

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

Выходные данные решения показаны в таблице 4.

Таблица 4. Выходные данные полного решения

План выполнения этого решения очень эффективен. На рисунке 1 показан мой план (построенный с использованием обозревателя планов SQL Sentry (http://www.sqlsentry.com/products/plan-explorer)) для больших наборов тестовых данных.

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

Как мы видим, выполняется только один упорядоченный просмотр вспомогательного индекса. Обе оконные функции полагаются на порядок индекса, а не на явную сортировку. Я получил следующие статистические данные о производительности для этого запроса на своем компьютере: время центрального процессора = 12 545 мс, истекшее время = 4277 мс, число логических операций чтения = 3300.

Сравнение со старыми решениями

Прежние решения задачи упаковки интервалов описаны в статьях http://www.osp.ru/win2000/2014/06/13041415/ и http://www.osp.ru/win2000/2014/07/13041861/. В данной статье я просто представляю данные о производительности, чтобы вы могли сравнить их с новым решением. Помните, что для оптимального функционирования нового решения требуется только один индекс. Старые решения разбивают события начала и завершения, чтобы разделить результирующие строки и организовать их в хронологическом порядке. Поэтому для их оптимальной производительности требуется два вспомогательных индекса: один для событий начала и другой для событий завершения. Используйте следующий программный код для создания рекомендуемых индексов:

CREATE UNIQUE INDEX idx_start ON
   dbo.Sessions(actid, starttime, sessionid);
CREATE UNIQUE INDEX idx_end ON
   dbo.Sessions(actid, endtime, sessionid);

В листинге 4 приводится одно из старых решений (назовем его старым решением 1). Это решение основано на оконном агрегате для вычисления суммы с нарастающим итогом и номера строк.

План для старого решения 1 показан на рисунке 2.

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

Статистика производительности для старого решения 1: время центрального процессора = 6047 мс, истекшее время = 6549 мс, число логических операций чтения = 4974. В новом решении используется меньше операций чтения, хотя при этом расходуется больше времени центрального процессора.

В листинге 5 приведено другое старое решение (назовем его старым решением 2). Это решение основывается только на номерах строк.

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

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

Статистика производительности для старого решения 2: время центрального процессора = 2719 мс, истекшее время = 3147 мс, число логических операций чтения = 4974. Новое решение немного медленнее и требует больше времени центрального процессора, но в нем используется меньше операций чтения.

Итак, я нашел решение задачи упаковки интервалов, требующее лишь одного вспомогательного индекса и единственного прохода по данным. Любопытно сравнение с прежними решениями. При наличии лишь одного индекса вместо двух новое решение оказывает меньшее негативное влияние на производительность записи и требует меньшего числа операций чтения. Длительность выполнения меньше, чем у старого решения 1 и немного больше, чем у старого решения 2. Эти результаты показывают, сколь полезно повторно обращаться к известным задачам и никогда не считать дело завершенным. Бывает, что удается найти новые решения, улучшающие некоторые характеристики прежних.

Листинг 1. DDL и тестовые данные (малый набор)

SET NOCOUNT ON;
USE tempdb;
IF OBJECT_ID('dbo.Sessions') IS NOT NULL DROP TABLE dbo.Sessions;
IF OBJECT_ID('dbo.Accounts') IS NOT NULL DROP TABLE dbo.Accounts;
CREATE TABLE dbo.Accounts
(
  actid INT NOT NULL,
  CONSTRAINT PK_Accounts PRIMARY KEY(actid)
);
GO

INSERT INTO dbo.Accounts(actid) VALUES(1), (2), (3);

CREATE TABLE dbo.Sessions
(
  sessionid INT          NOT NULL IDENTITY(1, 1),
  actid     INT          NOT NULL,
  starttime DATETIME2(0) NOT NULL,
  endtime   DATETIME2(0) NOT NULL,
  CONSTRAINT PK_Sessions PRIMARY KEY(sessionid),
  CONSTRAINT CHK_endtime_gteq_starttime
    CHECK (endtime >= starttime)
);
GO
INSERT INTO dbo.Sessions(actid, starttime, endtime) VALUES
  (1, '20151231 08:00:00', '20151231 08:30:00'),
  (1, '20151231 08:30:00', '20151231 09:00:00'),
  (1, '20151231 09:00:00', '20151231 09:30:00'),
  (1, '20151231 10:00:00', '20151231 11:00:00'),
  (1, '20151231 10:30:00', '20151231 12:00:00'),
  (1, '20151231 11:30:00', '20151231 12:30:00'),
  (2, '20151231 08:00:00', '20151231 10:30:00'),
  (2, '20151231 08:30:00', '20151231 10:00:00'),
  (2, '20151231 09:00:00', '20151231 09:30:00'),
  (2, '20151231 11:00:00', '20151231 11:30:00'),
  (2, '20151231 11:32:00', '20151231 12:00:00'),
  (2, '20151231 12:04:00', '20151231 12:30:00'),
  (3, '20151231 08:00:00', '20151231 09:00:00'),
  (3, '20151231 08:00:00', '20151231 08:30:00'),
  (3, '20151231 08:30:00', '20151231 09:00:00'),
  (3, ‘20151231 09:30:00’, ‘20151231 09:30:00’);
GO

Листинг 2. Большой набор тестовых данных

-- 1 000 000 интервалов
DECLARE
  @num_accounts AS INT = 5000,
  @sessions_per_account AS INT = 200,
  @start_period AS DATETIME2(3) = '20160101',
  @end_period AS DATETIME2(3) = '20160201',
  @max_duration_in_seconds AS INT = 86400;
TRUNCATE TABLE dbo.Sessions;
TRUNCATE TABLE dbo.Accounts;
INSERT INTO dbo.Accounts(actid)
  SELECT A.n AS actid
  FROM TSQLV3.dbo.GetNums(1, @num_accounts) AS A;
WITH C AS
(
  SELECT A.n AS actid,
    DATEADD(second,
      ABS(CHECKSUM(NEWID())) %
        (DATEDIFF(s, @start_period, @end_period) - @max_duration_in_seconds),
      @start_period) AS starttime
  FROM TSQLV3.dbo.GetNums(1, @num_accounts) AS A
    CROSS JOIN TSQLV3.dbo.GetNums(1, @sessions_per_account) AS I
)
INSERT INTO dbo.Sessions WITH (TABLOCK) (actid, starttime, endtime)
  SELECT actid, starttime,
    DATEADD(second,
      ABS(CHECKSUM(NEWID())) % (@max_duration_in_seconds + 1),
      starttime) AS endtime
  FROM C;
GO

Листинг 3. Полное новое решение

WITH C1 AS
(
  SELECT *,
    MAX(endtime) OVER(PARTITION BY actid
                      ORDER BY starttime, endtime, sessionid
                      ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) AS prvend
  FROM dbo.Sessions
),
C2 AS
(
  SELECT *,
    SUM(isstart) OVER(PARTITION BY actid
                      ORDER BY starttime, endtime, sessionid
                      ROWS UNBOUNDED PRECEDING) AS grp
  FROM C1
    CROSS APPLY ( VALUES(CASE WHEN starttime <= prvend THEN NULL ELSE 1 END) ) AS A(isstart)
)
SELECT actid, MIN(starttime) AS starttime, MAX(endtime) AS endtime
FROM C2
GROUP BY actid, grp;

Листинг 4. Прежнее решение с использованием оконного агрегата и номеров строк

WITH C1 AS
(
  SELECT sessionid, actid, starttime AS ts, +1 AS type
  FROM dbo.Sessions

  UNION ALL

  SELECT sessionid, actid, endtime AS ts, -1 AS type
  FROM dbo.Sessions
),
C2 AS
(
  SELECT *,
    SUM(type) OVER(PARTITION BY actid
                   ORDER BY ts, type DESC
                   ROWS UNBOUNDED PRECEDING)
      - CASE WHEN type = 1 THEN 1 ELSE 0 END AS cnt
  FROM C1
),
C3 AS
(
  SELECT *,
    FLOOR((ROW_NUMBER() OVER(PARTITION BY actid ORDER BY ts) + 1) / 2) AS p
  FROM C2
  WHERE cnt = 0
)
SELECT actid, MIN(ts) AS starttime, max(ts) AS endtime
FROM C3
GROUP BY actid, p;

Листинг 5. Старое решение с использованием только номеров строк

WITH C1 AS
(
  SELECT sessionid, actid, starttime AS ts, +1 AS type,
    ROW_NUMBER() OVER(PARTITION BY actid ORDER BY starttime, sessionid) AS s,
    NULL AS e
  FROM dbo.Sessions
  UNION ALL
  SELECT sessionid, actid, endtime AS ts, -1 AS type,
    NULL AS s,
    ROW_NUMBER() OVER(PARTITION BY actid ORDER BY endtime, sessionid) AS e
  FROM dbo.Sessions
),
C2 AS
(
  SELECT *,
    ROW_NUMBER() OVER(PARTITION BY actid ORDER BY ts, type DESC, sessionid) AS se
  FROM C1
),
C3 AS
(
  SELECT *,
    FLOOR((ROW_NUMBER() OVER(PARTITION BY actid ORDER BY ts) + 1) / 2) AS p
  FROM C2
    CROSS APPLY ( VALUES(s - (se - s) - 1, (se - e) - e) ) AS A(cs, ce)
  WHERE cs = 0 OR ce = 0
)
SELECT actid, MIN(ts) AS starttime, MAX(ts) AS endtime
FROM C3
GROUP BY actid, p;