I think that the decision of the column order in the composite index should also be informed by the other indexes on the table.

If the column is already in its own index or the first in another index, then I'd consider using a different column as the first in the new composite index. That way, the query optimizer can make use of the two index and make an intersect them in other queries. For example, if there already is an index on address_id, then I would try using (address_type, address_id). With the address_type first, the query analyzer could now use that index when address_type is in your where clause. This _may_ increase performance of other queries. However, you will definitely have to test and see if the trade-off is worth it. The (address_id, address_type) may have a bigger payoff than the queries with address_type in the where clause.

I'm not really sure about what benefits a composite index would give over 2 indexes. Wouldn't an index intersection of separate address_id and address_type indexes be as effective as the composite (address_id, address_type)? If not in a single query, it may be more beneficial overall (since other queries can use the two, separate indexes). I could use some clarification on this. Thanks!