11

For every version of Postgres that supported hash indexing, there is a warning or note that hash indexes are "similar or slower" or "not better" than btree indexes, at least up to version 8.3. From the docs:

Version 7.2:

Note: Because of the limited utility of hash indexes, a B-tree index should generally be preferred over a hash index. We do not have sufficient evidence that hash indexes are actually faster than B-trees even for = comparisons. Moreover, hash indexes require coarser locks; see Section 9.7.

Version 7.3 (and up to 8.2):

Note: Testing has shown PostgreSQL's hash indexes to be similar or slower than B-tree indexes, and the index size and build time for hash indexes is much worse. Hash indexes also suffer poor performance under high concurrency. For these reasons, hash index use is discouraged.

Version 8.3:

Note: Testing has shown PostgreSQL's hash indexes to perform no better than B-tree indexes, and the index size and build time for hash indexes is much worse. Furthermore, hash index operations are not presently WAL-logged, so hash indexes might need to be rebuilt with REINDEX after a database crash. For these reasons, hash index use is presently discouraged.

In this version 8.0 thread, they claim that had never found a case where hash indexes were actually faster than btree.

Even in version 9.2, the performance gain for anything other than writing the actual index was almost nothing according to this blog post (14 March 2016):
Hash Indexes on Postgres by André Barbosa.

My question is how is that possible?

By definition, Hash indexes are a O(1) operation, where a btree is an O(log n) operation. So how is it possible for a O(1) lookup to be slower than (or even similar to) finding the correct branch, and then finding the correct record?

I want to know what about indexing theory could EVER make that a possibility!

3
  • Discussion has moved to chat. – ypercubeᵀᴹ Jul 19 '18 at 18:33
  • The versions discussed here are ancient, and it's not true that hash indexes are slower than btree in more recent versions (e.g. Postgres 11). – qris Dec 20 '20 at 12:14
  • @qris stop necrobumping. I've already covered this with you. This is about the THEORY not whether it's improved now – Sampson Crowley Dec 22 '20 at 20:01
9

Disk based Btree indexes truly are O(log N), but that is pretty much irrelevant for disk arrays that fit in this solar system. Due to caching, they are mostly O(1) with a very large constant plus O((log N)-1) with a small constant. Formally, that is the same thing as O(log N), because constants don't matter in big O notation. But they do matter in reality.

Much of the slow down in hash index lookups came from the need to protect against corruption or deadlocks caused by hash-table resizing concurrent with the lookups. Until recent versions (every version you mention is comically out of date), this need led to even higher constants and to rather poor concurrency. Vastly more man hours went into the optimization of BTree concurrency than hash concurrency.

1
  • Thank you. I'm very aware of how far past their expiration date those versions are, but I was still curious about how the performance was so far behind what I would have expected – Sampson Crowley Jul 19 '18 at 19:42
6

Hash lookup is theoretically an O(1) operation when the key hash maps directly to the physical location of the target record. The way it works in Postgres, if I understand it correctly, is a bit more complicated: the key hash maps to a bucket that contains the OID you're looking for. A bucket can potentially comprise more than one page, which you need to sequentially scan until you find your particular key (hash). This is why it appears slower than you expect.

The hash index access method README file in the source code repo has all the details.

9
  • so basically a hash index IS a type of branching index as far as psql is concerned – Sampson Crowley Jul 19 '18 at 19:22
  • that actually makes a lot more sense knowing they use buckets to store the actual keys – Sampson Crowley Jul 19 '18 at 19:24
  • also thank you for the link to the readme. I had no idea those existed in the repo – Sampson Crowley Jul 19 '18 at 19:27
  • 2
    The overflow pages do need to be searched linearly, and in worse-case degenerate cases there can be an unbounded number of them. But the searches within a page have a bounded number of items that can exist on a page so they are O(1) per overflow page, and they use a binary search so the constant is not too shabby either. It really was the provision to make operations concurrency safe that was the bottleneck. – jjanes Jul 19 '18 at 19:47
  • 1
    @AnoE -- you'll be surprised... There's always a trade-off between performance and [waste of] resources; in some cases one might favour performance. – mustaccio Jul 19 '18 at 23:18
4

The why? issue is already addressed by other answers, but I question whether the premise is still correct.

Things have moved on in Postgres since 9.6. Hash indexes are now first-class citizens (as they are WAL logged and thus safe to use). And I measured a 40% performance increase over btree in a simple test (unique integers) on Postgres 11.

Like all benchmarks this should be treated with extreme caution. But it's no longer the case that hash indexes are never faster than btree.

The benchmark retrieves 1e7 rows out of 1e8 in a large synthetic table, and consists of the following SQL statements:

create table hash_test as 
select * from generate_series(1e10, 1e10+1e8) as id;

create index idx_btree on hash_test using btree (id); -- 2.5 minutes
create index idx_hash on hash_test using hash (id); -- 4 minutes
analyze hash_test;

-- enable one index (e.g. idx_hash) and disable the other:
update pg_index set indisvalid = (indexrelid = 'idx_hash'::regclass)
where indexrelid in ('idx_btree'::regclass, 'idx_hash'::regclass);

-- fetch and sum 1e7 randomly selected rows:
with ids_to_fetch as (
    select 1e10 + (random() * 1e8)::int as id 
    from generate_series(1, 1e7) as num_rows_to_fetch
)
select sum(id) from hash_test
natural inner join ids_to_fetch

-- only idx_btree enabled: 72, 72, 72 seconds (3 runs)
-- only idx_hash enabled: 42, 43, 43 seconds (3 runs)
4
  • This question is not about if current versions have improved (they have, and the out-of-date-ness of the versions being questioned has already been addressed, and we're up to v13 now; and the question itself event says "up to version 8.3"). It's about the theory on why it didn't match up in the first place. No one ever made the claim that hash indexes are never faster, as you mention. Your answer itself is still well written, but it's not really on-topic – Sampson Crowley Dec 16 '20 at 20:58
  • 2
    @SampsonCrowley the questions still says "For every version of Postgres that supported hash indexing, there is a warning or note that hash indexes are "similar or slower" or "not better" than btree indexes, at least up to version 8.3." This is really badly written, because it definitely implies that hash indexes are not faster than btree, unless one knows that 8.3 is ancient, and that the situation has changed since. And a google search for whether they are brings us to this question. There will be confusion. – qris Dec 17 '20 at 21:11
  • the question is very clear about what versions are being talked about and is accurate for the versions considered. if you can't deduce from the fact that the actual question itself makes it clear that this is about how it's possible for hashing to be slower, the content of the question very clearly saying up to 8.3 and mentioning 9.2 in the same question and has the date 2016 in the question and the fact that PSQL is up to version 13 now, you have other issues that have nothing to do with this question – Sampson Crowley Dec 18 '20 at 23:56
  • 1
    This answer is still useful as Google brings this question up when searching for current information. The original question is perfectly fine, but so is this answer. They are both useful and valuable to have. – Freedom_Ben Dec 29 '20 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.