Historia: W hurtowniach danych czasowych technika Last Observation Carried Forward (LOCF) dominuje w imputacji brakujących wartości, wykorzystując poprzednie valid records do wypełnienia luk. Jednakże, w określonych dziedzinach analitycznych — takich jak stosowanie końcowych rozrachunków dziennych do transakcji finansowych w ciągu dnia lub propagowanie laboratoriów potwierdzeń do wcześniejszych wstępnych diagnoz — wymagana jest odwrotna technika Next Observation Carried Backward (NOCB). Historycznie, NOCB była implementowana poprzez skorelowane subzapytania lub proceduralne kursory, które oba wykazują złożoność O(n²) i nie wykorzystują nowoczesnych optymalizatorów opartych na zbiorach.
Problem: Dając całkowicie uporządkowaną sekwencję (np. event_time), każda wartość NULL musi zostać zastąpiona najbliższą nie-NULL wartością, która występuje po niej w sekwencji. Kolejne NULL przed walidowanym rekordem powinny otrzymać tę samą następną wartość. Standardowe funkcje, takie jak LEAD(), uzyskują dostęp tylko do bezpośrednio następnego wiersza, co nie działa, gdy istnieje wiele kolejnych NULL przed nie-NULL kotwicą. Samo-łączenia i rekurencyjne CTE są zakazane ze względów wydajnościowych.
Rozwiązanie: Rozwiązanie wykorzystuje semantykę ignorowania NULL przez COUNT(expression). Licząc wartości nie-NULL od bieżącego wiersza do końca partycji (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING), generujemy stabilny "identyfikator kubełka", który jest identyczny dla wszystkich wierszy między dwoma nie-NULL kotwicami. W każdym kubełku, MAX(val) — który również ignoruje NULL — pobiera wartość kotwicy i rozsyła ją do wszystkich wierszy w tej grupie.
WITH bucketed AS ( SELECT record_id, event_time, status_code, COUNT(status_code) OVER ( ORDER BY event_time, record_id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING ) AS bucket_id FROM audit_log ) SELECT record_id, event_time, COALESCE( MAX(status_code) OVER ( PARTITION BY bucket_id ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING ), 'UNKNOWN' ) AS confirmed_status FROM bucketed;
Kontekst i opis problemu: Firma zajmująca się handlem wysokiej częstotliwości prowadzi tabelę execution, która rejestruje transakcje akcyjne na poziomie mikrosekundowym. Z powodu protokołów raportowania giełdowego, ostateczna „skonsolidowana cena” za dowolną minutę — weryfikowana przez izbę rozrachunkową — przybywa 30 sekund po zakończeniu minuty i jest stemplowana tylko na granicy (np. 14:30:00.000). Dla obliczeń regulacyjnych TWAP (Time-Weighted Average Price) każda milisekunda tej minuty musi odzwierciedlać ostateczną skonsolidowaną cenę, co wymaga wypełnienia wszystkich poprzednich rekordów 14:29:00.000 - 14:29:59.999. Dzienne wolumeny przekraczają 50 milionów wierszy, a okno wsadowe wynosi 10 minut.
Rozwiązanie 1: Skorelowane skalarne subzapytanie. To podejście wykorzystuje skalarne subzapytanie dla każdego wiersza, aby znaleźć MIN(event_time) przyszłych wierszy, gdzie consolidated_price IS NOT NULL, a następnie łączy z powrotem, aby pobrać tę cenę.
Zalety: Koncepcyjnie proste dla programistów z tłem proceduralnym.
Wady: Wykonuje porównania O(n²). Na danych produkcyjnych czas zapytania przekroczył 45 minut, co naruszyło okno wsadowe. Obsługa wielu kolejnych NULL wymaga dodatkowej logiki do przeskakiwania, co zwiększa złożoność i wskaźniki błędów.
Rozwiązanie 2: Rekursywna Traversal CTE. Rekursywny CTE iteruje wstecz wiersz po wierszu, przenosząc nie-NULL cenę do tyłu, aż napotka kolejny nie-NULL.
Zalety: Gwarantowane działanie w dowolnej bazie danych zgodnej z ANSI SQL.
Wady: Rekursywne CTE przetwarzają wiersze sekwencyjnie w wielu silnikach (np. PostgreSQL), co skutkuje jednoprocesorowym wykonywaniem i potencjalnym przepełnieniem stosu na głębokich partycjach. Wyniki benchmarków wykazały czas wykonania 20 minut przy wysokim ciśnieniu pamięci, co czyni to rozwiązanie nieodpowiednim do SLA produkcyjnych.
Rozwiązanie 3: Bucketizacja funkcji okiennych (wybrane). Implementacja wzoru COUNT i MAX. Liczenie wstecz COUNT tworzy identyczne kubełki dla wszystkich wierszy wymagających tej samej przyszłej wartości, podczas gdy MAX propaguje tę wartość w obrębie kubełka.
Zalety: Całkowicie oparte na zestawach, możliwe do równoległego przetwarzania, wykonuje się w czasie O(n log n) dzięki działaniu sortującym. Skaluje się liniowo z wolumenem i wykorzystuje standardowy ANSI SQL, przenośny między PostgreSQL, SQL Server, Oracle i DB2.
Wady: Wymaga dwóch przejść przez dane (CTE i zapytanie zewnętrzne), chociaż nowoczesne optymalizatory często łączą te przejścia. Wymaga całkowitego uporządkowania; zduplikowane znaczniki czasu potrzebują kolumny do rozstrzygania, aby zapewnić deterministyczność.
Wynik: Czas wykonywania potoku spadł z 45 minut do 8 sekund na zbiorze danych liczącym 50 milionów wierszy. Firma wyeliminowała delikatny skrypt uzupełniający w Pythonie, redukując złożoność infrastruktury i zapewniając generowanie raportów regulacyjnych w ramach okna zgodności.
Dlaczego należy używać COUNT(column) zamiast COUNT(*) lub ROW_NUMBER() przy konstruowaniu klucza grupującego?
Wielu kandydatów intuicyjnie używa COUNT(*) lub ROW_NUMBER(), wierząc, że te mogą segmentować dane. COUNT(*) liczy każdy wiersz niezależnie od NULL, produkując unikalną, monotonicznie zmieniającą się wartość dla każdego wiersza w oknie wstecznym, co uniemożliwia formowanie stabilnych grup. ROW_NUMBER() przypisuje unikalny identyfikator każdemu wierszowi, podobnie niszcząc grupowanie. Tylko COUNT(column) inkrementuje wyłącznie po napotkaniu wartości nie-NULL, przydzielając tę samą "identyfikator kubełka" wszystkim poprzednim NULL aż do następnej granicy nie-NULL. To rozróżnienie jest kluczowe, ponieważ wykorzystuje semantykę ignorowania NULL funkcji agregujących, aby zasymulować „look-ahead” bez logiki proceduralnej.
Jak zapytanie zachowuje się, jeśli partycja kończy się na końcowych wartościach NULL i jaka modyfikacja zapewnia deterministyczne traktowanie, gdy nie istnieje przyszła obserwacja?
Jeśli ostatnie wiersze w uporządkowanej partycji są NULL, COUNT(status_code) ocenia się na zero dla tych wierszy. W konsekwencji MAX(status_code) zwraca NULL, co jest logicznie poprawne — nie istnieje przyszła obserwacja do przeniesienia wstecz. Kandydaci często zapominają o obsłudze tego w dalszej logice biznesowej. Aby zapewnić wartość domyślną (np. statyczny placeholder lub wartość z zewnętrznego wyszukiwania), należy owijać wynik w COALESCE. Ponadto, aby odróżnić „wypełnione NULL” od „nie-wypełnialnych NULL” dla monitorowania jakości danych, należy porównać oryginalne i wypełnione wartości: CASE WHEN status_code IS NULL AND bucket_id = 0 THEN 'UNCONFIRMED' END.
Jaki problem deterministyczny pojawia się, jeśli klauzula ORDER BY zawiera zduplikowane wartości i dlaczego przejście z ROWS na RANGE pogarsza problem?
Gdy klucze porządkowe zawierają duplikaty (remisy), definicja okna staje się niejasna. Użycie ROWS (fizyczne przesunięcia) przydziela grupy na podstawie fizycznego porządku tabeli, co jest arbitralne, chyba że podano unikalny klucz sortujący. Przejście na RANGE (logiczne zakresy wartości) traktuje wszystkie wiersze z tą samą wartością porządkową jako równorzędne, powodując, że dzielą tę samą ramę. W tym rozwiązaniu, jeśli wiele wierszy dzieli ten sam event_time, RANGE może błędnie grupować NULL z nie-NULL z tego samego znacznika czasu lub losowo dzielić grupy. Kandydaci muszą zapewnić całkowite uporządkowanie, dodając unikalny klucz (np. record_id) do klauzuli ORDER BY: ORDER BY event_time, record_id, aby zapewnić deterministyczne przypisanie kubełków we wszystkich implementacjach ANSI SQL.