Re: Next Steps with Hash Indexes

John Naylor <john(dot)naylor(at)enterprisedb(dot)com> writes:
> (Standard disclaimer that I'm not qualified to design index AMs) I've seen
> one mention in the literature about the possibility of simply having a
> btree index over the hash values.

Yeah, that's been talked about in the past --- we considered it
moderately seriously back when the hash AM was really only a toy
for lack of WAL support. The main knock on it is that searching
a btree is necessarily O(log N), while in principle a hash probe
could be O(1). Of course, a badly-implemented hash AM could be
worse than O(1), but we'd basically be giving up on ever getting
to O(1).

There's a separate discussion to be had about whether there should
be an easier way for users to build indexes that are btrees of
hashes. You can do it today but the indexes aren't pleasant to
use, requiring query adjustment.

regards, tom lane