> If there are a very large number of users, and a very large number of phone number primary contacts, you cannot make this query fast/efficient

I think specific numbers would help make this point better. With a few hundred thousand to low millions of users this should be plenty fast in Postgres for example. That’s magnitudes more than most startups ever reach anyway.