IME almost every query that takes way longer than expected in PG has been because it elected to do a sequential scan instead of using an index. I've set both random_page_cost and seq_page_cost to 1 for a database on an SSD (where sequential is still faster than random) but PG still chooses sequential scans. I selectively disable sequential scans on the connection ahead of badly planned queries now.