Максимальное количество параллельных интервалов в T-SQL

Работа с базами данных в .NET Framework --- Оконные функции T-SQL --- Максимальное количество параллельных интервалов

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

Вот код создания таблицы Sessions и нескольких индексов, которые нам понадобятся в дальнейшем:

SET NOCOUNT ON;
USE TSQL2012;

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

CREATE TABLE dbo.Sessions
(
  keycol    INT         NOT NULL,
  app       VARCHAR(10) NOT NULL,
  usr       VARCHAR(10) NOT NULL,
  host      VARCHAR(10) NOT NULL,
  starttime DATETIME    NOT NULL,
  endtime   DATETIME    NOT NULL,
  CONSTRAINT PK_Sessions PRIMARY KEY(keycol),
  CHECK(endtime > starttime)
);
GO

CREATE UNIQUE INDEX idx_nc_app_st_et ON dbo.Sessions(app, starttime, keycol) INCLUDE(endtime);
CREATE UNIQUE INDEX idx_nc_app_et_st ON dbo.Sessions(app, endtime, keycol) INCLUDE(starttime);

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

TRUNCATE TABLE dbo.Sessions;

INSERT INTO dbo.Sessions(keycol, app, usr, host, starttime, endtime) VALUES
  (2,  'app1', 'user1', 'host1', '20120212 08:30', '20120212 10:30'),
  (3,  'app1', 'user2', 'host1', '20120212 08:30', '20120212 08:45'),
  (5,  'app1', 'user3', 'host2', '20120212 09:00', '20120212 09:30'),
  (7,  'app1', 'user4', 'host2', '20120212 09:15', '20120212 10:30'),
  (11, 'app1', 'user5', 'host3', '20120212 09:15', '20120212 09:30'),
  (13, 'app1', 'user6', 'host3', '20120212 10:30', '20120212 14:30'),
  (17, 'app1', 'user7', 'host4', '20120212 10:45', '20120212 11:30'),
  (19, 'app1', 'user8', 'host4', '20120212 11:00', '20120212 12:30'),
  (23, 'app2', 'user8', 'host1', '20120212 08:30', '20120212 08:45'),
  (29, 'app2', 'user7', 'host1', '20120212 09:00', '20120212 09:30'),
  (31, 'app2', 'user6', 'host2', '20120212 11:45', '20120212 12:00'),
  (37, 'app2', 'user5', 'host2', '20120212 12:30', '20120212 14:00'),
  (41, 'app2', 'user4', 'host3', '20120212 12:45', '20120212 13:30'),
  (43, 'app2', 'user3', 'host3', '20120212 13:00', '20120212 14:00'),
  (47, 'app2', 'user2', 'host4', '20120212 14:00', '20120212 16:30'),
  (53, 'app2', 'user1', 'host4', '20120212 15:30', '20120212 17:00');

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

app        mx
---------- -----------
app1       3
app2       4

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

TRUNCATE TABLE dbo.Sessions;

DECLARE 
  @numrows AS INT = 100000, -- кол-во сеансов
  @numapps AS INT = 10;     -- кол-во приложений

INSERT INTO dbo.Sessions WITH(TABLOCK)
    (keycol, app, usr, host, starttime, endtime)
  SELECT
    ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS keycol, 
    D.*,
    DATEADD(
      second,
      1 + ABS(CHECKSUM(NEWID())) % (20*60),
      starttime) AS endtime
  FROM
  (
    SELECT 
      'app' + CAST(1 + ABS(CHECKSUM(NEWID())) % @numapps AS VARCHAR(10)) AS app,
      'user1' AS usr,
      'host1' AS host,
      DATEADD(
        second,
        1 + ABS(CHECKSUM(NEWID())) % (30*24*60*60),
        '20120101') AS starttime
    FROM dbo.GetNums(1, @numrows) AS Nums
  ) AS D;

Вы вправе изменить число сеансов и приложений в соответствии с собственными потребностями.

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

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

Каждый сеанс можно считать состоящим из двух событий - начала сеанса, когда число активных сеансов увеличивается, и завершения сеанса, когда число сеансов уменьшается. Если взглянуть на временную шкалу, то мы увидим, что число активных сеансов остается константой в пределах между последовательными событиями начала или завершения сеанса. Более того, так как событие начала увеличивает число активных сеансов, максимальная численность сеансов должна приходиться на событие начала. В качестве примера представьте себе, что были два сеанса: сеанс приложения app1, который начался в момент P1 и закончился в P3, а также сеанс приложения с началом в P2 и концом в P4. Вот хронологический порядок событий и число активных сеансов после каждого события:

• P1, запуск - 1 активный сеанс;

• P1, запуск - 2 активных сеанса;

• P1, конец - 1 активный сеанс;

• P1, конец - 0 активных сеансов.

Число активных сеансов между двумя последовательными точками остается постоянным. Максимальное число попадает на момент начала сеанса - в данном случае на момент P2.

Традиционное основанное на наборах решение строится на основе этой логики. Решение предусматривает следующие операции:

1. Определение табличного выражения по имени TimePoints на основе запроса таблицы Sessions, которое возвращает app и starttime (псевдоним ts означает timestamp).

2. Использование второго табличного выражения Counts для запроса TimePoints (псевдоним P).

3. Во втором табличном выражении вложенный запрос используется для определения количества сеансов в таблице Sessions (псевдоним 5), у которых P.app равно S.app, P.ts равно или позже, чем S.starttime, и перед S.endtime. Вложенный запрос считает, сколько сеансов активны на протяжении каждого начала сеанса приложения.

4. Наконец во внешнем запросе выражения Counts строки группируются по app, и для каждого приложения возвращается максимальное число сеансов.

Вот код законченного решения:

WITH TimePoints AS 
(
  SELECT app, starttime AS ts FROM dbo.Sessions
),
Counts AS
(
  SELECT app, ts,
    (SELECT COUNT(*)
     FROM dbo.Sessions AS S
     WHERE P.app = S.app
       AND P.ts >= S.starttime
       AND P.ts < S.endtime) AS concurrent
  FROM TimePoints AS P
)      
SELECT app, MAX(concurrent) AS mx
FROM Counts
GROUP BY app;

Решение кажется прямолинейным и в нем не сразу заметна проблема с производительностью. Но при большом объеме данных решение выполняется очень долго. Чтобы понять, почему это происходит, посмотрите на план выполнения, показанный на рисунке:

Итератор Index Scan в верхней части плана (внешний элемент соединения Nested Loops) просматривает один из созданных ранее индексов покрытия запроса (idx_nc_app_et_st), чтобы получить все моменты начала приложения. Если p - число секций (приложений) и r - число строк в секции (сеансов в приложении), эта часть предусматривает просмотр примерно p*r строк. Внутренней частью соединения Nested Loops является итератор Index Seek для индекса idx_nc_app_et_st, который выполняется для каждой строки, возвращенной верхними входными данными. Его задача - определить строки, представляющие сеансы, которые были активны в данном приложении в момент времени, указанный во внешней строке.

А теперь обратите внимание на работу, выполняемую при каждом прогоне итератора Index Seek. Для элементов P.app (назовем это myapp) и P.ts (назовем это myts) текущей строки итератор ищет все строки, в которых S.app = myapp, S.starttime <= myts и S.endtime > myts. Так как первым ключом индекса является app, предикат поиска может эффективно выполнять фильтрацию первой части: S.app = myapp. Проблема наблюдается с двумя другими частями: S.starttime <= myts и S.endtime > myts. Нет индекса, который позволил бы предикату поиска просматривать только те строки, что удовлетворяют обоим условиям.

Предполагается, что этот предикат фильтрует строки, у которых значение находится между двумя столбцами. Это сильно отличается от ситуации, когда надо фильтровать строки, у которых столбец находится между двумя значениями. В первом случае можно задействовать индекс на фильтруемом столбце для отбора только подходящих столбцов. А вот во втором случае упорядочение по индексу можно задействовать только для одного из условий. Как показано выше, оптимизатор решил применить итератор Index Seek к индексу idx_nc_app_st_et. Поиск выполняется на основе предиката поиска S.starttime <= myts, поэтому обращение происходит только к строкам, удовлетворяющим этому предикату. Однако просматриваются все оставшиеся строки и с применением предиката S.endtime > myts возвращаются только те, что удовлетворяют этому условию.

Увидеть распределение между предикатами Seek Predicate и Predicate можно в свойствах итератора Index Seek. Вот свойство Seek Predicate:

Seek Keys[1]: Prefix: [TSQL2012].[dbo].[Sessions].app = 
    Scalar Operator([TSQL2012].[dbo].[Sessions].[app]); 
End: [TSQL2012].[dbo].[Sessions].starttime <= 
    Scalar Operator([TSQL2012].[dbo].[Sessions].[starttime])

А вот свойство Predicate:

[TSQL2012].[dbo].[Sessions].[starttime] < 
    [TSQL2012].[dbo].[Sessions].[endtime] as [S].[endtime]

Если вы еще не поняли, то скажу вам, что это очень плохо. Предикат поиска предотвращает чтение не удовлетворяющих требованиям строк, но предикат просмотра этого не делает. Строки должны считываться до применения предиката просмотра. Я уже упоминал, что итератор Index Scan считывает примерно p*r строк. Для каждой строки итератор Index Seek просматривает в среднем половину строк секции. Это означает, что если в секции r строк, итератор просматривает r² / 2 каждой секции. В целом число обрабатываемых строк составляет p*r + p*r² / 2. Это означает, что с увеличением размера секции ресурсоемкость плана растет по квадратичному закону. То есть если число строк в секции увеличивается в f раз, объем работы увеличивается примерно в f² раз. Так что с ростом размера секции производительность будет падать катастрофически.

Решение с использованием курсора

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

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

Как видите, запрос отмечает события начала сеанса числом +1, потому что такие события увеличивают общее число активных сеансов, а конец сеанса - числом -1, потому что они уменьшают число сеансов. Запрос сортирует события в хронологическом порядке по app, ts и type. Причина добавления типа в список ORDER BY - обеспечить, чтобы при совпадении моментов начала и завершения сеанса событие завершения учитывалось в первую очередь. (Как вы помните, в этом случае эти сеансы не считаются параллельными.)

План этого запроса:

Заметьте, что план очень эффективный. В нем выполняется упорядоченный просмотр двух созданных ранее индексов, а также используется итератор Merge Join для конкатенации результатов, что позволяет сохранить упорядочение по индексу и избежать операции сортировки.

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

DECLARE
  @app AS varchar(10), 
  @prevapp AS varchar (10),
  @ts AS datetime,
  @type AS int,
  @concurrent AS int, 
  @mx AS int;

DECLARE @AppsMx TABLE
(
  app varchar (10) NOT NULL PRIMARY KEY,
  mx int NOT NULL
);

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

OPEN sessions_cur;

FETCH NEXT FROM sessions_cur
  INTO @app, @ts, @type;

SET @prevapp = @app;
SET @concurrent = 0;
SET @mx = 0;

WHILE @@FETCH_STATUS = 0
BEGIN
  IF @app <> @prevapp
  BEGIN
    INSERT INTO @AppsMx VALUES(@prevapp, @mx);
    SET @concurrent = 0;
    SET @mx = 0;
    SET @prevapp = @app;
  END

  SET @concurrent = @concurrent + @type;
  IF @concurrent > @mx SET @mx = @concurrent;
  
  FETCH NEXT FROM sessions_cur
    INTO @app, @ts, @type;
END

IF @prevapp IS NOT NULL
  INSERT INTO @AppsMx VALUES(@prevapp, @mx);

CLOSE sessions_cur;

DEALLOCATE sessions_cur;

SELECT * FROM @AppsMx;

Решение обладает всеми недостатками решений на основе курсора. Что касается производительности, то приходится расходовать дополнительные энергию и время на обработку каждой строки, но масштабируется решение линейно. Если число строк в таблице примерно равно p*r, решение на основе курсора просматривает 2*p*r строк. Кроме того, ввиду дополнительной работы по обработке отдельных строк при каждом чтении курсора (назовем ее g), общие затраты равны 2pr + 2prg. Если объем данных увеличивается в f раз, затраты составляют 2prf + 2prfg. Поэтому это решение работает быстрее, чем традиционное решение на основе наборов, начиная даже с малого размера секции.

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

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

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

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

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

  UNION ALL

  SELECT app, endtime, -1
  FROM dbo.Sessions
),
C2 AS
(
  SELECT *,
    SUM(type) OVER(PARTITION BY app ORDER BY ts, type
                   ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS cnt
  FROM C1
)
SELECT app, MAX(cnt) AS mx
FROM C2
GROUP BY app;

Запрос в CTE-выражении C1 генерирует унифицированную последовательность событий начала и завершения. Запрос в CTE-выражении C2 вычисляет нарастающий итог типа, секционированный по app и упорядоченный по ts и type. Это число активных сеансов в каждый момент времени. Наконец внешний запрос группирует строки, возвращенные C2 по app и возвращает максимальное количество для каждого app (приложения).

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

Второе решение на основе оконных функций доступно в SQL Server, начиная с версии SQL Server 2005, и оно основано на использовании функции ROW_NUMBER. Об этом элегантном решении я узнал из блога Бена Фланагана. Как и в предыдущем решении, здесь события начала и завершения размещаются в хронологическом порядке и отмечаются соответственно типом события «+1» или «-1». Отличие только в той части, где вычисляются активные сеансы в каждый момент времени. Вот код законченного решения:

WITH C1 AS
(
  SELECT app, starttime AS ts, +1 AS type, keycol,
    ROW_NUMBER() OVER(PARTITION BY app ORDER BY starttime, keycol) AS start_ordinal
  FROM dbo.Sessions

  UNION ALL

  SELECT app, endtime, -1, keycol, NULL
  FROM dbo.Sessions
),
C2 AS
(
  SELECT *,
    ROW_NUMBER() OVER(PARTITION BY app ORDER BY ts, type, keycol) AS start_or_end_ordinal
  FROM C1
)
SELECT app, MAX(start_ordinal - (start_or_end_ordinal - start_ordinal)) AS mx
FROM C2
GROUP BY app;

Запрос, определяющий CTE-выражение C1, создает хронологическую последовательность событий. Здесь же используется функция ROW_NUMBER для вычисления порядкового номера событий начала (соответствующий атрибут называется start_ordinal). Атрибут start_ordinal указывает в каждом событии начала сеанса, сколько интервалов стартовали на данный момент. Для событий завершения во втором запросе используется NULL как знак подстановки для start_ordinal - это нужно для унификации событий запуска и завершения.

Запрос, определяющий CTE-выражение C2, запрашивает C1 и использует функцию ROW_NUMBER для вычисления атрибута start_or_end_ordinal на основе унифицированных событий, который определяет, сколько событий - начала и конца сеансов случилось на данный момент.

Магия происходит во внешнем запросе, который запрашивает C2. Пусть end_ordinal = start_or_end_ordinal - start_ordinal. Тогда число активных интервалов составляет start_ordinal - end_ordinal. Иначе говоря, число активных интервалов равно start_ordinal - (start_or_end_ordinal - start_ordinal). Как видите, внешнему запросу остается сгруппировать полученные из C2 строки по app и вернуть для каждого app максимальное число активных интервалов.

План этого решения показан на рисунке:

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

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

Я выполнил измерение производительности для сравнения производительности разных решений:

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