Données hiérarchiques avec PostgreSQL et Spring Data JPA

Celui qui plante un arbre,
Plante un espoir.
       Planter un arbre par Lucy Larcom ?

Introduction

Dans cet article, je vais vous montrer quelques options pour gérer les données hiérarchiques représentées sous la forme d'une arborescence structure de données. C'est l'approche naturelle lorsque vous devez mettre en œuvre des choses comme :

• chemins du système de fichiers
• organigrammes
• commentaires du forum de discussion
• un sujet plus contemporain : la récupération small2big pour les applications RAG

Si vous savez déjà ce qu'est un graphique, un arbre est fondamentalement un graphique sans aucun cycle. Vous pouvez en représenter un visuellement comme ceci.

Il existe plusieurs alternatives pour stocker des arbres dans des bases de données relationnelles. Dans les sections ci-dessous, je vais vous en montrer trois :

• liste de contiguïté
• chemins matérialisés
• Ensembles imbriqués

Il y aura deux parties dans cet article de blog. Dans cette première, les alternatives sont présentées et vous voyez comment charger et stocker des données – les bases. Cela étant dit, dans la deuxième partie, l'accent est davantage mis sur leur comparaison et leurs compromis. Par exemple, je souhaite examiner ce qui se passe lorsque les volumes de données augmentent et quelles sont les stratégies d'indexation appropriées.

Tous les codes que vous verrez dans les sections ci-dessous peuvent être trouvés ici si vous souhaitez le consulter.

Le cas d'utilisation en cours sera celui des employés et de leurs managers, et les identifiants pour chacun seront exactement ceux que vous avez vus dans la visualisation arborescente que j'ai montrée ci-dessus.

Environnement local

J'utilise le Postgres 17 récemment publié avec Testcontainers. Cela me donne une configuration reproductible avec laquelle travailler. Par exemple, nous pouvons utiliser des scripts SQL d'initialisation pour automatiser la création d'une base de données Postgres avec les tables nécessaires et la remplir avec quelques données de test.

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

Allons-y et jetons un coup d'œil à la première approche.

1. Le modèle de liste de contiguïté

Il s'agit de la première solution de gestion des données hiérarchiques, nous pouvons donc nous attendre à ce qu'elle soit encore largement présente dans les bases de code, il est donc probable que vous la rencontriez un jour. L'idée est que nous stockons l'identifiant du responsable, ou plus généralement, l'identifiant du parent dans la même ligne. Cela deviendra rapidement clair une fois que nous examinerons la structure du tableau.

Schéma

Le tableau correspondant à l'option liste de contiguïté ressemble à ceci :

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

En plus de ce qui précède, afin de garantir l'intégrité des données, nous devons également rédiger des contrôles de contraintes qui garantissent au moins ce qui suit :

• il y a un seul parent pour chaque nœud
• pas de cycles

Générer des données de test

Surtout pour la partie 2 de cette série, nous avons besoin d'un moyen de générer autant de données que nous le souhaitons pour remplir le schéma. Faisons-le d'abord étape par étape pour plus de clarté, puis ensuite de manière récursive.

Pas à pas

On commence simple en insérant explicitement trois niveaux de collaborateurs dans la hiérarchie.

Vous connaissez peut-être déjà les CTE dans Postgres : ce sont des requêtes nommées auxiliaires exécutées dans le contexte d'une requête principale. Ci-dessous, vous pouvez voir comment je construis chaque niveau sur la base du niveau précédent.

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

Vérifions que cela fonctionne comme prévu jusqu'à présent, et pour cela faisons un décompte pour voir combien d'éléments ont été insérés. Vous pouvez le comparer avec le nombre de nœuds dans la visualisation arborescente que j'ai montrée au début de cet article.

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

Ça a l'air bien ! Trois niveaux, et au total nous obtenons 15 nœuds.

Il est temps de passer à l'approche récursive.

Récursif

L'écriture de requêtes récursives suit une procédure standard. Nous définissons une étape de base et une étape récursive puis les « connectons » les unes aux autres en utilisant Union All. Au moment de l'exécution, Postgres suivra cette recette et générera tous nos résultats. Jetez un oeil.

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;

Après l'avoir exécuté, recomposons pour voir si le même nombre d'éléments est inséré.

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

Cool ! Nous sommes en affaires. Nous pouvons maintenant remplir le schéma avec autant de niveaux et d'éléments que nous voulons, et ainsi contrôler complètement le volume inséré. Pas d'inquiétude si pour l'instant les requêtes récursives semblent encore un peu difficiles, nous y reviendrons d'ailleurs un peu plus tard à l'occasion de l'écriture des requêtes pour récupérer les données.

Pour l'instant, examinons l'entité Hibernate que nous pouvons utiliser pour mapper notre table à une classe 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;

Rien de spécial, juste une relation un-à-plusieurs entre managers et employés. Vous avez vu cela venir. Commençons par interroger.

Descendance

Tous les subordonnés d'un manager

Pour récupérer tous les employés qui sont subordonnés à un manager spécifique référencé par son identifiant, nous écrirons à nouveau une requête récursive. Vous verrez à nouveau une étape de base et une étape récursive liée à l'étape de base. Postgres répétera ensuite cette opération et récupérera toutes les lignes pertinentes pour la requête. Prenons par exemple l'employé avec ID = 2. Il s'agit d'une représentation visuelle qui, espérons-le, permet de mieux comprendre ce que je viens de décrire. Je n'ai pas inclus tous les résultats, juste les premiers.

Voici la requête JPQL pour interroger les descendants :

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

Dans les requêtes comme celle ci-dessus, afin de les rendre plus propres et d'éviter d'avoir à écrire le nom complet de l'enregistrement dans lequel nous allons écrire les résultats, nous pouvons utiliser la bibliothèque hypersistence-utils pour écrire un ClassImportIntegratorProvider :

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

Examen des requêtes générées

Cela fonctionne, mais regardons de plus près ce que Hibernate a généré. Il est toujours bon de comprendre ce qui se passe sous le capot, sinon nous pourrions subir des inefficacités qui se produiront à chaque demande d'utilisateur, cela s'additionnera.

Nous devrons démarrer l'application Spring Boot avec le paramètre suivant :

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;

Très bien, jetons un coup d'oeil. Voici la requête pour les descendants générés par Hibernate.

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

Hmm - ça a l'air un peu plus compliqué que prévu ! Voyons si nous pouvons simplifier un peu, en gardant à l'esprit l'image que je vous ai montrée plus tôt à propos de l'étape de base et de l'étape récursive liée à l'étape de base. Nous ne devrions pas avoir besoin de faire plus que cela. Voyez ce que vous pensez de ce qui suit.

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;

Beaucoup mieux ! Nous avons supprimé certaines jointures inutiles. Cela devrait accélérer la requête, car elle nécessitera moins de travail.

Résultat final

En guise d'étape finale, nettoyons la requête et remplaçons les noms de table ajoutés par Hibernate par ceux qui sont plus lisibles par l'homme.

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

Très bien, il est temps de voir comment nous montons dans l'arbre.

Ancêtres

Tous les managers en amont de la chaîne

Essayons d'abord d'écrire les étapes conceptuelles pour obtenir les managers d'un employé avec ID = 14.

Ressemble beaucoup à celui des descendants, juste la connexion entre l'étape de base et l'étape récursive est dans l'autre sens.

Nous pouvons écrire la requête JPQL comme ceci :

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

Et c'est tout ! J'ai regardé la requête SQL générée mais je n'ai trouvé aucune commande supplémentaire que je pourrais supprimer. Il est temps de passer à l'approche 2.

2. Chemins matérialisés

ltree est une extension Postgres que nous pouvons utiliser pour travailler avec des structures arborescentes hiérarchiques sous forme de chemins matérialisés (en commençant par le haut de l'arborescence). Par exemple, voici comment nous enregistrerons le chemin du nœud feuille 8 : 1.2.4.8. Il comprend plusieurs fonctions utiles. Nous pouvons l'utiliser comme colonne de tableau :

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

Afin de remplir le tableau ci-dessus avec des données de test, l'approche que j'ai adoptée consiste essentiellement à migrer les données générées à partir du tableau utilisé pour la liste de contiguïté que vous avez vue auparavant, à l'aide de la commande SQL suivante. Il s'agit encore une fois d'une requête récursive qui collecte des éléments dans un accumulateur à chaque étape.

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

Voici les entrées générées par la commande ci-dessus.

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

Nous pouvons procéder à l'écriture de l'entité Hibernate. Afin de mapper des colonnes de type ltree, j'ai implémenté un UserType. Je peux ensuite mapper le champ de chemin avec @Type(LTreeType.class):

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

Nous sommes prêts à rédiger quelques requêtes. En SQL natif, cela ressemblerait à ceci :

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;

Mais écrivons nos requêtes en JPQL. Pour cela, nous devrons d’abord écrire notre StandardSQLFunction personnalisé. Cela nous permettra de définir une substitution pour l'opérateur natif Postgres.

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

Il faut ensuite l'enregistrer en tant que FunctionContributor, comme ceci :

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;

La dernière étape consiste à créer un fichier de ressources dans le dossier META-INF/services appelé org.hibernate.boot.model.FunctionContributor où nous ajouterons une seule ligne avec le nom complet de la classe ci-dessus.

D'accord, cool ! Nous sommes enfin en mesure d'écrire la requête suivante :

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

Par exemple, on peut appeler cette méthode comme ceci pour récupérer tous les chemins qui contiennent 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 propose un large éventail de fonctions pour travailler avec des ltrees. Vous pouvez les trouver sur la page de documentation officielle. De plus, il existe une aide-mémoire utile.

Il est important d'ajouter des contraintes à notre schéma afin de garantir la cohérence des données - voici une bonne ressource que j'ai trouvée sur ce sujet.

3. Ensembles imbriqués

Le plus simple à comprendre est d'utiliser une image montrant l'intuition. À chaque nœud de l'arborescence, nous avons une colonne "gauche" et une colonne "droite" supplémentaires en plus de son ID. La règle est que tous les enfants ont leur gauche et leur droite entre les valeurs gauche et droite de leurs parents.

Voici la structure du tableau pour représenter l'arbre ci-dessus.

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

Afin de remplir le tableau, j'ai converti le script du livre "SQL for smarties" de Joe Celko en syntaxe Postgres. Le voici :

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

Très bien, je suis prêt à faire quelques requêtes. Voici comment récupérer les ancêtres.

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

Pour les descendants, nous devons d'abord récupérer la gauche et la droite, après quoi nous pouvons utiliser la requête ci-dessous.

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

Et c'est tout ! Vous avez vu comment monter ou descendre l'arbre pour les trois approches. J'espère que vous avez apprécié le voyage et que vous le trouvez utile.

Postgres vs bases de données de documents/graphiques

La base de données que nous avons utilisée pour les exemples ci-dessus est PostgreSQL. Ce n'est pas la seule option, par exemple vous pourriez vous demander pourquoi ne pas choisir une base de données de documents comme MongoDB, ou des bases de données graphiques comme Neo4j, car elles ont en fait été construites avec ce type de charge de travail à l'esprit.

Il y a de fortes chances que vous disposiez déjà de votre source de données de vérité dans Postgres dans un modèle relationnel tirant parti des garanties transactionnelles. Dans ce cas, vous devez d'abord vérifier dans quelle mesure Postgres lui-même gère également vos cas d'utilisation auxiliaires, afin de tout conserver au même endroit. De cette façon, vous éviterez l’augmentation des coûts et la complexité opérationnelle nécessaires à la création et à la maintenance/mise à niveau d’un nouveau magasin de données spécialisé distinct, ainsi que la nécessité de vous familiariser avec celui-ci.

Conclusion

Il existe plusieurs options intéressantes pour modéliser des données hiérarchiques dans vos applications de bases de données. Dans cet article, je vous ai montré trois façons de procéder. Restez à l'écoute pour la partie 2 où nous les comparerons et verrons ce qui se passe avec un plus grand volume de données.

Références

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/

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!