I'm confused, how is matching against a hashed index faster than just matching against a string field? Surely postgres' indexing engine should treat these two things more or less the same, perhaps quietly performing the text -> hash conversion on the email field for quick lookups when it's used directly in an index (and perhaps performing even more optimizations than this basic transform)?

I can confirm that indexing on a hashed value is definitely faster on SQLite at least.

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.

This is purely up to the schema designer or dbadmin. You can create a Postgres index specifying “using hash” to specify that the index will not contain the contents of the field, just its hash.

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.

Surely you give up LIKE queries benefiting from the index this way?

Last time I needed this, LIKE queries still did sequential scans anyway, so the presence of an index or not did not matter.

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.

With a trigram index in PostgreSQL you can even do index-supported leading wildcard searches.

I think GP may be referring to the use of GIN indexes https://www.postgresql.org/docs/current/textsearch-tables.ht...

Yes that.

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!

I've used it successfully at admittedly a small scale to enable full text search of notes-type records on a TEXT field.

I was worried they were talking about doing it manually, and was thinking "surely there's a built-in way to create a hashed index" -- Glad to learn there is!

A couple of obvious reasons why it's not the same: a hashed index is not useful for anything but direct equality comparison.

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.

You're probably right. I'm not really a DB admin I just found the builtin fulltext search when I was tasked with reworking a million + users table to go fast. Boss thought we needed sphinx or elastic or something hahaha

Alternatively you might be able to just use a hash index if you don’t care about range query performance.

it's a huge waste of space and now you have to have triggers somewhere to keep the index field consistent.

the database should be able handle case insensitive indexed lookups directly.

you can use postgres generated columns to keep the index field automatically consistent. https://www.postgresql.org/docs/current/ddl-generated-column...

I've seen this kind of thing a lot before and I'm saying that it's almost never needed. All you're doing is building your own bespoke indexing system on top of a database that is doing it (much better) already.

You're augmenting the indexing system. By using hashes you get a column with fixed predictable size. If the average size of your large strings is larger than 16 bytes (or 32 bytes if you store the hex string) you'll get more rows per memory page. If you've got many millions of rows the savings adds up. A little bit of savings let's a smaller DB instance go farther.

Oh wow that makes perfect sense, I see exactly why this solution would work better now, very good point.

The other thing is that if you're inserting your emails in without running some ToLower() function on them first in the validation, you're probably making a bit of a mistake. There's some other discussion in the thread about this.

You should definitely normalize e-mails before hashing or doing any comparison on the back end. Especially if you've had a stage during account creation where you verified delivery of that normalized address. When you take in an address later you normalize the input and compare it to your stored value (that itself was normalized before storage).

This is using the DB as designed. Not a bespoke solution.

Couldn’t you use an expression index, or even a stored generated column with a normal index on it?

Just use an expression index.

Can't you use CITEXT for this?