🥇Antipatrones PostgreSQL: “¡El infinito no es el límite!”, o Un poco sobre recursividad

Recursion - un mecanismo muy poderoso y conveniente si se realizan las mismas acciones "en profundidad" en datos relacionados. Pero la recursividad incontrolada es un mal que puede llevar a ejecución sin fin proceso, o (lo que sucede más a menudo) a "comiendo" toda la memoria disponible.

Los DBMS a este respecto funcionan según los mismos principios: "Me dijeron que cavara, entonces cavo". Su solicitud no sólo puede ralentizar los procesos vecinos, consumiendo constantemente recursos del procesador, sino también "eliminar" toda la base de datos, "consumiendo" toda la memoria disponible. protección contra recursividad infinita - responsabilidad del propio desarrollador.

En PostgreSQL, la capacidad de utilizar consultas recursivas a través de WITH RECURSIVE apareció en tiempos inmemoriales de la versión 8.4, pero todavía es posible encontrar regularmente solicitudes "indefensas" potencialmente vulnerables. ¿Cómo deshacerse de problemas de este tipo?

No escriba consultas recursivas

Y escribe no recursivos. Atentamente, Su K.O.

De hecho, PostgreSQL proporciona una gran cantidad de funciones que puede utilizar para no aplicar recursividad.

Utilice un enfoque fundamentalmente diferente al problema.

A veces puedes simplemente mirar el problema desde el “lado diferente”. Di un ejemplo de tal situación en el artículo. "SQL HowTo: 1000 y una forma de agregación" — multiplicación de un conjunto de números sin utilizar funciones agregadas personalizadas:

WITH RECURSIVE src AS (
  SELECT '{2,3,5,7,11,13,17,19}'::integer[] arr
)
, T(i, val) AS (
  SELECT
    1::bigint
  , 1
UNION ALL
  SELECT
    i + 1
  , val * arr[i]
  FROM
    T
  , src
  WHERE
    i <= array_length(arr, 1)
)
SELECT
  val
FROM
  T
ORDER BY -- отбор финального результата
  i DESC
LIMIT 1;

Esta solicitud se puede sustituir por una opción de expertos en matemáticas:

WITH src AS (
  SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime
)
SELECT
  exp(sum(ln(prime)))::integer val
FROM
  src;

Utilice generate_series en lugar de bucles

Digamos que nos enfrentamos a la tarea de generar todos los prefijos posibles para una cadena. 'abcdefgh':

WITH RECURSIVE T AS (
  SELECT 'abcdefgh' str
UNION ALL
  SELECT
    substr(str, 1, length(str) - 1)
  FROM
    T
  WHERE
    length(str) > 1
)
TABLE T;

¿Estás seguro de que necesitas recursividad aquí?... Si usas LATERAL и generate_series, entonces ni siquiera necesitarás CTE:

SELECT
  substr(str, 1, ln) str
FROM
  (VALUES('abcdefgh')) T(str)
, LATERAL(
    SELECT generate_series(length(str), 1, -1) ln
  ) X;

Cambiar la estructura de la base de datos

Por ejemplo, tiene una tabla de mensajes del foro con conexiones de quién respondió a quién, o un hilo en red social:

CREATE TABLE message(
  message_id
    uuid
      PRIMARY KEY
, reply_to
    uuid
      REFERENCES message
, body
    text
);
CREATE INDEX ON message(reply_to);

Bueno, una solicitud típica para descargar todos los mensajes sobre un tema se parece a esta:

WITH RECURSIVE T AS (
  SELECT
    *
  FROM
    message
  WHERE
    message_id = $1
UNION ALL
  SELECT
    m.*
  FROM
    T
  JOIN
    message m
      ON m.reply_to = T.message_id
)
TABLE T;

Pero como siempre necesitamos el tema completo desde el mensaje raíz, ¿por qué no lo hacemos? agregue su ID a cada entrada ¿automático?

-- добавим поле с общим идентификатором темы и индекс на него
ALTER TABLE message
  ADD COLUMN theme_id uuid;
CREATE INDEX ON message(theme_id);

-- инициализируем идентификатор темы в триггере при вставке
CREATE OR REPLACE FUNCTION ins() RETURNS TRIGGER AS $$
BEGIN
  NEW.theme_id = CASE
    WHEN NEW.reply_to IS NULL THEN NEW.message_id -- берем из стартового события
    ELSE ( -- или из сообщения, на которое отвечаем
      SELECT
        theme_id
      FROM
        message
      WHERE
        message_id = NEW.reply_to
    )
  END;
  RETURN NEW;
END;
$$ LANGUAGE plpgsql;

CREATE TRIGGER ins BEFORE INSERT
  ON message
    FOR EACH ROW
      EXECUTE PROCEDURE ins();

Ahora toda nuestra consulta recursiva se puede reducir a esto:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Utilice "limitadores" aplicados

Si por algún motivo no podemos cambiar la estructura de la base de datos, veamos en qué podemos confiar para que incluso la presencia de un error en los datos no conduzca a una recursión interminable.

Contador de profundidad de recursividad

Simplemente aumentamos el contador en uno en cada paso de recursividad hasta llegar a un límite que consideramos obviamente inadecuado:

WITH RECURSIVE T AS (
  SELECT
    0 i
  ...
UNION ALL
  SELECT
    i + 1
  ...
  WHERE
    T.i < 64 -- предел
)

Pro: Cuando intentamos realizar un bucle, no haremos más que el límite especificado de iteraciones "en profundidad".
contras: No hay garantía de que no volveremos a procesar el mismo registro, por ejemplo, a una profundidad de 15 y 25, y luego cada +10. Y nadie prometió nada sobre “amplitud”.

Formalmente, tal recursividad no será infinita, pero si en cada paso el número de registros aumenta exponencialmente, todos sabemos bien cómo termina...

ver “El problema de los granos en un tablero de ajedrez”

Guardián del "camino"

Alternativamente agregamos todos los identificadores de objetos que encontramos a lo largo de la ruta de recursividad en una matriz, que es una "ruta" única:

WITH RECURSIVE T AS (
  SELECT
    ARRAY[id] path
  ...
UNION ALL
  SELECT
    path || id
  ...
  WHERE
    id <> ALL(T.path) -- не совпадает ни с одним из
)

Pro: Si hay un ciclo en los datos, no procesaremos el mismo registro repetidamente dentro de la misma ruta.
contras: Pero al mismo tiempo, podemos literalmente saltarnos todos los registros sin repetirnos.

ver "Problema del movimiento del caballo"

Límite de longitud de ruta

Para evitar la situación de recursividad “vagando” a una profundidad incomprensible, podemos combinar los dos métodos anteriores. O, si no queremos admitir campos innecesarios, complemente la condición para continuar la recursividad con una estimación de la longitud de la ruta:

WITH RECURSIVE T AS (
  SELECT
    ARRAY[id] path
  ...
UNION ALL
  SELECT
    path || id
  ...
  WHERE
    id <> ALL(T.path) AND
    array_length(T.path, 1) < 10
)

¡Elige un método a tu gusto!

Fuente: habr.com

Antipatrones de PostgreSQL: “¡El infinito no es el límite!”, o Un poco sobre recursividad