Как найти самый длинный непрерывный ряд событий с помощью SQL / forpes.ru

Главная
Как найти самый длинный непрерывный ряд событий с помощью SQL

Как найти самый длинный непрерывный ряд событий с помощью SQL +20

10.11.2015 10:00

Z80A 15 1 Источник

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

Для примера возьмём Stack Overflow. Он использует клёвую систему репутации с наградами за определенные достижения. Как и во многих социальных проектах, они поощряют пользователей ежедневно посещать ресурс. Обратим внимание на эти две награды:

Нетрудно понять, что они означают. Зайдите на сайт в первый день. Затем на второй день. Затем на третий (возможно несколько раз, это не имеет значения). Не зашли на четвёртый? Начинаем считать заново.

Как отследить это с помощью SQL?

Для доступа к данным мы будем использовать Stack Exchange Data Explorer.

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

В качестве базы данных используется SQL Server, следовательно мы можем использовать следующий запрос:

SELECT DISTINCT CAST(CreationDate AS DATE) AS date
FROM Posts
WHERE OwnerUserId = ##UserId##
ORDER BY 1

…который выдаст что-то подобное:

date          
----------
2010-11-26
2010-11-27
2010-11-29
2010-11-30
2010-12-01
2010-12-02
2010-12-03
2010-12-05
2010-12-06
2010-12-07
2010-12-08
2010-12-09
2010-12-13
2010-12-14
...
(769 rows)

(можете сделать запрос самостоятельно, здесь)

Как можно заметить, есть несколько пропусков:

date          
--------------------------------------
2010-11-26
2010-11-27 <---- Пропуск после 2 дней

2010-11-29
2010-11-30
2010-12-01
2010-12-02
2010-12-03 <---- Пропуск после 5 дней

2010-12-05
2010-12-06
2010-12-07
2010-12-08
2010-12-09 <---- Пропуск после 5 дней

2010-12-13
2010-12-14
...

Человеку легко увидеть, сколько дней подряд идут даты без пропусков. Но как сделать это посредством SQL?

Чтобы упростить задачу, давайте «сохраним» индивидуальные запросы в обобщённых табличных выражениях. Предыдущий запрос мы назовём dates:

WITH
 
  -- This table contains all the distinct date 
  -- instances in the data set
  dates(date) AS (
    SELECT DISTINCT CAST(CreationDate AS DATE)
    FROM Posts
    WHERE OwnerUserId = ##UserId##
  )
...

Теперь цель полученного запроса — поместить все последовательные даты в одну и ту же группу, чтобы мы могли объединить их. Вот как мы это сделаем:

SELECT
  COUNT(*) AS consecutiveDates,
  MIN(week) AS minDate,
  MAX(week) AS maxDate
FROM groups
GROUP BY grp -- This "grp" value will be explained later
ORDER BY 1 DESC, 2 DESC

Мы хотим объединить каждую группу «grp» и подсчитать количество дат в группе, а также найти минимум и максимум в каждой группе.

Создание групп для последовательных дат

Давайте теперь посмотрим на результат запроса, и, чтобы было понятнее, мы пронумеруем строки независимо от пропусков в датах:

row number   date          
--------------------------------
1            2010-11-26
2            2010-11-27

3            2010-11-29 <-- пропуск перед этой строкой
4            2010-11-30
5            2010-12-01
6            2010-12-02
7            2010-12-03

8            2010-12-05 <-- пропуск перед этой строкой

Как можно видеть, независимо от того, что существует разрыв между датами (две даты не являются последовательными), их номера строк по-прежнему будут последовательными. Мы можем сделать это с помощью функции ROW_NUMBER():

SELECT
  ROW_NUMBER() OVER (ORDER BY date) AS [row number],
  date
FROM dates

Теперь давайте посмотрим вот такой интересный запрос:

WITH
 
  -- This table contains all the distinct date 
  -- instances in the data set
  dates(date) AS (
    SELECT DISTINCT CAST(CreationDate AS DATE)
    FROM Posts
    WHERE OwnerUserId = ##UserId##
  ),
   
  -- Generate "groups" of dates by subtracting the
  -- date's row number (no gaps) from the date itself
  -- (with potential gaps). Whenever there is a gap,
  -- there will be a new group
  groups AS (
    SELECT
      ROW_NUMBER() OVER (ORDER BY date) AS rn,
      dateadd(day, -ROW_NUMBER() OVER (ORDER BY date), date) AS grp,
      date
    FROM dates
  )
SELECT *
FROM groups
ORDER BY rn

Приведённый выше запрос даёт нам следующий результат:

rn  grp          date          
--- ----------   ----------
1   2010-11-25   2010-11-26
2   2010-11-25   2010-11-27

3   2010-11-26   2010-11-29
4   2010-11-26   2010-11-30
5   2010-11-26   2010-12-01
6   2010-11-26   2010-12-02
7   2010-11-26   2010-12-03

8   2010-11-27   2010-12-05
9   2010-11-27   2010-12-06
10  2010-11-27   2010-12-07
11  2010-11-27   2010-12-08
12  2010-11-27   2010-12-09

13  2010-11-30   2010-12-13
14  2010-11-30   2010-12-14

(можете сделать запрос самостоятельно, здесь)

Все, что мы сделали, это вычли номер строки из дня, чтобы получить новую дату «grp». Полученная таким образом дата не имеет смысла, это просто вспомогательное значение.

Однако, мы можем гарантировать, что для последовательных дат, значение «grp» будет одинаковое, потому что для всех последовательно идущих дат, следующие два уравнения верны:

date2 - date1 = 1 // разница в днях между двумя датами
rn2 - rn1 = 1 // Разница в цифрах строк

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

rn  grp          date          
--- ----------   ----------
1   2010-11-25   2010-11-26
2   2010-11-25   2010-11-27

3   2010-11-26   2010-11-29
4   2010-11-26   2010-11-30
5   2010-11-26   2010-12-01
6   2010-11-26   2010-12-02
7   2010-11-26   2010-12-03

8   2010-11-27   2010-12-05
9   2010-11-27   2010-12-06
10  2010-11-27   2010-12-07
11  2010-11-27   2010-12-08
12  2010-11-27   2010-12-09

13  2010-11-30   2010-12-13
14  2010-11-30   2010-12-14

Таким образом, финальный запрос будет следующим:

WITH
 
  -- This table contains all the distinct date 
  -- instances in the data set
  dates(date) AS (
    SELECT DISTINCT CAST(CreationDate AS DATE)
    FROM Posts
    WHERE OwnerUserId = ##UserId##
  ),
   
  -- Generate "groups" of dates by subtracting the
  -- date's row number (no gaps) from the date itself
  -- (with potential gaps). Whenever there is a gap,
  -- there will be a new group
  groups AS (
    SELECT
      ROW_NUMBER() OVER (ORDER BY date) AS rn,
      dateadd(day, -ROW_NUMBER() OVER (ORDER BY date), date) AS grp,
      date
    FROM dates
  )
SELECT
  COUNT(*) AS consecutiveDates,
  MIN(week) AS minDate,
  MAX(week) AS maxDate
FROM groups
GROUP BY grp
ORDER BY 1 DESC, 2 DESC

И его результат:

consecutiveDates minDate       maxDate       
---------------- ------------- ------------- 
14               2012-08-13    2012-08-26
14               2012-02-03    2012-02-16
10               2013-10-24    2013-11-02
10               2011-05-11    2011-05-20
9                2011-06-30    2011-07-08
7                2012-01-17    2012-01-23
7                2011-06-14    2011-06-20
6                2012-04-10    2012-04-15
6                2012-04-02    2012-04-07
6                2012-03-26    2012-03-31
6                2011-10-27    2011-11-01
6                2011-07-17    2011-07-22
6                2011-05-23    2011-05-28
...

(можете сделать запрос самостоятельно, здесь)

Бонус: найти последовательность недель

То, что мы использовали дни — это просто наш выбор. Мы взяли точное время и округлили его до дня с помощью функции CAST:

SELECT DISTINCT CAST(CreationDate AS DATE)

Если бы мы хотели узнать последовательность, например, из недель, мы могли бы округлять время до недель:

SELECT DISTINCT datepart(year, CreationDate) * 100 
              + datepart(week, CreationDate)

Этот запрос использует численное выражение года и недели и создаёт числа типа 201503 для третьей недели 2015 года. Остальная часть запроса остаётся без изменений:

WITH
  weeks(week) AS (
    SELECT DISTINCT datepart(year, CreationDate) * 100 
                  + datepart(week, CreationDate)
    FROM Posts
    WHERE OwnerUserId = ##UserId##
  ),
  groups AS (
    SELECT
      ROW_NUMBER() OVER (ORDER BY week) AS rn,
      dateadd(day, -ROW_NUMBER() OVER (ORDER BY week), week) AS grp,
      week
    FROM weeks
  )
SELECT
  COUNT(*) AS consecutiveWeeks,
  MIN(week) AS minWeek,
  MAX(week) AS maxWeek
FROM groups
GROUP BY grp
ORDER BY 1 DESC, 2 DESC

И вот что мы получим:

consecutiveWeeks minWeek maxWeek 
---------------- ------- ------- 
45               201401  201445  
29               201225  201253  
25               201114  201138  
23               201201  201223  
20               201333  201352  
16               201529  201544  
15               201305  201319  
12               201514  201525  
12               201142  201153  
9                201502  201510  
7                201447  201453  
7                201321  201327  
6                201048  201053  
4                201106  201109  
3                201329  201331  
3                201102  201104  
2                201301  201302  
2                201111  201112  
1                201512  201512

(можете сделать запрос самостоятельно, здесь)

Неудивительно, что последовательные недели охватывают гораздо более длинные диапазоны, так как автор регулярно пишет на Stack Overflow.

Комментарии (15)

VioletGiraffe
10.11.2015 13:59
#8649517
919 дней посещения SO без прогулов, кто больше? :)
1. zharikovpro
  10.11.2015 17:13
  #8649953
  +4
  Любой бот :)

vedenin1980
10.11.2015 14:19
#8649545
+2
Интересный запрос, ради интереса попробовал написать такой запрос сам, получился в лоб на чистом sql (первый запрос находит дату начала непрерывного интервала, второй конца, третий сводит дату начала и конца). Но ваш запрос будет работать, вероятно, быстрее.
```
WITH date AS (
    SELECT DISTINCT 
      CAST(CreationDate AS DATE) as date,
      CAST(CreationDate - 1 AS DATE) as min1, 
      CAST(CreationDate + 1 AS DATE) as plus1
    FROM Posts
    WHERE OwnerUserId = ##UserId##
  ),
firstdate AS (  
   SELECT * from date as d1 where NOT EXISTS(SELECT * FROM date d2 Where d1.min1 = d2.date)
),
lastdate AS (  
   SELECT * from date as d1 where NOT EXISTS(SELECT * FROM date d2 Where d1.plus1 = d2.date)
),
dates AS (
  SELECT firstdate.date as first, min(lastdate.date) as last FROM firstdate, lastdate WHERE firstdate.date <= lastdate.date
  GROUP BY firstdate.date 
)
SELECT first, last, DATEDIFF(dd,first, last)+1 as days FROM dates order by days desc
```
1. encyclopedist
  10.11.2015 15:02
  #8649655
  +1
  Обратите внимание что это перевод.
  1. vedenin1980
    10.11.2015 15:04
    #8649663
    Ясно, не заметил. :) В любом случае практика лишней не будет.

zzashpaupat
10.11.2015 14:48
#8649605
+3
В Oracle есть такая штука, как Pattern matching, с помощью неё тоже можно сделать. Но, это, конечно, будет работать только для Oracle, тогда как подход, описанный выше, работает везде, где есть CTE и оконные функции.

dtestyk
10.11.2015 15:34
#8649727
Затем на второй день. Затем на третий (возможно несколько раз, это не имеет значения). Не зашли на четвёртый? Начинаем считать заново.
т.е. по сути алгоритм работы debounce
Зашел пользователь — запустили таймер на 30 дней :)
1. dtestyk
  10.11.2015 16:44
  #8649901
  подробности
  зашел пользователь: если таймер "30 дней" не запущен запускаем таймер "30 дней" если запущен таймер "1 день без посещения" сбрасываем таймер "1 день без посещения" запускаем таймер "1 день без посещения" сработал таймер "1 день без посещения": сбросываем таймер "30 дней" сработал таймер "30 дней": alert('прошло ровно 30 дней с перерывами в посещении не больше 1 дня')
  
  dtestyk
  10.11.2015 21:08
  #8650231
  Еще для решения этой задачи:
  
  можно приспособить регулярные выражения
  m — midnight event
  v — visit event
  
  «vmmmvvvm» — не подходит, есть несколько суток без посещения
  «vvvmvmvvmvv» — пока что подходит
  
  if(event_seq_str.match(/m(v+m){30,}/)) alert('30 days online')

biduin
10.11.2015 17:41
#8649999
Можно сделать значительно проще.
Заджоините табличку саму с собой по on t1.mydate = dateadd(t2.mydate,-1) Ну и дальше по вычисляемому полю(t1.mydate-t2.mydate) будет всё понятно. К результируещей таблице безусловно нужно будет сделать запрос с агрегацией.
1. dtestyk
  10.11.2015 18:00
  #8650027
  А если не использовать промежуточную таблицу, будет медленнее?
  Оптимизируют ли sql-движки вложенные запросы,
  или просто делают выборку из декартового произведения?
  1. biduin
    10.11.2015 18:29
    #8650079
    Многие оптимизируют.

xtender
10.11.2015 18:01
#8650033
+3
еще легко такое делается с помощью разницы текущего значения и аналитических lead/lag этого поля и известного алгоритма «start_of_group». Причем это будет значительно легче для «гибких» диапазонов, т.е. например, если захотим считать перерывом 10 дней или 2 недели и тд…

SemenovVV

11.11.2015 08:58

#8650567

скрипт без group by, легко переделать в пропущенные интервалы T-sql

declare @Posts table ( data date  )
insert into @Posts (data) values('2010-11-26')
insert into @Posts (data) values('2010-11-27')
insert into @Posts (data) values('2010-11-29')
insert into @Posts (data) values('2010-11-30')
insert into @Posts (data) values('2010-12-01')
insert into @Posts (data) values('2010-12-02')
insert into @Posts (data) values('2010-12-03')
insert into @Posts (data) values('2010-12-05')
insert into @Posts (data) values('2010-12-06')
insert into @Posts (data) values('2010-12-07')
insert into @Posts (data) values('2010-12-08')
insert into @Posts (data) values('2010-12-09')
insert into @Posts (data) values('2010-12-13')
insert into @Posts (data) values('2010-12-14')
insert into @Posts (data) values('2010-12-15')  
insert into @Posts (data) values('2010-12-16')  
insert into @Posts (data) values('2010-12-19')  

;
with 
 grup0 as (  --- считаем пред и след дни
   select data  
    , dateadd( d, -1,   data ) as d_prev 
	, dateadd( d, +1,   data ) as d_next 
	 from @Posts  
  )
 ,  grup1 as
  ( select p.data
    ,  n.data   as next_exist 
    ,  s.data   as prev_exist
    from @Posts p 
	left join grup0 n   
	   on  n.d_prev  = p.data
	left join grup0 s
	   on s.d_next = p.data
   )
  ,  start as ( 
   select  data  , ROW_NUMBER()OVER(ORDER BY data) as npp 
      from grup1 p 
	  where prev_exist is null  )
  ,  finish as ( 
   select  data, ROW_NUMBER()OVER(ORDER BY data) as npp   
      from grup1 p where next_exist is null )
select   s.data as start 
  , f.data as finish   
  , datediff(d, s.data,f.data) +1  as kol_day 
  from start s, finish f
  where s.npp   = f.npp -- +1 получим интервалы пропуски 
order by start  --- kol_day desc

m36

12.11.2015 15:00

#8652069

Так еще можно:

declare @Posts table ( CreationDate date  )
insert into @Posts (CreationDate) values('2010-11-26')
insert into @Posts (CreationDate) values('2010-11-27')
insert into @Posts (CreationDate) values('2010-11-29')
insert into @Posts (CreationDate) values('2010-11-30')
insert into @Posts (CreationDate) values('2010-12-01')
insert into @Posts (CreationDate) values('2010-12-02')
insert into @Posts (CreationDate) values('2010-12-03')
insert into @Posts (CreationDate) values('2010-12-05')
insert into @Posts (CreationDate) values('2010-12-06')
insert into @Posts (CreationDate) values('2010-12-07')
insert into @Posts (CreationDate) values('2010-12-08')
insert into @Posts (CreationDate) values('2010-12-09')
insert into @Posts (CreationDate) values('2010-12-13')
insert into @Posts (CreationDate) values('2010-12-14')
insert into @Posts (CreationDate) values('2010-12-15')  
insert into @Posts (CreationDate) values('2010-12-16')  
insert into @Posts (CreationDate) values('2010-12-19')  

insert into @Posts (CreationDate) values('1900-01-01')  
insert into @Posts (CreationDate) values('3000-01-01')  


;with dates AS (
	select cast(p1.CreationDate as date) FinishDate, cast(MIN(p2.CreationDate) as date) StartDate 
	from @Posts p1, @Posts p2
	where p1.CreationDate < p2.CreationDate
	group by cast(p1.CreationDate as date)
	having MIN(datediff(day, cast(p1.CreationDate as date), cast(p2.CreationDate as date))) > 1
)
select d1.StartDate, MIN(d2.FinishDate) FinishDate from dates d1, dates d2
where d1.StartDate <= d2.FinishDate
group by d1.StartDate;

Стремился только к краткости, как его SQL-SERVER оптимизирует, не проверял. Суть: добавляются две граничные даты сверху и снизу. И ищутся дырки.