I hope Postgres keeps on getting Cooler. Reading all the Change Logs makes me feel warm and fuzzy inside .
PostgreSQL's Hash Indexes Are Now Cool
11–20 of 39 posts
Re: PostgreSQL's Hash Indexes Are Now Cool
#12Wasn'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
Hopefully Postgres will also use them for joins? That’s the real performance win, since an equijoin is like N * WHERE X = Y.
Re: PostgreSQL's Hash Indexes Are Now Cool
#13Wasn'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 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.
Re: PostgreSQL's Hash Indexes Are Now Cool
#14Wasn'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
Hopefully Postgres will also use them for joins? That’s the real performance win, since an equijoin is like N * WHERE X = Y.
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.
Re: PostgreSQL's Hash Indexes Are Now Cool
#15Are 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.
Re: PostgreSQL's Hash Indexes Are Now Cool
#16Wasn'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…
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.
Re: PostgreSQL's Hash Indexes Are Now Cool
#17Wasn'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
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.
Re: PostgreSQL's Hash Indexes Are Now Cool
#18Wasn'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
Probably to avoid returning the wrong result for statistically-inevitable collisions, right?
Re: PostgreSQL's Hash Indexes Are Now Cool
#19Wasn'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
> 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.
Re: PostgreSQL's Hash Indexes Are Now Cool
#20Earlier 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?
Probably it is needed to check if the row is still visible to that transaction.