- een zeer krachtig en handig mechanisme als dezelfde “diepgaande” acties worden uitgevoerd op gerelateerde gegevens. Maar ongecontroleerde recursie is een kwaad dat tot beide kan leiden eindeloze uitvoering proces, of (wat vaker gebeurt) naar "eet" al het beschikbare geheugen.
DBMS werken in dit opzicht volgens dezelfde principes - "Ze zeiden dat ik moest graven, dus ik graaf". Uw verzoek kan niet alleen aangrenzende processen vertragen, waarbij voortdurend processorbronnen in beslag worden genomen, maar ook de hele database "laten vallen", waardoor al het beschikbare geheugen wordt "opgegeten". Daarom bescherming tegen oneindige recursie - de verantwoordelijkheid van de ontwikkelaar zelf.
In PostgreSQL is de mogelijkheid om recursieve zoekopdrachten te gebruiken via verscheen al in de onheuglijke tijd van versie 8.4, maar u kunt nog steeds regelmatig potentieel kwetsbare “weerloze” vragen tegenkomen. Hoe kunt u zich van dit soort problemen ontdoen?
Schrijf geen recursieve query's
En schrijf niet-recursieve. Met vriendelijke groet, Uw K.O.
PostgreSQL biedt zelfs behoorlijk wat functionaliteit waar u gebruik van kunt maken geen recursie toepassen.
Gebruik een fundamenteel andere benadering van het probleem
Soms kun je het probleem gewoon van de ‘andere kant’ bekijken. Ik gaf een voorbeeld van een dergelijke situatie in het artikel — vermenigvuldiging van een reeks getallen zonder gebruik te maken van aangepaste aggregatiefuncties:
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;Dit verzoek kan worden vervangen door een optie van wiskunde-experts:
WITH src AS (
SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime
)
SELECT
exp(sum(ln(prime)))::integer val
FROM
src;Gebruik genereren_series in plaats van lussen
Laten we zeggen dat we voor de taak staan om alle mogelijke voorvoegsels voor een string te genereren '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;
Weet je zeker dat je hier recursie nodig hebt?.. Als je gebruikt LATERAL и generate_series, dan heb je niet eens CTE nodig:
SELECT
substr(str, 1, ln) str
FROM
(VALUES('abcdefgh')) T(str)
, LATERAL(
SELECT generate_series(length(str), 1, -1) ln
) X;Wijzig de databasestructuur
U hebt bijvoorbeeld een tabel met forumberichten met verbindingen van wie op wie heeft gereageerd, of een thread erin :
CREATE TABLE message(
message_id
uuid
PRIMARY KEY
, reply_to
uuid
REFERENCES message
, body
text
);
CREATE INDEX ON message(reply_to);
Een typisch verzoek om alle berichten over één onderwerp te downloaden ziet er ongeveer zo uit:
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;Maar omdat we altijd het hele onderwerp uit de kernboodschap nodig hebben, waarom doen we dat dan niet? voeg de ID toe aan elk item automatisch?
-- добавим поле с общим идентификатором темы и индекс на него
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();
Nu kan onze hele recursieve vraag worden teruggebracht tot dit:
SELECT
*
FROM
message
WHERE
theme_id = $1;Gebruik toegepaste "begrenzers"
Als we om de een of andere reden de structuur van de database niet kunnen veranderen, laten we dan eens kijken waar we op kunnen vertrouwen, zodat zelfs de aanwezigheid van een fout in de gegevens niet tot eindeloze recursie leidt.
Recursie diepteteller
We verhogen eenvoudigweg de teller met één bij elke recursiestap totdat we een limiet bereiken die we duidelijk ontoereikend vinden:
WITH RECURSIVE T AS (
SELECT
0 i
...
UNION ALL
SELECT
i + 1
...
WHERE
T.i < 64 -- предел
)
Pro: Wanneer we proberen een lus te maken, zullen we nog steeds niet meer doen dan de gespecificeerde limiet van iteraties “in de diepte”.
nadelen: Er is geen garantie dat we dezelfde record niet opnieuw zullen verwerken - bijvoorbeeld op een diepte van 15 en 25, en vervolgens elke +10. En niemand beloofde iets over “breedte”.
Formeel zal een dergelijke recursie niet oneindig zijn, maar als bij elke stap het aantal records exponentieel toeneemt, weten we allemaal goed hoe het eindigt...
Bewaker van het "pad"
We voegen afwisselend alle object-ID's toe die we tegenkwamen langs het recursiepad in een array, wat een uniek "pad" is:
WITH RECURSIVE T AS (
SELECT
ARRAY[id] path
...
UNION ALL
SELECT
path || id
...
WHERE
id <> ALL(T.path) -- не совпадает ни с одним из
)
Pro: Als er een cyclus in de gegevens zit, zullen we absoluut niet hetzelfde record herhaaldelijk binnen hetzelfde pad verwerken.
nadelen: Maar tegelijkertijd kunnen we letterlijk alle records omzeilen zonder onszelf te herhalen.
Limiet voor padlengte
Om de situatie van recursie op een onbegrijpelijke diepte te vermijden, kunnen we de twee voorgaande methoden combineren. Of, als we geen onnodige velden willen ondersteunen, vul dan de voorwaarde voor het voortzetten van de recursie aan met een schatting van de padlengte:
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
)
Kies een methode naar jouw smaak!
Bron: www.habr.com