- un mécanisme très puissant et pratique si les mêmes actions « en profondeur » sont effectuées sur les données associées. Mais la récursion incontrôlée est un mal qui peut conduire soit à exécution sans fin processus, ou (ce qui arrive plus souvent) à "manger" toute la mémoire disponible.
Les SGBD à cet égard fonctionnent sur les mêmes principes - "Ils m'ont dit de creuser, alors je creuse". Votre demande peut non seulement ralentir les processus voisins, occupant constamment les ressources du processeur, mais également « supprimer » l'intégralité de la base de données, « manger » toute la mémoire disponible. Par conséquent protection contre la récursion infinie - la responsabilité du développeur lui-même.
Dans PostgreSQL, la possibilité d'utiliser des requêtes récursives via est apparu depuis les temps immémoriaux de la version 8.4, mais vous pouvez encore régulièrement rencontrer des requêtes « sans défense » potentiellement vulnérables. Comment se débarrasser de problèmes de ce genre ?
N'écrivez pas de requêtes récursives
Et écrivez-en des non récursifs. Cordialement, Votre K.O.
En fait, PostgreSQL fournit de nombreuses fonctionnalités que vous pouvez utiliser pour aucun appliquer la récursivité.
Utiliser une approche fondamentalement différente du problème
Parfois, vous pouvez simplement regarder le problème sous un « autre angle ». J'ai donné un exemple d'une telle situation dans l'article — multiplication d'un ensemble de nombres sans utiliser de fonctions d'agrégation personnalisées :
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;Cette demande peut être remplacée par une option d'experts en mathématiques :
WITH src AS (
SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime
)
SELECT
exp(sum(ln(prime)))::integer val
FROM
src;Utilisez generate_series au lieu de boucles
Disons que nous sommes confrontés à la tâche de générer tous les préfixes possibles pour une chaîne '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;
Etes-vous sûr d'avoir besoin d'une récursivité ici ?.. Si vous utilisez LATERAL и generate_series, alors vous n'aurez même pas besoin de CTE :
SELECT
substr(str, 1, ln) str
FROM
(VALUES('abcdefgh')) T(str)
, LATERAL(
SELECT generate_series(length(str), 1, -1) ln
) X;Modifier la structure de la base de données
Par exemple, vous disposez d'un tableau de messages de forum avec les connexions de qui a répondu à qui, ou d'un fil de discussion dans :
CREATE TABLE message(
message_id
uuid
PRIMARY KEY
, reply_to
uuid
REFERENCES message
, body
text
);
CREATE INDEX ON message(reply_to);
Eh bien, une demande typique pour télécharger tous les messages sur un sujet ressemble à ceci :
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;Mais puisque nous avons toujours besoin de l’intégralité du sujet à partir du message racine, alors pourquoi ne pas ajouter son identifiant à chaque entrée automatique?
-- добавим поле с общим идентификатором темы и индекс на него
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();
Maintenant, toute notre requête récursive peut être réduite à ceci :
SELECT
*
FROM
message
WHERE
theme_id = $1;Utiliser des "limiteurs" appliqués
Si nous ne parvenons pas à modifier la structure de la base de données pour une raison quelconque, voyons sur quoi nous pouvons compter pour que même la présence d'une erreur dans les données ne conduise pas à une récursion sans fin.
Compteur de profondeur de récursion
On augmente simplement le compteur de un à chaque pas de récursion jusqu'à atteindre une limite que l'on considère manifestement insuffisante :
WITH RECURSIVE T AS (
SELECT
0 i
...
UNION ALL
SELECT
i + 1
...
WHERE
T.i < 64 -- предел
)
Pro: Lorsque nous essayons de boucler, nous ne ferons toujours pas plus que la limite spécifiée d'itérations « en profondeur ».
contre: Il n'y a aucune garantie que nous ne traiterons pas à nouveau le même enregistrement - par exemple, à une profondeur de 15 et 25, puis tous les +10. Et personne n’a rien promis concernant la « largeur ».
Formellement, une telle récursion ne sera pas infinie, mais si à chaque étape le nombre d'enregistrements augmente de façon exponentielle, nous savons tous bien comment cela se termine...
Gardien du "chemin"
Nous ajoutons alternativement tous les identifiants d'objet que nous avons rencontrés le long du chemin de récursion dans un tableau, qui est un « chemin » unique :
WITH RECURSIVE T AS (
SELECT
ARRAY[id] path
...
UNION ALL
SELECT
path || id
...
WHERE
id <> ALL(T.path) -- не совпадает ни с одним из
)
Pro: S'il y a un cycle dans les données, nous ne traiterons absolument pas le même enregistrement de manière répétée dans le même chemin.
contre: Mais en même temps, nous pouvons littéralement contourner tous les enregistrements sans nous répéter.
Limite de longueur de chemin
Pour éviter la situation de récursion « errant » à une profondeur incompréhensible, on peut combiner les deux méthodes précédentes. Ou, si nous ne voulons pas prendre en charge les champs inutiles, complétons la condition de poursuite de la récursion avec une estimation de la longueur du chemin :
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
)
Choisissez une méthode à votre goût !
Source: habr.com