Статьи

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

Декабрь 20, 2018

Очень интересная проблема, которую можно очень легко решить с помощью SQL, — это найти последовательный ряд событий во временном ряду. Но что такое последовательный ряд событий во временном ряду?

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

StackOverflow-визиты

Неформально очевидно, что это значит. Вам нужно будет войти в день 1. Затем снова в день 2. Затем снова (возможно, несколько раз, это не имеет значения) в день 3. Забыли войти в день 4? По электронной почте Ой. Мы начнем считать снова.

Как это сделать в SQL?

В этом блоге каждая проблема найдет свое решение в SQL . Так же и это. И чтобы решить эту проблему, мы собираемся использовать потрясающий Stack Exchange Data Explorer , который предоставляет много общедоступной информации об использовании Stack Exchange.

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

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

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

… который, для моего собственного UserId генерирует что-то вроде:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
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)

( запустите заявление самостоятельно, здесь )

Как мы видим из данных, в первые дни были пробелы:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
date         
--------------------------------------
2010-11-26
2010-11-27 <---- Gap here after 2 days
 
2010-11-29
2010-11-30
2010-12-01
2010-12-02
2010-12-03 <---- Gap here after 5 days
 
2010-12-05
2010-12-06
2010-12-07
2010-12-08
2010-12-09 <---- Gap here after 5 days
 
2010-12-13
2010-12-14
...

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

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

01
02
03
04
05
06
07
08
09
10
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##
  )
...

Теперь цель результирующего запроса состоит в том, чтобы поместить все последовательные даты в одну группу, чтобы мы могли агрегировать по этой группе. Следующий запрос — это то, что мы хотим написать:

1
2
3
4
5
6
7
SELECT
  COUNT(*) AS consecutiveDates,
  MIN(week) AS minDate,
  MAX(week) AS maxDate
FROM groups
GROUP BY grp
ORDER BY 1 DESC, 2 DESC

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

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

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

01
02
03
04
05
06
07
08
09
10
11
12
row number   date         
--------------------------------
1            2010-11-26
2            2010-11-27
 
3            2010-11-29 <-- gap before this row
4            2010-11-30
5            2010-12-01
6            2010-12-02
7            2010-12-03
 
8            2010-12-05 <-- gap before this row

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

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

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

Вышеприведенный запрос дает:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
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 ». Фактическая дата, полученная таким способом, не имеет значения. Это просто вспомогательное значение.

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

1
2
date2 - date1 = 1 // difference in days between dates
rn2   - rn1   = 1 // difference in row numbers

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
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

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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

И это дает:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
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
...

( запустите заявление самостоятельно, здесь )

Бонусный запрос 1: найдите недели подряд

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

1
SELECT DISTINCT CAST(CreationDate AS DATE)

Если мы хотим знать последовательные недели, мы просто изменим эту функцию на другое выражение, например

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

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

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
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

И мы получим следующий результат:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
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.

Бонусный запрос 2: Упростите запрос с помощью DENSE_RANK ()

В предыдущей статье мы показали, что SQL Trick: ROW_NUMBER() должен SELECT то, что DENSE_RANK() должен SELECT DISTINCT .

Если мы вернемся к нашему примеру с последовательными днями, мы можем переписать запрос, чтобы найти отличные даты И группы за один раз, используя DENSE_RANK() :

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
WITH
  groups(date, grp) AS (
    SELECT DISTINCT
      CAST(CreationDate AS DATE),
      dateadd(day,
        -DENSE_RANK() OVER (ORDER BY CAST(CreationDate AS DATE)),
        CAST(CreationDate AS DATE)) AS grp
    FROM Posts
    WHERE OwnerUserId = ##UserId##
  )
SELECT
  COUNT(*) AS consecutiveDates,
  MIN(date) AS minDate,
  MAX(date) AS maxDate
FROM groups
GROUP BY grp
ORDER BY 1 DESC, 2 DESC

( запустите заявление самостоятельно, здесь )

Если вышеупомянутое не имеет смысла, я рекомендую прочитать нашу предыдущую статью здесь, которая объясняет это:

http://blog.jooq.org/2013/10/09/sql-trick-row_number-is-to-select-what-dense_rank-is-to-select-distinct/

дальнейшее чтение

Выше приведен один очень полезный пример использования оконных функций ( ROW_NUMBER() ) в SQL. Узнайте больше о функциях окна в любой из следующих статей:

Ссылка: Как найти самую длинную последовательность событий в SQL от нашего партнера по JCG Лукаса Эдера в блоге JAVA, SQL и AND JOOQ .
60
Share: