Hierarchische Daten mit PostgreSQL und Spring Data JPA

Wer einen Baum pflanzt,
Pflanzen eine Hoffnung.
       Einen Baum pflanzen von Lucy Larcom ?

Einführung

In diesem Beitrag zeige ich Ihnen einige Optionen zum Verwalten hierarchischer Daten, die als Baum-Datenstruktur dargestellt werden. Dies ist der natürliche Ansatz, wenn Sie Dinge implementieren müssen wie:

• Dateisystempfade
• Organigramme
• Kommentare im Diskussionsforum
• ein aktuelleres Thema: small2big-Retrieval für RAG-Anwendungen

Wenn Sie bereits wissen, was ein Graph ist, ist ein Baum im Grunde ein Graph ohne Zyklen. Sie können eines visuell so darstellen.

Es gibt mehrere Alternativen zum Speichern von Bäumen in relationalen Datenbanken. In den folgenden Abschnitten zeige ich Ihnen drei davon:

• Adjazenzliste
• materialisierte Pfade
• verschachtelte Mengen

Dieser Blogbeitrag besteht aus zwei Teilen. In diesem ersten Teil werden die Alternativen vorgestellt und Sie erfahren, wie Sie Daten laden und speichern – die Grundlagen. Nachdem dies geklärt ist, liegt der Schwerpunkt im zweiten Teil eher auf deren Vergleich und Kompromissen. Ich möchte beispielsweise untersuchen, was bei erhöhten Datenmengen passiert und welche geeigneten Indexierungsstrategien es gibt.

Der gesamte Code, den Sie in den folgenden Abschnitten sehen, finden Sie hier, wenn Sie daran interessiert sind, ihn auszuprobieren.

Der laufende Anwendungsfall wird der von Mitarbeitern und ihren Managern sein, und die IDs für jeden werden genau die sein, die Sie in der oben gezeigten Baumvisualisierung gesehen haben.

Lokale Umgebung

Ich verwende das kürzlich veröffentlichte Postgres 17 mit Testcontainern. Dies gibt mir ein wiederholbares Setup, mit dem ich arbeiten kann. Beispielsweise können wir Initialisierungs-SQL-Skripte verwenden, um die Erstellung einer Postgres-Datenbank mit den erforderlichen Tabellen zu automatisieren und mit einigen Testdaten zu füllen.

@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");
    }
}

Lassen Sie uns einsteigen und einen Blick auf den ersten Ansatz werfen.

1. Das Adjazenzlistenmodell

Dies war die erste Lösung für die Verwaltung hierarchischer Daten. Daher können wir davon ausgehen, dass sie in Codebasen immer noch weit verbreitet ist. Daher ist die Wahrscheinlichkeit groß, dass Sie irgendwann darauf stoßen. Die Idee ist, dass wir die übergeordnete ID des Managers oder allgemeiner gesagt in derselben Zeile speichern. Es wird schnell klar, wenn wir uns die Tabellenstruktur ansehen.

Schema

Die Tabelle, die der Adjazenzlistenoption entspricht, sieht folgendermaßen aus:

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

Zusätzlich zu den oben genannten Punkten sollten wir zur Gewährleistung der Datenintegrität auch Einschränkungsprüfungen schreiben, die mindestens Folgendes sicherstellen:

• Für jeden Knoten gibt es einen einzigen übergeordneten Knoten
• keine Zyklen

Testdaten generieren

Insbesondere für Teil 2 dieser Serie benötigen wir eine Möglichkeit, so viele Daten zu generieren, wie wir möchten, um das Schema zu füllen. Machen wir es der Übersichtlichkeit halber zunächst Schritt für Schritt, anschließend rekursiv.

Schritt für Schritt

Wir beginnen einfach, indem wir explizit drei Ebenen von Mitarbeitern in die Hierarchie einfügen.

Vielleicht kennen Sie bereits CTEs in Postgres – dabei handelt es sich um benannte Hilfsabfragen, die im Kontext einer Hauptabfrage ausgeführt werden. Unten können Sie sehen, wie ich jedes Level auf der Grundlage des vorherigen Levels aufbaue.

@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");
    }
}

Überprüfen wir, ob es bisher wie erwartet funktioniert, und führen Sie zu diesem Zweck eine Zählung durch, um zu sehen, wie viele Elemente eingefügt wurden. Sie können es mit der Anzahl der Knoten in der Baumvisualisierung vergleichen, die ich am Anfang dieses Beitrags gezeigt habe.

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

Sieht gut aus! Drei Ebenen und insgesamt erhalten wir 15 Knoten.

Zeit, zum rekursiven Ansatz überzugehen.

Rekursiv

Das Schreiben rekursiver Abfragen erfolgt nach einem Standardverfahren. Wir definieren einen Basisschritt und einen rekursiven Schritt und „verbinden“ sie dann mithilfe von Union All miteinander. Zur Laufzeit folgt Postgres diesem Rezept und generiert alle unsere Ergebnisse. Schauen Sie mal vorbei.

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;

Nachdem wir es ausgeführt haben, führen wir noch einmal eine Zählung durch, um zu sehen, ob die gleiche Anzahl an Elementen eingefügt wurde.

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

Cool! Wir sind im Geschäft. Wir können das Schema nun mit beliebig vielen Ebenen und Elementen füllen und so das eingefügte Volumen vollständig steuern. Keine Sorge, wenn rekursive Abfragen vorerst noch etwas schwierig erscheinen, werden wir sie etwas später noch einmal aufgreifen, wenn wir die Abfragen schreiben, um die Daten abzurufen.

Lassen Sie uns zunächst einen Blick auf die Hibernate-Entität werfen, mit der wir unsere Tabelle einer Java-Klasse zuordnen können.

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;

Nichts Besonderes, nur eine Eins-zu-Viele-Beziehung zwischen Managern und Mitarbeitern. Du hast es kommen sehen. Beginnen wir mit der Abfrage.

Nachkommen

Alle Untergebenen eines Managers

Um alle Mitarbeiter abzurufen, die einem bestimmten Manager unterstellt sind, auf den sich seine ID bezieht, schreiben wir erneut eine rekursive Abfrage. Sie sehen wieder einen Basisschritt und einen rekursiven Schritt, der mit dem Basisschritt verknüpft ist. Postgres wiederholt dies dann und ruft alle relevanten Zeilen für die Abfrage ab. Nehmen wir als Beispiel den Mitarbeiter mit der ID = 2. Dies ist eine visuelle Darstellung, die es hoffentlich einfacher macht, das zu verstehen, was ich gerade beschrieben habe. Ich habe nicht alle Ergebnisse aufgeführt, sondern nur die ersten.

Hier ist die JPQL-Abfrage zum Abfragen von Nachkommen:

@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");
    }
}

Um sie sauberer zu machen und zu vermeiden, dass bei Abfragen wie der oben genannten der vollständig qualifizierte Name des Datensatzes geschrieben werden muss, in den wir die Ergebnisse schreiben, können wir die Hypersistence-Utils-Bibliothek verwenden, um einen ClassImportIntegratorProvider zu schreiben:

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

Überprüfung der generierten Abfragen

Es funktioniert, aber schauen wir uns genauer an, was Hibernate generiert hat. Es ist immer gut zu verstehen, was unter der Haube passiert, sonst kann es zu Ineffizienzen kommen, die bei jeder Benutzeranfrage auftreten und sich summieren.

Wir müssen die Spring Boot-App mit der folgenden Einstellung starten:

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;

Okay, lass uns einen Blick darauf werfen. Hier ist die Abfrage für die von Hibernate generierten Nachkommen.

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

Hmm – sieht etwas komplizierter aus als erwartet! Mal sehen, ob wir es ein wenig vereinfachen können, indem wir das Bild im Hinterkopf behalten, das ich Ihnen zuvor über den Basisschritt und den mit dem Basisschritt verknüpften rekursiven Schritt gezeigt habe. Mehr sollten wir nicht tun müssen. Sehen Sie, was Sie von Folgendem halten.

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;

Viel besser! Wir haben einige unnötige Verknüpfungen entfernt. Es wird erwartet, dass die Abfrage dadurch schneller wird, da weniger Arbeit erforderlich ist.

Endergebnis

Als letzten Schritt bereinigen wir die Abfrage und ersetzen die von Hibernate hinzugefügten Tabellennamen durch solche, die für den Menschen besser lesbar sind.

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

Okay, Zeit zu sehen, wie wir den Baum „rauf“ gehen.

Vorfahren

Alle Manager in der Kette

Versuchen wir zunächst, die konzeptionellen Schritte aufzuschreiben, um die Manager des Mitarbeiters mit der ID = 14 zu finden.

Sieht dem für die Nachkommen sehr ähnlich, nur die Verbindung zwischen dem Basisschritt und dem rekursiven Schritt ist umgekehrt.

Wir können die JPQL-Abfrage so schreiben:

@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<>();
}

Und das ist es! Ich habe mir die generierte SQL-Abfrage angesehen, konnte aber keine zusätzlichen Befehle finden, die ich weglassen könnte. Zeit, mit Ansatz 2 fortzufahren.

2. Materialisierte Pfade

ltree ist eine Postgres-Erweiterung, mit der wir mit hierarchischen Baumstrukturen als materialisierte Pfade arbeiten können (beginnend an der Spitze des Baums). So zeichnen wir beispielsweise den Pfad für Blattknoten 8 auf: 1.2.4.8. Es verfügt über mehrere nützliche Funktionen. Wir können es als Tabellenspalte verwenden:

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();

Um die obige Tabelle mit Testdaten zu füllen, habe ich im Grunde genommen die generierten Daten aus der Tabelle migriert, die für die Adjazenzliste verwendet wurde, die Sie zuvor gesehen haben, und zwar mithilfe des folgenden SQL-Befehls. Es handelt sich wiederum um eine rekursive Abfrage, die bei jedem Schritt Elemente in einem Akkumulator sammelt.

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

Hier sind die Einträge, die der obige Befehl generiert hat.

@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");
    }
}

Wir können mit dem Schreiben der Hibernate-Entität fortfahren. Um Spalten vom Typ ltree abzubilden, habe ich einen UserType implementiert. Ich kann dann das Pfadfeld mit @Type(LTreeType.class):
zuordnen

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

Wir sind bereit, einige Anfragen zu schreiben. In nativem SQL würde es wie folgt aussehen:

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;

Aber schreiben wir unsere Abfragen in JPQL. Dazu müssen wir zunächst unsere benutzerdefinierte StandardSQLFunction schreiben. Dadurch können wir einen Ersatz für den nativen Postgres-Operator definieren.

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

Wir müssen es dann als FunctionContributor registrieren, etwa so:

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;

Der letzte Schritt besteht darin, eine Ressourcendatei im Ordner META-INF/services mit dem Namen org.hibernate.boot.model.FunctionContributor zu erstellen, in der wir eine einzelne Zeile mit dem vollständig qualifizierten Namen der oben genannten Klasse hinzufügen.

Okay, cool! Endlich sind wir in der Lage, die folgende Abfrage zu schreiben:

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

Zum Beispiel können wir diese Methode so aufrufen, um alle Pfade abzurufen, die ID = 2:
enthalten

@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 bietet eine Vielzahl von Funktionen für die Arbeit mit Ltrees. Sie finden sie auf der offiziellen Dokumentenseite. Außerdem gibt es einen nützlichen Spickzettel.

Es ist wichtig, Einschränkungen zu unserem Schema hinzuzufügen, um die Datenkonsistenz sicherzustellen – hier ist eine gute Ressource, die ich zu diesem Thema gefunden habe.

3. Verschachtelte Mengen

Am einfachsten zu verstehen ist ein Bild, das die Intuition zeigt. An jedem Knoten des Baums haben wir neben seiner ID eine zusätzliche „linke“ und eine „rechte“ Spalte. Die Regel ist, dass alle Kinder ihre linken und rechten Werte zwischen den linken und rechten Werten ihrer Eltern haben.

Hier ist die Tabellenstruktur zur Darstellung des Baums oben.

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();

Um die Tabelle zu füllen, habe ich das Skript aus Joe Celkos Buch „SQL für Smarties“ in die Postgres-Syntax konvertiert. Hier ist es:

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

Okay, ich bin bereit, ein paar Fragen zu stellen. So rufen Sie die Vorfahren ab.

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

Für die Nachkommen müssten wir zuerst links und rechts abrufen, danach können wir die folgende Abfrage verwenden.

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

Und das ist es! Sie haben gesehen, wie Sie bei allen drei Ansätzen den Baum hinauf- oder hinuntergehen. Ich hoffe, dass Ihnen die Reise gefallen hat und Sie sie nützlich finden.

Postgres vs. Dokument-/Grafikdatenbanken

Die Datenbank, die wir für die obigen Beispiele verwendet haben, ist PostgreSQL. Dies ist nicht die einzige Option. Sie fragen sich beispielsweise, warum Sie sich nicht für eine Dokumentendatenbank wie MongoDB oder eine Diagrammdatenbank wie Neo4j entscheiden, da diese eigentlich für diese Art von Arbeitslast entwickelt wurden.

Die Chancen stehen gut, dass Sie Ihre Source-of-Truth-Daten bereits in Postgres in einem relationalen Modell haben, das Transaktionsgarantien nutzt. In diesem Fall sollten Sie zunächst prüfen, wie gut Postgres selbst auch Ihre Hilfsanwendungsfälle handhabt, um alles an einem Ort zu behalten. Auf diese Weise vermeiden Sie die erhöhten Kosten und die betriebliche Komplexität, die für die Einrichtung und Wartung/Aktualisierung eines neuen separaten spezialisierten Datenspeichers erforderlich sind, sowie die Notwendigkeit, sich damit vertraut zu machen.

Abschluss

Es gibt mehrere interessante Optionen für die Modellierung hierarchischer Daten in Ihren Datenbankanwendungen. In diesem Beitrag habe ich Ihnen drei Möglichkeiten gezeigt, dies zu tun. Seien Sie gespannt auf Teil 2, in dem wir sie vergleichen und sehen, was mit größeren Datenmengen passiert.

Referenzen

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/

Das obige ist der detaillierte Inhalt vonHierarchische Daten mit PostgreSQL und Spring Data JPA. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!