Fastest way to find (rare) rows with a null value among millions of rows?
There is a very fast way, create a partial index:

CREATE INDEX foo_idx ON addresses (address_id)  -- arbitrary pick
WHERE address_id IS NULL; 


The indexed column is largely irrelevant. Use any small column(s) that might be relevant to your queries. The important point is that only the few rows with address_id IS NULL end up in the index.

The index incurs a (very small) cost on write performance, obviously.

Related:


Very large btree index with few rows (openstreetmap gis data)