PR

 以下,簡単にHOTの動作原理を解説する。

 なお,冒頭で述べたようにPostgreSQL 8.3はまだ開発中なので,今後の展開によっては,違った実装になる可能性があることをお断りしておく。また,最悪8.3での実装が見送りになることもあるかもしれない(その可能性は低いと思うが)。

インデックスの不要領域の増加を抑制

 Webページのアクセス回数を管理する以下のような簡単なテーブルを考える。あるURLにアクセスするたびに,cntがカウントアップされ,頻繁に更新が発生する典型的なケースだ。

CREATE TABLE t1(
url TEXT PRIMARY KEY,-- 主キーなので自動的にインデックスが付く
cnt INTEGER
);

 cntが更新されると,それにつれてurlに張られたインデックスも更新される。しかし考えてみるとcntが変化してもurlは変化していないので,urlのインデックスを更新するのは無駄だ。そこでHOTでは,このようなケースではurlのインデックスを更新しない。その結果インデックスの肥大化を従来よりも抑えることができる。

 このように,インデックスの更新を伴わなかった行を「HEAP ONLY TUPLE」と呼ぶ(HOTはここから名付けられた)。

VACUUMなしにテーブルの不要領域増加を抑制

 cntを更新すると,その行は削除され(正確にはこの時点では見えなくなるだけ),新しい行が追加される。削除された行には,削除されたことを示すフラグが立つとともに,新しい行へのポインタが格納される。再びその行を更新するときには,古い行からポインタをたどって有効な行にたどりつき,先ほどと同じように削除フラグを立てて新しい行へのポインタを格納する。こうして,更新を繰り返すとポインタの連鎖ができる。これを「UPDATE連鎖(UPDATE chain)」と呼ぶ。

 UPDATE連鎖が長くなると検索も更新も時間がかかるようになる。これはVACUUMを実施するまでは解消されない。これが現在のPostgreSQLの問題点である。

 HOTでもUPDATE連鎖ができることには変わりないが,他のトランザクションから参照されていなければ,HEAP ONLY TUPLEに関しては,VACUUMをせずにただちに削除行を回収することができるようになっている。これは,HEAP ONLYTUPLEがインデックスから参照されていないためだ。回収はSELECT 処理で行う。HEAP ONLY TUPLEのUPDATE連鎖をたどりながらその行が不要かどうかを判断し,不要であればただちに再利用可能対象とする。したがって,UPDATE連鎖の長さを最小限に抑えることができる。

 このような処理をSELECT時に行うとオーバヘッドが心配になるが,PostgreSQL ではテーブルのアクセスを常にブロック単位で行っており,以上のようなUPDATE連鎖をたどる処理はブロックを読み込んだバッファ上で行うため余分なI/Oが発生せず,効率よく処理を行うことができる。

 もちろん更新後のデータがそのブロックに入りきらない場合はこのような処理ができないので,VACUUMが必要になるが,実務の多くのケースでは更新後もさほど行の長さが増えないのであまり問題にならないと思われる。