PostgreSQL と Spring Data JPA による階層型データ

木を植える者
希望を植えます。
       木を植える by Lucy Larcom ?

イントロ

この投稿では、ツリー データ構造として表される階層データを管理するためのオプションをいくつか紹介します。これは、次のようなものを実装する必要がある場合の自然なアプローチです。

• ファイルシステムのパス
• 組織図
• ディスカッションフォーラムのコメント
• より現代的なトピック: RAG アプリケーションの small2big 取得

グラフが何であるかをすでに知っている場合、ツリーは基本的に サイクルのないグラフです。このように視覚的に表現できます。

リレーショナル データベースにツリーを保存する方法は複数あります。以下のセクションでは、そのうちの 3 つを紹介します:

• 隣接リスト
• 具体化されたパス
• ネストされたセット

このブログ投稿は 2 つの部分に分かれています。この最初のバージョンでは、代替手段が紹介され、データのロードと保存の基本的な方法がわかります。それはさておき、第 2 部では、それらの比較とトレードオフに焦点を当てます。たとえば、データ量が増加した場合に何が起こるか、および適切なインデックス付け戦略は何かについて見ていきたいと思います。

以下のセクションに表示されるすべてのコードは、興味がある場合はここで確認できます。

実行中のユースケースは、従業員とそのマネージャーのユースケースであり、それぞれの ID は、上で示したツリーの視覚化で確認したものとまったく同じになります。

地域環境

私は最近リリースされた Postgres 17 を Testcontainers で使用しています。これにより、繰り返し可能なセットアップで作業できるようになります。たとえば、初期化 SQL スクリプトを使用して、必要なテーブルを備えた Postgres データベースの作成を自動化し、テスト データを追加できます。

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

早速、最初のアプローチを見てみましょう。

1. 隣接リストモデル

これは階層データを管理するための最初のソリューションであったため、コードベースにまだ広く存在していることが予想されるため、いつか遭遇する可能性があります。考え方としては、マネージャーの (より一般的に言えば) 親 ID を同じ行に保存するということです。テーブル構造を見ればすぐにわかります。

スキーマ

隣接リスト オプションに対応するテーブルは次のようになります:

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

上記に加えて、データの整合性を確保するには、少なくとも次のことを保証する制約チェックも記述する必要があります。

• すべてのノードに単一の親があります
• サイクルなし

テストデータの生成

特にこのシリーズのパート 2 では、スキーマにデータを設定するために必要なだけのデータを生成する方法が必要です。わかりやすくするために、最初は段階的に実行し、その後再帰的に実行してみましょう。

一歩ずつ

まず、階層に 3 つのレベルの従業員を明示的に挿入することから始めます。

Postgres の CTE についてはすでにご存じかもしれません。CTE は、メイン クエリのコンテキスト内で実行される補助的な名前付きクエリです。以下に、前のレベルに基づいて各レベルをどのように構築するかを示します。

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

これまでのところ期待どおりに動作することを確認してみましょう。この目的のために、挿入された要素の数を確認するためにカウントを実行します。この投稿の冒頭で示したツリー視覚化のノード数と比較できます。

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

大丈夫そうですね！ 3 つのレベルで、合計 15 個のノードが得られます。

再帰的アプローチに移りましょう。

再帰的

再帰クエリの作成は標準的な手順に従います。基本ステップと再帰ステップを定義し、union all を使用してそれらを相互に「接続」します。実行時に Postgres はこのレシピに従い、すべての結果を生成します。ぜひご覧ください。

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;

実行後、もう一度カウントして、同じ数の要素が挿入されているかどうかを確認してみましょう。

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

かっこいい！私たちはビジネスをしています。これで、必要な数のレベルと要素をスキーマに追加できるようになり、挿入されたボリュームを完全に制御できるようになりました。現時点では再帰クエリがまだ少し難しそうに見えても心配する必要はありません。実際には、少し後で、データを取得するクエリを作成する機会に再考します。

ここでは、テーブルを Java クラスにマップするために使用できる Hibernate エンティティを見てみましょう。

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;

特別なことは何もありません。マネージャーと従業員の間には 1 対多の関係があるだけです。あなたはこれが来るのを見ました。クエリを開始しましょう。

子孫

マネージャーのすべての部下

ID で参照される特定のマネージャーの部下であるすべての従業員を取得するには、再帰クエリを再度作成します。 ベース ステップと、ベース ステップにリンクされている再帰ステップが再度表示されます。 Postgres はこれを繰り返し、クエリに関連するすべての行を取得します。たとえば、ID = 2 の従業員を考えてみましょう。これは視覚的に表現したもので、今説明した内容を理解しやすくするものです。すべての結果を含めたわけではありません。最初のいくつかだけを示します。

子孫をクエリするための JPQL クエリは次のとおりです。

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

上記のようなクエリでは、クエリをわかりやすくし、結果を書き込むレコードの完全修飾名を記述する必要を避けるために、hypersistence-utils ライブラリを使用して ClassImportIntegratorProvider を記述することができます。

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

生成されたクエリの確認

これは機能しますが、Hibernate が生成したものを詳しく見てみましょう。内部で何が起こっているのかを理解することは常に良いことです。そうでないと、ユーザーのリクエストごとに非効率が発生し、それが積み重なってしまう可能性があります。

次の設定で Spring Boot アプリを起動する必要があります:

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;

それでは、見てみましょう。 Hibernate によって生成された子孫のクエリは次のとおりです。

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

うーん、予想より少し複雑ですね!ベース ステップとベース ステップにリンクされた再帰ステップについて前に示した図を念頭に置き、これを少し単純化できるかどうかを見てみましょう。それ以上のことをする必要はないはずです。以下についてどう思うか見てください。

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;

ずっと良くなりました!いくつかの不要な結合を削除しました。これにより、実行する作業が減り、クエリが高速化されることが期待されます。

最終結果

最後のステップとして、クエリをクリーンアップし、Hibernate が追加するテーブル名を人間が読みやすい名前に置き換えましょう。

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

さて、ツリーをどのように「登る」か見てみましょう。

祖先

チェーン上のすべてのマネージャー

まず、ID = 14 の従業員のマネージャーを取得するための概念的な手順を書き留めてみましょう。

子孫の場合と非常によく似ていますが、基本ステップと再帰ステップの間の接続が逆になっているだけです。

JPQL クエリは次のように記述できます。

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

それで終わりです!生成された SQL クエリを確認しましたが、削除できる余分なコマンドは見つかりませんでした。アプローチ 2 に進みます。

2. 実体化されたパス

ltree は、(ツリーの最上部から始まる) 実体化されたパスとして階層ツリー構造を操作するために使用できる Postgres 拡張機能です。たとえば、リーフ ノード 8 のパス 1.2.4.8 を記録する方法は次のとおりです。いくつかの便利な機能が搭載されています。これをテーブルの列として使用できます:

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

上記のテーブルにテスト データを設定するために私がとったアプローチは、基本的に、次の SQL コマンドを使用して、前に見た隣接リストに使用されたテーブルから生成されたデータを移行することです。これもまた、各ステップで要素をアキュムレータに収集する再帰的クエリです。

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

上記のコマンドで生成されたエントリは次のとおりです。

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

Hibernate エンティティの作成に進むことができます。 ltree 型の列をマップするために、UserType を実装しました。その後、パス フィールドを @Type(LTreeType.class):
でマッピングできます。

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

いくつかのクエリを作成する準備ができました。ネイティブ SQL では、次のようになります:

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;

しかし、JPQL でクエリを書いてみましょう。このためには、まずカスタム StandardSQLFunction を作成する必要があります。これにより、Postgres ネイティブ オペレーターの置換を定義できるようになります。

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

次に、次のように FunctionContributor として登録する必要があります。

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;

最後のステップは、META-INF/services フォルダーに org.hibernate.boot.model.FunctionContributor というリソース ファイルを作成し、上記のクラスの完全修飾名を 1 行追加します。

わかりました、クールです!ついに次のクエリを作成できるようになりました:

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

たとえば、このメソッドを次のように呼び出して、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 は、ltree を操作するための幅広い関数セットを提供します。それらは公式ドキュメントページで見つけることができます。便利なチートシートもあります。

データの一貫性を確保するには、スキーマに制約を追加することが重要です。このトピックに関して見つけた優れたリソースは次のとおりです。

3. ネストされたセット

直感を示す画像を使用するのが最も簡単です。ツリーの各ノードには、ID のほかに追加の「左」列と「右」列があります。ルールは、すべての子の左と右が親の左と右の値の間にあることです。

上記のツリーを表すテーブル構造は次のとおりです。

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

テーブルにデータを設定するために、Joe Celko の書籍「SQL for Smarties」のスクリプトを Postgres 構文に変換しました。それは次のとおりです:

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

わかりました。いくつかのクエリを実行する準備ができました。祖先を取得する方法は次のとおりです。

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

子孫の場合は、まず左側と右側を取得する必要があり、その後、以下のクエリを使用できます。

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

それで終わりです! 3 つのアプローチすべてについて、ツリーを上り下りする方法を確認しました。旅を楽しんでいただけて、お役に立てば幸いです。

Postgres とドキュメント/グラフ データベースの比較

上記の例で使用したデータベースは PostgreSQL です。これが唯一の選択肢ではありません。たとえば、MongoDB のようなドキュメント データベースや Neo4j のようなグラフ データベースを選択しないのはなぜではないかと疑問に思うかもしれません。なぜなら、これらは実際にこの種のワークロードを念頭に置いて構築されているからです。

おそらく、トランザクション保証を活用したリレーショナル モデルの Postgres に、信頼できるデータのソースがすでに存在していると思われます。その場合、すべてを 1 か所にまとめておくために、まず Postgres 自体が補助的なユースケースをどのように適切に処理するかを確認する必要があります。こうすることで、新しい別個の専用データ ストアの立ち上げと保守/アップグレードに必要なコストと運用の複雑さの増加、およびそれに慣れる必要を回避できます。

結論

データベース アプリケーションで階層データをモデル化するための興味深いオプションがいくつかあります。この記事では 3 つの方法を紹介しました。パート 2 では、それらを比較し、より大量のデータで何が起こるかを見ていきますので、ご期待ください。

参考文献

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://aregal.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/

以上がPostgreSQL と Spring Data JPA による階層型データの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。