Explaining CREATE INDEX CONCURRENTLY というブログ記事がなかなかおもしろかったので、自分なりにまとめなおしてみます。PostgreSQLのソースコードでもコメントで説明されているので、それを読むのもおすすめです。それ読みながら書きました。
通常インデックスの作成時には、その最中にインデックスに影響する変更が行われるのを防ぐため、テーブルレベルのロックが行われます。CREATE INDEX CONCURRENTLY はこのようなロックを行わずにインデックスを作成する機能です。
（ソースコードやネット上の記事を参考に書いているので、勘違い等あればご指摘ください）
どうしたら実現できるか
基本的な考え方は、ある時点のスナップショットを元にインデックスを作成し、インデックスへの挿入を有効化してから、改めて取ったスナップショットとの差分をインデックスに反映するというものです。
Heap Only Tuple (HOT) の存在
PostgreSQL ではレコードの変更も新規タプルの作成として処理されるため、タプルへの参照を保持するインデックスもそのたびに更新、もといエントリを追加する必要があります。この方法では更新にかかるコストが馬鹿にならないので、どのインデックスにも影響しない変更ならヒープ内のリダイレクトで済ますというのが HOT です。ヒープ内に存在するだけでインデックス等からは直接参照されないので Heap Only Tuple だそうな。
ところで、インデックスの作成は「どのインデックスにも影響しない」という判定に影響します。インデックスが作成される前に作成されたHOTチェインはこのルールを満たしていない可能性が、つまり末端のタプルではもはやキーと異なる値に変更されている可能性があります。
これらを踏まえて、処理の流れを追ってみます。
Step1. とりあえず宣言する
早速スナップショットを取りたいところですが、その前にインデックスの存在をカタログに登録します。こうすることで、インデックス作成中の更新の際、この新インデックスを考慮してHOT作成が行われるようになります。この時点ではインデックスはまだ挿入も参照もできません。
この時点でShareLockと競合するトランザクションがある場合、それらによる更新はまだ新インデックスのことを考慮していない可能性があります。このためそれらのトランザクションを待ちます。
Step2. 作る
スナップショットを取り、普通にインデックスを作成します。対象のカラムにインデックスが作られることは既に周知されているので、並行して更新が発生してもHOTにできるかどうかが正しく判断されます。
これが済んだらインデックスを挿入可能としてマークし、Step1同様にShareLockと競合するトランザクションが全て終了するまで待機します。
Step3. 差分を反映
ここまでで既存レコードのほとんどはもちろん、今後発生する挿入や更新もインデックスに反映されるようになりました。残るはStep2の最中に発生した差分を反映するだけです。
インデックスを参照可能にする前にもう一度、今度は古いスナップショットを参照しているトランザクションが終了するのを待ちます。インデックス作成時までに変更・削除が行われていたレコードがあった場合に、それらのトランザクションのクエリにインデックスを使うとまずいので。
最後に、インデックスを参照可能としてマークし、テーブル情報のキャッシュも飛ばすことで再計画を促します。