Historique de la question.
L'algorithme de Kadane, formulé par Jay Kadane en 1984, résout le problème du sous-tableau maximal via la programmation dynamique en suivant deux états : la somme maximale se terminant à la position actuelle et le maximum global rencontré. Traduire ce modèle impératif en ANSI SQL déclaratif nécessite de simuler l'itération séquentielle à travers des CTE récursifs, car les fonctions de fenêtre standard ne peuvent pas exprimer les agrégats en cours qui dépendent des résultats calculés des lignes précédentes d'une manière mutuellement récursive. Ce problème teste la capacité d'un candidat à implémenter une logique algorithmique complexe dans les contraintes du traitement par ensembles.
Le problème.
Étant donné une table d'observations numériques ordonnées (par exemple, les profits/pertes quotidiens), l'objectif est d'identifier le seul bloc contigu de lignes produisant la somme la plus élevée possible. Contrairement à un simple total en cours, le sous-tableau optimal peut commencer et se terminer à n'importe quel point arbitraire, et la décision d'étendre le sous-tableau actuel ou de recommencer à chaque ligne dépend de la somme accumulée du sous-tableau immédiatement précédent—une dépendance qui crée une définition récursive interdisant une agrégation simple.
La solution.
Nous utilisons un CTE récursif qui initialise la première ligne avec sa valeur comme à la fois current_max_ending_here et global_max_so_far. Le membre récursif se joint à la ligne suivante en utilisant une clé d'ordre, calculant le nouveau current_max comme GREATEST(current_value, previous_current_max + current_value) et en mettant à jour global_max comme GREATEST(previous_global_max, new_current_max). Une agrégation finale sélectionne le maximum global_max à travers toutes les itérations. Cette approche s'exécute en O(n) temps par partition tout en restant strictement basée sur des ensembles.
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 ( -- Ancre : initialiser avec la première ligne de chaque 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 -- Étape récursive : propager l'état vers l'avant 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;
Un bureau de trading quantitatif avait besoin d'identifier la fenêtre historique optimale pour une stratégie de momentum—spécifiquement, la séquence contiguë de jours de trading produisant le rendement cumulatif le plus élevé pour chaque classe d'actifs. L'ensemble de données contenait des millions de dossiers quotidiens de P&L partitionnés par symbole d'action, et l'équipe de recherche nécessitait une latence de quelques secondes pour une analyse ad hoc à travers des milliers de titres.
La preuve de concept initiale utilisait une approche de jointure auto-jointe brute qui cross-joignait la table avec elle-même pour générer toutes les dates de début et de fin possibles, puis agrégait les sommes entre elles. Bien que cela ne nécessitât pas de CTE récursif et fût simple à conceptualiser, sa complexité O(n²) entraînait des délais d'expiration de requête après des heures d'exécution, rendant cette méthode non viable pour l'analyse à l'échelle de production en raison de la consommation excessive de CPU et I/O.
Une approche alternative avait utilisé un curseur procédural en Python avec psycopg2 pour itérer sur les lignes tout en maintenant des variables en cours. Cela offrait une logique impérative intuitive et un débogage facile, mais violait le mandat de l'équipe pour le calcul dans la base de données afin de minimiser les frais de transfert de données, et le traitement basé sur des curseurs présentait de mauvaises performances en raison de la latence aller-retour et du manque d'optimisation basée sur des ensembles.
L'implémentation de CTE récursifs simulant l'algorithme de Kadane a été sélectionnée. Cette solution a traité chaque partition en un seul passage linéaire, stockant uniquement deux valeurs scalaires par niveau de récursion et exploitant l'optimisation native du moteur de base de données pour les requêtes récursives. Elle a atteint les temps de réponse souhaités au niveau des millisecondes sur l'ensemble du jeu de données tout en restant purement déclarative.
L'implémentation a réussi à identifier les séquences les plus rentables pour plus de cinq mille titres en moins de 400 ms. L'équipe DBA a ensuite adopté ce modèle pour des analyses similaires de "meilleure fenêtre", y compris le calcul de métriques de risque et la détection de clusters de volatilité.
Comment le CTE récursif gère-t-il les partitions contenant exclusivement des valeurs négatives, et pourquoi la sélection de la première ligne d'ancrage empêche-t-elle le retour erroné de zéro ?
De nombreux candidats initialisent incorrectement current_max et global_max à zéro dans le membre d'ancrage, ce qui entraîne un retour zéro pour toutes les séquences négatives (impliquant à tort qu'un sous-tableau vide est optimal). L'approche correcte initialise les deux agrégats à la valeur réelle de la première ligne de chaque partition. Cela garantit que pour une séquence comme [-5, -2, -8], la requête renvoie correctement -2 plutôt que 0, respectant la contrainte selon laquelle le sous-tableau doit contenir au moins un élément. Ne pas tenir compte de ce cas limite entraîne des erreurs logiques silencieuses lors de l'analyse des périodes de perte uniquement.
Pouvez-vous récupérer les véritables frontières de début et de fin (les lignes spécifiques) du sous-tableau maximum, et pas seulement la valeur de somme, en utilisant strictement ANSI SQL ?
Oui, mais cela nécessite d'étendre le CTE récursif pour suivre les métadonnées. Vous devez faire avancer deux colonnes supplémentaires : current_start_rn (l'indice de départ du sous-tableau candidat actuel) et best_start_rn/best_end_rn (les frontières du maximum global). Dans le membre récursif, si la valeur actuelle seule dépasse la somme étendue, définissez current_start_rn à la row_num actuelle ; sinon, prenez-la de la ligne précédente. Lorsque global_max_so_far est mis à jour, capturez la row_num actuelle comme best_end_rn et current_start_rn comme best_start_rn. Cela démontre la compréhension que les CTE récursifs peuvent maintenir des objets d'état complexes, pas seulement des accumulateurs scalaires, permettant ainsi de reconstruire l'emplacement de la fenêtre optimale.
Pourquoi ce problème ne peut-il pas être résolu à l'aide des fonctions de fenêtre standard telles que SUM() OVER ou MAX() OVER, et quelle limitation spécifique de la norme SQL empêche une approche basée sur des fenêtres ?
Les fonctions de fenêtre standard calculent des agrégats sur des cadres statiquement définis (par exemple, ROWS BETWEEN). Le problème du sous-tableau maximum nécessite un agrégat en cours où la décision d'inclure la ligne actuelle dépend du résultat de l'agrégation pour la ligne précédente—spécifiquement, si cette somme précédente était positive. Cela crée une dépendance mutuelle ou une récursion que les fonctions de fenêtre ne peuvent pas exprimer car elles n'ont pas la capacité de référencer la sortie de la fonction de fenêtre depuis la ligne immédiatement précédente dans le même ensemble de résultats. Les CTE récursifs sont requis car ils permettent à la sortie d'une itération de servir d'entrée pour la suivante, permettant ainsi un calcul d'état ligne par ligne dans le paradigme déclaratif.