Antypatterny w PostgreSQL: „Nieskończoność to nie limit!”, czyli trochę o rekurencji

Rekurencja to bardzo potężny i wygodny mechanizm, jeśli na powiązanych danych wykonywane są te same operacje „wgłąb”. Jednak niekontrolowana rekurencja to zło, które może prowadzić do nieskończonego wykonania procesu, lub (co zdarza się częściej) do „wyczerpania” całej dostępnej pamięci.

Bazy danych w tym aspekcie działają na tych samych zasadach — "powiedzieli kopać, to kopię". Twoje zapytanie może nie tylko spowolnić sąsiednie procesy, ciągle zajmując zasoby CPU, ale także „zrzucić” całą bazę danych, „zjadając” całą dostępną pamięć. Dlatego ochrona przed nieskończoną rekurencją to obowiązek samego programisty.

W PostgreSQL możliwość korzystania z zapytań rekurencyjnych przez WITH RECURSIVE pojawiła się już w zamierzchłych czasach wersji 8.4, ale do dziś można regularnie spotykać potencjalnie wrażliwe „bezbronne” zapytania. Jak pozbyć się problemów tego typu?

Nie pisać zapytań rekurencyjnych

A pisać nierkurencyjne. Z poważaniem, Twój K.O.

W rzeczywistości PostgreSQL oferuje wystarczającą ilość funkcjonalności, z której można skorzystać, aby nie zastosować rekurencję.

Użyć zasadniczo innego podejścia do zadania

Czasami wystarczy spojrzeć na problem „z innej strony”. Przykład takiej sytuacji podawałem w artykule „SQL HowTo: 1000 i jeden sposób agregacji” — mnożenie zbioru liczb bez użycia własnych funkcji agregujących:

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 -- wybór ostatecznego wyniku
  i DESC
LIMIT 1;

To zapytanie można zastąpić wersją znawców matematyki:

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

Użyć generate_series zamiast pętli

Załóżmy, że mamy do rozwiązania problem, aby wygenerować wszystkie możliwe prefiksy dla napisu '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;

Czy naprawdę potrzebna tu rekurencja?.. Jeśli użyjemy LATERAL i generate_series, to nawet CTE nie będą potrzebne:

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

Zmienić strukturę bazy danych

Na przykład macie tabelę wiadomości forum z relacjami kto komu odpowiedział lub wątek w sieci społecznościowej:

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

Typowy zapytanie o wczytanie wszystkich wiadomości dotyczących jednego tematu wygląda mniej więcej tak:

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;

Ponieważ zawsze potrzebujemy całego wątku od wiadomości głównej, czemu by nie dodać jego identyfikator do każdego wpisu automatycznie?

-- dodajemy pole z ogólnym identyfikatorem tematu i indeks na to
ALTER TABLE message
  ADD COLUMN theme_id uuid;
CREATE INDEX ON message(theme_id);

-- inicjujemy identyfikator tematu w wyzwalaczu podczas wstawiania
CREATE OR REPLACE FUNCTION ins() RETURNS TRIGGER AS $$
BEGIN
  NEW.theme_id = CASE
    WHEN NEW.reply_to IS NULL THEN NEW.message_id -- bierzemy z pierwszego zdarzenia
    ELSE ( -- lub z wiadomości, na którą odpowiadamy
      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();

Teraz nasze całe zapytanie rekurencyjne można zredukować do takiego:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Użyj aplikacyjnych „ograniczeń”

Jeśli z jakiegoś powodu nie jesteśmy w stanie zmienić struktury bazy, przyjrzyjmy się, na czym możemy oprzeć się, aby nawet obecność błędu w danych nie prowadziła do nieskończonego wykonania rekursji.

Licznik „głębokości” rekursji

Po prostu zwiększamy licznik o jeden na każdym kroku rekursji aż do osiągnięcia limitu, który uznajemy za z góry nieadekwatny:

WITH RECURSIVE T AS (
  SELECT
    0 i
  ...
UNION ALL
  SELECT
    i + 1
  ...
  WHERE
    T.i < 64 -- limit
)

Pro: Podczas próby cykliczności mimo wszystko nie wykonamy więcej niż określony limit iteracji „w głąb”.
Contra: Nie ma gwarancji, że nie przetworzymy tej samej rekordy powtórnie — na przykład na głębokości 15 i 25, a potem co +10. Nikt także nie obiecywał nic o „w szerz”.

Formalnie taka rekursja nie będzie nieskończona, ale jeśli przy każdym kroku liczba rekordów wzrasta eksponencjalnie, wszyscy dobrze wiemy, czym to się kończy…

zob. „Problem ziaren na szachownicy”

Stróż „ścieżki”

Kolejno zapisujemy wszystkie identyfikatory obiektów, które napotkaliśmy na drodze rekursji, w tablicy, która jest unikalną „ścieżką” do niego:

Z REKURSJĄ T JAKO (
  WYBIERZ
    TABLICĘ[id] ścieżka
  ...
UNIA WSZYSTKIE
  WYBIERZ
    ścieżka || id
  ...
  GDZIE
    id  WSZYSTKIE(T.ścieżka) -- nie zgadza się z żadnym z
)

Pro: W przypadku wystąpienia cyklu w danych na pewno nie będziemy przetwarzać tej samej rekordu w ramach tej samej ścieżki.
Contra: Jednak możemy dosłownie przejść przez wszystkie rekordy, nie powtarzając się.

zob. «Problem ruchu skoczka»

Ograniczenie długości ścieżki

Aby uniknąć sytuacji „błądzenia” rekurencji na niejasnej głębokości, możemy połączyć dwie poprzednie metody. Lub, jeśli nie chcemy przechowywać zbędnych pól, dodać warunek kontynuacji rekurencji oceniając długość ścieżki:

Z REKURSJĄ T JAKO (
  WYBIERZ
    TABLICĘ[id] ścieżka
  ...
UNIA WSZYSTKIE
  WYBIERZ
    ścieżka || id
  ...
  GDZIE
    id  WSZYSTKIE(T.ścieżka) I
    array_length(T.ścieżka, 1) < 10
)

Wybierz sposób według własnych upodobań!

Źródło: habr.com