Liczymy dni, czyli przedziały czasowe w SQL

Rybiński śpiewał kiedyś, że nie liczy godzin i lat, a ja na przekórw ostatnio właśnie liczę.

A konkretnie: jakiś czas temu kolega z biurka obok (wirtualnego, bo teraz każdy pracuje z domu, ale jednak biurko to biurko) zagaił do mnie o wsparcie, bo on już trzeci dzień z tym walczy i nic, a ja lubię takie zagadki. Zagadnienie okazało się na tyle ciekawe, że nie tylko poświęciłem mu całą swoją uwagę, ale postanowiłem z niego zrobić wpis, który właśnie czytasz.

Temat jest z pozoru błahy, ale zaraz okazuje się, że czym dalej w las, tym bardziej w lesie.

Chodzi o policzenie ile dni każdy z klientów spędził na różnych aktywnościach. Mamy więc - w największym możliwym uproszczeniu - id klienta oraz datę rozpoczęcia i (opcjonalnie) zakończenia aktywności. Opcjonalnie, bo niektóre aktywności są jeszcze w trakcie i mają datę zakończenia ustawioną na NULL - w takim przypadku trzeba przyjąć do obliczeń datę bieżącą.

W rzeczywistości kolumn jest dużo więcej, ale nie rzucajmy sobie niepotrzebnie kłód pod nóg... kłodów pod nogów... czy coś...

Haczyk jest pogrzebany w dodatkowym warunku: jeżeli danego dnia klient ma zarejestrowaną więcej niż jedną aktywność, dzień ten liczymy tylko raz. A więc jeżeli, dajmy na to, klient A ma trzy aktywności:

Od 1 stycznia 2024 do 10 stycznia 2024
Od 5 stycznia 2024 do 20 stycznia 2024
Od 1 lutego 2024 do 2 lutego 2024

... wówczas liczbę dni należy wyznaczyć jako:

Liczbę dni od 1 stycznia do 20 stycznia (20 dni)
powiększoną o liczbę dni od 1 lutego do 2 lutego (2)
Razem: 22

Proste, prawda? Jednak kiedy zaczniemy pisać kod SQL, który to wylicza, szybko okaże się, że zadanie wcale nie jest takie proste. Zwłaszcza, że niektórzy klienci mają całkiem dużo aktywności, które mogą się zazębiać w kalendarzu na wszystkie możliwe sposoby. Aha, i jeszcze trzeba pamiętać, że całość musi działać możliwie szybko, bo dane idą w miliony rekordów.

Najprostszym podejściem byłoby skonstruować sobie tabelę kalendarz, zawierającą wszystkie daty, a potem zliczać unikalne daty mieszczące się w aktywnościach poszczególnych klientów. Takie podejście jednak, choć proste logicznie, nie sprawdza się na dużych zbiorach danych.

Dlatego trzeba przysiąść fałdów, zakasać rękawy i...

Zaczniemy od najprostszego kawałka, czyli od zastąpienia wszystkich NULL-i w datach zakończenia datą bieżącą:

WITH DateAdjusted AS (
    SELECT customer_id,
           start_date,
           CONVERT(date, COALESCE(end_date, GETDATE())) AS end_date
      FROM activity
) SELECT * FROM DateAdjusted;

Co dalej?

Pomyślmy: trzeba tak naprawdę podzielić aktywności każdego klienta na grupy aktywności nakładających się na siebie, a następnie w każdej takiej grupie znaleźć najwcześniejszą datę rozpoczęcia i najpóźniejszą datę zakończenia, po czym policzyć liczbę dni między tymi datami. A na koniec dodać wyniki ze wszystkich grup danego klienta.

Weźmy konkretny przykład z początku tego tekstu:

Od 1 stycznia 2024 do 10 stycznia 2024 (GRUPA 1)
Od 5 stycznia 2024 do 20 stycznia 2024 (GRUPA 1)
Od 1 lutego 2024 do 2 lutego 2024 (GRUPA 2)

Dwie pierwsze pozycje na liście należą to tej samej grupy, bo się nakładają. Trzecia pozycja stanowi swoją osobną grupę, bo między nią a poprzednią aktywnością jest przerwa (klient nic nie robił między 21 stycznia a 31 stycznia). Dlatego dwie pierwsze aktywności przypisaliśmy do grupy 1, a ostatnią - do grupy 2. W ten sposób wystarczy teraz policzyć ile jest dni między 1 stycznia a 20 stycznia, dodać do tego dwa dni z lutego et voila.

WITH DateAdjusted AS (
    SELECT customer_id,
           start_date,
           CONVERT(date, COALESCE(end_date, GETDATE())) AS end_date
      FROM activity
)
, FlaggedIntervals AS (
    SELECT customer_id,
           start_date,
           end_date,
           CASE
               WHEN LAG(end_date) OVER (PARTITION BY customer_id ORDER BY start_date, end_date) >= start_date THEN 0
               ELSE 1
        END AS NewGroup
       FROM DateAdjusted
) SELECT * FROM FlaggedIntervals;

Podzapytanie FlaggedIntervals oznacza jedynką aktywności, które rozpoczynają się po przerwie. Pozostałe aktywności mają tę flagę ustawioną na zero. Interesującym elementem jest tutaj operator LAG:

LAG(end_date) OVER (PARTITION BY customer_id ORDER BY start_date, end_date)

Operator ten domyślnie zwraca wartość zadanej kolumny (tutaj: end_date) z poprzedniego rekordu, z opcjonalnym partycjonowaniem według jakiejś kolumny. Stąd też w klauzuli OVER mamy zarówno element PARTITION BY jak też ORDER BY.

Cała linia wygląda tak:

WHEN LAG(end_date) OVER (PARTITION BY customer_id ORDER BY start_date, end_date) >= start_date THEN 0

Oznacza to, że jeżeli end_date poprzedniego rekordu jest większe niż start_date rekordu bieżącego, to ustawiamy kolumnę NewGroup na 0 (bo aktywności się nakładają), w przeciwnym wypadku na 1 (poprzednia aktywność zakończyła się, zanim bieżąca się rozpoczęła). Korzystnym efektem ubocznym jest to, że pierwsza aktywność w każdej grupie będzie oznaczona jedynką (ponieważ poprzedni rekord nie istnieje, nie ma jak wygenerować zera, więc wykona się blok ELSE).

W kolejnym kroku policzymy sobie z tych jedynek sumę bieżącą:

WITH DateAdjusted AS (
    SELECT customer_id,
           start_date,
           CONVERT(date, COALESCE(end_date, GETDATE())) AS end_date
      FROM activity
)
, FlaggedIntervals AS (
    SELECT customer_id,
           start_date,
           end_date,
           CASE
               WHEN LAG(end_date) OVER (PARTITION BY customer_id ORDER BY start_date, end_date) >= start_date THEN 0
               ELSE 1
           END AS NewGroup
    FROM DateAdjusted
)
, GroupedIntervals AS (
    SELECT customer_id,
           start_date,
           end_date,
           SUM(NewGroup) OVER (PARTITION BY customer_id ORDER BY start_date, end_date) AS GroupID
      FROM FlaggedIntervals
) SELECT * FROM GroupedIntervals;

Tutaj interesujący kawałek to:

SUM(NewGroup) OVER (PARTITION BY customer_id ORDER BY start_date, end_date) AS GroupID

Operator SUM ... OVER ... jest jedną z niedocenianych perełek języka SQL. Został on po raz pierwszy zaimplementowany w SQL Server 2005. W tym konkretnym przypadku dla każdego rekordu nastąpi wyliczenie sumy wszystkich wartości NewGroup począwszy od pierwszego rekordu w partycji aż do rekordu bieżącego (zauważamy brak operatora GROUP BY w tym podzapytaniu - operacja sumowania przebiega na bieżąco dla każdego rekordu w ramach aktualnego klienta).

Wynik tego podzapytania jest bardzo podobny do poprzedniego, tylko zamiast zer i jedynek w kolumnie NewGroup dostajemy narastająco ponumerowane grupy w kolumnie GroupID.

No a skoro mamy już aktywności pogrupowane w kupki, możemy teraz w każdej kupce wyznaczyć najwcześniejszą datę rozpoczęcia oraz najpóźniejszą datę zakończenia:

WITH DateAdjusted AS (
    SELECT customer_id,
           start_date,
           CONVERT(date, COALESCE(end_date, GETDATE())) AS end_date
      FROM activity
)
, FlaggedIntervals AS (
    SELECT customer_id,
           start_date,
           end_date,
           CASE
               WHEN LAG(end_date) OVER (PARTITION BY customer_id ORDER BY start_date, end_date) >= start_date THEN 0
               ELSE 1
           END AS NewGroup
    FROM DateAdjusted
)
, GroupedIntervals AS (
    SELECT customer_id,
           start_date,
           end_date,
           SUM(NewGroup) OVER (PARTITION BY customer_id ORDER BY start_date, end_date) AS GroupID
      FROM FlaggedIntervals
)
, MergedIntervals AS (
    SELECT customer_id,
           MIN(start_date) AS start_date,
           MAX(end_date) AS end_date
      FROM GroupedIntervals
     GROUP BY customer_id
         , GroupID
) SELECT * FROM MergedIntervals;

Podzapytanie MergedIntervals zwraca ni mniej ni więcej jak listę dat otwierających i zamykających każdą grupę nakładających się aktywności.

Czas na finał:

WITH DateAdjusted AS (
    SELECT customer_id,
           start_date,
           CONVERT(date, COALESCE(end_date, GETDATE())) AS end_date
      FROM activity
)
, FlaggedIntervals AS (
    SELECT customer_id,
           start_date,
           end_date,
           CASE
               WHEN LAG(end_date) OVER (PARTITION BY customer_id ORDER BY start_date, end_date) >= start_date THEN 0
               ELSE 1
           END AS NewGroup
    FROM DateAdjusted
)
, GroupedIntervals AS (
    SELECT customer_id,
           start_date,
           end_date,
           SUM(NewGroup) OVER (PARTITION BY customer_id ORDER BY start_date, end_date) AS GroupID
      FROM FlaggedIntervals
)
, MergedIntervals AS (
    SELECT customer_id,
           MIN(start_date) AS start_date,
           MAX(end_date) AS end_date
      FROM GroupedIntervals
     GROUP BY customer_id
         , GroupID
)
SELECT customer_id,
       SUM(DATEDIFF(day, start_date, end_date) + 1) AS total_days
  FROM MergedIntervals
 GROUP BY customer_id;

A dlaczego +1 przy sumowaniu? No bo jak się odejmie od siebie dwie daty, trzeba dodać jedynkę, żeby się zgadzało. Przykładowo (2 luty) minus (1 luty) zwróci 1, a to przecież są dwa dni.

W taki oto sposób dostaliśmy zapytanie, które robi dokładnie to, o co poprosiliśmy; w dodatku dość szybko: na milionie rekordów i średnio z około dziesięcioma aktywnościami na każdego klienta u mnie powyższy kod wykonuje się w niecałe dwie sekundy.

Jeżeli ktoś z P.T. Czytelników miał kiedyś do czynienia z podobnym problemem i udało się go rozwiązać w mniej skomplikowany sposób, chętnie posłucham.

https://xpil.eu/v16Aa

4 komentarze

Cichy pisze:

2024-05-29 o 19:57

Mniej skomplikowany sposób to napisanie skryptu w PHP, Pythonie czy czego tam używasz, który pobierze dane prostymi zapytaniami i je sobie przerobi jak trzeba. SQL ma ten problem, że większe zapytania szybko robią się mocno nieczytelne, a ewentualna korzyść wydajnościowa zwykle nie jest warta świeczki – skomplikowane raporty na ogół generuje się raz dziennie albo rzadziej, więc nikogo nie obejdzie, jeśli potrwa to trzy sekundy zamiast dwóch. A jeśli robisz to co pół minuty, to lepiej mieć do tego jakąś dodatkową tablicę agregującą statystyki czy coś, gdzie elementarne zapytanie zajmie kilkadziesiąt milisekund.

Odpowiedz
Borys pisze:

2024-05-30 o 04:33
Fajna zagadka informatyczna. Abstrahując od składni SQL-owej, której w ogóle nie znam — choć rozumiem, że w tym przypadku jest istotnym ograniczeniem — rozwiązałbym to tak:
1) Posortuj przedziały aktywności według dat rozpoczęcia.
2) Dodaj do licznika długość pierwszego przedziału i zapamiętaj datę końcową D.
3) Sprawdź datę zakończenia następnego przedziału.
4) Jeżeli jest wcześniejsza niż D, powtórz 3.
5) Jeżeli jest późniejsza niż D to porównaj też datę początkową z D.
6) Jeżeli data początkowa jest wcześniejsza niż D, dodaj do licznika długość nowego przedziału minus różnica między bieżącą datą początkową i D. Zapisz bieżącą datę końcową jako nowe D, powtórz 3.
7) Jeżeli data początkowa jest późniejsza niż D, dodaj do licznika długość nowego przedziału w całości. Zapisz bieżącą końcową jako nowe D, powtórz 3.

W pseudokodzie:
```
 
N = 0
sort(intervals, key=startDate)
N += length(intervals[0])
D = intervals[0].endDate
del(intervals[0])
for i in intervals:
    if (i.endDate  D):
            N += length(i)
        else:
            N += length(i) + (D - i.startDate)
        D = i.endDate
```
Odpowiedz
1. rozie pisze:
  
  2024-05-30 o 09:54
  
  Z tego co pamiętam podobne zagadnienie było kiedyś na AoC. IIRC rozwiązałem w ten sposób, że do listy zapisałem posortowane chronologicznie daty rozpoczęcia i zakończenia. Jeśli jest i zakończenie, i rozpoczęcie, to wpisujemy tylko rozpoczęcie. Potem jedna iteracja po liście, jeśli elementem jest rozpoczęcie, to ustal początek okresu (chyba, że już jest ustalony, to nic nie rób), jeśli elementem jest zakończenie, to policz długość okresu i dolicz do sumy i wyzeruj (None) początek okresu.
  
  Odpowiedz
SpeX pisze:

2024-05-31 o 02:07

Dobrze, iż liczysz tylko dni, bo jak byś miał liczyć godziny i jeszcze zapewnić wsparcie dla stref czasowych, nie byłoby tak łatwo.

Odpowiedz

4 komentarze

Leave a Comment Anuluj pisanie odpowiedzi