Wenn eine Datenbank trotz korrekt vorhandener Indices ein Performanceverhalten hat als ob kein Index vorhanden ist, so kann es sein das die Indices, oder ein einzelner Index defekt oder unaktuell ist. Man kann PostgreSQL anweisen seine Indices neu aufzubauen. Dieses funktioniert auf Datenbankebene mit

REINDEX DATABASE <Datenbank>;

auf Tabellenebene mit

REINDEX TABLE <Tabellenname>;

und auf Indexebene mit

REINDEX INDEX <Index>;

Weitergehende Informationen dazu gibt es unter
http://www.postgresql.org/docs/9.4/static/sql-reindex.html