空間インデックスを使用した空間データクエリの最適化
この記事では、既存の非効率な実装について議論し、それを改善するために試みた方法を記録します。
既存の問題点
複数のデータベースに分散されたテーブルを単一のクエリで結合することは不可能ではなかったが、困難だった...
- 特定の座標がエリア「a」に含まれているか？
- テーブルが物理的に異なるサーバーに存在するため、結合クエリの 記述が難しかった
- なぜ単一のクエリが必要なのか？クエリ対象のデータが大規模であるため、アプリケーションメモリに読み込む量を最小限に抑えたかったからです。
- データベース結合が不可能だったため、アプリケーション結合が必要となり、約240億回のループ（60000 * 40000）が発生した
- パーティショニングによって処理時間は最小限に抑えられたが、ループによるCPU負荷は依然として高かった。
- 物理的に異なるデータベースを1つに統合する移行プロセスを通じて、結合が可能になったため、クエリの最適化の機会が得られた。
アプローチ
データベース結合ができなかった主な理由が解決されたため、ジオメトリ処理にインデックススキャンを活用することを積極的に検討しました。
- PostGISのGISTインデックスを使用すると、R-treeに似た空間インデックスを作成でき、インデックススキャンを通じて直接クエリが可能です。
- 空間インデックスを使用するには、ジオメトリ型のカラムが必要です。
- 緯度と経度の座標は利用可能でしたが、ジオメトリ型がなかったため、まず座標を使用してジオメトリPOINT値を作成する必要がありました。
このプロセスをシミュレートするために、本番DBと同じデータを用意し、実験を行いました。
まず、インデックスを作成しました：
CREATE INDEX idx_port_geom ON port USING GIST (geom);
次に、PostGISのcontains関数を実行しました：
SELECT *
FROM ais AS a
JOIN port AS p ON st_contains(p.geom, a.geom);
素晴らしい...
結果
空間インデックス適用前
1分47秒から2分30秒
空間インデックス適用後
0.23ミリ秒から0.243ミリ秒
キャプチャは用意していませんが、インデックス適用前のクエリは1分30秒以上かかっていました。
結論から始めて、なぜこれらの結果が得られたのかを掘り下げていきましょう。
GiST（Generalized Search Tree）
複雑なジオメトリデータのクエリに非常に有用なインデックスで、その内部構造は以下の通りです。
R-treeのアイデアは、平面を長方形に分割してすべてのインデックスされたポイントを包含することです。インデックス行は長方形を格納し、次のように定義できます：
"探しているポイントは指定された長方形の中にある。"
R-treeのルートには、いくつかの最大の長方形（交差することもある）が含まれます。子ノードには、親ノードに含まれる小さな長方形が含まれ、すべての基本ポイントを包含します。
理論的には、リーフノードにはインデックスされたポイントが含まれるべきですが、すべてのインデックス行は同じデータ型を持つ必要があるため、ポイントに縮小された長方形が繰り返し格納されます。
この構造を視覚化するために、R-treeの3つのレベルの画像を見てみましょう。ポイントは空港の座標を表しています。
レベル1：2つの大きな交差する長方形が見えます。
2つの交差する長方形が表示されています。
レベル2：大きな長方形が小さなエリアに分割されています。
大きな長方形が小さなエリアに分割されています。
レベル3：各長方形には1つのインデックスページに収まるだけのポイントが含まれています。
各長方形には1つのインデックスページに収まるポイントが含まれています。
これらのエリアはツリー構造になっており、クエリ中にスキャンされます。詳細な情報については、次の記事を参照することをお勧めします。
結論
この記事では、具体的な条件、遭遇した問題、それを解決するために行った努力、およびこれらの問題に対処するために必要な基本概念を簡単に紹介しました。要約すると：
- 物理的に分離されたデータベースでは、インデックスを使用した効率的な結合ができなかった。
- 移行によって物理的な結合が可能になり、パフォーマンスが大幅に向上した。
- インデックススキャンを活用することで、全体的なパフォーマンスが大幅に向上した。
- アプリケーションメモリにデータを不必要に読み込む必要がなくなった。
- ループによるCPU負荷が軽減された。