The least-appreciated part of query optimization is the collection of database statistics. Often, when questions such as "why isn't the optimizer using my index?" are asked, it is poor statistics that are really to blame.
Statistics are collected for each column in every table in a database when ANALYZE is executed against the table. If you're running with autovacuum turned on, it will usually run often enough to keep accurate statistics available. Unlike a complete vacuum cleanup, which can take quite some time on large tables, analyzing a table should take only a few seconds at any table size. It doesn't take anything other than a read lock while running, either.
