Ah, fair point. So we agree they need a (possibly not unique) user name too. [edit: note this is for 5 billion accounts, on a 10 year old cpu. So for 500.000 accounts, it would be ~1 seconds (average 0.5). Still probably too long for log-in (or particularly log-in failure feedback)).]

If you have a username and emails aren't used for contacting users, why bother storing the email address to begin with?

To verify that a username matches a given email address, so that you can provide password resets?