Historia pytania: Analiza interwałów czasowych stanowi wyzwanie dla baz danych relacyjnych od lat 70-tych, ponieważ SQL został pierwotnie zaprojektowany bez natywnych typów interwałów. Wczesne rozwiązania polegały na iteracji opartej na kursorach lub iloczynach kartezjańskich między interwałami, co skutkowało kwadratową złożonością. Wprowadzenie funkcji okienkowych w SQL:2003 i specyfikacji ramki ROWS BETWEEN umożliwiło efektywne agregaty biegowe, ustanawiając podstawy dla nowoczesnych obliczeń współbieżności opartych na zdarzeniach.
Problem: Określenie maksymalnej współbieżności wymaga zrozumienia precyzyjnych momentów, w których zachodzą zmiany stanu — konkretnie, gdy rezerwacja się zaczyna lub kończy. Naiwne podejście rozszerza każdy interwał na dyskretne jednostki czasu (podział czasu), co jest obliczeniowo nieopłacalne dla długoterminowych pobytów. Kluczowym wyzwaniem jest obliczenie, ile interwałów pokrywa się w danym momencie bez materializacji każdego momentu linii czasowej.
Rozwiązanie: Zastosuj wzorzec symulacji zdarzeń dyskretnych. Przekształć tabelę interwałów w strumień zdarzeń za pomocą UNION ALL, przypisując wagę +1 do każdego zameldowania (początek) i -1 do każdego wymeldowania (koniec). Sortując te zdarzenia chronologicznie i stosując sumę biegową za pomocą funkcji okienkowej SUM() OVER (ORDER BY ...), uzyskasz liczbę aktywnych rezerwacji w każdym punkcie przejścia. Maksymalna wartość tej sumy biegowej reprezentuje szczytową współbieżność.
WITH events AS ( SELECT check_in AS event_time, 1 AS delta FROM reservations UNION ALL SELECT check_out AS event_time, -1 AS delta FROM reservations ), concurrency AS ( SELECT event_time, SUM(delta) OVER ( ORDER BY event_time, delta DESC ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW ) AS active_count FROM events ) SELECT MAX(active_count) AS peak_concurrency FROM concurrency;
Opis problemu: Luksusowa sieć ośrodków wypoczynkowych doświadczyła tajemniczych incydentów z nadmiernym rezerwowaniem w czasie weekendów świątecznych mimo tego, że ich system dostępności zgłaszał wolne miejsca. Dziedzictwo zapytania obliczało codzienną zajętość, rozwalając każdą rezerwację na poszczególne wiersze nocne za pomocą rekurencyjnego CTE, generując miliony wierszy dla pobytów trwających miesiąc. Podczas analizy Nowego Roku, to podejście zajmowało 12 sekund na wykonanie i powodowało zakleszczenia w tabeli transakcji rezerwacyjnych, uniemożliwiając rezerwacje w czasie rzeczywistym.
Rozwiązanie A: Rozszerzenie poprzez podział czasu z tabelami liczbowymi. Zespół operacyjny początkowo zasugerował wstępne wygenerowanie tabeli kalendarza i połączenie jej z rezerwacjami za pomocą event_date BETWEEN check_in AND check_out. Metoda ta daje intuicyjne agregaty dzienne kompatybilne z standardowymi klauzulami GROUP BY. Plusy: Konceptualnie prosta dla analityków biznesowych, łatwa do zintegrowania z istniejącymi narzędziami BI. Minusy: Generuje O(N × D) wierszy, gdzie D to średni czas trwania, powodując wykładniczy wzrost; katastrofalnie zawodzi w przypadku podziału na minuty lub długoterminowych umów; zużywa nadmierną ilość przestrzeni w tempdb.
Rozwiązanie B: Drzewo interwałowe z zmaterializowanymi ścieżkami. Starszy architekt zaproponował wdrożenie struktury drzewa segmentowego przy użyciu zagnieżdżonych zbiorów do indeksowania granic interwałów, co umożliwiłoby zapytania o pokrycie w czasie logarytmicznym. Plusy: Optymalna teoretyczna złożoność dla częstych aktualizacji i zapytań punktowych. Minusy: Wymaga skomplikowanych wyzwalaczy do utrzymania równowagi drzewa; narusza przenośność ANSI SQL polegając na rozszerzeniach proceduralnych; wprowadza amplifikację zapisu, co szkodzi obciążeniu OLTP podczas szczytów rezerwacyjnych.
Rozwiązanie C: Chronologiczny strumień zdarzeń z biegłymi sumami (wybrane). Zespół baz danych przyjął podejście oparte na zdarzeniach, traktując każdą granicę rezerwacji jako operację delta. To zmniejszyło zbiór danych z milionów rozwalonych wierszy do dokładnie 2N zdarzeń (początek i koniec dla każdej rezerwacji). Plusy: Złożoność O(N log N) zdominowana przez operację sortowania, stały ślad pamięci, oraz czysta kompatybilność ANSI SQL w PostgreSQL, Oracle i SQL Server. Minusy: Wymaga starannego zarządzania równoczesnymi zdarzeniami i nie identyfikuje automatycznie, które konkretnie rezerwacje przyczyniły się do szczytu bez dodatkowych połączeń.
Efekt: Opóźnienie zapytania spadło z 12 sekund do 45 milisekund. Analiza ujawniła, że prawdziwym wąskim gardłem nie była liczba pokoi (500 jednostek), ale pojemność wind, ponieważ 320 gości próbowało jednoczesnych zameldowań o 18:00. To spostrzeżenie skłoniło do wdrożenia stopniowanych poziomów zameldowania, zamiast budowania nowego skrzydła, co zaoszczędziło 2 miliony dolarów wydatków kapitałowych, eliminując jednocześnie zakleszczenia.
Dlaczego rozwiązanie wymaga ORDER BY event_time, delta DESC dokładnie, i co się stanie, jeśli pominiesz wtórne sortowanie po delta?
Kandydaci często ignorują semantykę warunków granicznych w punktach czasowych. Gdy jeden gość wymeldowuje się dokładnie o 10:00, a inny zameldowuje się o 10:00, kolejność przetwarzania decyduje o tym, czy pokój wydaje się być zajęty przez dwóch gości jednocześnie. Sortując według delta DESC, zapewniamy, że -1 (opuszczenie) jest przetwarzane przed +1 (przybycie) w identycznych znacznikach czasu. Bez tego wtórnego sortowania suma biegowa tymczasowo spada, a następnie skacze, potencjalnie rejestrując fałszywy szczyt, podczas gdy wcześniejszy stan był w rzeczywistości wyższy. To subtelne sortowanie zapobiega błędom o jeden, które prowadzą do zagrożeń związanych z nadmiernym rezerwowaniem w systemach produkcyjnych.
Jak zmodyfikowałbyś to zapytanie, aby zidentyfikować które konkretne rezerwacje były aktywne w momencie szczytowej współbieżności, a nie tylko liczbę?
Większość kandydatów próbuje filtrować w tym samym CTE, nie zauważając, że szczyt może obejmować ciągły interwał, a nie tylko jeden punkt. Solidne podejście wymaga strategii dwuetapowej: najpierw oddzielić znacznik czasu, w którym active_count równa się maksymalnej wartości, używając podzapytania lub CTE, następnie dołączyć z powrotem do oryginalnej tabeli rezerwacji za pomocą predykatu nakładania r.check_in <= peak.event_time AND r.check_out > peak.event_time. Kandydaci nie dostrzegają, że wiele znaczników czasu może dzielić tę samą maksymalną wartość, co wymaga klauzuli DISTINCT lub EXISTS, aby uniknąć duplikacji rezerwacji, gdy szczytowa płaskowyż utrzymuje się przez kilka przejść zdarzeń.
Jakie zmiany są konieczne, jeśli zasady biznesowe zmieniają się tak, że czas wymeldowania jest wliczany (gość zajmuje pokój do 23:59), a jak to wpływa na ważenie zdarzeń?
Kandydaci często pomijają semantykę granic interwałów. Wliczające końce [start, end] tworzą nakładki, gdy jedna rezerwacja kończy się, a inna zaczyna w tym samym dniu. Rozwiązanie wymaga przekształcenia końców wliczających na wyłączne poprzez dodanie nieskończonego epsilonu (lub następnej dyskretnej jednostki czasowej) do czasów wymeldowania przed generowaniem zdarzenia -1. Alternatywnie, należy dostosować logikę dołączania, aby używać check_out >= event_time, zachowując logiczną sumę biegową nienaruszoną. Niepowodzenie w dokonaniu tej zmiany przekształca model zdarzenia dyskretnego z półotwartych interwałów na domknięte, co powoduje, że algorytm zgłasza konflikty, gdzie ich nie ma i niedoszacowuje prawdziwej pojemności o dokładnie jedną jednostkę podczas wysokich okresów rotacji.