> In addition, there is ALTER INDEX <indexname> SELECTIVITY which performs
> an online, non-destructive traversal of the leaf level to recompute
> index selectivity. This feeds back into the query optimizer's
> statistics.

I was going to mention this earlier but, forgot to.
The syntax is actually a tad bit different than
Charlie suggests.

pg. 148, 5.5 Lang Ref.

SET STATISTICS INDEX <index_name>

It says: For tables where the number of duplicate values
in indexed columns radically increases or decreases,
periodically recomputing index selectivity can
improve performance.

NOTE: SET STATISTICS does _not_ rebuild an index.

Markus