Odpowiedź na pytanie.

Historia pytania.

Algorytm Kadane'a, sformułowany przez Jaya Kadane'a w 1984 roku, rozwiązuje problem maksymalnej podtablicy za pomocą programowania dynamicznego, śledząc dwa stany: maksymalną sumę kończącą się w aktualnej pozycji oraz globalną maksymalną wartość napotkaną do tej pory. Przekładając ten imperatywny wzór na deklacyjną SQL ANSI, należy symulować iterację sekwencyjną za pomocą Rekurencyjnych CTE, ponieważ standardowe funkcje okienkowe nie mogą wyrażać agregatów bieżących zależnych od wyników obliczeń poprzednich wierszy w sposób wzajemnie rekurencyjny. To zadanie testuje zdolność kandydata do implementacji złożonej logiki algorytmicznej w ramach przetwarzania opartego na zbiorach.

Problem.

Mając tabelę uporządkowanych obserwacji liczbowych (np. codzienny zysk/strata), celem jest zidentyfikowanie pojedynczego ciągłego bloku wierszy produkującego najwyższą możliwą sumę. W przeciwieństwie do prostego bieżącego całkowitego, optymalna podtablica może zaczynać się i kończyć w dowolnych punktach, a decyzja o rozszerzeniu bieżącej podtablicy lub rozpoczęciu na nowo w każdym wierszu zależy od skumulowanej sumy bezpośrednio poprzedniej podtablicy - zależność, która tworzy definicję rekurencyjną zabraniającą prostego agregowania.

Rozwiązanie.

Wykorzystujemy Rekurencyjny CTE, który inicjalizuje pierwszy wiersz swoją wartością zarówno jako current_max_ending_here, jak i global_max_so_far. Część rekurencyjna łączy się z następnym wierszem, używając klucza porządkującego, obliczając nową current_max jako GREATEST(current_value, previous_current_max + current_value) i aktualizując global_max jako GREATEST(previous_global_max, new_current_max). Ostateczna agregacja wybiera maksymalne global_max we wszystkich iteracjach. Podejście to działa w czasie O(n) na partycję, pozostając ściśle oparte na zbiorach.

WITH RECURSIVE numbered AS (
    SELECT 
        partition_id,
        observation_date,
        value,
        ROW_NUMBER() OVER (PARTITION BY partition_id ORDER BY observation_date) AS rn
    FROM daily_returns
),
kadane AS (
    -- Kotwica: inicjalizacja z pierwszego wiersza każdej partycji
    SELECT 
        partition_id,
        rn,
        value,
        value AS current_max_ending_here,
        value AS global_max_so_far
    FROM numbered
    WHERE rn = 1
    
    UNION ALL
    
    -- Krok rekurencyjny: propagacja stanu do przodu
    SELECT 
        n.partition_id,
        n.rn,
        n.value,
        GREATEST(n.value, k.current_max_ending_here + n.value) AS current_max_ending_here,
        GREATEST(k.global_max_so_far, GREATEST(n.value, k.current_max_ending_here + n.value)) AS global_max_so_far
    FROM kadane k
    JOIN numbered n 
        ON k.partition_id = n.partition_id 
        AND n.rn = k.rn + 1
)
SELECT partition_id, MAX(global_max_so_far) AS maximum_subarray_sum
FROM kadane
GROUP BY partition_id;

Sytuacja z życia wzięta

Stół handlowy zajmujący się handlem ilościowym potrzebował zidentyfikować optymalne historyczne okno dla strategii momentum - konkretnie, ciągły ciąg dni handlowych dający najwyższy skumulowany zwrot dla każdej klasy aktywów. Zestaw danych zawierał miliony dziennych rekordów P&L podzielonych na symbole akcji, a zespół badawczy wymagał analizy z opóźnieniem poniżej sekundy w przypadku analiz ad-hoc na tysiącach papierów wartościowych.

Wstępny dowód koncepcji wykorzystał podejście brute-force self-join, które łączyło tabelę z samą sobą w celu wygenerowania wszystkich możliwych dat rozpoczęcia i zakończenia, a następnie agregowało sumy pomiędzy nimi. Chociaż nie wymagało to Rekurencyjnego CTE i było proste do zrozumienia, jego złożoność O(n²) prowadziła do wygaśnięcia zapytania po godzinach wykonywania, co czyniło je niewykonalnym dla analiz na dużą skalę ze względu na nadmierne zużycie CPU i I/O.

Alternatywne podejście wykorzystało kursor proceduralny w Pythonie z psycopg2, aby iterować po wierszach, utrzymując zmienne bieżące. To oferowało intuicyjną logikę imperatywną i łatwe debugowanie, ale naruszało mandat zespołu dotyczący obliczeń w bazie danych, aby zminimalizować przenoszenie danych, a przetwarzanie oparte na kursorach wykazywało słabą wydajność z powodu opóźnień związanych z okrążeniem i braku optymalizacji opartej na zbiorach.

Implementacja Rekurencyjnego CTE symulującego Algorytm Kadane'a została wybrana. To rozwiązanie przetwarzało każdą partycję w pojedynczym liniowym przebiegu, przechowując tylko dwie wartości skalarne na poziomie rekurencji i wykorzystując natywną optymalizację silnika bazy danych dla zapytań rekurencyjnych. Osiągnęło pożądane czasy odpowiedzi na poziomie milisekund w całym zbiorze danych, pozostając całkowicie deklarecyjnym.

Implementacja pomyślnie zidentyfikowała maksymalne rentowne okresy dla ponad pięciu tysięcy papierów wartościowych w ciągu 400 ms. Zespół DBA następnie przyjął ten wzór do podobnych analiz „najlepszego okna”, w tym obliczeń metryk ryzyka i detekcji klastrów zmienności.

Co często umyka kandydatom

Jak rekurencyjny CTE obsługuje partycje zawierające wyłącznie wartości ujemne i dlaczego początkowy wybór wiersza kotwicy zapobiega błędnemu zwrotowi zera?

Wielu kandydatów błędnie inicjalizuje current_max i global_max na zero w członie kotwicy, co powoduje, że algorytm zwraca zero dla całkowicie ujemnych sekwencji (błędnie sugerując, że optymalna jest pusta podtablica). Poprawne podejście inicjalizuje obie agregaty rzeczywistą wartością pierwszego wiersza w każdej partycji. Zapewnia to, że dla sekwencji takiej jak [-5, -2, -8], zapytanie prawidłowo zwraca -2, a nie 0, przestrzegając ograniczenia, że podtablica musi zawierać co najmniej jeden element. Niedostrzeżenie tego przypadku brzegowego prowadzi do cichych błędów logicznych podczas analizy okresów tylko strat.

Czy można odzyskać rzeczywiste granice startowe i końcowe (konkretne wiersze) maksymalnej podtablicy, a nie tylko wartość sumy, używając wyłącznie SQL ANSI?

Tak, ale wymaga to rozszerzenia rekurencyjnego CTE o śledzenie metadanych. Należy przenieść dwie dodatkowe kolumny: current_start_rn (indeks początkowy bieżącej kandydatki na podtablicę) oraz best_start_rn/best_end_rn (granice globalnej maksymalnej wartości). W członie rekurencyjnym, jeśli sama aktualna wartość przewyższa rozszerzoną sumę, ustaw current_start_rn na aktualny row_num; w przeciwnym razie odziedzicz je z poprzedniego wiersza. Gdy global_max_so_far jest aktualizowane, przechwyć aktualny row_num jako best_end_rn i current_start_rn jako best_start_rn. To pokazuje zrozumienie, że Rekurencyjne CTE mogą utrzymywać złożone obiekty stanu, a nie tylko akumulatory skalarne, co pozwala na rekonstrukcję lokalizacji optymalnego okna.

Dlaczego ten problem nie może być rozwiązany przy użyciu standardowych funkcji okienkowych, takich jak SUM() OVER lub MAX() OVER, i jakie konkretne ograniczenie standardu SQL uniemożliwia podejście oparte na oknach?

Standardowe funkcje okienkowe obliczają agregaty nad statycznie określonymi ramami (np. ROWS BETWEEN). Problem maksymalnej podtablicy wymaga bieżącej agregacji, gdzie decyzja o uwzględnieniu bieżącego wiersza zależy od rezultatu agregacji dla poprzedniego wiersza - a konkretnie, czy ta poprzednia suma była dodatnia. To tworzy wzajemną zależność lub rekurencję, której funkcje okienkowe nie mogą wyrazić, ponieważ nie mają możliwości odniesienia się do wyniku funkcji okienkowej z natychmiast poprzedniego wiersza w tym samym zbiorze wyników. Rekurencyjne CTE są wymagane, ponieważ pozwalają na wykorzystanie wyników jednej iteracji jako wejścia dla następnej, efektywnie umożliwiając obliczenia stanowe wiersz po wierszu w ramach paradygmatu deklarecyjnego.