🥇PostgreSQL Antipatterns: Sejauh manakah dalam lubang arnab? mari kita melalui hierarki

Dalam sistem ERP yang kompleks banyak entiti mempunyai sifat hierarkiapabila objek homogen berbaris masuk pokok hubungan nenek moyang-keturunan - ini ialah struktur organisasi perusahaan (semua cawangan, jabatan dan kumpulan kerja ini), dan katalog barangan, dan kawasan kerja, dan geografi tempat jualan,...

Malah, tidak ada kawasan automasi perniagaan, di mana tidak akan ada sebarang hierarki akibatnya. Tetapi walaupun anda tidak bekerja "untuk perniagaan", anda masih boleh menghadapi perhubungan hierarki dengan mudah. Sudah basi, malah salasilah keluarga anda atau pelan lantai premis di pusat membeli-belah adalah struktur yang sama.

Terdapat banyak cara untuk menyimpan pokok sedemikian dalam DBMS, tetapi hari ini kita akan menumpukan pada satu pilihan sahaja:

CREATE TABLE hier(
  id
    integer
      PRIMARY KEY
, pid
    integer
      REFERENCES hier
, data
    json
);

CREATE INDEX ON hier(pid); -- не забываем, что FK не подразумевает автосоздание индекса, в отличие от PK

Dan semasa anda meninjau kedalaman hierarki, ia sedang menunggu untuk melihat betapa berkesannya cara "naif" anda bekerja dengan struktur sedemikian.

Mari kita lihat masalah biasa yang timbul, pelaksanaannya dalam SQL, dan cuba perbaiki prestasinya.

#1. Berapa dalam lubang arnab?

Marilah kita, untuk kepastian, menerima bahawa struktur ini akan mencerminkan subordinasi jabatan dalam struktur organisasi: jabatan, bahagian, sektor, cawangan, kumpulan kerja... - apa sahaja panggilan anda.

Mula-mula, mari kita hasilkan 'pokok' 10K elemen kita

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;

Mari kita mulakan dengan tugas paling mudah - mencari semua pekerja yang bekerja dalam sektor tertentu, atau dari segi hierarki - cari semua anak nod. Ia juga bagus untuk mendapatkan "kedalaman" keturunan... Semua ini mungkin perlu, sebagai contoh, untuk membina beberapa jenis pemilihan kompleks berdasarkan senarai ID pekerja ini.

Semuanya akan baik-baik saja jika hanya terdapat beberapa peringkat keturunan ini dan jumlahnya dalam sedozen, tetapi jika terdapat lebih daripada 5 peringkat, dan sudah ada berpuluh-puluh keturunan, mungkin ada masalah. Mari lihat cara pilihan carian turun-pokok tradisional ditulis (dan berfungsi). Tetapi pertama-tama, mari kita tentukan nod mana yang paling menarik untuk penyelidikan kami.

Yang paling banyak "dalam" pokok kecil:

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}
...

Yang paling banyak "lebar" pokok kecil:

...
SELECT
  path[1] id
, count(*)
FROM
  T
GROUP BY
  1
ORDER BY
  2 DESC;

id   | count
------------
5300 |   30
 450 |   28
1239 |   27
1573 |   25

Untuk pertanyaan ini kami menggunakan pertanyaan biasa rekursif SERTAI:

Jelas sekali, dengan model permintaan ini bilangan lelaran akan sepadan dengan jumlah bilangan keturunan (dan terdapat beberapa dozen daripadanya), dan ini boleh mengambil sumber yang agak ketara, dan, akibatnya, masa.

Mari kita semak subpokok "terluas":

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;

[lihat explain.tensor.ru]

Seperti yang dijangka, kami menemui kesemua 30 rekod. Tetapi mereka menghabiskan 60% daripada jumlah masa untuk perkara ini - kerana mereka juga melakukan 30 carian dalam indeks. Adakah mungkin untuk melakukan lebih sedikit?

Bacaan pruf pukal mengikut indeks

Adakah kita perlu membuat pertanyaan indeks berasingan untuk setiap nod? Ternyata tidak - kita boleh membaca dari indeks menggunakan beberapa kekunci sekaligus dalam satu panggilan melalui = ANY(array).

Dan dalam setiap kumpulan pengecam sedemikian, kita boleh mengambil semua ID yang terdapat dalam langkah sebelumnya dengan "nod". Iaitu, pada setiap langkah seterusnya kita akan mencari semua keturunan peringkat tertentu sekali gus.

Cuma, itulah nasib malang, dalam pemilihan rekursif, anda tidak boleh mengakses dirinya sendiri dalam pertanyaan bersarang, tetapi entah bagaimana kita perlu memilih hanya apa yang ditemui pada peringkat sebelumnya... Ternyata mustahil untuk membuat pertanyaan bersarang untuk keseluruhan pemilihan, tetapi untuk medan khususnya adalah mungkin. Dan medan ini juga boleh menjadi tatasusunan - itulah yang perlu kita gunakan ANY.

Kedengarannya agak gila, tetapi dalam rajah semuanya mudah.

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;

[lihat explain.tensor.ru]

Dan di sini perkara yang paling penting adalah tidak sekata menang 1.5 kali dalam masa, dan bahawa kami telah menolak penimbal yang lebih sedikit, kerana kami hanya mempunyai 5 panggilan ke indeks dan bukannya 30!

Bonus tambahan ialah hakikat bahawa selepas unnest terakhir, pengecam akan kekal dipesan mengikut "tahap".

Tanda nod

Pertimbangan seterusnya yang akan membantu meningkatkan prestasi ialah − "daun" tidak boleh mempunyai anak, iaitu, bagi mereka tidak perlu melihat "ke bawah" sama sekali. Dalam rumusan tugasan kami, ini bermakna jika kami mengikuti rangkaian jabatan dan mencapai seorang pekerja, maka tidak perlu melihat lebih jauh di sepanjang cawangan ini.

Jom masuk ke dalam meja kami tambahan boolean-padang, yang akan segera memberitahu kami sama ada entri tertentu dalam pokok kami ini ialah "nod" - iaitu, sama ada ia boleh mempunyai keturunan sama sekali.

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 мс.

Hebat! Ternyata hanya lebih sedikit daripada 30% daripada semua unsur pokok mempunyai keturunan.

Sekarang mari kita gunakan mekanik yang sedikit berbeza - sambungan ke bahagian rekursif melalui LATERAL, yang akan membolehkan kami mengakses dengan segera medan "jadual" rekursif dan menggunakan fungsi agregat dengan keadaan penapisan berdasarkan nod untuk mengurangkan set kunci:

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;

[lihat explain.tensor.ru]

Kami dapat mengurangkan satu lagi panggilan indeks dan menang lebih daripada 2 kali dalam jumlah baca pruf.

#2. Mari kita kembali ke akar umbi

Algoritma ini berguna jika anda perlu mengumpul rekod untuk semua elemen "up the tree", sambil mengekalkan maklumat tentang helaian sumber (dan dengan penunjuk apa) yang menyebabkannya dimasukkan ke dalam sampel - contohnya, untuk menjana laporan ringkasan dengan pengagregatan ke dalam nod.

Perkara berikut harus diambil semata-mata sebagai bukti konsep, kerana permintaan itu ternyata sangat menyusahkan. Tetapi jika ia menguasai pangkalan data anda, anda harus berfikir tentang menggunakan teknik yang serupa.

Mari kita mulakan dengan beberapa pernyataan mudah:

Rekod yang sama dari pangkalan data Sebaiknya baca sekali sahaja.
Rekod daripada pangkalan data Ia lebih cekap untuk membaca secara berkelompokdaripada bersendirian.

Sekarang mari kita cuba membina permintaan yang kita perlukan.

Langkah 1

Jelas sekali, apabila memulakan rekursi (di manakah kita tanpanya!) kita perlu menolak rekod daun itu sendiri berdasarkan set pengecam awal:

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
  ...

Jika seseorang kelihatan pelik bahawa "set" disimpan sebagai rentetan dan bukan tatasusunan, maka terdapat penjelasan mudah untuk ini. Terdapat fungsi "pelekatan" agregat terbina dalam untuk rentetan string_agg, tetapi bukan untuk tatasusunan. Walaupun dia mudah untuk dilaksanakan sendiri.

Langkah 2

Sekarang kita akan mendapat satu set ID bahagian yang perlu dibaca lebih lanjut. Hampir selalu mereka akan diduplikasi dalam rekod berbeza set asal - jadi kami akan melakukannya kumpulan mereka, sambil mengekalkan maklumat tentang daun sumber.

Tetapi di sini tiga masalah menanti kita:

Bahagian "subrekursif" pertanyaan tidak boleh mengandungi fungsi agregat dengan GROUP BY.
Rujukan kepada "jadual" rekursif tidak boleh dalam subkueri bersarang.
Permintaan dalam bahagian rekursif tidak boleh mengandungi CTE.

Nasib baik, semua masalah ini agak mudah untuk diselesaikan. Mari kita mulakan dari akhir.

CTE dalam bahagian rekursif

Di sini begitu tiada berfungsi:

WITH RECURSIVE tree AS (
  ...
UNION ALL
  WITH T (...)
  SELECT ...
)

Jadi ia berfungsi, kurungan membuat perbezaan!

WITH RECURSIVE tree AS (
  ...
UNION ALL
  (
    WITH T (...)
    SELECT ...
  )
)

Pertanyaan bersarang terhadap "jadual" rekursif

Hmm... CTE rekursif tidak boleh diakses dalam subkueri. Tetapi ia boleh berada di dalam CTE! Dan permintaan bersarang sudah boleh mengakses CTE ini!

KUMPULAN MENGIKUT rekursi dalam

Ia tidak menyenangkan, tetapi... Kami mempunyai cara mudah untuk meniru GROUP BY menggunakan DISTINCT ON dan fungsi tetingkap!

SELECT
  (rec).pid id
, string_agg(chld::text, ',') chld
FROM
  tree
WHERE
  (rec).pid IS NOT NULL
GROUP BY 1 -- не работает!

Dan ini adalah cara ia berfungsi!

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

Sekarang kita melihat mengapa ID berangka ditukar kepada teks - supaya ia boleh dicantumkan bersama dipisahkan dengan koma!

Langkah 3

Untuk perlawanan akhir kami tidak mempunyai apa-apa lagi:

kami membaca rekod "bahagian" berdasarkan set ID berkumpulan
kami membandingkan bahagian yang ditolak dengan "set" helaian asal
"kembangkan" rentetan set menggunakan 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;

[lihat explain.tensor.ru]

Sumber: www.habr.com

Antipattern PostgreSQL: Sejauh manakah lubang arnab? mari kita melalui hierarki

#1. Berapa dalam lubang arnab?

Bacaan pruf pukal mengikut indeks

Tanda nod

#2. Mari kita kembali ke akar umbi

Langkah 1

Langkah 2

CTE dalam bahagian rekursif

Pertanyaan bersarang terhadap "jadual" rekursif

KUMPULAN MENGIKUT rekursi dalam

Langkah 3

Tambah komen Batal reply