Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

PostgreSQL's Hash Indexes Are Now Cool

rhaas.blogspot.com

Post reply on HN
Print view View original

31–39 of 39 posts

Re: PostgreSQL's Hash Indexes Are Now Cool

#31

Post by lathiat »

misterbowfinger wrote: post #2

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 SO post: https://stackoverflow.com/a/398921

It is for this reason that the InnoDB Adaptive Hash Index exists: 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.

Re: PostgreSQL's Hash Indexes Are Now Cool

#32

Post by colanderman »

anarazel wrote: post #24
colanderman wrote: post #13

Earlier quoted context omitted.

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…

> 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.) I don't think that's really true - even for btree indexes the heap is accessed to check row visibility. That's necessary because postgres doesn't store visibility information in indexes. There…

The heap need only be accessed if the visibility bitmap indicates it ought to be. (Otherwise index-only scans would be pretty useless.)

"Visibility information is not stored in index entries, only in heap entries; so at first glance it would seem that every row retrieval would require a heap access anyway. And this is indeed the case, if the table row has been modified recently. However, for seldom-changing data there is a way around this problem. PostgreSQL tracks, for each page in a table's heap, whether all rows stored in that page are old enough to be visible to all current and future transactions." [1]

But you are right regarding UNIQUE. No reason it couldn't be implemented for hash indexes.

[1] https://www.postgresql.org/docs/9.6/static/indexes-index-onl...

Re: PostgreSQL's Hash Indexes Are Now Cool

#33

Post by colanderman »

agacera wrote: post #20
Terr_ wrote: post #18

Earlier quoted context omitted.

> Finally, hash indexes always require that the found row be confirmed in the data table Probably to avoid returning the wrong result for statistically-inevitable collisions, right?

Probably it is needed to check if the row is still visible to that transaction.

Postgres uses a visibility bitmap [1] to avoid hitting the heap merely to determine visibility of stable data.

[1] https://www.postgresql.org/docs/9.6/static/indexes-index-onl...

Re: PostgreSQL's Hash Indexes Are Now Cool

#34

Post by anarazel »

colanderman wrote: post #32
anarazel wrote: post #24

Earlier quoted context omitted.

> 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.) I don't think that's really true - even for btree indexes the heap is accessed to check row visibility. That's necessary because postgres doesn't store visibility information in indexes. There…

The heap need only be accessed if the visibility bitmap indicates it ought to be. (Otherwise index-only scans would be pretty useless.) "Visibility information is not stored in index entries, only in heap entries; so at first glance it would seem that every row retrieval would require a heap access anyway. And this is indeed the case, if the table row has been modified recently. However, for seldom-changing data ther…

I think you might have misunderstood what I meant - I was talking about the index insertion case, to verify uniqueness. And that indeed checks the heap regardless of the VM bit. Check _bt_doinsert() invocation of _bt_check_unique() and the latter's content. Therefore there's no fundamental problem with having to do the same in hash insertion cases, even if more heap fetches are likely to be necessary.

https://git.postgresql.org/gitweb/?p=postgresql.git;a=blob;f...

Re: PostgreSQL's Hash Indexes Are Now Cool

#35

Post by colanderman »

anarazel wrote: post #34
colanderman wrote: post #32

Earlier quoted context omitted.

The heap need only be accessed if the visibility bitmap indicates it ought to be. (Otherwise index-only scans would be pretty useless.) "Visibility information is not stored in index entries, only in heap entries; so at first glance it would seem that every row retrieval would require a heap access anyway. And this is indeed the case, if the table row has been modified recently. However, for seldom-changing data ther…

I think you might have misunderstood what I meant - I was talking about the index insertion case, to verify uniqueness. And that indeed checks the heap regardless of the VM bit. Check _bt_doinsert() invocation of _bt_check_unique() and the latter's content. Therefore there's no fundamental problem with having to do the same in hash insertion cases, even if more heap fetches are likely to be necessary. https://git.pos…

Ah gotcha, I thought you were making two separate comments. Makes sense.

Re: PostgreSQL's Hash Indexes Are Now Cool

#36

Post by colanderman »

ankrgyl wrote: post #16
colanderman wrote: post #13

Earlier quoted context omitted.

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…

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…

> 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.

Exactly – my comment is directed at those who think they might be, because O(1) sounds way better than O(log(n)). When really, except for data sets in the 10s of billions of rows, there are more subtle reasons to use them (as you point out).

Re: PostgreSQL's Hash Indexes Are Now Cool

#37

Post by colanderman »

colanderman wrote: post #13
misterbowfinger wrote: post #2

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 SO post: https://stackoverflow.com/a/398921

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…

Too late to edit now but "100 million" should read "20 billion"… I missed a tree layer. (Assuming a branching factor of 200 and 4 GiB of index cache: 500 thousand inner nodes of 8 KiB each can fit in cache, corresponding to 100 million leaves, which can contain 20 billion entries.)

So hash indexes really only begin to show benefits for individual lookups when your data is terabyte-scale, and below that can even be harmful for that use case (if you could otherwise benefit from an index-only lookup). But see ankrgyl's comment (sibling to this one) for better reasons to consider hash indexes.

Re: PostgreSQL's Hash Indexes Are Now Cool

#39

Post by JohnCohorn »

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.
Post reply on HN