در سیستم های پیچیده ERP بسیاری از موجودیت ها ماهیت سلسله مراتبی دارندهنگامی که اشیاء همگن در یک ردیف قرار می گیرند درخت روابط اجداد و اجداد - این ساختار سازمانی شرکت (همه این شعب، بخش ها و گروه های کاری) و کاتالوگ کالاها و زمینه های کاری و جغرافیای نقاط فروش است.
در واقع هیچ کدام وجود ندارد ، جایی که در نتیجه هیچ سلسله مراتبی وجود نخواهد داشت. اما حتی اگر "برای کسب و کار" کار نکنید، باز هم می توانید به راحتی با روابط سلسله مراتبی روبرو شوید. عادی است، حتی شجره نامه شما یا پلان ساختمان در یک مرکز خرید نیز همین ساختار است.
راه های زیادی برای ذخیره چنین درختی در DBMS وجود دارد، اما امروز ما تنها بر روی یک گزینه تمرکز می کنیم:
CREATE TABLE hier(
id
integer
PRIMARY KEY
, pid
integer
REFERENCES hier
, data
json
);
CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK
و در حالی که شما به اعماق سلسله مراتب نگاه می کنید، صبورانه منتظر است تا ببینید روش های «ساده لوحانه» شما برای کار با چنین ساختاری چقدر [نا] مؤثر خواهد بود.
بیایید به مشکلات معمولی که به وجود می آیند، پیاده سازی آنها در SQL نگاه کنیم و سعی کنیم عملکرد آنها را بهبود دهیم.
#1. عمق سوراخ خرگوش چقدر است؟
اجازه دهید، برای قطعیت، بپذیریم که این ساختار منعکس کننده زیرمجموعه بخش ها در ساختار سازمان خواهد بود: بخش ها، بخش ها، بخش ها، شاخه ها، گروه های کاری... - هر چه شما آنها را بنامید.
ابتدا، بیایید "درخت" خود را از 10K عناصر تولید کنیم
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;بیایید با ساده ترین کار شروع کنیم - یافتن همه کارکنانی که در یک بخش خاص یا از نظر سلسله مراتبی کار می کنند. همه فرزندان یک گره را پیدا کنید. همچنین خوب است که "عمق" نسل را بدست آوریم ... همه اینها ممکن است لازم باشد، به عنوان مثال، برای ساختن نوعی از .
اگر فقط چند سطح از این نوادگان وجود داشته باشد و تعداد آنها در یک دوجین باشد، همه چیز خوب خواهد بود، اما اگر بیش از 5 سطح وجود داشته باشد، و در حال حاضر ده ها نفر از فرزندان وجود داشته باشند، ممکن است مشکلاتی وجود داشته باشد. بیایید ببینیم که چگونه گزینه‌های جستجوی سنتی پایین درخت نوشته می‌شوند (و کار می‌کنند). اما ابتدا، بیایید تعیین کنیم که کدام گره ها برای تحقیق ما جالب تر خواهند بود.
بیشترین "عمیق" درختان فرعی:
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}
...بیشترین "وسیع" درختان فرعی:
...
SELECT
path[1] id
, count(*)
FROM
T
GROUP BY
1
ORDER BY
2 DESC;id | count
------------
5300 | 30
450 | 28
1239 | 27
1573 | 25
برای این پرس و جوها از معمولی استفاده کردیم بازگشتی JOIN:
بدیهی است با این مدل درخواست تعداد تکرارها با تعداد کل فرزندان مطابقت دارد (و چندین ده مورد از آنها وجود دارد)، و این می تواند منابع بسیار قابل توجهی و در نتیجه زمان را بگیرد.
بیایید "عریض ترین" زیردرخت را بررسی کنیم:
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;
همانطور که انتظار می رفت، ما هر 30 رکورد را پیدا کردیم. اما آنها 60٪ از کل زمان را صرف این کار کردند - زیرا آنها همچنین 30 جستجو در فهرست انجام دادند. آیا می توان کمتر انجام داد؟
تصحیح انبوه بر اساس نمایه
آیا باید برای هر گره یک پرس و جو شاخص جداگانه ایجاد کنیم؟ معلوم می شود که نه - می توانیم از شاخص بخوانیم با استفاده از چندین کلید در یک تماس با کمک = ANY(array).
و در هر یک از این گروه از شناسه‌ها، می‌توانیم تمام شناسه‌هایی را که در مرحله قبل یافت شده‌اند توسط «گره‌ها» بگیریم. یعنی در هر مرحله بعدی ما این کار را خواهیم کرد همه فرزندان یک سطح معین را به طور همزمان جستجو کنید.
فقط مشکل اینجاست در انتخاب بازگشتی، شما نمی توانید به خود در یک پرس و جوی تودرتو دسترسی داشته باشید، اما ما باید به نحوی فقط آنچه را در سطح قبلی یافت شد انتخاب کنیم... معلوم می شود که ایجاد یک پرس و جو تو در تو برای کل انتخاب غیرممکن است، اما برای فیلد خاص آن امکان پذیر است. و این فیلد همچنین می تواند یک آرایه باشد - چیزی که ما باید از آن استفاده کنیم ANY.
کمی دیوانه به نظر می رسد، اما در نمودار همه چیز ساده است.
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;
و در اینجا مهمترین چیز یکنواخت نیست 1.5 بار در زمان برنده شوید، و اینکه ما بافرهای کمتری را کم کردیم، زیرا به جای 5 فقط 30 تماس با ایندکس داریم!
یک امتیاز اضافی این واقعیت است که پس از جداسازی نهایی، شناسه ها بر اساس "سطوح" مرتب می شوند.
علامت گره
ملاحظات بعدی که به بهبود عملکرد کمک می کند - است "برگ" نمی تواند بچه دار شود، یعنی برای آنها اصلاً نیازی به نگاه "پایین" نیست. در فرمول بندی وظیفه ما، این بدان معنی است که اگر ما زنجیره ادارات را دنبال کردیم و به یک کارمند رسیدیم، دیگر نیازی به جستجوی بیشتر در این شاخه نیست.
بیایید وارد جدول خود شویم اضافی boolean-رشته، که بلافاصله به ما می گوید که آیا این ورودی خاص در درخت ما یک "گره" است - یعنی اصلاً می تواند فرزندانی داشته باشد یا خیر.
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 мс.عالی! به نظر می رسد که فقط کمی بیش از 30٪ از تمام عناصر درخت دارای فرزندان هستند.
اکنون اجازه دهید از مکانیک کمی متفاوت استفاده کنیم - اتصالات به قسمت بازگشتی از طریق LATERAL، که به ما امکان می دهد فوراً به فیلدهای "جدول" بازگشتی دسترسی پیدا کنیم و از یک تابع انبوه با شرایط فیلتر مبتنی بر یک گره برای کاهش مجموعه کلیدها استفاده کنیم:
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;
ما توانستیم یک تماس شاخص دیگر را کاهش دهیم و برنده بیش از 2 بار در حجم تصحیح
#2. به ریشه ها برگردیم
این الگوریتم در صورتی مفید خواهد بود که شما نیاز به جمع‌آوری سوابق برای همه عناصر "بالا درخت" داشته باشید، در حالی که اطلاعاتی در مورد اینکه کدام برگه منبع (و با چه شاخص‌هایی) باعث شده است که در نمونه گنجانده شود - به عنوان مثال، برای تولید یک گزارش خلاصه، مفید خواهد بود. با تجمع در گره ها.
آنچه در ادامه می آید باید صرفاً به عنوان یک اثبات مفهوم در نظر گرفته شود، زیرا به نظر می رسد درخواست بسیار دست و پا گیر است. اما اگر بر پایگاه داده شما تسلط دارد، باید به فکر استفاده از تکنیک های مشابه باشید.
بیایید با چند جمله ساده شروع کنیم:
- همان رکورد از پایگاه داده بهتر است آن را فقط یک بار بخوانید.
- سوابق از پایگاه داده خواندن به صورت دسته‌ای کارآمدتر استاز تنهایی
حالا بیایید سعی کنیم درخواستی را که نیاز داریم بسازیم.
مرحله 1
بدیهی است که هنگام شروع مجدد بازگشت (بدون آن کجا خواهیم بود!) باید رکوردهای خود برگها را بر اساس مجموعه شناسه های اولیه کم کنیم:
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
...
اگر برای کسی عجیب به نظر می رسید که "مجموعه" به عنوان یک رشته و نه یک آرایه ذخیره می شود، توضیح ساده ای برای این وجود دارد. یک تابع "چسباندن" جمع‌آوری داخلی برای رشته‌ها وجود دارد string_agg، اما نه برای آرایه ها. اگرچه او .
مرحله 2
اکنون مجموعه ای از شناسه های بخش دریافت می کنیم که باید بیشتر خوانده شوند. تقریباً همیشه آنها در رکوردهای مختلف مجموعه اصلی تکرار می شوند - بنابراین ما این کار را می کنیم آنها را گروه بندی کنید، ضمن حفظ اطلاعات مربوط به برگ های منبع.
اما در اینجا سه مشکل در انتظار ما است:
- بخش "زیر نوری" پرس و جو نمی تواند شامل توابع انبوه با باشد
GROUP BY. - ارجاع به یک "جدول" بازگشتی نمی تواند در یک پرس و جو فرعی تودرتو باشد.
- درخواست در بخش بازگشتی نمی تواند حاوی CTE باشد.
خوشبختانه، حل همه این مشکلات بسیار آسان است. بیایید از آخر شروع کنیم.
CTE در بخش بازگشتی
در اینجا چنین است هیچ کار کردن:
WITH RECURSIVE tree AS (
...
UNION ALL
WITH T (...)
SELECT ...
)و بنابراین کار می کند، پرانتز تفاوت را ایجاد می کند!
WITH RECURSIVE tree AS (
...
UNION ALL
(
WITH T (...)
SELECT ...
)
)پرس و جوی تودرتو در برابر یک "جدول" بازگشتی
هوم... یک CTE بازگشتی در یک پرسش فرعی قابل دسترسی نیست. اما ممکن است داخل CTE باشد! و یک درخواست تو در تو می تواند از قبل به این CTE دسترسی داشته باشد!
GROUP BY در داخل بازگشت
ناخوشایند است، اما... ما یک راه ساده برای شبیه سازی GROUP BY با استفاده داریم DISTINCT ON و توابع پنجره!
SELECT
(rec).pid id
, string_agg(chld::text, ',') chld
FROM
tree
WHERE
(rec).pid IS NOT NULL
GROUP BY 1 -- не работает!و این روش کار می کند!
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اکنون می بینیم که چرا شناسه عددی به متن تبدیل شده است - به طوری که آنها می توانند با کاما از هم جدا شوند!
مرحله 3
برای فینال چیزی نداریم:
- ما رکوردهای "بخش" را بر اساس مجموعه ای از شناسه های گروه بندی شده می خوانیم
- ما بخش های تفریق شده را با "مجموعه های" برگه های اصلی مقایسه می کنیم
- "گسترش" مجموعه-رشته با استفاده از
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;
منبع: www.habr.com