Data hierarki dengan PostgreSQL dan Spring Data JPA

Dia yang menanam pokok,
Menanam harapan.
       Tanam pokok oleh Lucy Larcom ?

Pengenalan

Dalam siaran ini saya akan menunjukkan kepada anda beberapa pilihan untuk mengurus data hierarki yang diwakili sebagai struktur data pokok. Ini adalah pendekatan semula jadi apabila anda perlu melaksanakan perkara seperti:

• laluan sistem fail
• carta organisasi
• komen forum perbincangan
• topik yang lebih kontemporari: cari semula small2big untuk aplikasi RAG

Jika anda tahu apa itu graf, pokok pada asasnya ialah graf tanpa sebarang kitaran. Anda boleh mewakilinya secara visual seperti ini.

Terdapat pelbagai alternatif untuk menyimpan pokok dalam pangkalan data hubungan. Dalam bahagian di bawah, saya akan menunjukkan kepada anda tiga daripadanya:

• senarai bersebelahan
• laluan terwujud
• set bersarang

Akan ada dua bahagian untuk catatan blog ini. Dalam yang pertama ini alternatif diperkenalkan dan anda melihat cara memuatkan dan menyimpan data - asasnya. Setelah itu, di bahagian kedua, tumpuan lebih kepada perbandingan dan pertukaran mereka, contohnya saya ingin melihat apa yang berlaku pada peningkatan volum data dan apakah strategi pengindeksan yang sesuai.

Semua kod yang anda akan lihat dalam bahagian di bawah boleh didapati di sini jika anda berminat untuk menyemaknya.

Kes penggunaan yang sedang dijalankan ialah pekerja dan pengurus mereka, dan ID untuk setiap satu ialah yang anda lihat dalam visualisasi pokok yang saya tunjukkan di atas.

Persekitaran tempatan

Saya menggunakan Postgres 17 yang dikeluarkan baru-baru ini dengan Testcontainers. Ini memberi saya persediaan berulang untuk digunakan. Sebagai contoh, kita boleh menggunakan skrip SQL permulaan untuk mengautomasikan penciptaan pangkalan data Postgres dengan jadual yang diperlukan dan mengisi dengan beberapa data ujian.

@TestConfiguration(proxyBeanMethods = false)
class TestcontainersConfiguration {

    private static final String POSTGRES = "postgres";

    @Bean
    @ServiceConnection
    PostgreSQLContainer<?> postgresContainer() {
        return new PostgreSQLContainer<>(DockerImageName.parse("postgres:latest"))
                .withUsername(POSTGRES)
                .withPassword(POSTGRES)
                .withDatabaseName(POSTGRES)
                .withInitScript("init-script.sql");
    }
}

Mari masuk dan lihat pendekatan pertama.

1. Model senarai bersebelahan

Ini adalah penyelesaian pertama untuk mengurus data hierarki, jadi kami boleh menjangkakan bahawa ia masih terdapat secara meluas dalam pangkalan kod, oleh itu kemungkinan besar anda mungkin menemuinya suatu masa nanti. Ideanya ialah kami menyimpan ID induk pengurus, atau lebih umum, ID induk dalam baris yang sama. Ia akan menjadi jelas dengan cepat apabila kita melihat struktur jadual.

Skema

Jadual yang sepadan dengan pilihan senarai bersebelahan kelihatan seperti ini:

create table employees
(
    id           bigserial primary key,
    manager_id   bigint references employees
    name         text,
);

Selain perkara di atas, untuk memastikan integriti data, kami juga harus menulis semakan kekangan yang memastikan sekurang-kurangnya perkara berikut:

• terdapat ibu bapa tunggal untuk setiap nod
• tiada kitaran

Menjana data ujian

Terutama untuk Bahagian 2 siri ini, kami memerlukan cara untuk menjana seberapa banyak data yang kami mahu untuk mengisi skema. Mari kita lakukan pada mulanya langkah demi langkah untuk kejelasan, kemudian selepas itu secara rekursif.

Langkah demi langkah

Kami bermula dengan mudah dengan memasukkan tiga peringkat pekerja dalam hierarki secara eksplisit.

Anda mungkin sudah tahu tentang CTE dalam Postgres - ia adalah pertanyaan bernama tambahan yang dilaksanakan dalam konteks pertanyaan utama. Di bawah, anda boleh melihat cara saya membina setiap peringkat berdasarkan tahap sebelumnya.

@TestConfiguration(proxyBeanMethods = false)
class TestcontainersConfiguration {

    private static final String POSTGRES = "postgres";

    @Bean
    @ServiceConnection
    PostgreSQLContainer<?> postgresContainer() {
        return new PostgreSQLContainer<>(DockerImageName.parse("postgres:latest"))
                .withUsername(POSTGRES)
                .withPassword(POSTGRES)
                .withDatabaseName(POSTGRES)
                .withInitScript("init-script.sql");
    }
}

Mari sahkan bahawa ia berfungsi seperti yang diharapkan setakat ini, dan untuk tujuan ini lakukan kiraan untuk melihat berapa banyak elemen yang telah dimasukkan. Anda boleh membandingkannya dengan bilangan nod dalam visualisasi pokok yang saya tunjukkan pada permulaan siaran ini.

create table employees
(
    id           bigserial primary key,
    manager_id   bigint references employees
    name         text,
);

Nampak ok! Tiga tahap, dan secara keseluruhan kami mendapat 15 nod.

Masa untuk beralih kepada pendekatan rekursif.

rekursif

Menulis pertanyaan rekursif mengikut prosedur standard. Kami mentakrifkan langkah asas dan langkah rekursif kemudian "sambungkan" antara satu sama lain menggunakan kesatuan semua. Pada masa runtime Postgres akan mengikuti resipi ini dan menjana semua hasil kami. Sila lihat.

with root as (
  insert into 
    employees(manager_id, name)
      select 
        null, 
        'root' || md5(random()::text) 
      from  
        generate_series(1, 1) g
      returning 
        employees.id
  ),
  first_level as (
    insert into 
      employees(manager_id, name)
        select 
          root.id, 
          'first_level' || md5(random()::text) 
        from 
          generate_series(1, 2) g, 
          root
        returning 
          employees.id
  ),
  second_level as (
    insert into 
      employees(manager_id, name)
        select 
          first_level.id, 
          'second_level' || md5(random()::text) 
        from 
          generate_series(1, 2) g, 
          first_level
        returning 
          employees.id
  )
insert into 
  employees(manager_id, name)
select 
  second_level.id, 
  'third_level' || md5(random()::text) 
from 
  generate_series(1, 2) g, 
  second_level;

Selepas menjalankannya, mari kita buat kiraan sekali lagi untuk melihat sama ada bilangan elemen yang sama dimasukkan.

postgres=# select count(*) from employees;
 count 
-------
 15
(1 row)

Sejuk! Kami dalam perniagaan. Kami kini boleh mengisi skema dengan berapa banyak tahap dan elemen yang kami mahu, dan dengan itu, mengawal sepenuhnya kelantangan yang dimasukkan. Jangan risau jika buat masa ini pertanyaan rekursif masih kelihatan agak sukar, kami sebenarnya akan menyemaknya semula sedikit kemudian dengan kesempatan menulis pertanyaan untuk mendapatkan semula data.

Buat masa ini, mari kita teruskan untuk melihat entiti Hibernate yang boleh kita gunakan untuk memetakan jadual kita ke kelas Java.

create temporary sequence employees_id_seq;
insert into employees (id, manager_id, name)
with recursive t(id, parent_id, level, name) AS
(
  select 
    nextval('employees_id_seq')::bigint,
    null::bigint, 
    1, 
    'root' from generate_series(1,1) g

    union all

    select 
      nextval('employees_id_seq')::bigint, 
      t.id, 
      level+1, 
      'level' || level || '-' || md5(random()::text) 
    from 
      t, 
      generate_series(1,2) g
    where 
      level < 4
)
select 
  id, 
  parent_id, 
  name 
from 
  t;
drop sequence employees_id_seq;

Tiada apa-apa yang istimewa, hanya hubungan satu dengan ramai antara pengurus dan pekerja. Anda melihat ini datang. Mari mulakan pertanyaan.

Keturunan

Semua orang bawahan pengurus

Untuk mendapatkan semula semua pekerja yang merupakan bawahan pengurus tertentu yang dirujuk oleh ID beliau, kami akan menulis pertanyaan rekursif sekali lagi. Anda akan melihat sekali lagi langkah asas dan langkah rekursif yang dipautkan dengan langkah asas. Postgres kemudian akan mengulangi ini dan mendapatkan semula semua baris yang berkaitan untuk pertanyaan. Mari kita ambil pekerja dengan ID = 2 sebagai contoh. Ini ialah perwakilan visual yang memudahkan untuk memahami perkara yang baru saya jelaskan. Saya tidak memasukkan semua keputusan, hanya beberapa yang pertama.

Berikut ialah pertanyaan JPQL untuk menanyakan keturunan:

@TestConfiguration(proxyBeanMethods = false)
class TestcontainersConfiguration {

    private static final String POSTGRES = "postgres";

    @Bean
    @ServiceConnection
    PostgreSQLContainer<?> postgresContainer() {
        return new PostgreSQLContainer<>(DockerImageName.parse("postgres:latest"))
                .withUsername(POSTGRES)
                .withPassword(POSTGRES)
                .withDatabaseName(POSTGRES)
                .withInitScript("init-script.sql");
    }
}

Dalam pertanyaan seperti di atas, untuk menjadikannya lebih bersih dan mengelakkan keperluan untuk menulis nama rekod yang layak sepenuhnya, kami akan menulis hasilnya, kami boleh menggunakan perpustakaan hypersistence-utils untuk menulis ClassImportIntegratorProvider:

create table employees
(
    id           bigserial primary key,
    manager_id   bigint references employees
    name         text,
);

Menyemak pertanyaan yang dijana

Ia berfungsi, tetapi mari kita lihat dengan lebih mendalam tentang perkara yang dijana oleh Hibernate. Ia sentiasa baik untuk memahami apa yang berlaku di bawah hud, jika tidak, kami mungkin mengalami ketidakcekapan yang akan berlaku dengan setiap permintaan pengguna, ini akan bertambah.

Kita perlu memulakan apl Spring Boot dengan tetapan berikut:

with root as (
  insert into 
    employees(manager_id, name)
      select 
        null, 
        'root' || md5(random()::text) 
      from  
        generate_series(1, 1) g
      returning 
        employees.id
  ),
  first_level as (
    insert into 
      employees(manager_id, name)
        select 
          root.id, 
          'first_level' || md5(random()::text) 
        from 
          generate_series(1, 2) g, 
          root
        returning 
          employees.id
  ),
  second_level as (
    insert into 
      employees(manager_id, name)
        select 
          first_level.id, 
          'second_level' || md5(random()::text) 
        from 
          generate_series(1, 2) g, 
          first_level
        returning 
          employees.id
  )
insert into 
  employees(manager_id, name)
select 
  second_level.id, 
  'third_level' || md5(random()::text) 
from 
  generate_series(1, 2) g, 
  second_level;

Baiklah, mari kita lihat. Berikut ialah pertanyaan untuk keturunan yang dijana oleh Hibernate.

postgres=# select count(*) from employees;
 count 
-------
 15
(1 row)

Hmm - kelihatan lebih rumit daripada yang dijangkakan! Mari lihat jika kita boleh memudahkannya sedikit, dengan mengingati gambar yang saya tunjukkan sebelum ini tentang langkah asas dan langkah rekursif yang dikaitkan dengan langkah asas. Kita tidak perlu melakukan lebih daripada itu. Lihat pendapat anda tentang perkara berikut.

create temporary sequence employees_id_seq;
insert into employees (id, manager_id, name)
with recursive t(id, parent_id, level, name) AS
(
  select 
    nextval('employees_id_seq')::bigint,
    null::bigint, 
    1, 
    'root' from generate_series(1,1) g

    union all

    select 
      nextval('employees_id_seq')::bigint, 
      t.id, 
      level+1, 
      'level' || level || '-' || md5(random()::text) 
    from 
      t, 
      generate_series(1,2) g
    where 
      level < 4
)
select 
  id, 
  parent_id, 
  name 
from 
  t;
drop sequence employees_id_seq;

Lebih baik! Kami mengalih keluar beberapa sambungan yang tidak perlu. Ini dijangka membuat pertanyaan berjalan lebih pantas kerana ia akan mempunyai lebih sedikit kerja untuk dilakukan.

Keputusan akhir

Sebagai langkah terakhir mari kita bersihkan pertanyaan dan gantikan nama jadual yang Hibernate tambahkan dengan nama yang lebih mudah dibaca oleh manusia.

postgres=# select count(*) from employees;
 count 
-------
 15
(1 row)

Baiklah, masa untuk melihat cara kita "naik" pokok.

Nenek moyang

Semua pengurus dalam rangkaian

Mari kita cuba tuliskan langkah-langkah konseptual untuk mendapatkan pengurus pekerja dengan ID = 14.

Kelihatan sangat seperti yang untuk keturunan, cuma sambungan antara langkah asas dan langkah rekursif adalah sebaliknya.

Kita boleh menulis pertanyaan JPQL kelihatan seperti ini:

@Entity
@Table(name = "employees")
@Getter
@Setter
public class Employee {
    @Id
    private Long id;

    private String name;

    @ManyToOne(fetch = FetchType.LAZY)
    @JoinColumn(name = "manager_id")
    private Employee manager;

    @OneToMany(
            mappedBy = "parent",
            cascade = CascadeType.ALL,
            orphanRemoval = true
    )
    private List<Employee> employees = new ArrayList<>();
}

Dan itu sahaja! Saya telah melihat pertanyaan SQL yang dihasilkan tetapi saya tidak dapat mencari sebarang arahan tambahan yang boleh saya cukur. Masa untuk terus menghampiri 2.

2. Laluan terwujud

ltree ialah sambungan Postgres yang boleh kami gunakan untuk bekerja dengan struktur pokok hierarki sebagai laluan terwujud (bermula dari bahagian atas pokok). Sebagai contoh, ini adalah bagaimana kita akan merekodkan laluan untuk nod daun 8: 1.2.4.8. Terdapat beberapa fungsi berguna yang disertakan. Kita boleh menggunakannya sebagai lajur jadual:

return entityManager.createQuery("""
 with employeeRoot as (
  select
    employee.employees employee
  from
    Employee employee
  where
    employee.id = :employeeId

  union all

  select
    employee.employees employee
  from
    Employee employee
  join
    employeeRoot root ON employee = root.employee
  order by
    employee.id
  )
  select 
    new Employee(
     root.employee.id
   )
  from 
  employeeRoot root
 """, Employee.class
)
 .setParameter("employeeId", employeeId)
 .getResultList();

Untuk mengisi jadual di atas dengan data ujian, pendekatan yang saya ambil pada asasnya ialah memindahkan data yang dijana daripada jadual yang digunakan untuk senarai bersebelahan yang anda lihat sebelum ini, menggunakan arahan SQL berikut. Ia sekali lagi merupakan pertanyaan rekursif yang mengumpul elemen menjadi penumpuk pada setiap langkah.

public class ClassImportIntegratorProvider implements IntegratorProvider {
    @Override
    public List<Integrator> getIntegrators() {
        return List.of(
                new ClassImportIntegrator(
                        singletonList(
                                Employee.class
                        )
                )
        );
    }
}

Berikut ialah entri yang dijana oleh arahan di atas.

@TestConfiguration(proxyBeanMethods = false)
class TestcontainersConfiguration {

    private static final String POSTGRES = "postgres";

    @Bean
    @ServiceConnection
    PostgreSQLContainer<?> postgresContainer() {
        return new PostgreSQLContainer<>(DockerImageName.parse("postgres:latest"))
                .withUsername(POSTGRES)
                .withPassword(POSTGRES)
                .withDatabaseName(POSTGRES)
                .withInitScript("init-script.sql");
    }
}

Kita boleh meneruskan untuk menulis entiti Hibernate. Untuk memetakan lajur jenis ltree, saya melaksanakan UserType. Saya kemudiannya boleh memetakan medan laluan dengan @Type(LTreeType.class):

create table employees
(
    id           bigserial primary key,
    manager_id   bigint references employees
    name         text,
);

Kami bersedia untuk menulis beberapa pertanyaan. Dalam SQL asli, ia akan kelihatan seperti berikut:

with root as (
  insert into 
    employees(manager_id, name)
      select 
        null, 
        'root' || md5(random()::text) 
      from  
        generate_series(1, 1) g
      returning 
        employees.id
  ),
  first_level as (
    insert into 
      employees(manager_id, name)
        select 
          root.id, 
          'first_level' || md5(random()::text) 
        from 
          generate_series(1, 2) g, 
          root
        returning 
          employees.id
  ),
  second_level as (
    insert into 
      employees(manager_id, name)
        select 
          first_level.id, 
          'second_level' || md5(random()::text) 
        from 
          generate_series(1, 2) g, 
          first_level
        returning 
          employees.id
  )
insert into 
  employees(manager_id, name)
select 
  second_level.id, 
  'third_level' || md5(random()::text) 
from 
  generate_series(1, 2) g, 
  second_level;

Tetapi mari tulis pertanyaan kami dalam JPQL. Untuk ini, kami perlu menulis StandardSQLFunction tersuai kami dahulu. Ini akan membolehkan kami mentakrifkan penggantian untuk pengendali asli Postgres.

postgres=# select count(*) from employees;
 count 
-------
 15
(1 row)

Kami kemudiannya perlu mendaftarkannya sebagai FunctionContributor, seperti:

create temporary sequence employees_id_seq;
insert into employees (id, manager_id, name)
with recursive t(id, parent_id, level, name) AS
(
  select 
    nextval('employees_id_seq')::bigint,
    null::bigint, 
    1, 
    'root' from generate_series(1,1) g

    union all

    select 
      nextval('employees_id_seq')::bigint, 
      t.id, 
      level+1, 
      'level' || level || '-' || md5(random()::text) 
    from 
      t, 
      generate_series(1,2) g
    where 
      level < 4
)
select 
  id, 
  parent_id, 
  name 
from 
  t;
drop sequence employees_id_seq;

Langkah terakhir ialah mencipta fail sumber dalam folder META-INF/services yang dipanggil org.hibernate.boot.model.FunctionContributor di mana kami akan menambah satu baris dengan nama kelas yang layak sepenuhnya di atas.

Baiklah, bagus! Kami akhirnya berada dalam kedudukan untuk menulis pertanyaan berikut:

postgres=# select count(*) from employees;
 count 
-------
 15
(1 row)

Sebagai contoh, kita boleh memanggil kaedah ini seperti ini untuk mendapatkan semula semua laluan yang mengandungi ID = 2:

@Entity
@Table(name = "employees")
@Getter
@Setter
public class Employee {
    @Id
    private Long id;

    private String name;

    @ManyToOne(fetch = FetchType.LAZY)
    @JoinColumn(name = "manager_id")
    private Employee manager;

    @OneToMany(
            mappedBy = "parent",
            cascade = CascadeType.ALL,
            orphanRemoval = true
    )
    private List<Employee> employees = new ArrayList<>();
}

Postgres menawarkan satu set fungsi yang luas untuk bekerja dengan ltrees. Anda boleh menemuinya dalam halaman dokumen rasmi. Selain itu, terdapat helaian curang yang berguna.

Adalah penting untuk menambah kekangan pada skema kami untuk memastikan ketekalan data - berikut ialah sumber yang bagus yang saya temui tentang topik ini.

3. Set bersarang

Paling mudah difahami ialah dengan imej yang menunjukkan gerak hati. Pada setiap nod pokok kami mempunyai lajur "kiri" dan "kanan" tambahan selain IDnya. Peraturannya ialah semua anak mempunyai kiri dan kanan di antara nilai kiri dan kanan ibu bapa mereka.

Berikut ialah struktur jadual untuk mewakili pokok di atas.

return entityManager.createQuery("""
 with employeeRoot as (
  select
    employee.employees employee
  from
    Employee employee
  where
    employee.id = :employeeId

  union all

  select
    employee.employees employee
  from
    Employee employee
  join
    employeeRoot root ON employee = root.employee
  order by
    employee.id
  )
  select 
    new Employee(
     root.employee.id
   )
  from 
  employeeRoot root
 """, Employee.class
)
 .setParameter("employeeId", employeeId)
 .getResultList();

Untuk mengisi jadual, saya telah menukar skrip daripada buku "SQL for smarties" Joe Celko kepada sintaks Postgres. Ini dia:

public class ClassImportIntegratorProvider implements IntegratorProvider {
    @Override
    public List<Integrator> getIntegrators() {
        return List.of(
                new ClassImportIntegrator(
                        singletonList(
                                Employee.class
                        )
                )
        );
    }
}

Baiklah, saya bersedia untuk melakukan beberapa pertanyaan. Begini cara untuk mendapatkan semula nenek moyang.

@DynamicPropertySource
static void registerPgProperties(DynamicPropertyRegistry registry) {
    registry.add("spring.jpa.show_sql", () -> true);
}

Untuk keturunan, kita perlu mendapatkan semula kiri dan kanan, selepas itu kita boleh menggunakan pertanyaan di bawah.

with recursive employeeRoot (employee_id) as 
(
select 
  e1_0.id
from 
  employees eal1_0
join 
  employees e1_0 on eal1_0.id = e1_0.manager_id
where eal1_0.id=?

union all

(
select 
  e2_0.id
from 
  employees eal2_0
join 
  employeeRoot root1_0 on eal2_0.id = root1_0.employee_id
join 
  employees e2_0 on eal2_0.id = e2_0.manager_id
order by 
  eal2_0.id
)
)
select 
  root2_0.employee_id
from 
  employeeRoot root2_0

Dan itu sahaja! Anda telah melihat cara untuk naik atau turun pokok untuk ketiga-tiga pendekatan. Saya harap anda menikmati perjalanan ini dan anda rasa ia berguna.

Pangkalan data postgres lwn. dokumen/graf

Pangkalan data yang kami gunakan untuk contoh di atas ialah PostgreSQL. Ia bukan satu-satunya pilihan, contohnya anda mungkin tertanya-tanya mengapa tidak memilih pangkalan data dokumen seperti MongoDB, atau pangkalan data graf seperti Neo4j, kerana ia sebenarnya dibina dengan mengambil kira jenis beban kerja ini.

Kemungkinan, anda sudah mempunyai sumber data kebenaran anda dalam Postgres dalam model hubungan yang memanfaatkan jaminan transaksi. Dalam kes itu, anda harus terlebih dahulu menyemak sejauh mana Postgres sendiri mengendalikan kes penggunaan tambahan anda juga, untuk memastikan semuanya berada di satu tempat. Dengan cara ini, anda akan mengelakkan peningkatan kos dan kerumitan operasi yang diperlukan untuk memutar dan menyelenggara/meningkatkan stor data khusus berasingan baharu, serta perlu membiasakan diri dengannya.

Kesimpulan

Terdapat beberapa pilihan menarik untuk memodelkan data hierarki dalam aplikasi pangkalan data anda. Dalam siaran ini saya telah menunjukkan kepada anda tiga cara untuk melakukannya. Nantikan Bahagian 2 di mana kami akan membandingkannya serta melihat apa yang berlaku dengan volum data yang lebih besar.

Rujukan

https://dev.to/yugabyte/learn-how-to-write-sql-recursive-cte-in-5-steps-3n88
https://vladmihalcea.com/hibernate-with-recursive-query/
https://vladmihalcea.com/dto-projection-jpa-query/
https://tudborg.com/posts/2022-02-04-postgres-hierarchical-data-with-ltree/
https://aregall.tech/hibernate-6-custom-functions#heading-implementing-a-custom-function
https://www.amazon.co.uk/Joe-Celkos-SQL-Smarties-Programming/dp/0128007613
https://madecurious.com/curiosities/trees-in-postgresql/
https://schinckel.net/2014/11/27/postgres-tree-shootout-part-2:-adjacency-list-using-ctes/

Atas ialah kandungan terperinci Data hierarki dengan PostgreSQL dan Spring Data JPA. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!