Optimizing Postgres query
I'm trying to fetch addresses for certain users only ...


IN does not scale well with big lists. Compare performance to unnest() / JOIN 

SELECT a.*
FROM   unnest(ARRAY[9681,23824,23760,20098,962,14730,12294,9552,534,
                    553,5837,6768,6583,956,24179]) AS t(user_id)
JOIN   addresses a USING (user_id)
WHERE  a.type  =  'VerifiedAddress'
AND    a.state &lt;&gt; 'manual_verification'


I hope state and type are at least enum types. Otherwise you should normalize your database design. Have lookup-tables for state and type and only use a small IDs referencing entries there. Makes the addresses table smaller and everything faster.

Assuming all columns NOT NULL for lack of information.

Partial index

If you need it faster still, and if there are more than a few rows with type &lt;&gt; 'VerifiedAddress' or state = 'manual_verification', a partial index would help some more. The gain grows with the percentage of rows you can exclude from the index.

CREATE INDEX addresses_selection_idx ON addresses (user_id)
WHERE  type  =  'VerifiedAddress'
AND    state &lt;&gt; 'manual_verification';


Be sure to use matching WHERE conditions in your query to allow Postgres to use this index. And weigh the benefit of tailored indexes against their cost (maintenance, extra disk space, small penalty for write operations).