To wyzwanie pochodzi z obszaru planowania pojemności i alokacji zasobów, szczególnie w systemach takich jak platformy rezerwacji hotelowych, automatyczne skalowanie infrastruktury chmurowej i harmonogramowanie placówek medycznych. Wczesne rozwiązania polegały na iteracji opartej na kursorach lub logice zewnętrznych aplikacji do przeglądania osi czasu, co wiązało się z poważnymi karami wydajnościowymi przy dużych zbiorach danych. Pojawienie się funkcji okienkowych ANSI SQL:2003 umożliwiło czysto relacyjne podejścia do analizy czasowej, pozwalając bazom danych na efektywne zarządzanie złożoną arytmetyką przedziałów wewnątrz silnika.
Dany jest stół rezerwacji zasobów z znacznikami czasowymi start_time i end_time, celem jest określenie maksymalnej liczby równoczesnych rezerwacji aktywnych w każdym momencie oraz identyfikacja konkretnych przedziałów czasowych, kiedy ten szczyt wystąpił. Złożoność polega na tym, że standardowa agregacja zniekształca dane czasowe, podczas gdy proste łączenia tworzą eksplozję kartezjańską, gdy przedziały się pokrywają. Solidne rozwiązanie musi traktować początek i koniec przedziału jako odrębne zdarzenia, obliczając bieżące zliczanie aktywnych zasobów w każdym punkcie przejścia.
Kanoniczne podejście przekształca przedziały w odrębne zdarzenia, używając UNION ALL do oddzielenia początków (waga +1) i końców (waga -1), a następnie stosuje sumę kumulacyjną za pomocą SUM() OVER (ORDER BY timestamp), aby śledzić równoczesność. Aby deterministycznie obsłużyć jednoczesne początki/końce, zdarzenia końcowe muszą być przetwarzane przed zdarzeniami początkowymi w tym samym znaczniku czasowym (z wykorzystaniem pomocniczego klucza sortowania). Na koniec owinięto to w CTE w celu filtrowania maksymalnej wartości równoczesności.
WITH events AS ( SELECT start_time AS ts, 1 AS delta, 0 AS is_end FROM reservations UNION ALL SELECT end_time AS ts, -1 AS delta, 1 AS is_end FROM reservations ), concurrency AS ( SELECT ts, SUM(delta) OVER (ORDER BY ts, is_end, delta ROWS UNBOUNDED PRECEDING) AS concurrent_count FROM events ) SELECT MAX(concurrent_count) AS peak_concurrency FROM concurrency;
Aby znaleźć konkretne przedziały czasowe szczytowego użycia, należy połączyć z powrotem, aby zidentyfikować okresy między kolejnych znacznikami czasowymi, gdzie liczba równa się maksymalnej.
Platforma SaaS śledziła miliony zadań transkodowania wideo w tabeli jobs z znacznikami czasowymi started_at i completed_at. Zespół operacyjny potrzebował zidentyfikować dokładne okresy, kiedy wykorzystanie GPU osiągnęło 100%, aby zoptymalizować harmonogram kolejkowania.
Jednym z rozważanych podejść było użycie kursora do iteracyjnego przeglądania danych chronologicznie, zwiększając licznik przy początkach i zmniejszając przy końcach. Choć proste dla programistów zaznajomionych z językami imperatywnymi, metoda ta przetwarzała wiersze sekwencyjnie, zajmując ponad 45 minut na produkcyjnych danych i blokując tabele. Wymagała również skomplikowanego zarządzania transakcjami, aby zapewnić spójność odczytów.
Inna alternatywa polegała na generowaniu tabeli szeregów czasowych z jednym wierszem na minutę i dołączeniu jej do przedziałów z wykorzystaniem predykatów BETWEEN. To dawało dokładne wyniki, ale wymagało miliardów wierszy dla precyzji na poziomie minut przez rok, konsumując terabajty tymczasowego miejsca na dane i nie łapiąc szczytowych skoków w czasie sub-minutowym.
Zespół wybrał podejście oparte na zdarzeniach UNION ALL z funkcjami okienkowymi ANSI SQL. Traktując początki i końce jako zdarzenia +1/-1, zapytanie wykonało się w 12 sekund, wykorzystując standardowe indeksy B-tree na kolumnach znaczników czasowych. Metoda ta poprawnie obsługiwała przypadki skrajne, w których zadania kończyły się dokładnie w momencie, gdy inne zaczynały.
Analiza ujawniła, że szczytowa równoczesność występowała podczas nocnego przetwarzania wsadowego między 02:00 a 02:07 UTC, osiągając 847 jednoczesnych zadań. Dzięki wdrożeniu dynamicznego zarządzania kolejkami specjalnie dla tego okresu, zapobiegli awariom kaskadowym i zmniejszyli nadmierne przydzielanie infrastruktury o 30%.
Jak obsługujesz przedziały o zerowej długości (start_time = end_time) bez niewłaściwego zwiększania liczby równoczesnych połączeń?
Przedziały o zerowej długości reprezentują zdarzenia chwilowe, które nie powinny przyczyniać się do równoczesnego obciążenia. Jeśli traktowane są jako standardowe przedziały, mogą być liczone jako aktywne podczas swojego własnego zdarzenia końcowego. Rozwiązanie wymaga przypisania ścisłego klucza porządkowego: przetwarzaj zdarzenia końcowe (-1) przed zdarzeniami początkowymi (+1), gdy znaczników czasowych kolidują, i całkowicie wykluczaj przedziały o zerowej długości z strumienia zdarzeń lub przypisuj im deltę równą 0, w zależności od logiki biznesowej. W ANSI SQL implementuje się to poprzez dodanie kolumny dyskryminacyjnej: ORDER BY ts, is_end ASC, delta ASC, zapewniając, że zakończenia zmniejszają liczbę przed nowymi alokacjami, które ją zwiększają w tym samym znaczniku czasowym.
Dlaczego podejście oparte na zdarzeniach może potencjalnie zwrócić nieprawidłowe wyniki, jeśli użyjesz UNION zamiast UNION ALL przy łączeniu zdarzeń początkowych i końcowych?
UNION domyślnie wykonuje operację DISTINCT, zmniejszając powtarzające się znaczniki czasowe. Jeśli dwie rezerwacje zaczynają się dokładnie o 2023-10-01 10:00:00, UNION redukuje to do jednego wiersza, powodując, że suma kumulacyjna pomija jedno zwiększenie +1. Skutkuje to niedoszacowaniem równoczesności. UNION ALL zachowuje każde pojedyncze granice przedziału jako oddzielne zdarzenie, co jest matematycznie wymagane, ponieważ każda rezerwacja niezależnie przyczynia się do całkowitego obciążenia. Kandydaci często pomijają tę różnicę, zakładając unikalność znaczników czasowych, gdzie wielokrotność jest niezbędna dla poprawnej agregacji.
Jak obliczając konkretne przedziały czasowe szczytowej równoczesności (nie tylko maksymalną wartość), unikasz luk w wynikach, jeśli wiele kolejnych okresów czasowych dzieli tę samą wartość szczytową?
Po zidentyfikowaniu maksymalnej wartości równoczesności, łączenie z powrotem, aby znaleźć wszystkie znaczniki czasowe, gdzie to występuje, daje początkowe punkty. Aby odtworzyć ciągłe bloki czasowe trwania, należy zastosować technikę Gaps and Islands: użyj LAG(), aby sprawdzić, czy poprzedni wiersz również był na szczycie, i LEAD(), aby sprawdzić, czy następny wiersz jest na szczycie. Wypisz tylko wiersze, w których poprzednia wartość różni się (początek wyspy) lub następna wartość różni się (koniec wyspy). Następnie sparuj te wartości, używając ROW_NUMBER() do tworzenia par początek-koniec. Kandydaci często podają surowe listy znaczników czasowych lub używają GROUP BY na wartości zliczenia, co traci potrzebne informacje o sąsiedztwie czasowym potrzebne do rozróżnienia oddzielnych zdarzeń szczytowych od jednego ciągłego okresu szczytowego.