pg_rast, pg_senna あたりを勧めたいところだけど
＞レコード件数が最大で億を超えることが予想されるようです。
ということなら Rast や Senna ではキツいですね。
Hyper Estraier は件数が増えても性能劣化しないように作られているけど
pgestraier は PostgreSQL のカラムに対するインデックス作成ができないので使えないわけで。

8.1 で導入されるテーブル・パーティショニングを使ってカテゴリごとにテーブルを分けるとかすれば
pg_rast や pg_senna でもいけるかな？