PostgreSQL Antipatterns: რამდენად ღრმაა კურდღლის ხვრელი? მოდით გავიაროთ იერარქია

რთულ 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;

[ნახეთ description.tensor.ru]

როგორც მოსალოდნელი იყო, 30-ვე ჩანაწერი ვიპოვეთ. მაგრამ მათ მთლიანი დროის 60% დახარჯეს ამაზე - რადგან მათ ასევე გააკეთეს 30 ძიება ინდექსში. შესაძლებელია თუ არა ნაკლების გაკეთება?

ნაყარი კორექტირება ინდექსით

გვჭირდება თუ არა ცალკე ინდექსის მოთხოვნა თითოეული კვანძისთვის? გამოდის, რომ არა - ჩვენ შეგვიძლია წავიკითხოთ ინდექსიდან ერთდროულად რამდენიმე კლავიშის გამოყენება ერთ ზარზე via = ANY(array).

იდენტიფიკატორების თითოეულ ასეთ ჯგუფში ჩვენ შეგვიძლია ავიღოთ წინა ეტაპზე ნაპოვნი ყველა ID-ები "კვანძების" მიხედვით. ანუ, ყოველ მომდევნო ეტაპზე ჩვენ გავაკეთებთ მოძებნეთ გარკვეული დონის ყველა შთამომავალი ერთდროულად.

მხოლოდ აქ არის პრობლემა, რეკურსიული შერჩევისას, თქვენ ვერ შეძლებთ საკუთარ თავს წვდომას წყობილ მოთხოვნაში, მაგრამ ჩვენ როგორმე უნდა შევარჩიოთ მხოლოდ ის, რაც წინა დონეზე იყო ნაპოვნი... გამოდის, რომ შეუძლებელია წყობილი მოთხოვნის გაკეთება მთელი სელექციისთვის, მაგრამ მისი კონკრეტული ველისთვის შესაძლებელია. და ეს ველი ასევე შეიძლება იყოს მასივი - რაც უნდა გამოვიყენოთ 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;

[ნახეთ description.tensor.ru]

და აქ ყველაზე მნიშვნელოვანი ის კი არაა მოიგეთ 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;

[ნახეთ description.tensor.ru]

ჩვენ შევძელით კიდევ ერთი ინდექსის ზარის შემცირება და მოიგო 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

ახლა ჩვენ მივიღებთ განყოფილების ID-ების კომპლექტს, რომელიც შემდგომ წაკითხვას საჭიროებს. თითქმის ყოველთვის ისინი იქნება დუბლირებული ორიგინალური ნაკრების სხვადასხვა ჩანაწერებში - ასე მოვიქცევით დააჯგუფე ისინი, წყაროს ფოთლების შესახებ ინფორმაციის შენარჩუნებისას.

მაგრამ აქ სამი უბედურება გველოდება:

1. მოთხოვნის "სუბკურსიული" ნაწილი არ შეიძლება შეიცავდეს აგრეგატულ ფუნქციებს GROUP BY.
2. რეკურსიულ „ცხრილზე“ მითითება არ შეიძლება იყოს ჩადგმულ ქვემოთხოვნაში.
3. მოთხოვნა რეკურსიულ ნაწილში არ შეიძლება შეიცავდეს 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

ახლა ჩვენ ვხედავთ, რატომ გადაკეთდა ციფრული ID ტექსტად - ისე, რომ მათი შეერთება შეიძლებოდა მძიმით გამოყოფილი!

ნაბიჯი 3

ფინალისთვის არაფერი დაგვრჩენია:

• ჩვენ ვკითხულობთ „სექციების“ ჩანაწერებს დაჯგუფებული ID-ების ნაკრების საფუძველზე
• ჩვენ ვადარებთ გამოკლებულ მონაკვეთებს ორიგინალური ფურცლების „კომპლექტებს“.
• "გაფართოება" set-string გამოყენებით 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;

[ნახეთ description.tensor.ru]

წყარო: www.habr.com