With an index on User (createdAt, id) and one on ContactMethod ( primary,ContactMethod,userId), it should be fast (check that the the execution plan starts with User). Except if lot of recent users have no phones, but that will not be better in a single table (except if columnar storage)