(495) 925-0049, ITShop интернет-магазин 229-0436, Учебный Центр 925-0049
  Главная страница Карта сайта Контакты
Поиск
Вход
Регистрация
Рассылки сайта
 
 
 
 
 

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

Источник: osp
Ицик Бен Ган

Пользователям 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. Результаты запроса в листинге 5 

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

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

План для запроса в листинге 6 
Рисунок 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 показан план для данного решения.

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

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

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

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

Листинг 1. DDL для таблицы Sessions

SET NOCOUNT ON; USE tempdb; IF OBJECT_ID(N'dbo.Sessions', N'U') IS NOT NULL DROP TABLE dbo.Sessions; IF OBJECT_ID(N'dbo.Apps', N'U') IS NOT NULL DROP TABLE dbo.Apps; CREATE TABLE dbo.Apps ( app VARCHAR(10) NOT NULL, CONSTRAINT PK_Apps PRIMARY KEY(app) ); CREATE TABLE dbo.Sessions ( keycol INT NOT NULL, app VARCHAR(10) NOT NULL, starttime DATETIME2(0) NOT NULL, endtime DATETIME2(0) NOT NULL, CONSTRAINT PK_Sessions PRIMARY KEY(keycol), CONSTRAINT CHK_Sessios_et_st CHECK(endtime > starttime) ); CREATE UNIQUE INDEX idx_start ON dbo.Sessions(app, starttime, keycol); CREATE UNIQUE INDEX idx_end ON dbo.Sessions(app, endtime, keycol);

Листинг 2. Программный код для заполнения таблицы Sessions малым набором тестовых данных

TRUNCATE TABLE dbo.Sessions; TRUNCATE TABLE dbo.Apps; INSERT INTO dbo.Apps(app) VALUES('app1'),('app2'),('app3'); INSERT INTO dbo.Sessions(keycol, app, starttime, endtime) VALUES (2, 'app1', '20130212 08:30:00', '20130212 10:30:00'), (3, 'app1', '20130212 08:30:00', '20130212 08:45:00'), (5, 'app1', '20130212 09:00:00', '20130212 09:30:00'), (7, 'app1', '20130212 09:15:00', '20130212 10:30:00'), (11, 'app1', '20130212 09:15:00', '20130212 09:30:00'), (13, 'app1', '20130212 10:30:00', '20130212 14:30:00'), (17, 'app1', '20130212 10:45:00', '20130212 11:30:00'), (19, 'app1', '20130212 11:00:00', '20130212 12:30:00'), (23, 'app2', '20130212 08:30:00', '20130212 08:45:00'), (29, 'app2', '20130212 09:00:00', '20130212 09:30:00'), (31, 'app2', '20130212 11:45:00', '20130212 12:00:00'), (37, 'app2', '20130212 12:30:00', '20130212 14:00:00'), (41, 'app2', '20130212 12:45:00', '20130212 13:30:00'), (43, 'app2', '20130212 13:00:00', '20130212 14:00:00'), (47, 'app2', '20130212 14:00:00', '20130212 16:30:00'), (53, 'app2', '20130212 15:30:00', '20130212 17:00:00'), (61, 'app3', '20130212 08:00:00', '20130212 08:30:00'), (62, 'app3', '20130212 08:00:00', '20130212 09:00:00'), (63, 'app3', '20130212 09:00:00', '20130212 09:30:00'), (64, 'app3', '20130212 09:30:00', '20130212 10:00:00');

Листинг 3. Вспомогательная функция GetNums

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

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

TRUNCATE TABLE dbo.Sessions; TRUNCATE TABLE dbo.Apps; DECLARE @numrows AS INT = 2000000, - total number of rows @numapps AS INT = 100; - number of applications INSERT INTO dbo.Apps WITH(TABLOCK) (app) SELECT 'app' + CAST(n AS VARCHAR(10)) AS app FROM dbo.GetNums(1, @numapps) AS Nums; INSERT INTO dbo.Sessions WITH(TABLOCK) (keycol, app, 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, DATEADD( second, 1 + ABS(CHECKSUM(NEWID())) % (30*24*60*60), '20130101') AS starttime FROM dbo.GetNums(1, @numrows) AS Nums ) AS D;

Листинг 5. Решение на основе агрегата для окна и функций Offset

WITH C1 AS ( SELECT app, starttime AS ts, +1 AS type FROM dbo.Sessions UNION ALL SELECT app, endtime AS ts, -1 AS type FROM dbo.Sessions ) 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 ORDER BY app, starttime;

Листинг 6. Программный код для удаления интервалов с подсчетом, равным 0

WITH C1 AS ( SELECT app, starttime AS ts, +1 AS type FROM dbo.Sessions UNION ALL SELECT app, endtime AS ts, -1 AS type FROM dbo.Sessions ), C2 AS ( 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 ) SELECT * FROM C2 WHERE cnt > 0 ORDER BY app, starttime;

Листинг 7. Решение на основе ранжирования и функций Offset для окна

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 ), C2 AS ( SELECT *, ROW_NUMBER() OVER(PARTITION BY app ORDER BY ts, type, keycol) AS se - start or end ordinal FROM C1 ), C3 AS ( 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 ) SELECT app, ts AS starttime, nextts AS endtime, cnt FROM C3 WHERE ts <> nextts AND cnt > 0 ORDER BY app, starttime;

Ссылки по теме


 Распечатать »
 Правила публикации »
  Обсудить материал в конференции Microsoft »
Обсудить материал в конференции Дизайн, графика, обработка изображений »
Написать редактору 
 Рекомендовать » Дата публикации: 27.02.2014 
 

Магазин программного обеспечения   WWW.ITSHOP.RU
Microsoft SQL Server Standard Edition 2017 Sngl OLP 1License NoLevel
Microsoft Office 365 для Дома 32-bit/x64. 5 ПК/Mac + 5 Планшетов + 5 Телефонов. Подписка на 1 год.
Microsoft System Center Standard Core Sngl License/Software Assurance Pack OLP 2Licenses NoLevel CoreLic Qualified
Microsoft Windows Professional 10, Электронный ключ
Microsoft Office 365 Бизнес. Подписка на 1 рабочее место на 1 год
 
Другие предложения...
 
Курсы обучения   WWW.ITSHOP.RU
 
Другие предложения...
 
Магазин сертификационных экзаменов   WWW.ITSHOP.RU
 
Другие предложения...
 
3D Принтеры | 3D Печать   WWW.ITSHOP.RU
 
Другие предложения...
 
Новости по теме
 
Рассылки Subscribe.ru
Информационные технологии: CASE, RAD, ERP, OLAP
Безопасность компьютерных сетей и защита информации
Новости ITShop.ru - ПО, книги, документация, курсы обучения
Программирование на Microsoft Access
CASE-технологии
eManual - электронные книги и техническая документация
Краткие описания программ и ссылки на них
 
Статьи по теме
 
Новинки каталога Download
 
Исходники
 
Документация
 
Обсуждения в форумах
Как извлечь рисунки из файла Word (42)
Вообще-то есть еще способ - сделать в Word-е Copy рисунка, открыть Microsoft Photo Editor и там:...
 
Сдача экзаменов Microsoft гарантия 100% (13)
Сдача экзаменов Microsoft гарантия 100%. Дополнительная информация по E-mail.
 
Подключение JavaScript (305)
Всем привет! Я подключаю JavaScript нижеприведенным образом. Код: <script...
 
Как восстановить рабочий стол? Помогите срочно надо! (3)
Windows 7 максимальная. В учетной записи сменила пароль и выключила комп, после включения...
 
Пять возможностей Windows, о которых вы могли не знать (5)
пыщпыщ
 
 
 



    
rambler's top100 Rambler's Top100