Zenn
🚅

PostgreSQLにおけるMaterialized Pathと前方一致検索の最適化

2025/03/11に公開
PostgreSQL
DB
tech

階層構造データをリレーショナルデータベースで効率的に扱うことは、多くの開発者が直面する課題です。特に深いネスト構造を持つカテゴリやディレクトリシステムを実装する場合、クエリのパフォーマンスが問題になることがよくあります。

この記事では、階層データのためのMaterialized Pathパターンと、PostgreSQLの特殊な演算子クラスtext_pattern_opsを組み合わせることで、どのように検索パフォーマンスを劇的に向上させられるかを解説します。

Materialized Pathとは

Materialized Path（具現化パス）は、階層構造をリレーショナルデータベースで表現する手法の一つです。各ノードに、そのノードへのパス全体を格納する方法です。

例えば、ディレクトリ構造が以下のようになっている場合：

root/
├── usr/
│   ├── local/
│   │   ├── bin/
│   ├── share/
└── etc/
    └── config/

各ノードのMaterialized Pathは次のようになります：

/root/ (ID: 1)
/root/usr/ (ID: 2)
/root/usr/local/ (ID: 3)
/root/usr/local/bin/ (ID: 4)
/root/usr/share/ (ID: 5)
/root/etc/ (ID: 6)
/root/etc/config/ (ID: 7)

または、ID値を使った形式も一般的です：

/1/
/1/2/
/1/2/3/
/1/2/3/4/
/1/2/5/
/1/6/
/1/6/7/

Materialized Pathの利点

このアプローチの主な利点は以下の通りです：

  1. 子孫ノードをすべて取得する操作が簡単
  2. 祖先ノードのパスを直接取得可能
  3. ノードの移動やリネームが比較的容易
  4. 複数レベルのクエリに適している

前方一致検索の問題

通常、子孫ノードをすべて取得する操作は、前方一致検索を使って行います：

-- 「/root/usr/local/」の下にあるすべてのノードを検索
SELECT * FROM directories WHERE path LIKE '/root/usr/local/%';

しかし、大量のデータがある場合、このクエリは遅くなることがあります。そこで、インデックスを追加する必要が出てきます：

CREATE INDEX idx_path ON directories (path);

しかし、ここに落とし穴があります。通常のB-treeインデックスはLIKE 'パターン%'の前方一致検索に対して、常に効率的に機能するとは限らないのです。

なぜ通常のインデックスでは不十分なのか

PostgreSQLのデフォルトのB-treeインデックスは、データベースの照合ルール（collation）に従って値を比較します。多くの照合設定では、大文字小文字を区別しなかったり、アクセント記号を無視したりします。

これが、前方一致検索の最適化を妨げる原因になります。前方一致検索は内部的に「パターン以上かつパターンの次の文字未満」という範囲検索に変換されますが、照合ルールがあると正確な範囲検索が難しくなるのです。

text_pattern_opsの登場

ここで活躍するのがtext_pattern_opsという特殊な演算子クラスです：

CREATE INDEX idx_path_pattern ON directories (path text_pattern_ops);

この演算子クラスは、文字列をバイナリレベルで比較します。つまり：

  1. 照合ルールを無視して厳密なバイト単位の比較を行う
  2. 前方一致検索を効率的な範囲検索に変換できる

実際の効果

例えば、10万件のディレクトリエントリがあるテーブルで以下のクエリを実行すると：

SELECT * FROM directories WHERE path LIKE '/1/2/3/%';

通常のインデックスを使用した場合

Seq Scan on directories  (cost=0.00..2345.00 rows=125 width=36)
  Filter: (path ~~ '/1/2/3/%'::text)
Execution Time: 58.273 ms

多くの場合、PostgreSQLはインデックスを使用せず、シーケンシャルスキャンを選択してしまいます。

text_pattern_opsを使用した場合

Index Scan using idx_path_pattern on directories  (cost=0.28..8.29 rows=125 width=36)
  Index Cond: ((path ~>=~ '/1/2/3/'::text) AND (path ~<~ '/1/2/4/'::text))
  Filter: (path ~~ '/1/2/3/%'::text)
Execution Time: 0.873 ms

約66倍の高速化が実現できています！

実装上の注意点

text_pattern_opsは万能ではありません。いくつかの制限があります：

  1. 前方一致のみに効果的: 中間一致（LIKE '%パターン%'）や後方一致（LIKE '%パターン'）には効果がありません。これらにはpg_trgm拡張の使用を検討してください。

  2. 照合ルールの違い: text_pattern_opsはバイナリ比較を使用するため、データベースの照合設定と異なる結果になることがあります。特に国際化対応には注意が必要です。

  3. 通常のインデックスとの併用: 通常の比較演算（=, <, >など）と前方一致検索の両方を頻繁に使用する場合は、両方のインデックスが必要になることがあります。

いつ使うべきか

以下のような場合にtext_pattern_opsの使用を検討してください：

  1. Materialized Pathパターンを使用している
  2. 頻繁に子孫ノードのクエリを実行する
  3. テーブルのサイズが大きい
  4. 前方一致検索のパフォーマンスが重要

代替手法

階層データを扱う他の手法との比較：

  1. 隣接リスト（Parent ID）: 最も単純ですが、複数レベルのクエリが非効率
  2. Nested Set: 読み取りが高速ですが、更新が複雑
  3. Closure Table: 柔軟性が高いがテーブルサイズが大きくなる
  4. ltree拡張: PostgreSQL固有の階層データ型

Materialized PathとlTree拡張を組み合わせるのも効果的なアプローチです。

まとめ

PostgreSQLのtext_pattern_ops演算子クラスは、Materialized Pathパターンを使用した階層データの前方一致検索を大幅に高速化できます。この小さな最適化テクニックを知っておくことで、アプリケーションのパフォーマンスを劇的に向上させることができます。

大規模なディレクトリ構造やカテゴリシステムを実装する際は、ぜひこのテクニックを検討してみてください。

サンプルコード

最後に、完全なサンプルコードを紹介します：

-- テーブル作成
CREATE TABLE directories (
    id SERIAL PRIMARY KEY,
    name VARCHAR(255) NOT NULL,
    path TEXT NOT NULL,
    created_at TIMESTAMP NOT NULL DEFAULT NOW()
);

-- text_pattern_ops演算子クラスを使用したインデックス
CREATE INDEX idx_directories_path ON directories (path text_pattern_ops);

-- サンプルデータ
INSERT INTO directories (name, path) VALUES
('root', '/1/'),
('usr', '/1/2/'),
('local', '/1/2/3/'),
('bin', '/1/2/3/4/'),
('share', '/1/2/5/'),
('etc', '/1/6/'),
('config', '/1/6/7/');

-- 子孫ノードの検索
SELECT * FROM directories WHERE path LIKE '/1/2/%';

-- 特定のレベルの子ノードのみを検索
SELECT * FROM directories 
WHERE path LIKE '/1/2/%' 
AND array_length(string_to_array(trim(both '/' from path), '/'), 1) = 3;

この技術を活用して、効率的な階層データ処理を実現してください。

Discussion