Trong các hệ thống ERP phức tạp nhiều thực thể có tính chất phân cấpkhi các vật thể đồng nhất xếp thành hàng cây quan hệ tổ tiên-con cháu - đây là cơ cấu tổ chức của doanh nghiệp (tất cả các chi nhánh, phòng ban, tổ công tác) và danh mục hàng hóa, lĩnh vực hoạt động, địa lý các điểm bán hàng,...
Trên thực tế, không có , kết quả là sẽ không có bất kỳ hệ thống phân cấp nào. Nhưng ngay cả khi không làm việc “vì doanh nghiệp”, bạn vẫn có thể dễ dàng gặp phải các mối quan hệ thứ bậc. Thật là sáo rỗng, ngay cả cây gia phả hoặc sơ đồ tầng của cơ sở trong một trung tâm mua sắm cũng có cấu trúc giống nhau.
Có nhiều cách để lưu trữ một cây như vậy trong DBMS, nhưng hôm nay chúng ta sẽ chỉ tập trung vào một tùy chọn:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
Và trong khi bạn đang nghiên cứu sâu hơn về hệ thống phân cấp, bạn hãy kiên nhẫn chờ xem cách làm việc “ngây thơ” của bạn với một cấu trúc như vậy sẽ hiệu quả đến mức nào.
Hãy xem xét các vấn đề điển hình phát sinh, việc triển khai chúng trong SQL và cố gắng cải thiện hiệu suất của chúng.
#1. Hang thỏ sâu bao nhiêu?
Để cho rõ ràng, chúng ta hãy chấp nhận rằng cơ cấu này sẽ phản ánh sự phụ thuộc của các bộ phận trong cơ cấu tổ chức: các phòng ban, bộ phận, ban, ngành, nhóm công tác... - bất kể bạn gọi chúng là gì.
Đầu tiên, hãy tạo 'cây' gồm 10K phần tử
INSERT INTO hier
WITH RECURSIVE T AS (
SELECT
1::integer id
, '{1}'::integer[] pids
UNION ALL
SELECT
id + 1
, pids[1:(random() * array_length(pids, 1))::integer] || (id + 1)
FROM
T
WHERE
id < 10000
)
SELECT
pids[array_length(pids, 1)] id
, pids[array_length(pids, 1) - 1] pid
FROM
T;Hãy bắt đầu với nhiệm vụ đơn giản nhất - tìm tất cả nhân viên làm việc trong một lĩnh vực cụ thể hoặc theo thứ bậc - tìm tất cả con của một nút. Cũng sẽ rất tốt nếu có được “chiều sâu” của hậu duệ... Ví dụ, tất cả những điều này có thể cần thiết để xây dựng một số loại .
Mọi chuyện sẽ ổn nếu chỉ có một vài cấp độ của những con cháu này và số lượng nằm trong khoảng chục, nhưng nếu có hơn 5 cấp độ và đã có hàng chục cấp độ con cháu thì có thể sẽ có vấn đề. Hãy xem cách các tùy chọn tìm kiếm truyền thống được viết (và hoạt động) như thế nào. Nhưng trước tiên, hãy xác định xem nút nào sẽ thú vị nhất cho nghiên cứu của chúng ta.
Hầu hết "sâu" cây con:
WITH RECURSIVE T AS (
SELECT
id
, pid
, ARRAY[id] path
FROM
hier
WHERE
pid IS NULL
UNION ALL
SELECT
hier.id
, hier.pid
, T.path || hier.id
FROM
T
JOIN
hier
ON hier.pid = T.id
)
TABLE T ORDER BY array_length(path, 1) DESC; id | pid | path
---------------------------------------------
7624 | 7623 | {7615,7620,7621,7622,7623,7624}
4995 | 4994 | {4983,4985,4988,4993,4994,4995}
4991 | 4990 | {4983,4985,4988,4989,4990,4991}
...Hầu hết "rộng" cây con:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
Đối với những truy vấn này, chúng tôi đã sử dụng cách điển hình đệ quy THAM GIA:
Rõ ràng, với mô hình yêu cầu này số lần lặp sẽ bằng tổng số con cháu (và có vài chục trong số chúng), và việc này có thể tiêu tốn khá nhiều nguồn lực và do đó, cả thời gian.
Hãy kiểm tra cây con “rộng nhất”:
WITH RECURSIVE T AS (
SELECT
id
FROM
hier
WHERE
id = 5300
UNION ALL
SELECT
hier.id
FROM
T
JOIN
hier
ON hier.pid = T.id
)
TABLE T;
Đúng như dự đoán, chúng tôi đã tìm thấy tất cả 30 bản ghi. Nhưng họ đã dành 60% tổng thời gian cho việc này - bởi vì họ cũng đã thực hiện 30 lượt tìm kiếm trong chỉ mục. Có thể làm ít hơn được không?
Hiệu đính hàng loạt theo chỉ mục
Chúng ta có cần tạo một truy vấn chỉ mục riêng cho từng nút không? Hóa ra là không - chúng ta có thể đọc từ chỉ mục sử dụng nhiều phím cùng lúc trong một cuộc gọi thông qua = ANY(array).
Và trong mỗi nhóm số nhận dạng như vậy, chúng ta có thể lấy tất cả các ID được tìm thấy ở bước trước bởi các “nút”. Tức là ở mỗi bước tiếp theo chúng ta sẽ tìm kiếm tất cả con cháu của một cấp độ nhất định cùng một lúc.
Chỉ có vấn đề là ở đây trong lựa chọn đệ quy, bạn không thể truy cập chính nó trong truy vấn lồng nhau, nhưng bằng cách nào đó chúng ta chỉ cần chọn những gì đã được tìm thấy ở cấp độ trước đó... Hóa ra là bạn không thể tạo một truy vấn lồng nhau cho toàn bộ lựa chọn, nhưng đối với trường cụ thể của nó thì bạn có thể. Và trường này cũng có thể là một mảng - đó là thứ chúng ta cần sử dụng ANY.
Nghe có vẻ hơi điên rồ, nhưng trong sơ đồ mọi thứ đều đơn giản.
WITH RECURSIVE T AS (
SELECT
ARRAY[id] id$
FROM
hier
WHERE
id = 5300
UNION ALL
SELECT
ARRAY(
SELECT
id
FROM
hier
WHERE
pid = ANY(T.id$)
) id$
FROM
T
WHERE
coalesce(id$, '{}') <> '{}' -- условие выхода из цикла - пустой массив
)
SELECT
unnest(id$) id
FROM
T;
Và ở đây điều quan trọng nhất thậm chí không phải là thắng 1.5 lần đúng lúcvà chúng tôi đã trừ đi ít bộ đệm hơn vì chúng tôi chỉ có 5 lệnh gọi tới chỉ mục thay vì 30!
Một phần thưởng bổ sung là thực tế là sau lần tháo cuối cùng, các mã định danh sẽ vẫn được sắp xếp theo “cấp độ”.
Dấu hiệu nút
Việc cân nhắc tiếp theo sẽ giúp cải thiện hiệu suất là − “lá” không thể có con, tức là đối với họ không cần phải nhìn “xuống” chút nào. Khi xây dựng nhiệm vụ của chúng tôi, điều này có nghĩa là nếu chúng tôi đi theo chuỗi các phòng ban và tiếp cận được một nhân viên, thì không cần phải tìm kiếm thêm dọc theo nhánh này.
Hãy vào bảng của chúng tôi thêm vào boolean-đồng ruộng, điều này sẽ ngay lập tức cho chúng ta biết liệu mục cụ thể này trong cây của chúng ta có phải là một “nút” hay không - nghĩa là liệu nó có thể có con cháu hay không.
ALTER TABLE hier
ADD COLUMN branch boolean;
UPDATE
hier T
SET
branch = TRUE
WHERE
EXISTS(
SELECT
NULL
FROM
hier
WHERE
pid = T.id
LIMIT 1
);
-- Запрос успешно выполнен: 3033 строк изменено за 42 мс.Tuyệt vời! Hóa ra chỉ có hơn 30% tổng số phần tử của cây có con cháu.
Bây giờ hãy sử dụng một cơ chế hơi khác - kết nối với phần đệ quy thông qua LATERAL, điều này sẽ cho phép chúng ta truy cập ngay vào các trường của “bảng” đệ quy và sử dụng hàm tổng hợp với điều kiện lọc dựa trên một nút để giảm bộ khóa:
WITH RECURSIVE T AS (
SELECT
array_agg(id) id$
, array_agg(id) FILTER(WHERE branch) ns$
FROM
hier
WHERE
id = 5300
UNION ALL
SELECT
X.*
FROM
T
JOIN LATERAL (
SELECT
array_agg(id) id$
, array_agg(id) FILTER(WHERE branch) ns$
FROM
hier
WHERE
pid = ANY(T.ns$)
) X
ON coalesce(T.ns$, '{}') <> '{}'
)
SELECT
unnest(id$) id
FROM
T;
Chúng tôi đã có thể giảm thêm một lệnh gọi chỉ mục và thắng hơn 2 lần về số lượng đã được hiệu đính.
#2. Chúng ta hãy quay về cội nguồn
Thuật toán này sẽ hữu ích nếu bạn cần thu thập các bản ghi cho tất cả các phần tử “lên cây”, trong khi vẫn giữ lại thông tin về trang nguồn nào (và với chỉ số nào) khiến nó được đưa vào mẫu - ví dụ: để tạo báo cáo tóm tắt với sự tổng hợp thành các nút.
Những điều sau đây chỉ nên được coi là bằng chứng về khái niệm vì yêu cầu hóa ra rất cồng kềnh. Nhưng nếu nó thống trị cơ sở dữ liệu của bạn, bạn nên nghĩ đến việc sử dụng các kỹ thuật tương tự.
Hãy bắt đầu với một vài câu nói đơn giản:
- Bản ghi tương tự từ cơ sở dữ liệu Tốt nhất nên đọc một lần.
- Bản ghi từ cơ sở dữ liệu Sẽ hiệu quả hơn khi đọc theo đợthơn là một mình.
Bây giờ hãy thử xây dựng yêu cầu mà chúng ta cần.
Bước 1
Rõ ràng, khi khởi tạo đệ quy (chúng ta sẽ ở đâu nếu không có nó!) chúng ta sẽ phải trừ các bản ghi của các lá dựa trên tập hợp các định danh ban đầu:
WITH RECURSIVE tree AS (
SELECT
rec -- это цельная запись таблицы
, id::text chld -- это "набор" приведших сюда исходных листьев
FROM
hier rec
WHERE
id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
UNION ALL
...
Nếu ai đó thấy lạ khi “bộ” được lưu trữ dưới dạng chuỗi chứ không phải mảng, thì có một lời giải thích đơn giản cho điều này. Có tích hợp sẵn chức năng “dán” tổng hợp cho chuỗi string_agg, nhưng không dành cho mảng. Mặc dù cô ấy .
Bước 2
Bây giờ chúng ta sẽ nhận được một bộ ID phần cần được đọc thêm. Hầu như chúng luôn được sao chép trong các bản ghi khác nhau của tập hợp ban đầu - vì vậy chúng ta sẽ nhóm chúng, trong khi vẫn giữ được thông tin về nguồn lá.
Nhưng ở đây có ba rắc rối đang chờ đợi chúng ta:
- Phần "đệ quy phụ" của truy vấn không thể chứa các hàm tổng hợp có
GROUP BY. - Tham chiếu đến một “bảng” đệ quy không thể nằm trong truy vấn con lồng nhau.
- Yêu cầu trong phần đệ quy không thể chứa CTE.
May mắn thay, tất cả những vấn đề này đều khá dễ giải quyết. Hãy bắt đầu từ cuối.
CTE trong phần đệ quy
Ở đây không làm:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)Và vì vậy nó hoạt động, dấu ngoặc đơn tạo nên sự khác biệt!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)Truy vấn lồng nhau đối với một "bảng" đệ quy
Hmm... Không thể truy cập CTE đệ quy trong truy vấn phụ. Nhưng nó có thể ở bên trong CTE! Và một yêu cầu lồng nhau đã có thể truy cập CTE này!
NHÓM THEO đệ quy bên trong
Thật khó chịu, nhưng... Chúng tôi có một cách đơn giản để mô phỏng GROUP BY bằng cách sử dụng DISTINCT ON và các chức năng của cửa sổ!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!Và đây là cách nó hoạt động!
SELECT DISTINCT ON((rec).pid)
(rec).pid id
, string_agg(chld::text, ',') OVER(PARTITION BY (rec).pid) chld
FROM
tree
WHERE
(rec).pid IS NOT NULLBây giờ chúng ta hiểu tại sao ID số được chuyển thành văn bản - để chúng có thể được nối với nhau và phân tách bằng dấu phẩy!
Bước 3
Đối với trận chung kết, chúng tôi không còn gì:
- chúng tôi đọc các bản ghi “phần” dựa trên một tập hợp ID được nhóm
- chúng tôi so sánh các phần bị trừ với “bộ” của trang gốc
- “mở rộng” chuỗi set bằng cách sử dụng
unnest(string_to_array(chld, ',')::integer[])
WITH RECURSIVE tree AS (
SELECT
rec
, id::text chld
FROM
hier rec
WHERE
id = ANY('{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192}'::integer[])
UNION ALL
(
WITH prnt AS (
SELECT DISTINCT ON((rec).pid)
(rec).pid id
, string_agg(chld::text, ',') OVER(PARTITION BY (rec).pid) chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
)
, nodes AS (
SELECT
rec
FROM
hier rec
WHERE
id = ANY(ARRAY(
SELECT
id
FROM
prnt
))
)
SELECT
nodes.rec
, prnt.chld
FROM
prnt
JOIN
nodes
ON (nodes.rec).id = prnt.id
)
)
SELECT
unnest(string_to_array(chld, ',')::integer[]) leaf
, (rec).*
FROM
tree;
Nguồn: www.habr.com