The executor is capable of splitting buckets during a hash join if too much memory is being used by a small number of buckets. However, this only helps if a bucket's population is actually divisible; if all the hash keys are alike, the tuples still end up in the same new bucket. This can result in an OOM failure if there are enough inner keys with identical hash values. The planner's cost estimates will bias it against choosing a hash join in such situations, but not by so much that it will never do so. To mitigate the OOM hazard, explicitly estimate the hash bucket space needed by just the inner side's most common value, and if that would exceed work_mem then add disable_cost to the hash cost estimate.
This approach doesn't account for the possibility that two or more common values would share the same hash value. On the other hand, work_mem is normally a fairly conservative bound, so that eating two or more times that much space is probably not going to kill us.
If we have no stats about the inner side, ignore this consideration. There was some discussion of making a conservative assumption, but that would effectively result in disabling hash join whenever we lack stats, which seems like an overreaction given how seldom the problem manifests in the field.
Per a complaint from David Hinkle. Although this could be viewed as a bug fix, the lack of similar complaints weighs against back-patching; indeed we waited for v11 because it seemed already rather late in the v10 cycle to be making plan choice changes like this one.
4867d7f Avoid out-of-memory in a hash join with many duplicate inner keys.
src/backend/nodes/copyfuncs.c | 2 +
src/backend/optimizer/path/costsize.c | 55 +++++++++++++++------
src/backend/optimizer/prep/prepunion.c | 2 +
src/backend/optimizer/util/restrictinfo.c | 2 +
src/backend/utils/adt/selfuncs.c | 80 ++++++++++++++++++-------------
src/include/nodes/relation.h | 2 +
src/include/utils/selfuncs.h | 6 ++-
7 files changed, 100 insertions(+), 49 deletions(-)