7 ms·

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 t

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)?

necovek 4y ago
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.
deleted 4y ago
[deleted]
CodeWriter23 4y ago
I think GP may be referring to the use of GIN indexes https://www.postgresql.org/docs/current/textsearch-tables.html#TEXTSEARCH-TABLES-INDEX https://www.postgresql.org/docs/current/textsearch-tables.ht...
- jamal-kumar 4y ago
  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!
  - CodeWriter23 4y ago
    I've used it successfully at admittedly a small scale to enable full text search of notes-type records on a TEXT field.
- jefftk 4y ago
  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!
sieabahlpark 4y ago
zffr 4y ago
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.
- quickthrower2 4y ago
  Surely you give up LIKE queries benefiting from the index this way?
  - necovek 4y ago
    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.
    - tpetry 4y ago
      With a trigram index in PostgreSQL you can even do index-supported leading wildcard searches.
- ComputerGuru 4y ago
  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.

necovek 4y ago

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.

deleted 4y ago

[deleted]

CodeWriter23 4y ago

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

jamal-kumar 4y ago
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!
- CodeWriter23 4y ago
  I've used it successfully at admittedly a small scale to enable full text search of notes-type records on a TEXT field.
jefftk 4y ago
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!

sieabahlpark 4y ago

zffr 4y ago

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.

quickthrower2 4y ago
Surely you give up LIKE queries benefiting from the index this way?
- necovek 4y ago
  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.
  - tpetry 4y ago
    With a trigram index in PostgreSQL you can even do index-supported leading wildcard searches.
ComputerGuru 4y ago
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.