Profundidad descendiente recursiva de PostgreSQL

Necesito calcular la profundidad de un descendiente de su antepasado. Cuando un registro tiene object_id = parent_id = ancestor_id, se considera un nodo raíz (el antepasado). He estado tratando de WITH RECURSIVEejecutar una consulta con PostgreSQL 9.4 .

No controlo los datos o las columnas. El esquema de datos y tablas proviene de una fuente externa. La mesa está creciendo continuamente . En este momento por unos 30k registros por día. Puede faltar cualquier nodo en el árbol y se extraerá de una fuente externa en algún momento. Por lo general, se extraen en created_at DESCorden, pero los datos se extraen con trabajos en segundo plano asincrónicos.

Inicialmente teníamos una solución de código para este problema, pero ahora con más de 5 millones de filas, tarda casi 30 minutos en completarse.

Ejemplo de definición de tabla y datos de prueba:

CREATE TABLE objects (
  id          serial NOT NULL PRIMARY KEY,
  customer_id integer NOT NULL,
  object_id   integer NOT NULL,
  parent_id   integer,
  ancestor_id integer,
  generation  integer NOT NULL DEFAULT 0
);

INSERT INTO objects(id, customer_id , object_id, parent_id, ancestor_id, generation)
VALUES (2, 1, 2, 1, 1, -1), --no parent yet
       (3, 2, 3, 3, 3, -1), --root node
       (4, 2, 4, 3, 3, -1), --depth 1
       (5, 2, 5, 4, 3, -1), --depth 2
       (6, 2, 6, 5, 3, -1), --depth 3
       (7, 1, 7, 7, 7, -1), --root node
       (8, 1, 8, 7, 7, -1), --depth 1
       (9, 1, 9, 8, 7, -1); --depth 2

Tenga en cuenta que object_idno es único, pero la combinación (customer_id, object_id)es única.
Ejecutando una consulta como esta:

WITH RECURSIVE descendants(id, customer_id, object_id, parent_id, ancestor_id, depth) AS (
  SELECT id, customer_id, object_id, parent_id, ancestor_id, 0
  FROM objects
  WHERE object_id = parent_id

  UNION

  SELECT o.id, o.customer_id, o.object_id, o.parent_id, o.ancestor_id, d.depth + 1
  FROM objects o
  INNER JOIN descendants d ON d.parent_id = o.object_id
  WHERE
    d.id <> o.id
  AND
    d.customer_id = o.customer_id
) SELECT * FROM descendants d;

Me gustaría que la generationcolumna se establezca como la profundidad que se calculó. Cuando se agrega un nuevo registro, la columna de generación se establece como -1. Hay algunos casos en los que es parent_idposible que todavía no se haya retirado. Si parent_idno existe, debería dejar la columna de generación establecida en -1.

Los datos finales deberían verse así:

id | customer_id | object_id | parent_id | ancestor_id | generation
2    1             2           1           1            -1
3    2             3           3           3             0
4    2             4           3           3             1
5    2             5           4           3             2
6    2             6           5           3             3
7    1             7           7           7             0
8    1             8           7           7             1
9    1             9           8           7             2

El resultado de la consulta debe ser actualizar la columna de generación a la profundidad correcta.

Comencé a trabajar a partir de las respuestas a esta pregunta relacionada sobre SO .

La consulta que tienes es básicamente correcta. El único error está en la segunda parte (recursiva) del CTE donde tiene:

INNER JOIN descendants d ON d.parent_id = o.object_id

Debería ser de otra manera:

INNER JOIN descendants d ON d.object_id = o.parent_id 

Desea unir los objetos con sus padres (que ya se han encontrado).

Por lo tanto, la consulta que calcula la profundidad puede escribirse (nada más cambió, solo el formato):

-- calculate generation / depth, no updates
WITH RECURSIVE descendants
  (id, customer_id, object_id, parent_id, ancestor_id, depth) AS
 AS ( SELECT id, customer_id, object_id, parent_id, ancestor_id, 0
      FROM objects
      WHERE object_id = parent_id

      UNION ALL

      SELECT o.id, o.customer_id, o.object_id, o.parent_id, o.ancestor_id, d.depth + 1
      FROM objects o
      INNER JOIN descendants d ON  d.customer_id = o.customer_id
                               AND d.object_id = o.parent_id  
      WHERE d.id <> o.id
    ) 
SELECT * 
FROM descendants d
ORDER BY id ;

Para la actualización, simplemente reemplace el último SELECT, con el UPDATE, uniendo el resultado del cte, de vuelta a la tabla:

-- update nodes
WITH RECURSIVE descendants
    -- nothing changes here except
    -- ancestor_id and parent_id 
    -- which can be omitted form the select lists
    ) 
UPDATE objects o 
SET generation = d.depth 
FROM descendants d
WHERE o.id = d.id 
  AND o.generation = -1 ;          -- skip unnecessary updates

Probado en SQLfiddle

Comentarios adicionales:

• el ancestor_idparent_idNo se necesita y el para estar en la lista de selección (el antepasado es obvio, el padre es un poco difícil de entender por qué), por lo que puede mantenerlos en la SELECTconsulta si lo desea, pero puede eliminarlos de forma segura UPDATE.
• El (customer_id, object_id)parece ser un candidato para una UNIQUErestricción. Si sus datos cumplen con esto, agregue dicha restricción. Las uniones realizadas en el CTE recursivo no tendrían sentido si no fuera único (de lo contrario, un nodo podría tener 2 padres).
• si agrega esa restricción, (customer_id, parent_id)sería un candidato para una FOREIGN KEYrestricción que REFERENCESel (único)(customer_id, object_id) . Lo más probable es que no embargo, lo desee agregar esa restricción FK, ya que según su descripción, está agregando nuevas filas y algunas filas pueden hacer referencia a otras que aún no se han agregado.
• Ciertamente, hay problemas con la eficiencia de la consulta, si se va a realizar en una tabla grande. No en la primera ejecución, ya que casi toda la tabla se actualizará de todos modos. Pero la segunda vez, querrá que solo se consideren las nuevas filas (y las que no fueron tocadas por la primera ejecución) para su actualización. El CTE tal como está tendrá que generar un gran resultado.
  En AND o.generation = -1la actualización final se asegurará de que las filas que se actualizaron en la primera ejecución no se actualizarán nuevamente, pero el CTE sigue siendo una parte costosa.

El siguiente es un intento de abordar estos problemas: mejorar el CTE para considerar la menor cantidad de filas posible y usar en (customer_id, obejct_id)lugar de (id)identificar filas (por lo que idse elimina por completo de la consulta. Se puede usar como la primera actualización o una posterior:

WITH RECURSIVE descendants 
  (customer_id, object_id, depth) 
 AS ( SELECT customer_id, object_id, 0
      FROM objects
      WHERE object_id = parent_id
        AND generation = -1

      UNION ALL

      SELECT o.customer_id, o.object_id, p.generation + 1
      FROM objects o
        JOIN objects p ON  p.customer_id = o.customer_id
                       AND p.object_id = o.parent_id
                       AND p.generation > -1
      WHERE o.generation = -1

      UNION ALL

      SELECT o.customer_id, o.object_id, d.depth + 1
      FROM objects o
      INNER JOIN descendants d ON  o.customer_id = d.customer_id
                               AND o.parent_id = d.object_id
      WHERE o.parent_id <> o.object_id
        AND o.generation = -1
    )
UPDATE objects o 
SET generation = d.depth 
FROM descendants d
WHERE o.customer_id = d.customer_id
  AND o.object_id = d.object_id
  AND o.generation = -1        -- this is not really needed

Observe cómo el CTE tiene 3 partes. Los dos primeros son las partes estables. La primera parte encuentra los nodos raíz que no se han actualizado antes y todavía generation=-1lo tienen, por lo que deben ser nodos recién agregados. La segunda parte encuentra elementos secundarios (con generation=-1) de nodos principales que se han actualizado previamente.
La tercera parte, recursiva, encuentra a todos los descendientes de las dos primeras partes, como antes.

Probado en SQLfiddle-2

@ypercube ya ofrece una amplia explicación, por lo que voy a ir al grano lo que tengo que agregar.

Si el parent_id no existe, debería dejar la columna de generación establecida en -1.

Supongo que se supone que esto se aplica de forma recursiva, es decir, el resto del árbol siempre tienegeneration = -1 después de cualquier nodo faltante.

Si falta algún nodo en el árbol (todavía), necesitamos encontrar filas con generation = -1eso ...
... son nodos raíz
... o tener un padre con generation > -1.
Y atraviesa el árbol desde allí. Los nodos secundarios de esta selección también deben tener generation = -1.

Tome el generationdel padre incrementado en uno o retroceda a 0 para los nodos raíz:

WITH RECURSIVE tree AS (
   SELECT c.customer_id, c.object_id, COALESCE(p.generation + 1, 0) AS depth
   FROM   objects      c
   LEFT   JOIN objects p ON c.customer_id = p.customer_id
                        AND c.parent_id   = p.object_id
                        AND p.generation > -1
   WHERE  c.generation = -1
   AND   (c.parent_id = c.object_id OR p.generation > -1)
       -- root node ... or parent with generation > -1

   UNION ALL
   SELECT customer_id, c.object_id, p.depth + 1
   FROM   objects c
   JOIN   tree    p USING (customer_id)
   WHERE  c.parent_id  = p.object_id
   AND    c.parent_id <> c.object_id  -- exclude root nodes
   AND    c.generation = -1           -- logically redundant, but see below!
   )
UPDATE objects o 
SET    generation = t.depth
FROM   tree t
WHERE  o.customer_id = t.customer_id
AND    o.object_id   = t.object_id;

La parte no recursiva es única de SELECTesta manera, pero lógicamente equivalente a las dos uniones de @ ypercubeSELECT . No estoy seguro de cuál es más rápido, tendrás que probar.
El punto mucho más importante para el rendimiento es:

¡Índice!

Si agrega repetidamente filas a una tabla grande de esta manera, agregue un índice parcial :

CREATE INDEX objects_your_name_idx ON objects (customer_id, parent_id, object_id)
WHERE  generation = -1;

Esto logrará más rendimiento que todas las otras mejoras discutidas hasta ahora, para pequeñas adiciones repetidas a una gran mesa.

Agregué la condición de índice a la parte recursiva del CTE (aunque lógicamente redundante) para ayudar al planificador de consultas a comprender que el índice parcial es aplicable.

Además, probablemente también debería tener la UNIQUErestricción sobre (object_id, customer_id)ese @ypercube ya mencionado. O, si no puede imponer unicidad por alguna razón (¿por qué?) Agregue un índice simple en su lugar. El orden de las columnas de índice es importante, por cierto:

• ¿Un índice compuesto también es bueno para consultas en el primer campo?