Historia de la pregunta.
Algoritmo de Kadane, formulado por Jay Kadane en 1984, resuelve el problema del subarreglo máximo a través de programación dinámica al rastrear dos estados: la suma máxima que termina en la posición actual y el máximo global encontrado. Traducir este patrón imperativo en ANSI SQL requiere simular la iteración secuencial a través de CTEs Recursivas, ya que las funciones de ventana estándar no pueden expresar agregados acumulativos que dependen de los resultados computados de filas anteriores de manera mutuamente recursiva. Este problema pone a prueba la capacidad de un candidato para implementar lógica algorítmica compleja dentro de las limitaciones del procesamiento basado en conjuntos.
El problema.
Dada una tabla de observaciones numéricas ordenadas (por ejemplo, ganancias/pérdidas diarias), el objetivo es identificar el único bloque contiguo de filas que produce la mayor suma posible. A diferencia de un simple total acumulado, el subarreglo óptimo puede comenzar y terminar en cualquier punto arbitrario, y la decisión de extender el subarreglo actual o comenzar de nuevo en cada fila depende de la suma acumulada del subarreglo anterior inmediato, una dependencia que crea una definición recursiva prohibiendo la agregación simple.
La solución.
Utilizamos un CTE Recursivo que siembra la fila inicial con su valor como tanto current_max_ending_here como global_max_so_far. El miembro recursivo se une a la fila siguiente utilizando una clave de ordenación, calculando el nuevo current_max como GREATEST(current_value, previous_current_max + current_value) y actualizando global_max como GREATEST(previous_global_max, new_current_max). Una agregación final selecciona el máximo global_max a través de todas las iteraciones. Este enfoque se ejecuta en O(n) tiempo por partición mientras se mantiene estrictamente basado en conjuntos.
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 ( -- Ancla: inicializa con la primera fila de cada partición SELECT partition_id, rn, value, value AS current_max_ending_here, value AS global_max_so_far FROM numbered WHERE rn = 1 UNION ALL -- Paso recursivo: propagar estado hacia adelante 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 escritorio de trading cuantitativo necesitaba identificar la ventana histórica óptima para una estrategia de momentum, específicamente, la secuencia contigua de días de trading que generaban el mayor retorno acumulado para cada clase de activo. El conjunto de datos contenía millones de registros de P&L diarios particionados por símbolo de acción, y el equipo de investigación requería latencias de sub-segundos para análisis ad-hoc en miles de valores.
La prueba de concepto inicial utilizó un enfoque de auto-unión de fuerza bruta que unió la tabla consigo misma para generar todas las posibles fechas de inicio y fin, y luego agregó sumas entre ellas. Si bien esto no requería un CTE Recursivo y era simple de conceptualizar, su complejidad de O(n²) resultó en tiempos de espera de consulta después de horas de ejecución, haciéndolo inviable para análisis a escala de producción debido al excesivo consumo de CPU y I/O.
Un enfoque alternativo utilizó un cursor procedural en Python con psycopg2 para iterar filas mientras mantenía variables en ejecución. Esto ofreció lógica imperativa intuitiva y fácil depuración, pero violó el mandato del equipo para el cálculo dentro de la base de datos para minimizar la sobrecarga de transferencia de datos, y el procesamiento basado en cursores mostró un rendimiento deficiente debido a la latencia de ida y vuelta y la falta de optimización basada en conjuntos.
La implementación del CTE Recursivo simulando el Algoritmo de Kadane fue seleccionada. Esta solución procesó cada partición en una única pasada lineal, almacenando solo dos valores escalares por nivel de recursión y aprovechando la optimización nativa del motor de base de datos para consultas recursivas. Logró los tiempos de respuesta deseados a nivel de milisegundos en todo el conjunto de datos mientras se mantenía puramente declarativa.
La implementación identificó con éxito las secuencias máximas rentables para más de cinco mil valores en menos de 400 ms. El equipo de DBA adoptó posteriormente este patrón para análisis similares de "mejor ventana", incluidos cálculos de métricas de riesgo y detección de agrupación de volatilidad.
¿Cómo maneja el CTE recursivo las particiones que contienen exclusivamente valores negativos, y por qué la selección de la fila ancla inicial previene el retorno erróneo de cero?
Muchos candidatos inicializan incorrectamente current_max y global_max en cero en el miembro ancla, lo que provoca que el algoritmo devuelva cero para secuencias totalmente negativas (implícitamente errónea sugiriendo que un subarreglo vacío es óptimo). El enfoque correcto inicializa ambos agregados al valor real de la primera fila dentro de cada partición. Esto asegura que para una secuencia como [-5, -2, -8], la consulta devuelva correctamente -2 en lugar de 0, cumpliendo con la restricción de que el subarreglo debe contener al menos un elemento. No tener en cuenta este caso extremo resulta en errores lógicos silenciosos al analizar períodos de solo pérdidas.
¿Puede recuperar los límites de inicio y fin reales (las filas específicas) del subarreglo máximo, no meramente el valor de suma, utilizando estrictamente SQL ANSI?
Sí, pero requiere extender el CTE recursivo para rastrear metadatos. Debe llevar adelante dos columnas adicionales: current_start_rn (el índice de inicio del subarreglo candidato actual) y best_start_rn/best_end_rn (los límites del máximo global). En el miembro recursivo, si el valor actual solo excede la suma extendida, establezca current_start_rn al row_num actual; de lo contrario, herédelo de la fila anterior. Cuando global_max_so_far se actualiza, capture el row_num actual como best_end_rn y current_start_rn como best_start_rn. Esto demuestra comprensión de que CTEs Recursivas pueden mantener objetos de estado complejos, no solo acumuladores escalares, permitiendo reconstruir la ubicación de la ventana óptima.
¿Por qué no se puede resolver este problema utilizando funciones de ventana estándar como SUM() OVER o MAX() OVER, y qué limitación específica del estándar SQL impide un enfoque basado en ventanas?
Las funciones de ventana estándar computan agregados sobre marcos definidos estáticamente (por ejemplo, ROWS BETWEEN). El problema del subarreglo máximo requiere un agregado en ejecución donde la decisión de incluir la fila actual depende del resultado de la agregación para la fila anterior, específicamente si esa suma anterior fue positiva. Esto crea una dependencia mutua o recursión que las funciones de ventana no pueden expresar porque carecen de la capacidad de hacer referencia a la salida de la función de ventana desde la fila inmediatamente anterior en el mismo conjunto de resultados. Se requieren CTEs Recursivas porque permiten que la salida de una iteración sirva como entrada para la siguiente, habilitando efectivamente el cálculo basado en estado fila por fila dentro del paradigma declarativo.