Antywzorce PostgreSQL: „Nieskończoność nie jest granicą!”, czyli Trochę o rekurencji

rekursja - bardzo wydajny i wygodny mechanizm, jeśli te same „dogłębne” działania są wykonywane na powiązanych danych. Ale niekontrolowana rekurencja jest złem, które może prowadzić do jednego i drugiego niekończąca się realizacja proces lub (co zdarza się częściej) do „zjada” całą dostępną pamięć.

DBMS w tym zakresie działa na tych samych zasadach - „Kazali mi kopać, więc kopię„. Twoje żądanie może nie tylko spowolnić sąsiednie procesy, stale zajmując zasoby procesora, ale także „upuścić” całą bazę danych, „zjadając” całą dostępną pamięć. Dlatego też ochrona przed nieskończoną rekursją - odpowiedzialność samego dewelopera.

W PostgreSQL możliwość korzystania z zapytań rekurencyjnych poprzez WITH RECURSIVE pojawił się od niepamiętnych czasów wersji 8.4, ale nadal regularnie można spotkać potencjalnie podatne na ataki „bezbronne” żądania. Jak pozbyć się tego typu problemów?

Nie pisz zapytań rekurencyjnych

I pisz nierekurencyjne. Z poważaniem, Twój K.O.

W rzeczywistości PostgreSQL zapewnia całkiem sporo funkcjonalności, z których możesz skorzystać nie zastosuj rekurencję.

Zastosuj zasadniczo inne podejście do problemu

Czasem wystarczy spojrzeć na problem z „innej strony”. Przykład takiej sytuacji podałem w artykule „SQL HowTo: 1000 i jeden sposób agregacji” — mnożenie zbioru liczb bez użycia niestandardowych 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 -- отбор финального результата
  i DESC
LIMIT 1;

Prośbę tę można zastąpić opcją przedstawioną przez ekspertów w dziedzinie 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żyj generate_series zamiast pętli

Załóżmy, że mamy do czynienia z zadaniem wygenerowania wszystkich możliwych przedrostków dla ciągu '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 na pewno potrzebujesz tutaj rekurencji?.. Jeśli używasz LATERAL и generate_series, to nie będziesz nawet potrzebował CTE:

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

Zmień strukturę bazy danych

Na przykład masz tabelę wiadomości na forum z połączeniami, od tego, kto na kogo odpowiedział, lub wątek sieć społeczna:

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

Cóż, typowe żądanie pobrania wszystkich wiadomości na jeden temat 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;

Ale skoro zawsze potrzebujemy całego tematu z wiadomości głównej, to dlaczego tego nie zrobić dodaj jego identyfikator do każdego wpisu automatyczny?

-- добавим поле с общим идентификатором темы и индекс на него
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();

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

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Użyj zastosowanych „ograniczników”

Jeżeli z jakiegoś powodu nie jesteśmy w stanie zmienić struktury bazy danych, zobaczmy na czym możemy polegać, aby nawet obecność błędu w danych nie prowadziła do niekończących się rekurencji.

Licznik głębokości rekurencji

Po prostu zwiększamy licznik o jeden na każdym kroku rekurencji, aż osiągniemy granicę, którą uważamy za oczywiście niewystarczającą:

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

Pro: Kiedy spróbujemy zapętlić, nadal nie zrobimy więcej niż określony limit iteracji „w głębi”.
Wady: Nie ma gwarancji, że nie przetworzymy ponownie tego samego rekordu – np. na głębokości 15 i 25, a potem co +10. I nikt nic nie obiecywał odnośnie „szerokości”.

Formalnie taka rekurencja nie będzie nieskończona, ale jeśli na każdym kroku liczba rekordów będzie rosła wykładniczo, to wszyscy dobrze wiemy, jak to się skończy…

zobacz „Problem ziaren na szachownicy”

Strażnik „ścieżki”

Na zmianę dodajemy wszystkie identyfikatory obiektów, które napotkaliśmy na ścieżce rekurencji, do tablicy, która stanowi jej unikalną „ścieżkę”:

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

Pro: Jeśli w danych występuje cykl, absolutnie nie będziemy przetwarzać wielokrotnie tego samego rekordu w ramach tej samej ścieżki.
Wady: Ale jednocześnie możemy dosłownie ominąć wszystkie zapisy, nie powtarzając się.

zobacz „Problem z ruchem rycerza”

Limit długości ścieżki

Aby uniknąć sytuacji „wędrowania” rekurencji na niezrozumiałą głębokość, możemy połączyć dwie poprzednie metody. Lub, jeśli nie chcemy obsługiwać niepotrzebnych pól, uzupełnij warunek kontynuacji rekurencji o szacunkową długość ścieżki:

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
)

Wybierz metodę według własnego gustu!

Źródło: www.habr.com