Sorry for resurrecting this thread, but this has been in my outbox for months and I think it is important: On Oct 27, 2010, at 12:56 PM, Tom Lane wrote: > Scott Carey writes: > > Why does hashjoin behave poorly when the inner relation is not > > uniformly distributed and the outer is? > Because a poorly distributed inner relation leads to long hash chains. > In the very worst case, all the keys are on the same hash chain and it > degenerates to a nested-loop join. (There is an assumption in the > costing code that the longer hash chains also tend to get searched more > often, which maybe doesn't apply if the outer rel is flat, but it's not > obvious that it's safe to not assume that.) I disagree. Either 1: The estimator is wrong or 2: The hash data structure is flawed. A pathological skew case (all relations with the same key), should be _cheaper_ to probe. There should be only _one_ entry in the hash (for the one key), and that entry will be a list of all relations matching the key. Therefore, hash probes will either instantly fail to match on an empty bucket, fail to match the one key with one compare, or match the one key and join on the matching list. In particular for anti-join, high skew should be the best case scenario. A hash structure that allows multiple entries per key is inappropriate for skewed data, because it is not O(n). One that has one entry per key remains O(n) for all skew. Furthermore, the hash buckets and # of entries is proportional to n_distinct in this case, and smaller and more cache and memory friendly to probe. > Not really. It's still searching a long hash chain; maybe it will find > an exact match early in the chain, or maybe not. It's certainly not > *better* than antijoin with a well-distributed inner rel. There shouldn't be long hash chains. A good hash function + proper bucket count + one entry per key = no long chains. > Although the > point is moot, anyway, since if it's an antijoin there is only one > candidate for which rel to put on the outside. You can put either relation on the outside with an anti-join, but would need a different algorithm and cost estimator if done the other way around. Construct a hash on the join key, that keeps a list of relations per key, iterate over the other relation, and remove the key and corresponding list from the hash when there is a match, when complete the remaining items in the hash are the result of the join (also already grouped by the key). It could be terminated early if all entries are removed. This would be useful if the hash was small, the other side of the hash too large to fit in memory, and alternative was a massive sort on the other relation. Does the hash cost estimator bias towards smaller hashes due to hash probe cost increasing with hash size due to processor caching effects? Its not quite O(n) due to caching effects. > regards, tom lane
