9 ms·

PostgreSQL's Hash Indexes Are Now Cool

214 points by rachbelaid 9y ago

misterbowfinger 9y ago
Wasn't sure what a hash index was vs. btree Short version - hash indexes are faster in PG11, but they only apply to "where = foobar" queries, giving a 0(1) time. Btree indexes have O(logn) But hash indexes can't be applied to range clauses, like "where < 50". You can still use a btree index however. SO post: https://stackoverflow.com/a/398921 https://stackoverflow.com/a/398921
- snaky 9y ago
  > We can see here that the hash index performs better than the btree index and the performance difference is in the range of 10 to 22%. In some other workloads we have seen a better performance like with hash index on varchar columns and even in the community, it has been reported that there is performance improvement in the range of 40-60% when hash indexes are used for unique index columns. the link is from the post http://amitkapila16.blogspot.com/2017/03/hash-indexes-are-faster-than-btree.html http://amitkapila16.blogspot.com/2017/03/hash-indexes-are-fa...
  - slagfart 9y ago
    Don't forget that the performance improvement of hash over b-tree gets better for wide keys - the wider the key, the better the improvement, as the key width is irrelevant to the hash index. Based on the width of the key, the row count and the amount of memory available, there might be instances where a disk-hit gets replaced with an in-memory cache, which is awesome for spinning-disk based systems.
    - snaky 9y ago
      > the wider the key, the better the improvement Good point, I think it would be nice to add it to the docs. Maybe with part numbers of goods as an example - in typical OLTP DB they are variable width strings, mostly read-heavy, unique (not as constraint but as the matter of fact) and searched by almost constantly.
- twoodfin 9y ago
  Hopefully Postgres will also use them for joins? That’s the real performance win, since an equijoin is like N * WHERE X = Y.
  - anarazel 9y ago
    Yes, it will for index nested loops. But e.g. a mergejoin can't really benefit from a hash index, in contrast to a btree index which can provide the ordering without a sort step.
- colanderman 9y ago
  Keep in mind that the log n factor of a B+tree is generally very low; B+tree branching factors are typically in the 100s. Also, the first few levels are generally kept in cache, so you'll only have to hit disk for inner nodes past 100 million entries or so. Finally, hash indexes always require that the found row be confirmed in the data table, even for simple existence queries, since the keys themselves aren't stored in the hash table. (This is why hash indexes can't be UNIQUE.) B+trees can often answer such queries without the extra lookup (an "index-only scan"). If your B+tree is so large that its inner nodes spill onto disk (necessitating a 2nd disk seek), chances are the equivalent hash index will as well, which, combined with the consult of the data table, kind of negates the benefit.
  - ankrgyl 9y ago
    You're right, but I don't think the use case you mentioned (as a competitor to B+ trees for direct lookups) is the target use case for a hash index. A hash index can be a big win for nested loop joins, especially at high concurrency. It is quite common to build a hash table over a subset of the inner table of an equijoin. This is (a) slow to construct and (b) memory-intensive (especially if many of these queries are run concurrently). With a hash index, a lot of cases that required building a hash table to speed up a query can just use the hash index directly. Furthermore, every concurrent instance of the query can use the same hash index. This is a big win for both performance of a single query (latency) and query scalability.
    - koolba 9y ago
      That's a hash join which has existed in Postgres for many years. Hash indexes are unrelated. The primary use case of hash indexes is situations where the indexes fields are very large. The hash index uses a fixed size regardless of the width in bytes of the key so it "wins" storage wise when the key is wide.
      - anarazel 9y ago
        > That's a hash join which has existed in Postgres for many years. Hash indexes are unrelated. I think the OP ankrgyl is aware of that. To quote: >> It is quite common to build a hash table over a subset of the inner table of an equijoin. This is (a) slow to construct and (b) memory-intensive (especially if many of these queries are run concurrently).
- ww520 9y ago
  I think hash index help in join as well. "where table1.c1 = table2.c2" A hash index on c2 would let the join be done in O(n) of c1 + O(1) of c2.
- alexnewman 9y ago
  For now, the big problem with range queries in my mind would be how you get it to return in any reasonable order in any reasonable amount of time.
- lathiat 9y ago
  It is for this reason that the InnoDB Adaptive Hash Index exists: https://dev.mysql.com/doc/refman/5.7/en/innodb-adaptive-hash.html https://dev.mysql.com/doc/refman/5.7/en/innodb-adaptive-hash... > Based on the observed pattern of searches, MySQL builds a hash index using a prefix of the index key. The prefix of the key can be any length, and it may be that only some of the values in the B-tree appear in the hash index. Hash indexes are built on demand for those pages of the index that are often accessed. > If a table fits almost entirely in main memory, a hash index can speed up queries by enabling direct lookup of any element, turning the index value into a sort of pointer. InnoDB has a mechanism that monitors index searches. If InnoDB notices that queries could benefit from building a hash index, it does so automatically. I am really excited by some of the PostgresQL developments lately.. in particular with parallel query execution. To the best of my knowledge the only place that currently exists within MySQL (or MariaDB) is MySQL Cluster.
tofflos 9y ago
Are there any plans for allowing hash indexes in uniqueness constraints such as the ones created for primary keys? It seems like a good fit for an index that is specialized for equality checks.
- snaky 9y ago
  Maybe it would be easier just to remove "A foreign key must reference columns that either are a primary key or form a unique constraint" restriction, stating that any unique index is enough.
  - anarazel 9y ago
    > Maybe it would be easier just to remove "A foreign key must reference columns that either are a primary key or form a unique constraint" restriction, stating that any unique index is enough. The problem is that only btree indexes support uniqueness atm. That's the relevant unsupported features, not the ability to have constraints (which essentially just requires uniqueness support of the underlying index): postgres[27716][1]# SELECT amname, pg_indexam_has_property(oid, 'can_unique') FROM pg_am; ┌────────┬─────────────────────────┐ │ amname │ pg_indexam_has_property │ ├────────┼─────────────────────────┤ │ btree │ t │ │ hash │ f │ │ gist │ f │ │ gin │ f │ │ spgist │ f │ │ brin │ f │ └────────┴─────────────────────────┘ (6 rows) Edit: different uses of word constrain (to constrain, and a constraint) seemed too confusing.
    - jontro 9y ago
      Is the hash guaranteed to be unique though? There is always a possibility of a hash collision
      - anarazel 9y ago
        > Is the hash guaranteed to be unique though? There is always a possibility of a hash collision I mean my point is that hashindexes do not support uniqueness right now. But hash collisions wouldn't be a problem there. Does mainly require some tricky concurrency aware code (consider cases lik ewhere one transaction just deleted a conflicting row but is still in progress, and a new value like that is inserted, etc).
frandroid 9y ago
> A report from a tester who goes by "AP" in July tipped us off to the need for a few further tweaks. AP found that trying to insert 2 billion rows into a newly-created hash index was causing an error. This is what I call trying things "at Indian scale" :D
qaq 9y ago
Any good articles that go into detail on when to use hash indexes in PG 10?
zitterbewegung 9y ago
I hope Postgres keeps on getting Cooler. Reading all the Change Logs makes me feel warm and fuzzy inside .
alexnewman 9y ago
We have been talking about this for a while. Consider the coming of more distributed and nvme based storage and a lot of these things eventually make sense.
Annatar 9y ago
Is it just me, or has PostgreSQL kept on getting better and better, to the point of being #1 DB in the open source market?
JohnCohorn 9y ago
I remember someone commenting a while back that with hash indexes allowing you to navigate relationships in O(1} time, relational DBs can approximate the perf characteristics of a graph DB. When I did a quick and dirty test a couple years ago(before they would have been usable anyway due to durability and replication) I found that hash indexes performed noticeably worse than btree for navigating a few test tables with 10-100m rows each. Curious whether this is a major enough improvement for hash indexes that btree will not still be faster for many common equality lookups.

214 points by rachbelaid 9y ago

Wasn't sure what a hash index was vs. btree Short version - hash indexes are faster in PG11, but they only apply to "where = foobar" queries, giving a 0(1) time. Btree indexes have O(logn) But hash indexes can't be applied to range clauses, like "where < 50". You can still use a btree index however. SO post: https://stackoverflow.com/a/398921 https://stackoverflow.com/a/398921

snaky 9y ago
> We can see here that the hash index performs better than the btree index and the performance difference is in the range of 10 to 22%. In some other workloads we have seen a better performance like with hash index on varchar columns and even in the community, it has been reported that there is performance improvement in the range of 40-60% when hash indexes are used for unique index columns. the link is from the post http://amitkapila16.blogspot.com/2017/03/hash-indexes-are-faster-than-btree.html http://amitkapila16.blogspot.com/2017/03/hash-indexes-are-fa...
- slagfart 9y ago
  Don't forget that the performance improvement of hash over b-tree gets better for wide keys - the wider the key, the better the improvement, as the key width is irrelevant to the hash index. Based on the width of the key, the row count and the amount of memory available, there might be instances where a disk-hit gets replaced with an in-memory cache, which is awesome for spinning-disk based systems.
  - snaky 9y ago
    > the wider the key, the better the improvement Good point, I think it would be nice to add it to the docs. Maybe with part numbers of goods as an example - in typical OLTP DB they are variable width strings, mostly read-heavy, unique (not as constraint but as the matter of fact) and searched by almost constantly.
twoodfin 9y ago
Hopefully Postgres will also use them for joins? That’s the real performance win, since an equijoin is like N * WHERE X = Y.
- anarazel 9y ago
  Yes, it will for index nested loops. But e.g. a mergejoin can't really benefit from a hash index, in contrast to a btree index which can provide the ordering without a sort step.
colanderman 9y ago
Keep in mind that the log n factor of a B+tree is generally very low; B+tree branching factors are typically in the 100s. Also, the first few levels are generally kept in cache, so you'll only have to hit disk for inner nodes past 100 million entries or so. Finally, hash indexes always require that the found row be confirmed in the data table, even for simple existence queries, since the keys themselves aren't stored in the hash table. (This is why hash indexes can't be UNIQUE.) B+trees can often answer such queries without the extra lookup (an "index-only scan"). If your B+tree is so large that its inner nodes spill onto disk (necessitating a 2nd disk seek), chances are the equivalent hash index will as well, which, combined with the consult of the data table, kind of negates the benefit.
- ankrgyl 9y ago
  You're right, but I don't think the use case you mentioned (as a competitor to B+ trees for direct lookups) is the target use case for a hash index. A hash index can be a big win for nested loop joins, especially at high concurrency. It is quite common to build a hash table over a subset of the inner table of an equijoin. This is (a) slow to construct and (b) memory-intensive (especially if many of these queries are run concurrently). With a hash index, a lot of cases that required building a hash table to speed up a query can just use the hash index directly. Furthermore, every concurrent instance of the query can use the same hash index. This is a big win for both performance of a single query (latency) and query scalability.
  - koolba 9y ago
    That's a hash join which has existed in Postgres for many years. Hash indexes are unrelated. The primary use case of hash indexes is situations where the indexes fields are very large. The hash index uses a fixed size regardless of the width in bytes of the key so it "wins" storage wise when the key is wide.
    - anarazel 9y ago
      > That's a hash join which has existed in Postgres for many years. Hash indexes are unrelated. I think the OP ankrgyl is aware of that. To quote: >> It is quite common to build a hash table over a subset of the inner table of an equijoin. This is (a) slow to construct and (b) memory-intensive (especially if many of these queries are run concurrently).
ww520 9y ago
I think hash index help in join as well. "where table1.c1 = table2.c2" A hash index on c2 would let the join be done in O(n) of c1 + O(1) of c2.
alexnewman 9y ago
For now, the big problem with range queries in my mind would be how you get it to return in any reasonable order in any reasonable amount of time.
lathiat 9y ago
It is for this reason that the InnoDB Adaptive Hash Index exists: https://dev.mysql.com/doc/refman/5.7/en/innodb-adaptive-hash.html https://dev.mysql.com/doc/refman/5.7/en/innodb-adaptive-hash... > Based on the observed pattern of searches, MySQL builds a hash index using a prefix of the index key. The prefix of the key can be any length, and it may be that only some of the values in the B-tree appear in the hash index. Hash indexes are built on demand for those pages of the index that are often accessed. > If a table fits almost entirely in main memory, a hash index can speed up queries by enabling direct lookup of any element, turning the index value into a sort of pointer. InnoDB has a mechanism that monitors index searches. If InnoDB notices that queries could benefit from building a hash index, it does so automatically. I am really excited by some of the PostgresQL developments lately.. in particular with parallel query execution. To the best of my knowledge the only place that currently exists within MySQL (or MariaDB) is MySQL Cluster.

tofflos 9y ago

Are there any plans for allowing hash indexes in uniqueness constraints such as the ones created for primary keys? It seems like a good fit for an index that is specialized for equality checks.

snaky 9y ago
Maybe it would be easier just to remove "A foreign key must reference columns that either are a primary key or form a unique constraint" restriction, stating that any unique index is enough.
- anarazel 9y ago
  > Maybe it would be easier just to remove "A foreign key must reference columns that either are a primary key or form a unique constraint" restriction, stating that any unique index is enough. The problem is that only btree indexes support uniqueness atm. That's the relevant unsupported features, not the ability to have constraints (which essentially just requires uniqueness support of the underlying index): postgres[27716][1]# SELECT amname, pg_indexam_has_property(oid, 'can_unique') FROM pg_am; ┌────────┬─────────────────────────┐ │ amname │ pg_indexam_has_property │ ├────────┼─────────────────────────┤ │ btree │ t │ │ hash │ f │ │ gist │ f │ │ gin │ f │ │ spgist │ f │ │ brin │ f │ └────────┴─────────────────────────┘ (6 rows) Edit: different uses of word constrain (to constrain, and a constraint) seemed too confusing.
  - jontro 9y ago
    Is the hash guaranteed to be unique though? There is always a possibility of a hash collision
    - anarazel 9y ago
      > Is the hash guaranteed to be unique though? There is always a possibility of a hash collision I mean my point is that hashindexes do not support uniqueness right now. But hash collisions wouldn't be a problem there. Does mainly require some tricky concurrency aware code (consider cases lik ewhere one transaction just deleted a conflicting row but is still in progress, and a new value like that is inserted, etc).

frandroid 9y ago

> A report from a tester who goes by "AP" in July tipped us off to the need for a few further tweaks. AP found that trying to insert 2 billion rows into a newly-created hash index was causing an error. This is what I call trying things "at Indian scale" :D

qaq 9y ago

Any good articles that go into detail on when to use hash indexes in PG 10?

zitterbewegung 9y ago

I hope Postgres keeps on getting Cooler. Reading all the Change Logs makes me feel warm and fuzzy inside .

alexnewman 9y ago

We have been talking about this for a while. Consider the coming of more distributed and nvme based storage and a lot of these things eventually make sense.

Annatar 9y ago

Is it just me, or has PostgreSQL kept on getting better and better, to the point of being #1 DB in the open source market?

JohnCohorn 9y ago

I remember someone commenting a while back that with hash indexes allowing you to navigate relationships in O(1} time, relational DBs can approximate the perf characteristics of a graph DB. When I did a quick and dirty test a couple years ago(before they would have been usable anyway due to durability and replication) I found that hash indexes performed noticeably worse than btree for navigating a few test tables with 10-100m rows each. Curious whether this is a major enough improvement for hash indexes that btree will not still be faster for many common equality lookups.