Tihiroの頭を休めるIT教室

少しだけ頭使って後は根性

PostgreSQLの結合のコスト

概要

PostgreSQLの結合処理に必要なコストのお話です。文章力がないのですごく分かりにくいです。すみません。

環境

結合処理

PostgreSQLでは3つの結合処理がサポートされています。ジョインジョインジョイン。

NestedLoop

2つのテーブルを順繰りに掛け合わせて結合します。要は2重ループですね。

結合するテーブルのレコード数の積の比較コストが発生します。式で表すと

O(M * N)

らしいです。

MとNが結合するテーブルの行数、Oが...なんかソート処理とかなんとかそんな感じらしいですがよくわかりません。ググってもよくわかりません。

MergeJoin

ソートしたテーブル同士を結合させます。

テーブルのソートコストと、結合するテーブルのレコード数の和の比較コストが発生します。式で表すと

O(MlogM + NlogN)

らしいです。

HashJoin

ハッシュ化した値で結合させます。

ハッシュテーブルを作成するコストと、結合するテーブルのレコード数の和の比較コストが発生します。式で表すと

O(M+N)

らしいです。

まとめ

8. エグゼキュータ · PostgreSQL Internals

↑すんごい分かりやすい。