I was idly thinking about Joseph Shraibman's problem here:
in which a large hash join seemed to be blowing out memory.
By chance I tried the following test case:

js=# create table ml (jid int);
js=# insert into ml select random()*1000 from generate_series(1,185391404);
INSERT 0 185391404
js=# create table tempjr (id int);
js=# insert into tempjr select random()*1000 from generate_series(1,60000);
INSERT 0 60000
js=# analyze ml;
js=# select count(*) from tempjr join ml on (jid=id) group by jid;

Since I hadn't remembered to increase work_mem beyond the default, this
set up a hash join with 4111 buckets in each of 8192 batches, which
didn't seem too awfully unreasonable, so I let it go.  Imagine my horror
as I watched it stuff all 185 million ml rows into batch 4365.
Naturally, when it got to trying to process that batch, the in-memory
hashtable blew out real good.  I'm not certain this is what happened to
Joseph, since I don't know the stats of his jid column, but in any case
it's got to be fixed.  Hash join is a probabilistic algorithm, so there
will always be some input distributions for which it sucks, but I don't
think we can tolerate "uniformly distributed on the integers 0-N" as
being one of them.

The problem comes from the rather simplistic assignment of bucket and
batch numbers in ExecHashGetBucketAndBatch():

 * Note: on-the-fly increases of nbatch must not change the bucket number
 * for a given hash code (since we don't move tuples to different hash
 * chains), and must only cause the batch number to remain the same or
 * increase.  Our algorithm is
 *              bucketno = hashvalue MOD nbuckets
 *              batchno = (hashvalue DIV nbuckets) MOD nbatch
 * where nbuckets should preferably be prime so that all bits of the
 * hash value can affect both bucketno and batchno.
 * nbuckets doesn't change over the course of the join.

This would be fine if the hashvalues were reasonably randomly
distributed over all uint32 values, but take a look at hashint4 ---
it's just a one's-complement:


Two inputs that differ by 1 will have hash values also differing by 1.
Therefore, in my test case with 4111 buckets, consecutive ranges of 4111
input values map to the same batch --- different buckets in the batch,
but the same batch.  My example with inputs 0..999 would have mapped to
either 1 or 2 batches depending on luck.  With a more realistic
work_mem, nbuckets would have been larger, making this problem worse not

8.1 and up are broken this way; in 8.0 and before we were calculating
the batch number in a different way that doesn't seem vulnerable to
this particular failure mode.

Arguably, the problem here is a chintzy hash function, and we should fix
it by making the integer hash functions use hash_any().  I'm inclined to
do that for 8.3.  The problem is that this is not a back-patchable
answer, because changing the hash functions would corrupt existing hash
indexes.  The best idea I can come up with for the back branches is
to make ExecHashGetBucketAndBatch do hash_any internally, say

        if (nbatch > 1)
                *bucketno = hashvalue % nbuckets;
                /* since nbatch is a power of 2, can do MOD by masking */
-               *batchno = (hashvalue / nbuckets) & (nbatch - 1);
+               *batchno = hash_any(&hashvalue, sizeof(int32)) & (nbatch - 1);
                *bucketno = hashvalue % nbuckets;
                *batchno = 0;

Comments, better ideas?

                        regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 7: You can help support the PostgreSQL project by donating at


Reply via email to