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

21–30 of 39 posts

Re: PostgreSQL's Hash Indexes Are Now Cool

#21

Post by colanderman »

Terr_ wrote: post #18
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 Probably to avoid returning the wrong result for statistically-inevitable collisions, right?

Correct.

Re: PostgreSQL's Hash Indexes Are Now Cool

#22

Post by snaky »

slagfart wrote: post #19
snaky wrote: post #3

Earlier quoted context omitted.

> 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 pos…

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.

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

Re: PostgreSQL's Hash Indexes Are Now Cool

#23

Post by anarazel »

smitherfield wrote: post #15
tofflos wrote: post #4

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.

Perhaps I'm missing something, but wouldn't the most efficient possible hash function for a set of unique integers be identity? So I don't see how an ID column would benefit.

You can use such a hashfunction, but it'd not be a good one for general purpose. Remember that hashtables, and also our hash-indexes, use buckets / ranges of hash values to keep the hash-table at reasonable sizes. If you don't use a hash function that has a good bit perturbation, you can end up with a lot of values in the same bucket.

Consider e.g. the common implementation where buckets are determined by masking out either the lowest or the highest bits of the hashvalue. If you mask out the highest bits and your values aren't sequential (pretty common), you end up with a lot of collisions. More extremely, if you mask the low bits and shift, if you only have small values everything ends up in the first bucket. Therefore what you want is a hashfunction where a one bit change at "one side" of the input value, is likely to affect most of the remaining bits.

Re: PostgreSQL's Hash Indexes Are Now Cool

#24

Post by anarazel »

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…

> 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's imo no really big problem making hash indexes support uniqueness - it's "just" work.

Re: PostgreSQL's Hash Indexes Are Now Cool

#25

Post by koolba »

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…

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.

Re: PostgreSQL's Hash Indexes Are Now Cool

#26

Post by anarazel »

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 think the win for that kind of scenario is smaller than you make it out to be. I agree on memory usage, but the concurrency argument seems largely faulty because you at the same time increase page-level contention on a shared resource (postgres' buffer cache).

I personally want a lazily filled hash-join / something like a index nested loop join that has a fixed size cache for both positive and negative lookups.

Re: PostgreSQL's Hash Indexes Are Now Cool

#27

Post by anarazel »

koolba wrote: post #25
ankrgyl wrote: post #16

Earlier quoted context omitted.

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…

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.

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

Re: PostgreSQL's Hash Indexes Are Now Cool

#28

Post by koolba »

anarazel wrote: post #27
koolba wrote: post #25

Earlier quoted context omitted.

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.

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

Ah I think I misread that section with the "nested loop join" stuck in my mind.

Re: PostgreSQL's Hash Indexes Are Now Cool

#30

Post by alexnewman »

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

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