Risposta alla domanda.

Storia della domanda.

Algoritmo di Kadane, formulato da Jay Kadane nel 1984, risolve il problema del massimo sottoarray tramite programmazione dinamica tracciando due stati: la somma massima che termina nella posizione attuale e il massimo globale incontrato. Tradurre questo modello imperativo in ANSI SQL dichiarativo richiede di simulare l'iterazione sequenziale attraverso CTE ricorsive, poiché le funzioni finestra standard non possono esprimere aggregati in esecuzione che dipendono dai risultati computati delle righe precedenti in un modo mutuamente ricorsivo. Questo problema mette alla prova la capacità di un candidato di implementare logica algoritmica complessa all'interno dei vincoli dell'elaborazione basata su set.

Il problema.

Data una tabella di osservazioni numeriche ordinate (ad esempio, profitti/perdite giornalieri), l'obiettivo è identificare il singolo blocco contiguo di righe che produce la somma massima possibile. A differenza di un semplice totale in esecuzione, il sottoarray ottimale può iniziare e finire in qualsiasi punto arbitrario, e la decisione di estendere il sottoarray attuale o di iniziare di nuovo a ogni riga dipende dalla somma accumulata del sottoarray immediatamente precedente—una dipendenza che crea una definizione ricorsiva che vieta l'aggregazione semplice.

La soluzione.

Utilizziamo un CTE ricorsivo che semina la riga iniziale con il suo valore sia come current_max_ending_here che come global_max_so_far. Il membro ricorsivo si unisce alla riga successiva utilizzando una chiave di ordinamento, calcolando il nuovo current_max come GREATEST(current_value, previous_current_max + current_value) e aggiornando global_max come GREATEST(previous_global_max, new_current_max). Un'aggregazione finale seleziona il massimo global_max attraverso tutte le iterazioni. Questo approccio si esegue in O(n) tempo per partizione, rimanendo rigorosamente basato su set.

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 (
    -- Ancora: inizializza con la prima riga di ciascuna partizione
    SELECT 
        partition_id,
        rn,
        value,
        value AS current_max_ending_here,
        value AS global_max_so_far
    FROM numbered
    WHERE rn = 1
    
    UNION ALL
    
    -- Passo ricorsivo: propagare lo stato in avanti
    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;

Situazione reale

Un desk di trading quantitativo aveva bisogno di identificare la finestra storica ottimale per una strategia di momentum—specificamente, la sequenza contigua di giorni di trading che produceva il rendimento cumulativo più alto per ciascuna classe di attivo. Il dataset conteneva milioni di record giornalieri di P&L partizionati per simbolo azionario e il team di ricerca richiedeva una latenza sub-secondo per analisi ad-hoc su migliaia di titoli.

La prova di concetto iniziale utilizzava un approccio di self-join brute-force che univa la tabella con se stessa per generare tutte le possibili date di inizio e fine, quindi aggregava le somme tra di esse. Anche se questo non richiedeva alcun CTE ricorsivo ed era semplice da concettualizzare, la sua complessità O(n²) comportava timeout delle query dopo ore di esecuzione, rendendolo non praticabile per analisi su scala di produzione a causa di un'eccessiva CPU e consumo di I/O.

Un approccio alternativo utilizzava un cursore procedurale in Python con psycopg2 per iterare tra le righe mantenendo variabili in esecuzione. Questo offriva logica imperativa intuitiva e facile debug, ma violava il mandato del team per il calcolo in-database per minimizzare il trasferimento di dati, e l'elaborazione basata su cursore mostrava scarse prestazioni a causa della latenza di round-trip e della mancanza di ottimizzazione basata su set.

L'implementazione CTE ricorsiva che simula l'algoritmo di Kadane è stata selezionata. Questa soluzione ha elaborato ogni partizione in un singolo passaggio lineare, memorizzando solo due valori scalari per livello di ricorsione e sfruttando l'ottimizzazione nativa del motore di database per le query ricorsive. Ha raggiunto i tempi di risposta desiderati a livello di millisecondi su tutto il dataset rimanendo puramente dichiarativa.

L'implementazione ha identificato con successo le massime strisce redditizie per oltre cinquemila titoli entro 400 ms. Il team DBA ha successivamente adottato questo modello per analisi simili di "migliore finestra", comprese le responsabilità di calcolo dei rischi e la rilevazione della clustering di volatilità.

Cosa spesso i candidati perdono

Come gestisce il CTE ricorsivo le partizioni contenenti esclusivamente valori negativi e perché la selezione errata della riga iniziale impedisce il ritorno errato di zero?

Molti candidati inizializzano erroneamente current_max e global_max a zero nel membro di ancoraggio, il che causa all'algoritmo di restituire zero per tutte le sequenze negative (erroneamente implicando che un sottoarray vuoto sia ottimale). L'approccio corretto inizializza entrambi gli aggregati al valore effettivo della prima riga all'interno di ciascuna partizione. Questo garantisce che per una sequenza come [-5, -2, -8], la query restituisca correttamente -2 piuttosto che 0, aderendo al vincolo che il sottoarray deve contenere almeno un elemento. Non tenere conto di questo caso limite porta a errori logici silenziosi nell'analisi di periodi solo di perdita.

Puoi recuperare i confini di inizio e fine effettivi (le righe specifiche) del massimo sottoarray, non solo il valore di somma, utilizzando esclusivamente SQL ANSI?

Sì, ma richiede di estendere il CTE ricorsivo per tenere traccia dei metadati. Devi portare avanti due colonne aggiuntive: current_start_rn (l'indice di partenza del corrente candidato di sottoarray) e best_start_rn/best_end_rn (i confini del massimo globale). Nel membro ricorsivo, se il valore corrente da solo supera la somma estesa, imposta current_start_rn all'attuale row_num; altrimenti, ereditalo dalla riga precedente. Quando global_max_so_far si aggiorna, cattura l'attuale row_num come best_end_rn e current_start_rn come best_start_rn. Questo dimostra la comprensione che CTE ricorsive possono mantenere oggetti di stato complessi, non solo accumulatori scalari, consentendo la ricostruzione della posizione della finestra ottimale.

Perché questo problema non può essere risolto utilizzando funzioni finestra standard come SUM() OVER o MAX() OVER, e quale specifica limitazione dello standard SQL impedisce un approccio basato su finestra?

Le funzioni finestra standard calcolano aggregati su frame definiti staticamente (ad esempio, ROWS BETWEEN). Il problema massimo del sottoarray richiede un'aggregazione in esecuzione in cui la decisione di includere la riga corrente dipende dal risultato dell'aggregazione per la riga precedente—specificamente, se quella somma precedente fosse positiva. Questo crea una dipendenza reciproca o ricorsione che le funzioni finestra non possono esprimere perché non hanno la capacità di fare riferimento all'output della funzione finestra dalla riga immediatamente precedente nello stesso set di risultati. CTE ricorsive sono richieste perché consentono che l'output di un'iterazione serva come input per la successiva, abilitando di fatto il calcolo con stato riga per riga all'interno del paradigma dichiarativo.