🥇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;

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

ทุกอย่างคงจะดีถ้ามีผู้สืบทอดเหล่านี้เพียงไม่กี่ระดับและจำนวนอยู่ภายในหนึ่งโหล แต่หากมีมากกว่า 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

สำหรับข้อความค้นหาเหล่านี้ เราใช้คำทั่วไป เข้าร่วมแบบเรียกซ้ำ:

แน่นอนว่าด้วยโมเดลคำขอนี้ จำนวนการวนซ้ำจะตรงกับจำนวนการสืบทอดทั้งหมด (และมีหลายโหล) และอาจต้องใช้ทรัพยากรที่ค่อนข้างสำคัญและเป็นผลให้เสียเวลา

มาตรวจสอบแผนผังย่อยที่ "กว้างที่สุด":

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;

[ดูที่ expand.tensor.ru]

ตามที่คาดไว้ เราพบทั้งหมด 30 รายการ แต่พวกเขาใช้เวลา 60% ไปกับเรื่องนี้ - เพราะพวกเขาทำการค้นหา 30 ครั้งในดัชนีด้วย เป็นไปได้ไหมที่จะทำน้อยลง?

การพิสูจน์อักษรจำนวนมากตามดัชนี

เราจำเป็นต้องสร้างแบบสอบถามดัชนีแยกต่างหากสำหรับแต่ละโหนดหรือไม่? ปรากฎว่าไม่ - เราสามารถอ่านได้จากดัชนี การใช้หลายปุ่มพร้อมกันในการโทรครั้งเดียว ด้วย = 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;

[ดูที่ expand.tensor.ru]

และนี่คือสิ่งที่สำคัญที่สุดคือไม่เท่ากัน ชนะในเวลา 1.5 เท่าและเราได้ลบบัฟเฟอร์น้อยลง เนื่องจากเรามีการเรียกดัชนีเพียง 5 ครั้งแทนที่จะเป็น 30 ครั้ง!

โบนัสเพิ่มเติมคือความจริงที่ว่าหลังจากการ Unnest สุดท้าย ตัวระบุจะยังคงเรียงลำดับตาม "ระดับ"

เครื่องหมายโหนด

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

เข้าไปในตารางของเรากันเถอะ เพิ่มเติม 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;

[ดูที่ expand.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
  ...

หากมีคนคิดว่ามันแปลกที่ “set” ถูกจัดเก็บเป็นสตริงไม่ใช่อาร์เรย์ ก็มีคำอธิบายง่ายๆ สำหรับเรื่องนี้ มีฟังก์ชันการรวม "การติดกาว" ในตัวสำหรับสตริง string_aggแต่ไม่ใช่สำหรับอาร์เรย์ แม้ว่าเธอ ง่ายต่อการใช้งานด้วยตัวคุณเอง.

ขั้นตอนที่ 2

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

แต่ปัญหาสามประการรอเราอยู่ที่นี่:

ส่วน "subrecursive" ของแบบสอบถามไม่สามารถมีฟังก์ชันรวมได้ 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 โดยใช้ 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

สำหรับรอบชิงชนะเลิศเราไม่เหลืออะไรแล้ว:

เราอ่านบันทึก “ส่วน” ตามชุดรหัสที่จัดกลุ่ม
เราเปรียบเทียบส่วนที่ลบกับ "ชุด" ของแผ่นงานต้นฉบับ
“ขยาย” ชุดสตริงโดยใช้ 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;

[ดูที่ expand.tensor.ru]

ที่มา: will.com

PostgreSQL Antipatterns: รูกระต่ายลึกแค่ไหน? มาดูลำดับชั้นกัน

#1. รูกระต่ายลึกแค่ไหน?

การพิสูจน์อักษรจำนวนมากตามดัชนี

เครื่องหมายโหนด

#2. กลับไปที่รากกัน

ขั้นตอนที่ 1

ขั้นตอนที่ 2

CTE ในส่วนแบบเรียกซ้ำ

แบบสอบถามที่ซ้อนกันกับ "ตาราง" แบบเรียกซ้ำ

จัดกลุ่มตามการเรียกซ้ำภายใน

ขั้นตอนที่ 3

เพิ่มความคิดเห็น ยกเลิกการตอบ