CTEs recursivas avanzadas

Las jerarquías y grafos son habituales en cualquier aplicación: organigramas, categorías de productos, dependencias entre tareas, listas de materiales o redes sociales. SQL tradicional no las maneja bien, pero las CTE recursivas del estándar SQL:1999 permiten resolverlas en una sola consulta. Esta lección va más allá de la jerarquía simple y aborda los patrones que aparecen en producción.

Anatomía de una CTE recursiva

Toda CTE recursiva tiene dos partes unidas por UNION ALL:

• Ancla (anchor): la consulta inicial, que devuelve el primer conjunto de filas.
• Recursiva (recursive term): consulta que se ejecuta sobre el resultado anterior repetidamente hasta que no devuelve filas.

WITH RECURSIVE numeros AS (
    SELECT 1 AS n                  -- ancla
    UNION ALL
    SELECT n + 1 FROM numeros      -- recursiva
    WHERE n < 10
)
SELECT * FROM numeros;

PostgreSQL ejecuta la ancla, luego repite la parte recursiva tomando como entrada el resultado de la iteración previa, hasta que la recursión devuelve cero filas.

El UNION ALL (no UNION) es importante: con UNION se eliminan duplicados, lo que cambia la semántica y degrada el rendimiento.

Árbol jerárquico con ruta ordenable

El caso más común es un árbol de categorías o un organigrama. Para que el resultado se pueda ordenar de manera natural ("padre antes que hijos, hermanos en orden"), se acumula la ruta como array.

CREATE TABLE categorias (
    id INT PRIMARY KEY,
    nombre TEXT NOT NULL,
    parent_id INT REFERENCES categorias(id),
    sort_order INT NOT NULL DEFAULT 0
);

WITH RECURSIVE arbol AS (
    SELECT
        id,
        nombre,
        parent_id,
        0 AS profundidad,
        ARRAY[sort_order, id] AS ruta_orden,
        ARRAY[nombre] AS ruta_nombres
    FROM categorias
    WHERE parent_id IS NULL
    UNION ALL
    SELECT
        c.id,
        c.nombre,
        c.parent_id,
        a.profundidad + 1,
        a.ruta_orden || c.sort_order || c.id,
        a.ruta_nombres || c.nombre
    FROM categorias c
    INNER JOIN arbol a ON c.parent_id = a.id
)
SELECT
    REPEAT('  ', profundidad) || nombre AS categoria_indentada,
    array_to_string(ruta_nombres, ' / ') AS ruta_completa,
    profundidad
FROM arbol
ORDER BY ruta_orden;

El array ruta_orden contiene los sort_order e id de cada nivel. Al ordenar por ese array, PostgreSQL hace una comparación lexicográfica que respeta la jerarquía. Una categoría aparece justo después de su padre y antes de sus hermanos posteriores.

Detección de ciclos en grafos

A diferencia de un árbol, un grafo puede tener ciclos que provoquen recursión infinita. PostgreSQL 14 introdujo la cláusula CYCLE que detecta y rompe ciclos automáticamente:

WITH RECURSIVE rutas AS (
    SELECT origen, destino, ARRAY[origen, destino] AS path
    FROM aristas
    WHERE origen = 'A'
    UNION ALL
    SELECT a.origen, a.destino, r.path || a.destino
    FROM aristas a
    INNER JOIN rutas r ON r.destino = a.origen
)
CYCLE destino SET es_ciclo USING ciclo_path
SELECT * FROM rutas WHERE NOT es_ciclo;

La cláusula CYCLE columna SET marca USING path indica:

• La columna sobre la que detectar repetición.
• Una columna booleana marca que indica si la fila es parte de un ciclo.
• Una columna path que guarda la ruta completa.

Si tu cluster ejecuta versiones anteriores a PostgreSQL 14, la alternativa es mantener el array manualmente:

WITH RECURSIVE rutas AS (
    SELECT origen, destino, ARRAY[origen, destino] AS visitados
    FROM aristas
    WHERE origen = 'A'
    UNION ALL
    SELECT a.origen, a.destino, r.visitados || a.destino
    FROM aristas a
    INNER JOIN rutas r ON r.destino = a.origen
    WHERE NOT (a.destino = ANY(r.visitados))
)
SELECT * FROM rutas;

La condición NOT (a.destino = ANY(r.visitados)) corta la recursión antes de visitar un nodo que ya está en la ruta. Es la defensa principal contra recursión infinita.

Bill of Materials con cantidades acumuladas

Un Bill of Materials (BOM) describe los componentes de un producto. Cada producto puede estar formado por subproductos en cantidades específicas, y a su vez cada subproducto tiene su propia composición. Calcular las cantidades reales de materia prima necesarias para fabricar N unidades de un producto requiere multiplicar las cantidades a través de los niveles.

CREATE TABLE componentes (
    producto_id INT,
    componente_id INT,
    cantidad NUMERIC(10,3) NOT NULL,
    PRIMARY KEY (producto_id, componente_id)
);

WITH RECURSIVE explosion AS (
    SELECT
        producto_id,
        componente_id,
        cantidad AS cantidad_acumulada,
        1 AS nivel
    FROM componentes
    WHERE producto_id = 1001
    UNION ALL
    SELECT
        e.producto_id,
        c.componente_id,
        e.cantidad_acumulada * c.cantidad AS cantidad_acumulada,
        e.nivel + 1
    FROM componentes c
    INNER JOIN explosion e ON c.producto_id = e.componente_id
    WHERE e.nivel < 10
)
SELECT
    componente_id,
    SUM(cantidad_acumulada) AS cantidad_total
FROM explosion
WHERE componente_id NOT IN (SELECT producto_id FROM componentes)
GROUP BY componente_id
ORDER BY cantidad_total DESC;

La consulta multiplica las cantidades en cada nivel y suma las apariciones del mismo material en distintas ramas. El filtro componente_id NOT IN (SELECT producto_id FROM componentes) restringe el resultado a las hojas del árbol, es decir, materias primas que no se descomponen más.

Limitar profundidad como protección

Aun con detección de ciclos, una recursión sobre datos sucios puede crecer mucho. La buena práctica defensiva es limitar la profundidad:

WITH RECURSIVE descendientes AS (
    SELECT id, parent_id, 0 AS nivel
    FROM categorias
    WHERE id = 1
    UNION ALL
    SELECT c.id, c.parent_id, d.nivel + 1
    FROM categorias c
    INNER JOIN descendientes d ON c.parent_id = d.id
    WHERE d.nivel < 50
)
SELECT * FROM descendientes;

Una jerarquía sana no debería pasar de 10-15 niveles. Si tu CTE encuentra más, hay datos corruptos. El límite debe ser suficiente para casos legítimos y bajo enough para detenerse rápido si algo va mal.

Búsqueda en anchura vs profundidad

PostgreSQL 14 también incorporó la cláusula SEARCH para controlar el orden de exploración:

WITH RECURSIVE arbol AS (
    SELECT id, parent_id, nombre
    FROM categorias
    WHERE parent_id IS NULL
    UNION ALL
    SELECT c.id, c.parent_id, c.nombre
    FROM categorias c
    INNER JOIN arbol a ON c.parent_id = a.id
)
SEARCH BREADTH FIRST BY id SET orden_visita
SELECT * FROM arbol ORDER BY orden_visita;

SEARCH DEPTH FIRST BY columna SET marca produce el orden equivalente a la búsqueda en profundidad. La elección depende del problema: para mostrar un árbol indentado prefieres profundidad; para encontrar el camino más corto en un grafo prefieres anchura.

Rendimiento y materialización

PostgreSQL materializa las CTEs recursivas en memoria. Para grafos con millones de nodos esto se nota. Algunas técnicas:

• Indexar las claves usadas en el JOIN recursivo: en el ejemplo de aristas, un índice sobre (origen) reduce drásticamente el tiempo.
• Filtrar pronto: cuanto más restrinjas la ancla, menos iteraciones.
• Limitar la profundidad explícitamente.
• Materializar el resultado en una tabla cacheada cuando la jerarquía cambie poco.

flowchart TB
    A[ANCLA: nodos raiz] --> B[Iteracion 1: hijos directos]
    B --> C[Iteracion 2: nietos]
    C --> D[Iteracion 3...]
    D --> E{Sin nuevas filas?}
    E -->|No| D
    E -->|Si| F[Resultado consolidado]

Las CTE recursivas son la herramienta SQL para problemas de grafos y árboles. Bien diseñadas con detección de ciclos, ordenación por ruta y límites de profundidad, sustituyen tanto a soluciones procedurales como a librerías externas en lenguajes de aplicación.