Re: Multicolumn hash indexes

Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> On Wed, Sep 27, 2017 at 9:56 AM, Jesper Pedersen
> <jesper(dot)pedersen(at)redhat(dot)com> wrote:
>> Maybe an initial proof-of-concept could store the hash of the first column
>> (col1) plus the hash of all columns (col1, col2, col3) in the index, and see
>> what requirements / design decisions would appear from that.

> I thought about that sort of thing yesterday but it's not that simple.
> The problem is that the hash code isn't just stored; it's used to
> assign tuples to buckets. If you have two hash codes, you have to
> pick one of the other to use for assigning the tuple to a bucket. And
> then if you want to search using the other hash code, you have to
> search all of the buckets, which will stink.

If we follow GIST's lead that the leading column is "most important",
the idea could be to require a search constraint on the first column,
which produces the hash that determines the bucket assignment. Hashes
for additional columns would just be payload data in the index entry.
If you have search constraint(s) on low-order column(s), you can check
for hash matches before visiting the heap, but they don't reduce how
much of the index you have to search. Even btree works that way for
many combinations of incomplete index constraints.

regards, tom lane