Saya perlu menghitung kedalaman keturunan dari leluhurnya. Ketika sebuah catatan memiliki object_id = parent_id = ancestor_id
, itu dianggap sebagai simpul akar (leluhur). Saya telah mencoba WITH RECURSIVE
menjalankan kueri dengan PostgreSQL 9.4 .
Saya tidak mengontrol data atau kolom. Skema data dan tabel berasal dari sumber eksternal. Meja tumbuh terus menerus . Saat ini sekitar 30 ribu catatan per hari. Setiap simpul di pohon dapat hilang dan mereka akan ditarik dari sumber eksternal di beberapa titik. Mereka biasanya ditarik dalam created_at DESC
urutan tetapi data ditarik dengan pekerjaan latar belakang asinkron.
Kami awalnya memiliki solusi kode untuk masalah ini, tetapi sekarang memiliki 5M + baris, dibutuhkan hampir 30 menit untuk menyelesaikannya.
Definisi tabel contoh dan data uji:
CREATE TABLE objects (
id serial NOT NULL PRIMARY KEY,
customer_id integer NOT NULL,
object_id integer NOT NULL,
parent_id integer,
ancestor_id integer,
generation integer NOT NULL DEFAULT 0
);
INSERT INTO objects(id, customer_id , object_id, parent_id, ancestor_id, generation)
VALUES (2, 1, 2, 1, 1, -1), --no parent yet
(3, 2, 3, 3, 3, -1), --root node
(4, 2, 4, 3, 3, -1), --depth 1
(5, 2, 5, 4, 3, -1), --depth 2
(6, 2, 6, 5, 3, -1), --depth 3
(7, 1, 7, 7, 7, -1), --root node
(8, 1, 8, 7, 7, -1), --depth 1
(9, 1, 9, 8, 7, -1); --depth 2
Perhatikan itu object_id
tidak unik, tetapi kombinasinya (customer_id, object_id)
unik.
Menjalankan kueri seperti ini:
WITH RECURSIVE descendants(id, customer_id, object_id, parent_id, ancestor_id, depth) AS (
SELECT id, customer_id, object_id, parent_id, ancestor_id, 0
FROM objects
WHERE object_id = parent_id
UNION
SELECT o.id, o.customer_id, o.object_id, o.parent_id, o.ancestor_id, d.depth + 1
FROM objects o
INNER JOIN descendants d ON d.parent_id = o.object_id
WHERE
d.id <> o.id
AND
d.customer_id = o.customer_id
) SELECT * FROM descendants d;
Saya ingin generation
kolom ditetapkan sebagai kedalaman yang dihitung. Ketika catatan baru ditambahkan, kolom generasi diatur sebagai -1. Ada beberapa kasus di mana a parent_id
mungkin belum ditarik. Jika parent_id
tidak ada, seharusnya membiarkan kolom generasi diatur ke -1.
Data akhir akan terlihat seperti:
id | customer_id | object_id | parent_id | ancestor_id | generation
2 1 2 1 1 -1
3 2 3 3 3 0
4 2 4 3 3 1
5 2 5 4 3 2
6 2 6 5 3 3
7 1 7 7 7 0
8 1 8 7 7 1
9 1 9 8 7 2
Hasil kueri harus memperbarui kolom generasi ke kedalaman yang benar.
Saya mulai bekerja dari jawaban untuk pertanyaan terkait ini di SO .
sumber
update
meja dengan hasil CTE rekursif Anda?ancestor_id
sudah diatur, jadi Anda hanya perlu menetapkan generasi dari CTE.depth?Jawaban:
Permintaan yang Anda miliki pada dasarnya benar. Satu-satunya kesalahan adalah di bagian kedua (rekursif) dari CTE di mana Anda memiliki:
Itu harus sebaliknya:
Anda ingin bergabung dengan benda-benda dengan orang tua mereka (yang telah ditemukan).
Jadi kueri yang menghitung kedalaman dapat ditulis (tidak ada yang berubah, hanya memformat):
Untuk pembaruan, Anda cukup mengganti yang terakhir
SELECT
, denganUPDATE
, bergabung dengan hasil dari cte, kembali ke tabel:Diuji pada SQLfiddle
Komentar tambahan:
ancestor_id
danparent_id
tidak perlu berada di daftar pilih (leluhur yang jelas, orang tua sedikit sulit untuk mencari tahu mengapa), sehingga Anda dapat menjaga mereka diSELECT
query jika Anda inginkan, tetapi Anda dapat dengan aman menghapus mereka dariUPDATE
.(customer_id, object_id)
tampaknya seperti kandidat untukUNIQUE
kendala. Jika data Anda mematuhi ini, tambahkan kendala seperti itu. Gabungan yang dilakukan dalam CTE rekursif tidak akan masuk akal jika tidak unik (sebuah simpul bisa memiliki 2 orang tua sebaliknya).(customer_id, parent_id)
akan menjadi kandidat untukFOREIGN KEY
kendala yangREFERENCES
(unik)(customer_id, object_id)
. Anda kemungkinan besar tidak ingin menambahkan batasan FK itu, karena dengan uraian Anda, Anda menambahkan baris baru dan beberapa baris dapat mereferensikan yang lain yang belum ditambahkan.The
AND o.generation = -1
di update akhir akan memastikan bahwa baris yang diperbarui pada tanggal 1 run tidak akan diperbarui lagi tapi CTE masih merupakan bagian yang mahal.Berikut ini adalah upaya untuk mengatasi masalah ini: tingkatkan CTE dengan mempertimbangkan beberapa baris sebanyak mungkin dan gunakan
(customer_id, obejct_id)
alih-alih(id)
mengidentifikasi baris (sehinggaid
sepenuhnya dihapus dari kueri. Dapat digunakan sebagai pembaruan pertama atau berikutnya:Perhatikan bagaimana CTE memiliki 3 bagian. Dua yang pertama adalah bagian yang stabil. Bagian 1 menemukan node root yang belum diperbarui sebelumnya dan masih
generation=-1
jadi mereka harus ditambahkan node baru. Bagian ke-2 menemukan anak-anak (dengangeneration=-1
) dari simpul orangtua yang sebelumnya telah diperbarui.Bagian ke-3, rekursif, menemukan semua keturunan dari dua bagian pertama, seperti sebelumnya.
Diuji pada SQLfiddle-2
sumber
@ ypercube sudah memberikan penjelasan yang cukup, jadi saya akan memotong apa yang harus saya tambahkan.
Saya menganggap ini seharusnya diterapkan secara rekursif, yaitu sisa pohon selalu memiliki
generation = -1
setelah simpul yang hilang.Jika ada simpul di pohon dapat hilang (belum) kita perlu mencari baris dengan
generation = -1
itu ...... adalah simpul root
... atau memiliki orangtua dengan
generation > -1
.Dan lintasi pohon itu dari sana. Node anak dari pilihan ini juga harus dimiliki
generation = -1
.Ambil salah satu
generation
dari induk yang bertambah satu atau turun kembali ke 0 untuk simpul root:Bagian non-rekursif adalah tunggal
SELECT
dengan cara ini, tetapi secara logis setara dengan dua penyatuan @ ypercubeSELECT
. Tidak yakin mana yang lebih cepat, Anda harus menguji.Poin yang jauh lebih penting untuk kinerja adalah:
Indeks!
Jika Anda berulang kali menambahkan baris ke tabel besar dengan cara ini, tambahkan sebagian indeks :
Ini akan mencapai lebih banyak untuk kinerja daripada semua perbaikan lain yang dibahas sejauh ini - untuk penambahan kecil berulang ke tabel besar.
Saya menambahkan kondisi indeks ke bagian rekursif CTE (meskipun secara logis berlebihan) untuk membantu perencana kueri memahami bahwa indeks parsial berlaku.
Selain itu Anda mungkin juga harus memiliki
UNIQUE
kendala pada(object_id, customer_id)
@ ypercube yang telah disebutkan. Atau, jika Anda tidak dapat memaksakan keunikan karena alasan tertentu (mengapa?) Tambahkan indeks biasa saja. Urutan kolom indeks penting, antara:sumber
ON objects (customer_id, parent_id, object_id) WHERE generation = -1;
dan mungkin yang lainON objects (customer_id, object_id) WHERE generation > -1;
. Pembaruan juga harus "mengalihkan" semua baris yang diperbarui dari satu indeks ke indeks lain, jadi tidak yakin apakah ini adalah ide yang baik untuk menjalankan awal UPDATE.