🥇Antipatróns PostgreSQL: "O infinito non é o límite!", ou Un pouco sobre a recursión

Recursión - un mecanismo moi poderoso e cómodo se se realizan as mesmas accións "en profundidade" sobre datos relacionados. Pero a recursión incontrolada é un mal que pode levar a calquera dos dous execución interminable proceso, ou (o que ocorre con máis frecuencia) a "comer" toda a memoria dispoñible.

DBMS neste sentido traballa nos mesmos principios - "Dixéronme que cave, entón eu cavo". A túa solicitude non só pode retardar os procesos veciños, ocupando constantemente os recursos do procesador, senón tamén "soltar" toda a base de datos, "comer" toda a memoria dispoñible. Polo tanto protección contra recursión infinita - a responsabilidade do propio desenvolvedor.

En PostgreSQL, a capacidade de usar consultas recursivas mediante WITH RECURSIVE apareceu nos tempos inmemoriais da versión 8.4, pero aínda podes atopar con regularidade solicitudes "sen defensa" potencialmente vulnerables. Como librarse de problemas deste tipo?

Non escriba consultas recursivas

E escribe outras non recursivas. Atentamente, o seu K.O.

De feito, PostgreSQL ofrece unha gran cantidade de funcionalidades que pode usar non aplicar recursividade.

Utiliza un enfoque fundamentalmente diferente do problema

Ás veces podes mirar o problema desde o "lado diferente". Puxen un exemplo de tal situación no artigo "SQL HowTo: 1000 e unha forma de agregación" — multiplicación dun conxunto de números sen utilizar funcións de agregación 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 solicitude pódese substituír por unha 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;

Use generate_series en lugar de bucles

Digamos que estamos ante a tarefa de xerar todos os prefixos posibles para unha cadea '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 recursión aquí?.. Se usas LATERAL и generate_series, entón nin sequera 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 a estrutura da base de datos

Por exemplo, tes unha táboa de mensaxes de foro con conexións de quen respondeu a quen ou un fío de conversa rede social:

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

Ben, unha solicitude típica para descargar todas as mensaxes sobre un tema é algo así:

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 sempre necesitamos todo o tema desde a mensaxe raíz, entón por que non engade o seu 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();

Agora toda a nosa consulta recursiva pódese reducir só a isto:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Usa "limitadores" aplicados

Se por algún motivo non somos capaces de cambiar a estrutura da base de datos, vexamos en que podemos confiar para que mesmo a presenza dun erro nos datos non leve a recursividade infinita.

Contador de profundidade de recursión

Simplemente aumentamos o contador en un en cada paso de recursión ata chegar 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: Cando tentamos realizar un bucle, aínda non faremos máis que o límite especificado de iteracións "en profundidade".
contra: Non hai garantía de que non volveremos procesar o mesmo rexistro, por exemplo, a unha profundidade de 15 e 25, e despois cada +10. E ninguén prometeu nada sobre a "amplitude".

Formalmente, tal recursividade non será infinita, pero se a cada paso o número de rexistros aumenta exponencialmente, todos sabemos ben como remata...

ver "O problema dos grans nun taboleiro de xadrez"

Gardián do "camiño"

Engadimos alternativamente todos os identificadores de obxectos que atopamos ao longo do camiño de recursión nunha matriz, que é un "camiño" único para ela:

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

Pro: Se hai un ciclo nos datos, absolutamente non procesaremos o mesmo rexistro repetidamente no mesmo camiño.
contra: Pero ao mesmo tempo, podemos literalmente ignorar todos os rexistros sen repetirnos.

ver "Problema do movemento do cabaleiro"

Límite de lonxitude do camiño

Para evitar a situación de recursividade "vagando" a unha profundidade incomprensible, podemos combinar os dous métodos anteriores. Ou, se non queremos admitir campos innecesarios, complemente a condición para continuar coa recursividade cunha estimación da lonxitude do camiño:

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
)

Escolle un método ao teu gusto!

Fonte: www.habr.com

Antipatróns de PostgreSQL: "O infinito non é o límite!", ou Un pouco sobre a recursión