Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Microsoft SQL Server Новый топик    Ответить
 Выделение интервалов в последовательности  [new]
uaggster
Member

Откуда:
Сообщений: 1155
Коллеги, приветствую!

Помогите решить задачку, не знаю, с какой стороны подступиться.
Имеется некая таблица событий:

Use tempdb
go

Create table dbo.[events] (N int not null identity(1,1) primary key, id int not null, dt datetime2(0) not null)

insert into dbo.[events] (id, dt)
Values
 (1, '20200101 10:00:01')
,(1, '20200101 10:00:05')
,(1, '20200101 10:00:06')
,(1, '20200101 10:01:00')
,(1, '20200101 10:40:01')
,(2, '20200101 10:00:01')
,(2, '20200101 10:01:01')
,(2, '20200101 10:02:03')
,(2, '20200101 10:15:01')
,(2, '20200101 10:15:02')
,(3, '20200101 10:00:01')
,(1, '20200101 10:01:01')
,(1, '20200101 10:02:01')
,(1, '20200101 10:10:01')
,(1, '20200101 10:30:00')

Select * from dbo.[events]

drop table dbo.[events]

Инцидентом называется последовательность событий, относящихся к одному id, и случившихся последовательно по времени, так, что временной интервал между предыдущим и последующим событиями не превышает 10 минут.
Задача - выделить инциденты, присвоив им уникальный номер, например - перенумеровав эти инциденты последовательно.
Например, в примере выше, инцидентом будет:
Niddt
112020-01-01 10:00:01
212020-01-01 10:00:05
312020-01-01 10:00:06
412020-01-01 10:01:00
1212020-01-01 10:01:01
1312020-01-01 10:02:01
1412020-01-01 10:10:01

Ему, например, можно присвоить номер NN = 1

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

SQL2016, но сгодится любой.
Помогите, затупил...
12 ноя 21, 14:44    [22395125]     Ответить | Цитировать Сообщить модератору
 Re: Выделение интервалов в последовательности  [new]
uaggster
Member

Откуда:
Сообщений: 1155
Не наглядный пример привел, прошу прощения.
Длительность инцидента - не 10 минут! Он может и сутки, и месяц длиться.
Событие принадлежит инциденту, если найдется хоть одно событие, связанное с этим Id, расстояние по времени до которого - меньше 10 минут.
Если это изолированное событие, до которого больше 10 минут и вверх и вниз - то это само по себе инцидент, из одного события.

Т.е. это вроде бы gap and island, но без перекрытия/примыкания.

Не могу додумать.
12 ноя 21, 15:01    [22395142]     Ответить | Цитировать Сообщить модератору
 Re: Выделение интервалов в последовательности  [new]
Konst_One
Member

Откуда:
Сообщений: 11677
lead , lag никак не прикрутить?
12 ноя 21, 15:02    [22395144]     Ответить | Цитировать Сообщить модератору
 Re: Выделение интервалов в последовательности  [new]
msLex
Member

Откуда:
Сообщений: 9540
Тут где-то aleks222 давал простой алгоритм поиска групп пересекающихся событий:

начало группы - дата начала отдельного события, которая не попадает ни в один из диапазонов
конец группы - ближайшая дата окончания отдельного события, которая не попадает ни в один из диапазонов

все, что внутри этого диапазона, одна группа событий

вам нужно просто добавить сюда свой десятиминутный лаг и разделение по id
12 ноя 21, 15:09    [22395147]     Ответить | Цитировать Сообщить модератору
 Re: Выделение интервалов в последовательности  [new]
uaggster
Member

Откуда:
Сообщений: 1155
Konst_One
lead , lag никак не прикрутить?

Так вопрос то как раз в том, как именно прикрутить :-)
12 ноя 21, 15:10    [22395148]     Ответить | Цитировать Сообщить модератору
 Re: Выделение интервалов в последовательности  [new]
Gerasimenko
Member

Откуда:
Сообщений: 4705
uaggster
Konst_One
lead , lag никак не прикрутить?

Так вопрос то как раз в том, как именно прикрутить :-)


DECLARE @StartDate DATETIME ='20211112 10:10:10 '
DECLARE @EndDate DATETIME = GETDATE()

SELECT DATEDIFF(MINUTE, @StartDate, @EndDate)
12 ноя 21, 15:16    [22395153]     Ответить | Цитировать Сообщить модератору
 Re: Выделение интервалов в последовательности  [new]
msLex
Member

Откуда:
Сообщений: 9540
msLex
Тут где-то aleks222 давал простой алгоритм поиска групп пересекающихся событий:

начало группы - дата начала отдельного события, которая не попадает ни в один из диапазонов
конец группы - ближайшая дата окончания отдельного события, которая не попадает ни в один из диапазонов

все, что внутри этого диапазона, одна группа событий

вам нужно просто добавить сюда свой десятиминутный лаг и разделение по id


Вот жеж.

У вас не интервалы, а атомарные события, и всякие "поглощения" тут не нужны



тогда все просто


если предыдущее событие дальше чем на 10 минут - это начало инцидента
если последующее событие дальше чем на 10 минут - это окончание инцидента

нумеруете все "начала" и цепляете к ним все ближайшие (с учетом ID) окончания

не забудьте только, что начало и окончание могут совпасть
12 ноя 21, 15:17    [22395154]     Ответить | Цитировать Сообщить модератору
 Re: Выделение интервалов в последовательности  [new]
uaggster
Member

Откуда:
Сообщений: 1155
msLex, так перенумерую то я их легко, и предыдущий N - легко прикручу.
Вопрос в том, как эти последовательности раскрутить то потом, не рекурсивно же!
12 ноя 21, 15:56    [22395174]     Ответить | Цитировать Сообщить модератору
 Re: Выделение интервалов в последовательности  [new]
msLex
Member

Откуда:
Сообщений: 9540
вот поиск интервалов

если нужно наложить на исходную таблицу, заджойните

Create table #events (N int not null identity(1,1) primary key, id int not null, dt datetime2(0) not null)

insert into #events (id, dt)
Values
 (1, '20200101 10:00:01')
,(1, '20200101 10:00:05')
,(1, '20200101 10:00:06')
,(1, '20200101 10:01:00')
,(1, '20200101 10:40:01')
,(2, '20200101 10:00:01')
,(2, '20200101 10:01:01')
,(2, '20200101 10:02:03')
,(2, '20200101 10:15:01')
,(2, '20200101 10:15:02')
,(3, '20200101 10:00:01')
,(1, '20200101 10:01:01')
,(1, '20200101 10:02:01')
,(1, '20200101 10:10:01')
,(1, '20200101 10:30:00')


; with t1 as (
	select 
		prev_dt = lag(e.dt, 1) over(partition by id order by dt)
		, next_dt = lead(e.dt, 1) over(partition by id order by dt)
		, *
	from #events e
)
, t2 as (
	select 
		is_start = case when dateadd(mi, 10, prev_dt) < dt or prev_dt is null then 1 else 0 end
		, is_end = case when dateadd(mi, -10, next_dt) > dt or next_dt is null then 1 else 0 end
		, *
	from t1 
	where
		dateadd(mi, 10, prev_dt) < dt or prev_dt is null
		or dateadd(mi, -10, next_dt) > dt or next_dt is null
)
, t3 as  (
	select 
		start_dt = dt
		, end_dt = case when is_end = 1 then dt else lead(dt, 1) over(partition by id order by dt) end
		, rn = ROW_NUMBER() over(order by dt)
		, n
		, id
		, is_start
	from t2
)
select * from t3 where is_start = 1 order by rn
drop table #events


Сообщение было отредактировано: 12 ноя 21, 16:41
12 ноя 21, 16:40    [22395198]     Ответить | Цитировать Сообщить модератору
 Re: Выделение интервалов в последовательности  [new]
PizzaPizza
Member

Откуда:
Сообщений: 441
uaggster,

Пронумеровать инциденты в таблице с 100 миллионов записей это одно. А что с этим дальше делать можно я не представляю. Положить пронумерованное в другую таблицу? Статистику посмотреть какую то? Искать то по номеру инцидента слишком тяжело.
12 ноя 21, 18:28    [22395272]     Ответить | Цитировать Сообщить модератору
 Re: Выделение интервалов в последовательности  [new]
invm
Member

Откуда: Москва
Сообщений: 9913
select
 a.*,
 cast(a.id as binary(4)) + cast(sum(case when b.dt is null then 1 else 0 end) over (order by a.id, a.dt) as binary(4))
from
 dbo.[events] a outer apply
 (select top (1) dt from dbo.[events] where id = a.id and dt < a.dt and datediff(mi, dt, a.dt) <= 10 order by dt desc) b
order by
 a.id, a.dt;
Плюс соответствующие индексы
12 ноя 21, 22:44    [22395405]     Ответить | Цитировать Сообщить модератору
 Re: Выделение интервалов в последовательности  [new]
invm
Member

Откуда: Москва
Сообщений: 9913
Так лучше
with a as
(
 select
  N, id, dt,
  lag(dt, 1, dt) over (partition by id order by dt) as dt__prev
 from
  dbo.[events]
)
select
 N, id, dt,
 cast(id as binary(4)) + cast(sum(case when datediff(mi, dt__prev, dt) > 10 then 1 else 0 end) over (partition by id order by dt) as binary(4))
from
 a
order by
 id, dt;
При правильном индексе будет один просмотр
12 ноя 21, 23:04    [22395415]     Ответить | Цитировать Сообщить модератору
 Re: Выделение интервалов в последовательности  [new]
uaggster
Member

Откуда:
Сообщений: 1155
invm, спасибо, попытаюсь вкурить.

Итого, как я понимаю, сначала в СТЕ строится последовательность, запись + предыдущее значение даты/времени инцидента, а потом поверх последовательности считается сумма: если расстояние до предыдущего - меньше 10 минут, то 0, в противном случае - +1.
Таким образом все члены последовательности получат + N, где N - количество десятиминутных разрывов от начала последовательности.
ИМХО, гениально, я б не недопёр.
Я всё время вертелся вокруг rows between unbounded preceding and current row, но там феерическая дичь получалась, в т.ч. и по производительности.
Спасибо, проверю, отпишусь.
14 ноя 21, 09:24    [22395754]     Ответить | Цитировать Сообщить модератору
 Re: Выделение интервалов в последовательности  [new]
Владислав Колосов
Member

Откуда:
Сообщений: 9155
uaggster,

сколько возникает проблем, если неверно организовано хранение данных...
14 ноя 21, 12:34    [22395790]     Ответить | Цитировать Сообщить модератору
 Re: Выделение интервалов в последовательности  [new]
uaggster
Member

Откуда:
Сообщений: 1155
Владислав Колосов, тут не то, что мопед не мой, а и гараж тоже :-)
14 ноя 21, 18:19    [22395929]     Ответить | Цитировать Сообщить модератору
Все форумы / Microsoft SQL Server Ответить