ProHoster > Blog > Pentadbiran > Antipattern PostgreSQL: "Infiniti bukan had!", atau Sedikit tentang rekursi

Antipattern PostgreSQL: "Infiniti bukan had!", atau Sedikit tentang rekursi

Rekursi - mekanisme yang sangat berkuasa dan mudah jika tindakan "mendalam" yang sama dilakukan pada data berkaitan. Tetapi rekursi yang tidak terkawal adalah kejahatan yang boleh menyebabkan sama ada pelaksanaan yang tidak berkesudahan proses, atau (yang berlaku lebih kerap) kepada "makan" semua memori yang ada.

Antipattern PostgreSQL: "Infiniti bukan had!", atau Sedikit tentang rekursi
DBMS dalam hal ini bekerja pada prinsip yang sama - "Mereka menyuruh saya menggali, jadi saya menggali". Permintaan anda bukan sahaja boleh memperlahankan proses jiran, sentiasa mengambil sumber pemproses, tetapi juga "menggugurkan" keseluruhan pangkalan data, "memakan" semua memori yang ada. Oleh itu perlindungan terhadap pengulangan tak terhingga - tanggungjawab pemaju sendiri.

Dalam PostgreSQL, keupayaan untuk menggunakan pertanyaan rekursif melalui WITH RECURSIVE muncul pada zaman berzaman versi 8.4, tetapi anda masih boleh kerap menghadapi pertanyaan "tanpa pertahanan" yang berpotensi terdedah. Bagaimana untuk menghilangkan diri anda daripada masalah seperti ini?

Jangan tulis pertanyaan rekursif

Dan tulis yang bukan rekursif. Yang Ikhlas, K.O Anda.

Malah, PostgreSQL menyediakan banyak fungsi yang boleh anda gunakan tiada gunakan rekursi.

Gunakan pendekatan yang berbeza secara asas untuk masalah

Kadang-kadang anda hanya boleh melihat masalah dari "sebelah yang berbeza". Saya memberikan contoh situasi sedemikian dalam artikel "SQL HowTo: 1000 dan satu cara pengagregatan" β€” pendaraban set nombor tanpa menggunakan fungsi agregat tersuai:

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 boleh digantikan dengan pilihan daripada pakar matematik:

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 dan bukannya gelung

Katakan kita berhadapan dengan tugas menjana semua kemungkinan awalan untuk rentetan '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;

Adakah anda pasti anda memerlukan rekursi di sini?.. Jika anda menggunakan LATERAL ΠΈ generate_series, maka anda tidak memerlukan CTE pun:

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

Tukar struktur pangkalan data

Sebagai contoh, anda mempunyai jadual mesej forum dengan sambungan daripada siapa yang membalas kepada siapa, atau urutan masuk rangkaian sosial:

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

Antipattern PostgreSQL: "Infiniti bukan had!", atau Sedikit tentang rekursi
Nah, permintaan biasa untuk memuat turun semua mesej pada satu topik kelihatan 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;

Tetapi kerana kita sentiasa memerlukan keseluruhan topik dari mesej akar, maka mengapa kita tidak tambahkan IDnya pada setiap entri automatik?

-- Π΄ΠΎΠ±Π°Π²ΠΈΠΌ ΠΏΠΎΠ»Π΅ с ΠΎΠ±Ρ‰ΠΈΠΌ ΠΈΠ΄Π΅Π½Ρ‚ΠΈΡ„ΠΈΠΊΠ°Ρ‚ΠΎΡ€ΠΎΠΌ Ρ‚Π΅ΠΌΡ‹ ΠΈ индСкс Π½Π° Π½Π΅Π³ΠΎ
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();

Antipattern PostgreSQL: "Infiniti bukan had!", atau Sedikit tentang rekursi
Kini keseluruhan pertanyaan rekursif kami boleh dikurangkan kepada ini sahaja:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

Gunakan "penghad" yang digunakan

Jika kita tidak dapat mengubah struktur pangkalan data atas sebab tertentu, mari lihat perkara yang boleh kita harapkan supaya kehadiran ralat dalam data tidak membawa kepada pengulangan yang tidak berkesudahan.

Kaunter kedalaman rekursi

Kami hanya meningkatkan pembilang sebanyak satu pada setiap langkah rekursi sehingga kami mencapai had yang kami anggap jelas tidak mencukupi:

WITH RECURSIVE T AS (
  SELECT
    0 i
  ...
UNION ALL
  SELECT
    i + 1
  ...
  WHERE
    T.i < 64 -- ΠΏΡ€Π΅Π΄Π΅Π»
)

Pro: Apabila kami cuba untuk menggelung, kami masih akan melakukan tidak lebih daripada had lelaran yang ditentukan "secara mendalam".
keburukan: Tiada jaminan bahawa kami tidak akan memproses rekod yang sama sekali lagi - contohnya, pada kedalaman 15 dan 25, dan kemudian setiap +10. Dan tiada siapa yang menjanjikan apa-apa tentang "keluasan".

Secara rasmi, rekursi sedemikian tidak akan menjadi tidak terhingga, tetapi jika pada setiap langkah bilangan rekod meningkat secara eksponen, kita semua tahu dengan baik bagaimana ia berakhir...

Antipattern PostgreSQL: "Infiniti bukan had!", atau Sedikit tentang rekursilihat "Masalah bijirin pada papan catur"

Penjaga "jalan"

Kami secara bergilir-gilir menambah semua pengecam objek yang kami temui di sepanjang laluan rekursi ke dalam tatasusunan, yang merupakan "laluan" unik kepadanya:

WITH RECURSIVE T AS (
  SELECT
    ARRAY[id] path
  ...
UNION ALL
  SELECT
    path || id
  ...
  WHERE
    id <> ALL(T.path) -- Π½Π΅ совпадаСт Π½ΠΈ с ΠΎΠ΄Π½ΠΈΠΌ ΠΈΠ·
)

Pro: Jika terdapat kitaran dalam data, kami sama sekali tidak akan memproses rekod yang sama berulang kali dalam laluan yang sama.
keburukan: Tetapi pada masa yang sama, kita benar-benar boleh memintas semua rekod tanpa mengulangi diri kita sendiri.

Antipattern PostgreSQL: "Infiniti bukan had!", atau Sedikit tentang rekursilihat "Masalah Pergerakan Knight"

Had Panjang Laluan

Untuk mengelakkan situasi rekursi "mengembara" pada kedalaman yang tidak dapat difahami, kita boleh menggabungkan dua kaedah sebelumnya. Atau, jika kami tidak mahu menyokong medan yang tidak diperlukan, tambah syarat untuk meneruskan rekursi dengan anggaran panjang laluan:

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 kaedah mengikut citarasa anda!

Sumber: www.habr.com

Tambah komen