Re: Multicolumn hash indexes

On Fri, Sep 29, 2017 at 10:54 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> There are few if any indexing techniques where the first column isn't
> significantly more important than the rest --- certainly that's true
> for btree, for example.

Well, BRIN doesn't care.

> I do not think it's a showstopper if that's
> true for hash as well.

Certainly true, but on the other hand, if the design for which you are
advocating doesn't address a problem Tomasz has, he probably won't
want to bother implementing it.

I think it's pretty interesting to think about what other index
designs we might have that using hashing but are not the same as our
existing hash indexes. Reviewing Amit's patches for hash indexes has
helped me to understand how the hash AM works a lot better than I had
before, and it's really a pretty limiting design. The buckets aren't
sorted by hashcode overall, just within a page, which sucks, and the
way that storage allocations are managed within the index is painful.
It might be worth thinking about what we might create for a hash index
today if we were starting over from scratch. Andres proposed a
hash-over-btree thing where you build a hash value for each tuple and
then sort them by hash code and arrange the results into a btree; I
think that would have the same multi-column index problems you're
talking about here, but it would be more space-efficient.

Now you could also imagine something where we keep a separate set of
hash buckets for each column and multi-column searches are handled by
searching each hash table separately and taking the intersection of
the sets of TIDs found for each column. Not sure that's a good idea,
but it's sort of like what GIN does.

There are probably other ideas, too. We should investigate what
others have done. I see that
https://docs.microsoft.com/en-us/sql/relational-databases/in-memory-oltp/hash-indexes-for-memory-optimized-tables
section E.1 claims that SQL Server requires a hash index to include an
equality condition on every column in the index. I still think that's
an appealing option from a theoretical point of view even if the
implementation difficulties are formidable.

Come to think of it, I think that the planner behavior you describe
whereby we put a premium on throwing away unnecessary conditions is
probably not so great in other cases, too. In a btree index, we have
to step through all the tuples in the range covered by the index scan
one by one; if the join sitting above the index scan will reject those
tuples anyway when it tests the join qual, I can see that doing the
same test redundantly at the scan level could well be a loser. But
suppose it's a BRIN index. Now doing the test at the scan level is a
lot more likely to win -- I think -- because BRIN can perform that
test once per page rather than once per tuple, whereas the join will
have to reject individual tuples.

This sounds very similar to the question of whether we ought to infer
implied inequalities, which as you know has been a regular complaint.
It's certainly the case that enforcing an inequality in multiple
places can be inefficient, but it can also be a tremendous win if the
inequality is highly selective, which is not uncommon (e.g. imagine a
sort-and-merge-join between two tables and an inequality on the join
column that knocks out 90% - or 99% - of the rows in each). I have
been wondering whether we need a concept of an optional qual. Instead
of dropping a qual that doesn't need to be enforced, move it to a
separate bucket of quals that can be enforced if it looks like a win
from a cost perspective and otherwise ignored without breaking
anything. Implied inequalities (and maybe implied equalities) could
be thrown into such a bucket as well, allowing the decision about
whether to enforce them to be based on some algorithm or heuristic
rather than a summary judgement.

Or maybe that's not the right concept at all, but I think we need some
idea about how cases like this can be handled. People want the
database to handle the cases about which they care, not judge which
cases those are.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company