PostgreSQL Antipatterns: “Infinity is not the Limit!” หรือเพียงเล็กน้อยเกี่ยวกับการเรียกซ้ำ

เรียกซ้ำ - กลไกที่ทรงพลังและสะดวกสบายมากหากดำเนินการ "เชิงลึก" แบบเดียวกันกับข้อมูลที่เกี่ยวข้อง แต่การเรียกซ้ำที่ไม่สามารถควบคุมได้นั้นเป็นความชั่วร้ายที่สามารถนำไปสู่สิ่งใดสิ่งหนึ่งได้ การดำเนินการที่ไม่มีที่สิ้นสุด กระบวนการหรือ (ซึ่งเกิดขึ้นบ่อยกว่า) ถึง “การกิน” ความทรงจำที่มีอยู่ทั้งหมด.

DBMS ในเรื่องนี้ทำงานบนหลักการเดียวกัน - "พวกเขาบอกให้ขุดฉันก็เลยขุด" คำขอของคุณไม่เพียงแต่จะทำให้กระบวนการข้างเคียงช้าลง ใช้ทรัพยากรของโปรเซสเซอร์อย่างต่อเนื่อง แต่ยัง "ทิ้ง" ฐานข้อมูลทั้งหมด "กิน" หน่วยความจำที่มีอยู่ทั้งหมด ดังนั้น ป้องกันการเรียกซ้ำไม่สิ้นสุด - ความรับผิดชอบของผู้พัฒนาเอง

ใน PostgreSQL ความสามารถในการใช้การสืบค้นแบบเรียกซ้ำผ่าน WITH RECURSIVE ปรากฏขึ้นมาแต่ไหนแต่ไรของเวอร์ชัน 8.4 แต่คุณยังคงพบคำขอที่ "ไม่มีการป้องกัน" ที่อาจมีความเสี่ยงอยู่เป็นประจำ จะกำจัดปัญหาประเภทนี้ได้อย่างไร?

อย่าเขียนแบบสอบถามแบบเรียกซ้ำ

และเขียนแบบไม่เรียกซ้ำ ขอแสดงความนับถือ K.O.

ในความเป็นจริง PostgreSQL มีฟังก์ชันการทำงานมากมายที่คุณสามารถใช้ได้ ไม่ ใช้การเรียกซ้ำ

ใช้แนวทางที่แตกต่างโดยพื้นฐานในการแก้ปัญหา

บางครั้งคุณสามารถมองปัญหาจาก "ด้านที่แตกต่าง" ได้ ฉันยกตัวอย่างสถานการณ์ดังกล่าวในบทความ "SQL HowTo: 1000 และวิธีเดียวในการรวมกลุ่ม" — การคูณชุดตัวเลขโดยไม่ต้องใช้ฟังก์ชันการรวมแบบกำหนดเอง:

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;

คำขอนี้สามารถแทนที่ด้วยตัวเลือกจากผู้เชี่ยวชาญด้านคณิตศาสตร์:

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

ใช้ Generate_series แทนการวนซ้ำ

สมมติว่าเรากำลังเผชิญกับงานสร้างคำนำหน้าที่เป็นไปได้ทั้งหมดสำหรับสตริง '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;

คุณแน่ใจหรือว่าต้องการการเรียกซ้ำที่นี่?.. ถ้าคุณใช้ LATERAL и generate_seriesคุณก็ไม่จำเป็นต้องใช้ CTE ด้วยซ้ำ:

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

เปลี่ยนโครงสร้างฐานข้อมูล

ตัวอย่างเช่น คุณมีตารางข้อความในฟอรัมพร้อมการเชื่อมต่อจากผู้ที่ตอบกลับ หรือเธรดใน เครือข่ายสังคม:

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

คำขอทั่วไปในการดาวน์โหลดข้อความทั้งหมดในหัวข้อเดียวจะมีลักษณะดังนี้:

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;

แต่เนื่องจากเราต้องการหัวข้อทั้งหมดจากข้อความรูทเสมอ แล้วทำไมเราไม่ต้องการล่ะ เพิ่ม ID ให้กับแต่ละรายการ อัตโนมัติ?

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

ตอนนี้แบบสอบถามแบบเรียกซ้ำทั้งหมดของเราสามารถลดลงเหลือเพียงเท่านี้:

SELECT
  *
FROM
  message
WHERE
  theme_id = $1;

ใช้ "ตัวจำกัด" ที่ใช้

หากเราไม่สามารถเปลี่ยนโครงสร้างของฐานข้อมูลได้ด้วยเหตุผลบางประการ เรามาดูกันว่าเราสามารถพึ่งพาอะไรได้บ้าง เพื่อให้แม้แต่ข้อมูลที่มีข้อผิดพลาดก็ไม่นำไปสู่การเรียกซ้ำอย่างไม่มีที่สิ้นสุด

ตัวนับความลึกของการเรียกซ้ำ

เราเพียงแค่เพิ่มตัวนับทีละตัวในแต่ละขั้นตอนการเรียกซ้ำจนกว่าเราจะถึงขีดจำกัดที่เราพิจารณาว่าไม่เพียงพออย่างเห็นได้ชัด:

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

Pro: เมื่อเราพยายามที่จะวนซ้ำ เราจะยังคงไม่เกินขีดจำกัดที่ระบุของการวนซ้ำ "ในเชิงลึก"
จุดด้อย: ไม่มีการรับประกันว่าเราจะไม่ประมวลผลบันทึกเดิมอีกครั้ง ตัวอย่างเช่น ที่ความลึก 15 และ 25 และทุกๆ +10 และไม่มีใครสัญญาอะไรเกี่ยวกับ "ความกว้าง"

อย่างเป็นทางการ การเรียกซ้ำดังกล่าวจะไม่ไม่มีที่สิ้นสุด แต่ถ้าในแต่ละขั้นตอน จำนวนบันทึกเพิ่มขึ้นแบบทวีคูณ เราทุกคนรู้ดีว่ามันจะจบลงอย่างไร...

ดู “ปัญหาเมล็ดข้าวบนกระดานหมากรุก”

ผู้พิทักษ์ "เส้นทาง"

เราสลับกันเพิ่มตัวระบุวัตถุทั้งหมดที่เราพบตามเส้นทางการเรียกซ้ำลงในอาร์เรย์ ซึ่งเป็น "เส้นทาง" ที่ไม่ซ้ำกัน:

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

Pro: หากมีวงจรในข้อมูล เราจะไม่ประมวลผลบันทึกเดิมซ้ำๆ ภายในเส้นทางเดียวกันโดยเด็ดขาด
จุดด้อย: แต่ในขณะเดียวกัน เราก็สามารถข้ามบันทึกทั้งหมดได้โดยไม่ต้องทำซ้ำอีก

ดู "ปัญหาการเคลื่อนไหวของอัศวิน"

ขีดจำกัดความยาวเส้นทาง

เพื่อหลีกเลี่ยงสถานการณ์การเรียกซ้ำ "หลงทาง" ในเชิงลึกที่ไม่อาจเข้าใจได้ เราสามารถรวมสองวิธีก่อนหน้านี้เข้าด้วยกันได้ หรือถ้าเราไม่ต้องการสนับสนุนฟิลด์ที่ไม่จำเป็น ให้เสริมเงื่อนไขสำหรับการเรียกซ้ำต่อไปด้วยการประมาณความยาวเส้นทาง:

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
)

เลือกวิธีการตามรสนิยมของคุณ!

ที่มา: will.com