🥇 Antipattern PostgreSQL: “Infinitas bukanlah batasnya!”, atau Sedikit tentang rekursi

Rekursi - mekanisme yang sangat kuat dan nyaman jika tindakan “mendalam” yang sama dilakukan pada data terkait. Namun rekursi yang tidak terkendali adalah sebuah kejahatan yang dapat menyebabkan keduanya eksekusi tanpa akhir proses, atau (yang lebih sering terjadi) ke "memakan" semua memori yang tersedia.

DBMS dalam hal ini bekerja berdasarkan prinsip yang sama - "Mereka menyuruhku menggali, jadi aku menggali". Permintaan Anda tidak hanya memperlambat proses di sekitarnya, terus-menerus menghabiskan sumber daya prosesor, tetapi juga "menjatuhkan" seluruh database, "memakan" semua memori yang tersedia. Oleh karena itu perlindungan terhadap rekursi tak terbatas - tanggung jawab pengembang itu sendiri.

Di PostgreSQL, kemampuan untuk menggunakan kueri rekursif melalui WITH RECURSIVE muncul sejak dahulu kala versi 8.4, namun Anda masih sering menemukan pertanyaan “tidak berdaya” yang berpotensi rentan. Bagaimana cara menghilangkan masalah seperti ini?

Jangan menulis pertanyaan rekursif

Dan tulis yang non-rekursif. Hormat kami, K.O.

Faktanya, PostgreSQL menyediakan cukup banyak fungsi yang dapat Anda manfaatkan tidak menerapkan rekursi.

Gunakan pendekatan yang berbeda secara mendasar terhadap masalah ini

Terkadang Anda hanya bisa melihat masalah dari “sisi yang berbeda”. Saya memberikan contoh situasi seperti itu di artikel "SQL HowTo: 1000 dan satu cara agregasi" — perkalian sekumpulan angka tanpa menggunakan fungsi agregat khusus:

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;

Permintaan ini dapat diganti dengan pilihan dari pakar matematika:

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

Gunakan generate_series alih-alih loop

Katakanlah kita dihadapkan pada tugas menghasilkan semua kemungkinan awalan untuk sebuah string '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;

Apakah Anda yakin Anda memerlukan rekursi di sini?.. Jika Anda menggunakan LATERAL и generate_series, maka Anda bahkan tidak memerlukan CTE:

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

Ubah struktur basis data

Misalnya, Anda memiliki tabel pesan forum dengan koneksi dari siapa yang merespons kepada siapa, atau rangkaian pesan di dalamnya jaringan sosial:

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

Nah, permintaan umum untuk mengunduh semua pesan tentang satu topik terlihat seperti ini:

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;

Namun karena kita selalu membutuhkan keseluruhan topik dari pesan utama, mengapa kita tidak melakukannya tambahkan ID-nya ke setiap entri otomatis?

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

Sekarang seluruh kueri rekursif kita dapat direduksi menjadi seperti ini:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Gunakan "pembatas" yang diterapkan

Jika kita tidak dapat mengubah struktur database karena alasan tertentu, mari kita lihat apa yang dapat kita andalkan sehingga bahkan adanya kesalahan pada data tidak menyebabkan rekursi tanpa akhir.

Penghitung kedalaman rekursi

Kami hanya menambah penghitung satu per satu pada setiap langkah rekursi hingga kami mencapai batas yang kami anggap jelas tidak memadai:

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

Pro: Ketika kami mencoba melakukan perulangan, kami masih akan melakukan tidak lebih dari batas iterasi yang ditentukan “secara mendalam”.
kontra: Tidak ada jaminan bahwa kami tidak akan memproses rekaman yang sama lagi - misalnya, pada kedalaman 15 dan 25, lalu setiap +10. Dan tidak ada seorang pun yang menjanjikan apa pun tentang “keluasan”.

Secara formal, rekursi seperti itu tidak akan terbatas, tetapi jika pada setiap langkah jumlah record bertambah secara eksponensial, kita semua tahu betul bagaimana akhirnya...

lihat “Masalah butiran di papan catur”

Penjaga "jalan"

Kami secara bergantian menambahkan semua pengidentifikasi objek yang kami temui di sepanjang jalur rekursi ke dalam array, yang merupakan “jalur” unik ke dalamnya:

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

Pro: Jika terdapat siklus pada data, kami sama sekali tidak akan memproses record yang sama berulang kali dalam jalur yang sama.
kontra: Namun pada saat yang sama, kita benar-benar dapat melewati semua catatan tanpa mengulanginya lagi.

lihat "Masalah Gerakan Ksatria"

Batas Panjang Jalur

Untuk menghindari situasi rekursi yang “berkeliaran” pada kedalaman yang tidak dapat dipahami, kita dapat menggabungkan dua metode sebelumnya. Atau, jika kita tidak ingin mendukung kolom yang tidak diperlukan, lengkapi kondisi untuk melanjutkan rekursi dengan perkiraan panjang jalur:

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
)

Pilih metode sesuai selera Anda!

Sumber: www.habr.com

Antipattern PostgreSQL: “Infinitas bukanlah batasnya!”, atau Sedikit tentang rekursi