DBMS về mặt này hoạt động dựa trên các nguyên tắc giống nhau - "Họ bảo tôi đào nên tôi đào". Yêu cầu của bạn không chỉ có thể làm chậm các tiến trình lân cận, liên tục chiếm dụng tài nguyên bộ xử lý mà còn có thể "thả" toàn bộ cơ sở dữ liệu, "ăn" hết bộ nhớ khả dụng. Do đó bảo vệ chống đệ quy vô hạn - trách nhiệm của chính nhà phát triển.
Trong PostgreSQL, khả năng sử dụng các truy vấn đệ quy thông qua WITH RECURSIVE
Đừng viết truy vấn đệ quy
Và viết những cái không đệ quy. Trân trọng, K.O.
Trên thực tế, PostgreSQL cung cấp khá nhiều chức năng mà bạn có thể sử dụng để không áp dụng đệ quy.
Sử dụng một cách tiếp cận khác về cơ bản cho vấn đề
Đôi khi bạn chỉ có thể nhìn vấn đề từ “phía khác”. Tôi đã đưa ra một ví dụ về tình huống như vậy trong bài viết
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;
Yêu cầu này có thể được thay thế bằng một lựa chọn từ các chuyên gia toán học:
WITH src AS (
SELECT unnest('{2,3,5,7,11,13,17,19}'::integer[]) prime
)
SELECT
exp(sum(ln(prime)))::integer val
FROM
src;
Sử dụng generate_series thay vì vòng lặp
Giả sử chúng ta phải đối mặt với nhiệm vụ tạo ra tất cả các tiền tố có thể có cho một chuỗi '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;
Bạn có chắc chắn cần đệ quy ở đây không?.. Nếu bạn sử dụng LATERAL
и generate_series
, thì bạn thậm chí sẽ không cần CTE:
SELECT
substr(str, 1, ln) str
FROM
(VALUES('abcdefgh')) T(str)
, LATERAL(
SELECT generate_series(length(str), 1, -1) ln
) X;
Thay đổi cấu trúc cơ sở dữ liệu
Ví dụ: bạn có một bảng các tin nhắn trên diễn đàn với các kết nối từ ai đã trả lời cho ai hoặc một chủ đề trong
CREATE TABLE message(
message_id
uuid
PRIMARY KEY
, reply_to
uuid
REFERENCES message
, body
text
);
CREATE INDEX ON message(reply_to);
Chà, một yêu cầu điển hình để tải xuống tất cả thư về một chủ đề sẽ giống như thế này:
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;
Nhưng vì chúng ta luôn cần toàn bộ chủ đề từ thông điệp gốc, vậy tại sao chúng ta không thêm ID của nó vào mỗi mục tự động?
-- добавим поле с общим идентификатором темы и индекс на него
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();
Bây giờ toàn bộ truy vấn đệ quy của chúng ta có thể được rút gọn thành thế này:
SELECT
*
FROM
message
WHERE
theme_id = $1;
Sử dụng các "bộ giới hạn" được áp dụng
Nếu vì lý do nào đó chúng ta không thể thay đổi cấu trúc của cơ sở dữ liệu, hãy xem chúng ta có thể dựa vào điều gì để ngay cả khi có lỗi trong dữ liệu cũng không dẫn đến đệ quy vô tận.
Bộ đếm độ sâu đệ quy
Chúng ta chỉ cần tăng bộ đếm lên một ở mỗi bước đệ quy cho đến khi đạt đến giới hạn mà chúng ta cho là không đủ:
WITH RECURSIVE T AS (
SELECT
0 i
...
UNION ALL
SELECT
i + 1
...
WHERE
T.i < 64 -- предел
)
Pro: Khi cố gắng lặp lại, chúng tôi vẫn sẽ không thực hiện nhiều hơn giới hạn số lần lặp được chỉ định "theo chiều sâu".
khuyết điểm: Không có gì đảm bảo rằng chúng tôi sẽ không xử lý lại cùng một bản ghi - ví dụ: ở độ sâu 15 và 25, sau đó là +10. Và không ai hứa hẹn bất cứ điều gì về “chiều rộng”.
Về mặt hình thức, đệ quy như vậy sẽ không phải là vô hạn, nhưng nếu ở mỗi bước, số lượng bản ghi tăng theo cấp số nhân thì tất cả chúng ta đều biết rõ nó kết thúc như thế nào...
Người bảo vệ “con đường”
Chúng tôi lần lượt thêm tất cả các mã định danh đối tượng mà chúng tôi gặp dọc theo đường dẫn đệ quy vào một mảng, đây là một “đường dẫn” duy nhất tới nó:
WITH RECURSIVE T AS (
SELECT
ARRAY[id] path
...
UNION ALL
SELECT
path || id
...
WHERE
id <> ALL(T.path) -- не совпадает ни с одним из
)
Pro: Nếu có sự tuần hoàn trong dữ liệu, chúng tôi tuyệt đối sẽ không xử lý lặp đi lặp lại cùng một bản ghi trong cùng một đường dẫn.
khuyết điểm: Nhưng đồng thời, chúng ta có thể bỏ qua tất cả các bản ghi theo đúng nghĩa đen mà không cần lặp lại chính mình.
Giới hạn độ dài đường dẫn
Để tránh tình trạng đệ quy “lang thang” ở độ sâu khó hiểu, chúng ta có thể kết hợp 2 phương pháp trước. Hoặc, nếu chúng tôi không muốn hỗ trợ các trường không cần thiết, hãy bổ sung điều kiện để tiếp tục đệ quy bằng ước tính độ dài đường dẫn:
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
)
Chọn một phương pháp theo sở thích của bạn!
Nguồn: www.habr.com