The reason is that indexing on a hash produces a much smaller index so more of it can fit in memory. By minimizing disk seeks, you can speed up query time even if the Big O is the same. In both cases it should be O(log n) since SQLite uses btree indices.

I’m pretty sure that still necessitates a hit to the db to prevent false hashes, but that’s going to be the case with your approach, too.

Also note that you can have multiple indexes in Postgres (well, any RDBMS).

For emails in particular, you can even do partial indexes (eg. imagine filtering emails on @gmail.com to hit a separate index that's only half of your full table index). This requires some care with queries, but a wonderful feature regardless.

When you get over a million users...

I've yet to try the index of hashed values trick though, when I revisit this problem in the future I'll make sure to take note of this!

If you need any normalization like lowercasing, you need to do that yourself.

Next, you can't do collation/ordering using the index (and greater/less than comparisons), unless the hash function maintains ordering properties.

By having an option of an expression index customised to your data, you can use it to get the fastest query performance.