Re: a few crazy ideas about hash joins

Robert Haas wrote:
> While investigating some performance problems recently I've had cause
> to think about the way PostgreSQL uses hash joins. So here are a few
> thoughts. Some of these have been brought up before.
>
> 1. When the hash is not expected to spill to disk, it preserves the
> pathkeys of the outer side of the join. If the optimizer were allowed
> to assume that, it could produce significantly more efficient query
> plans in some cases. The problem is what to do if we start executing
> the query and find out that we have more stuff to hash than we expect,
> such that we need multiple batches? Now the results won't be sorted.
> I think we could handle this as follows: Don't count on the hash join
> to preserve pathkeys unless it helps, and only rely on it when it
> seems as if the hash table will still fit even if it turns out to be,
> say, three times as big as expected. But if you are counting on the
> hash join to preserve pathkeys, then pass that information to the
> executor. When the executor is asked to perform a hash join, it will
> first hash the inner side of the relation. At that point, we know
> whether we've succesfully gotten everything into a single batch, or
> not. If we have, perform the join normally. If the worst has
> happened and we've gone multi-batch, then perform the join and sort
> the output before returning it. The performance will suck, but at
> least you'll get the right answer.
>
> Previous in-passing reference to this idea here:
> http://archives.postgresql.org/pgsql-hackers/2008-09/msg00806.php

Hmm, instead of a sorting the output if the worst happens, a final merge
step as in a merge sort would be enough.

> 2. Consider building the hash table lazily. I often see query planner
> pick a hash join over a nested inner indexscan because it thinks that
> it'll save enough time making hash probes rather than index probes to
> justify the time spent building the hash table up front. But
> sometimes the relation that's being hashed has a couple thousand rows,
> only a tiny fraction of which will ever be retrieved from the hash
> table. We can predict when this is going to happen because n_distinct
> for the outer column will be much less than the size of the inner rel.
> In that case, we could consider starting with an empty hash table
> that effectively acts as a cache. Each time a value is probed, we
> look it up in the hash table. If there's no entry, we use an index
> scan to find the matching rows and insert them into the hash table.
> Negative results must also be cached.

Yeah, that would be quite nice. One problem is that our ndistinct
estimates are not very accurate.

> 3. Avoid building the exact same hash table twice in the same query.
> This happens more often you'd think. For example, a table may have
> two columns creator_id and last_updater_id which both reference person
> (id). If you're considering a hash join between paths A and B, you
> could conceivably check whether what is essentially a duplicate of B
> has already been hashed somewhere within path A. If so, you can reuse
> that same hash table at zero startup-cost.

That seems like a quite simple thing to do. But would it work for a
multi-batch hash table?

> 4. As previously discussed, avoid hashing for distinct and then
> hashing the results for a hash join on the same column with the same
> operators.

This seems essentially an extension of idea 3.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com