Geschichte der Frage.
Kadane's Algorithmus, formuliert von Jay Kadane im Jahr 1984, löst das Maximum-Unterarray-Problem mithilfe von dynamischer Programmierung, indem er zwei Zustände verfolgt: die maximale Summe am aktuellen Punkt und das globale Maximum, das erreicht wurde. Die Übersetzung dieses imperativen Musters in deklarative ANSI SQL erfordert die Simulation einer sequentiellen Iteration durch Recursive CTEs, da Standardfensterfunktionen keine laufenden Aggregationen ausdrücken können, die von den berechneten Ergebnissen vorhergehender Zeilen in gegenseitiger rekursiver Weise abhängen. Dieses Problem testet die Fähigkeit eines Kandidaten, komplexe algorithmische Logik innerhalb der Einschränkungen prozessorientierter Verarbeitung zu implementieren.
Das Problem.
Gegeben ist eine Tabelle von geordneten numerischen Beobachtungen (z. B. täglicher Gewinn/Verlust), wobei das Ziel darin besteht, den einzigen zusammenhängenden Block von Zeilen zu identifizieren, der die höchstmögliche Summe produziert. Im Gegensatz zu einer einfachen laufenden Summe kann das optimale Unterarray an beliebigen Punkten beginnen und enden, und die Entscheidung, das aktuelle Unterarray zu erweitern oder bei jeder Zeile neu zu beginnen, hängt von der kumulierten Summe des unmittelbar vorhergehenden Unterarrays ab – eine Abhängigkeit, die eine rekursive Definition schafft, die einfache Aggregation verbietet.
Die Lösung.
Wir nutzen eine Recursive CTE, die die erste Zeile mit ihrem Wert sowohl als current_max_ending_here als auch als global_max_so_far initialisiert. Das rekursive Mitglied verbindet sich mit der folgenden Zeile unter Verwendung eines Ordnungs-Schlüssels, berechnet das neue current_max als GREATEST(current_value, previous_current_max + current_value) und aktualisiert global_max als GREATEST(previous_global_max, new_current_max). Eine abschließende Aggregation wählt das maximale global_max über alle Iterationen aus. Dieser Ansatz wird in O(n) Zeit pro Partition ausgeführt, während er strikt set-basiert bleibt.
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 ( -- Anker: initialisiere mit der ersten Zeile jeder Partition SELECT partition_id, rn, value, value AS current_max_ending_here, value AS global_max_so_far FROM numbered WHERE rn = 1 UNION ALL -- Rekursiver Schritt: Zustand nach vorne propagieren 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;
Ein quantitatives Handelsteam musste das optimale historische Zeitfenster für eine Momentum-Strategie identifizieren – spezifisch die zusammenhängende Sequenz von Handelstagen, die die höchsten kumulierten Renditen für jede Vermögensklasse liefert. Der Datensatz enthielt Millionen täglicher P&L-Records, die nach Aktiensymbol partitioniert waren, und das Forschungsteam benötigte eine Latenz von unter einer Sekunde für Ad-hoc-Analysen über tausende von Wertpapieren.
Der ursprüngliche Proof-of-Concept verwendete einen bruteforce Selbst-Join-Ansatz, der die Tabelle mit sich selbst kreuzjointe, um alle möglichen Start- und Enddaten zu generieren, und dann Summen zwischen ihnen aggregierte. Obwohl dies keine Recursive CTE erforderte und einfach zu konzipieren war, führte die O(n²)-Komplexität zu Zeitüberschreitungen bei Abfragen nach Stunden der Ausführung, wodurch es für die Produktionsanalysen aufgrund übermäßigen CPU- und I/O-Verbrauchs unbrauchbar wurde.
Ein alternativer Ansatz nutzte einen prozeduralen Cursor in Python mit psycopg2, um durch Zeilen zu iterieren und gleichzeitig laufende Variablen zu verwalten. Dies bot intuitive imperative Logik und einfaches Debugging, verletzte jedoch das Mandat des Teams für Berechnungen innerhalb der Datenbank, um den Datentransferüberkopf zu minimieren, und die Verarbeitung mit Cursor zeigte aufgrund der Round-Trip-Latenz und des Mangels an set-basierter Optimierung eine schlechte Leistung.
Die Implementierung der Recursive CTE, die Kadane's Algorithmus simuliert, wurde ausgewählt. Diese Lösung verarbeitete jede Partition in einem einzigen linearen Durchgang, speicherte nur zwei skalare Werte pro Rekursionsebene und nutzte die native Optimierung der Datenbank-Engine für rekursive Abfragen. Sie erreichte die gewünschten Antwortzeiten im Millisekundenbereich über den gesamten Datensatz hinweg und blieb dabei rein deklarativ.
Die Implementierung identifizierte erfolgreich die maximal profitablen Zeiträume für über fünftausend Wertpapiere in 400 ms. Das DBA-Team übernahm daraufhin dieses Muster für ähnliche "beste Fenster"-Analysen, einschließlich Risikometriken und der Erkennung von Volatilitätsclustern.
Wie verarbeitet die rekursive CTE Partitionen, die ausschließlich negative Werte beinhalten, und warum verhindert die Auswahl der anfänglichen Ankerzeile die fehlerhafte Rückgabe von null?
Viele Kandidaten initialisieren current_max und global_max fälschlicherweise mit null im Ankermitglied, was dazu führt, dass der Algorithmus für vollständig negative Sequenzen null zurückgibt (was fälschlicherweise impliziert, dass ein leeres Unterarray optimal ist). Der korrekte Ansatz initialisiert beide Aggregationen mit dem tatsächlichen Wert der ersten Zeile innerhalb jeder Partition. Dies stellt sicher, dass für eine Sequenz wie [-5, -2, -8] die Abfrage korrekt -2 anstelle von 0 zurückgibt, was die Bedingung einhält, dass das Unterarray mindestens ein Element enthalten muss. Das Versäumnis, diesen Randfall zu berücksichtigen, führt zu stillen logischen Fehlern bei der Analyse nur verlustergebender Perioden.
Können Sie die tatsächlichen Start- und Endgrenzen (die spezifischen Zeilen) des maximalen Unterarrays abrufen, nicht nur den Summenwert, unter Verwendung von ausschließlich ANSI SQL?
Ja, aber es erfordert die Erweiterung der rekursiven CTE, um Metadaten zu verfolgen. Sie müssen zwei zusätzliche Spalten weitergeben: current_start_rn (den Startindex des aktuellen Kandidatenunterarrays) und best_start_rn/best_end_rn (die Grenzen des globalen Maximums). Im rekursiven Mitglied, wenn der aktuelle Wert allein die erweiterte Summe übersteigt, setzen Sie current_start_rn auf die aktuelle row_num; andernfalls übernehmen Sie es von der vorhergehenden Zeile. Wenn global_max_so_far aktualisiert wird, erfassen Sie die aktuelle row_num als best_end_rn und current_start_rn als best_start_rn. Dies zeigt das Verständnis, dass Recursive CTEs komplexe Zustandsobjekte aufrechterhalten können, nicht nur skalare Akkumulatoren, und die Rekonstruktion des Standorts des optimalen Fensters ermöglicht.
Warum kann dieses Problem nicht mit Standardfensterfunktionen wie SUM() OVER oder MAX() OVER gelöst werden, und welche spezifische Einschränkung des SQL-Standards verhindert einen fensterbasierten Ansatz?
Standardfensterfunktionen berechnen Aggregationen über statisch definierte Rahmen (z.B. ROWS BETWEEN). Das maximale Unterarray-Problem erfordert eine laufende Aggregation, bei der die Entscheidung, die aktuelle Zeile einzubeziehen, von dem Ergebnis der Aggregation der vorhergehenden Zeile abhängt - konkret, ob diese vorherige Summe positiv war. Dies schafft eine gegenseitige Abhängigkeit oder Rekursion, die Fensterfunktionen nicht ausdrücken können, weil sie die Möglichkeit fehlen, die Ausgabe der Fensterfunktion aus der unmittelbar vorhergehenden Zeile im gleichen Ergebnissatz zu referenzieren. Recursive CTEs sind erforderlich, da sie es erlauben, dass die Ausgabe einer Iteration als Eingabe für die nächste dient, was eine zeilenweise zustandsabhängige Berechnung innerhalb des deklarativen Paradigmas ermöglicht.