diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c index 05d8538..c2cdd79 100644 *** a/src/backend/nodes/copyfuncs.c --- b/src/backend/nodes/copyfuncs.c *************** _copyRestrictInfo(const RestrictInfo *fr *** 2070,2075 **** --- 2070,2077 ---- COPY_SCALAR_FIELD(hashjoinoperator); COPY_SCALAR_FIELD(left_bucketsize); COPY_SCALAR_FIELD(right_bucketsize); + COPY_SCALAR_FIELD(left_mcvfreq); + COPY_SCALAR_FIELD(right_mcvfreq); return newnode; } diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index d01630f..f88c1c5 100644 *** a/src/backend/optimizer/path/costsize.c --- b/src/backend/optimizer/path/costsize.c *************** final_cost_hashjoin(PlannerInfo *root, H *** 2800,2805 **** --- 2800,2806 ---- double hashjointuples; double virtualbuckets; Selectivity innerbucketsize; + Selectivity innermcvfreq; ListCell *hcl; /* Mark the path with the correct row estimate */ *************** final_cost_hashjoin(PlannerInfo *root, H *** 2827,2835 **** virtualbuckets = (double) numbuckets *(double) numbatches; /* ! * Determine bucketsize fraction for inner relation. We use the smallest ! * bucketsize estimated for any individual hashclause; this is undoubtedly ! * conservative. * * BUT: if inner relation has been unique-ified, we can assume it's good * for hashing. This is important both because it's the right answer, and --- 2828,2836 ---- virtualbuckets = (double) numbuckets *(double) numbatches; /* ! * Determine bucketsize fraction and MCV frequency for the inner relation. ! * We use the smallest bucketsize or MCV frequency estimated for any ! * individual hashclause; this is undoubtedly conservative. * * BUT: if inner relation has been unique-ified, we can assume it's good * for hashing. This is important both because it's the right answer, and *************** final_cost_hashjoin(PlannerInfo *root, H *** 2837,2850 **** --- 2838,2856 ---- * non-unique-ified paths. */ if (IsA(inner_path, UniquePath)) + { innerbucketsize = 1.0 / virtualbuckets; + innermcvfreq = 0.0; + } else { innerbucketsize = 1.0; + innermcvfreq = 1.0; foreach(hcl, hashclauses) { RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(hcl); Selectivity thisbucketsize; + Selectivity thismcvfreq; Assert(IsA(restrictinfo, RestrictInfo)); *************** final_cost_hashjoin(PlannerInfo *root, H *** 2853,2860 **** * is the inner side. * * Since we tend to visit the same clauses over and over when ! * planning a large query, we cache the bucketsize estimate in the ! * RestrictInfo node to avoid repeated lookups of statistics. */ if (bms_is_subset(restrictinfo->right_relids, inner_path->parent->relids)) --- 2859,2866 ---- * is the inner side. * * Since we tend to visit the same clauses over and over when ! * planning a large query, we cache the bucket stats estimates in ! * the RestrictInfo node to avoid repeated lookups of statistics. */ if (bms_is_subset(restrictinfo->right_relids, inner_path->parent->relids)) *************** final_cost_hashjoin(PlannerInfo *root, H *** 2864,2875 **** if (thisbucketsize < 0) { /* not cached yet */ ! thisbucketsize = ! estimate_hash_bucketsize(root, get_rightop(restrictinfo->clause), ! virtualbuckets); restrictinfo->right_bucketsize = thisbucketsize; } } else { --- 2870,2884 ---- if (thisbucketsize < 0) { /* not cached yet */ ! estimate_hash_bucket_stats(root, get_rightop(restrictinfo->clause), ! virtualbuckets, ! &thismcvfreq, ! &thisbucketsize); restrictinfo->right_bucketsize = thisbucketsize; + restrictinfo->right_mcvfreq = thismcvfreq; } + thismcvfreq = restrictinfo->right_mcvfreq; } else { *************** final_cost_hashjoin(PlannerInfo *root, H *** 2880,2899 **** if (thisbucketsize < 0) { /* not cached yet */ ! thisbucketsize = ! estimate_hash_bucketsize(root, get_leftop(restrictinfo->clause), ! virtualbuckets); restrictinfo->left_bucketsize = thisbucketsize; } } if (innerbucketsize > thisbucketsize) innerbucketsize = thisbucketsize; } } /* * Compute cost of the hashquals and qpquals (other restriction clauses) * separately. */ --- 2889,2926 ---- if (thisbucketsize < 0) { /* not cached yet */ ! estimate_hash_bucket_stats(root, get_leftop(restrictinfo->clause), ! virtualbuckets, ! &thismcvfreq, ! &thisbucketsize); restrictinfo->left_bucketsize = thisbucketsize; + restrictinfo->left_mcvfreq = thismcvfreq; } + thismcvfreq = restrictinfo->left_mcvfreq; } if (innerbucketsize > thisbucketsize) innerbucketsize = thisbucketsize; + if (innermcvfreq > thismcvfreq) + innermcvfreq = thismcvfreq; } } /* + * If the bucket holding the inner MCV would exceed work_mem, we don't + * want to hash unless there is really no other alternative, so apply + * disable_cost. (The executor normally copes with excessive memory usage + * by splitting batches, but obviously it cannot separate equal values + * that way, so it will be unable to drive the batch size below work_mem + * when this is true.) + */ + if (relation_byte_size(clamp_row_est(inner_path_rows * innermcvfreq), + inner_path->pathtarget->width) > + (work_mem * 1024L)) + startup_cost += disable_cost; + + /* * Compute cost of the hashquals and qpquals (other restriction clauses) * separately. */ diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c index 06e843d..f6ddb2e 100644 *** a/src/backend/optimizer/prep/prepunion.c --- b/src/backend/optimizer/prep/prepunion.c *************** adjust_appendrel_attrs_mutator(Node *nod *** 1961,1966 **** --- 1961,1968 ---- newinfo->scansel_cache = NIL; newinfo->left_bucketsize = -1; newinfo->right_bucketsize = -1; + newinfo->left_mcvfreq = -1; + newinfo->right_mcvfreq = -1; return (Node *) newinfo; } diff --git a/src/backend/optimizer/util/restrictinfo.c b/src/backend/optimizer/util/restrictinfo.c index 045b5cf..e7efe36 100644 *** a/src/backend/optimizer/util/restrictinfo.c --- b/src/backend/optimizer/util/restrictinfo.c *************** make_restrictinfo_internal(Expr *clause, *** 199,204 **** --- 199,206 ---- restrictinfo->left_bucketsize = -1; restrictinfo->right_bucketsize = -1; + restrictinfo->left_mcvfreq = -1; + restrictinfo->right_mcvfreq = -1; return restrictinfo; } diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c index d14f0f9..816cb65 100644 *** a/src/backend/utils/adt/selfuncs.c --- b/src/backend/utils/adt/selfuncs.c *************** estimate_num_groups(PlannerInfo *root, L *** 3521,3529 **** } /* ! * Estimate hash bucketsize fraction (ie, number of entries in a bucket ! * divided by total tuples in relation) if the specified expression is used ! * as a hash key. * * XXX This is really pretty bogus since we're effectively assuming that the * distribution of hash keys will be the same after applying restriction --- 3521,3536 ---- } /* ! * Estimate hash bucket statistics when the specified expression is used ! * as a hash key for the given number of buckets. ! * ! * This attempts to determine two values: ! * ! * 1. The frequency of the most common value of the expression (returns ! * zero into *mcv_freq if we can't get that). ! * ! * 2. The "bucketsize fraction", ie, average number of entries in a bucket ! * divided by total tuples in relation. * * XXX This is really pretty bogus since we're effectively assuming that the * distribution of hash keys will be the same after applying restriction *************** estimate_num_groups(PlannerInfo *root, L *** 3549,3563 **** * discourage use of a hash rather strongly if the inner relation is large, * which is what we want. We do not want to hash unless we know that the * inner rel is well-dispersed (or the alternatives seem much worse). */ ! Selectivity ! estimate_hash_bucketsize(PlannerInfo *root, Node *hashkey, double nbuckets) { VariableStatData vardata; double estfract, ndistinct, stanullfrac, - mcvfreq, avgfreq; bool isdefault; float4 *numbers; --- 3556,3577 ---- * discourage use of a hash rather strongly if the inner relation is large, * which is what we want. We do not want to hash unless we know that the * inner rel is well-dispersed (or the alternatives seem much worse). + * + * The caller should also check that the mcv_freq is not so large that the + * most common value would by itself require an impractically large bucket. + * In a hash join, the executor can split buckets if they get too big, but + * obviously that doesn't help for a bucket that contains many duplicates of + * the same value. */ ! void ! estimate_hash_bucket_stats(PlannerInfo *root, Node *hashkey, double nbuckets, ! Selectivity *mcv_freq, ! Selectivity *bucketsize_frac) { VariableStatData vardata; double estfract, ndistinct, stanullfrac, avgfreq; bool isdefault; float4 *numbers; *************** estimate_hash_bucketsize(PlannerInfo *ro *** 3565,3578 **** examine_variable(root, hashkey, 0, &vardata); /* Get number of distinct values */ ndistinct = get_variable_numdistinct(&vardata, &isdefault); ! /* If ndistinct isn't real, punt and return 0.1, per comments above */ if (isdefault) { ReleaseVariableStats(vardata); ! return (Selectivity) 0.1; } /* Get fraction that are null */ --- 3579,3618 ---- examine_variable(root, hashkey, 0, &vardata); + /* Look up the frequency of the most common value, if available */ + *mcv_freq = 0.0; + + if (HeapTupleIsValid(vardata.statsTuple)) + { + if (get_attstatsslot(vardata.statsTuple, + vardata.atttype, vardata.atttypmod, + STATISTIC_KIND_MCV, InvalidOid, + NULL, + NULL, NULL, + &numbers, &nnumbers)) + { + /* + * The first MCV stat is for the most common value. + */ + if (nnumbers > 0) + *mcv_freq = numbers[0]; + free_attstatsslot(vardata.atttype, NULL, 0, + numbers, nnumbers); + } + } + /* Get number of distinct values */ ndistinct = get_variable_numdistinct(&vardata, &isdefault); ! /* ! * If ndistinct isn't real, punt. We normally return 0.1, but if the ! * mcv_freq is known to be even higher than that, use it instead. ! */ if (isdefault) { + *bucketsize_frac = (Selectivity) Max(0.1, *mcv_freq); ReleaseVariableStats(vardata); ! return; } /* Get fraction that are null */ *************** estimate_hash_bucketsize(PlannerInfo *ro *** 3614,3647 **** estfract = 1.0 / ndistinct; /* - * Look up the frequency of the most common value, if available. - */ - mcvfreq = 0.0; - - if (HeapTupleIsValid(vardata.statsTuple)) - { - if (get_attstatsslot(vardata.statsTuple, - vardata.atttype, vardata.atttypmod, - STATISTIC_KIND_MCV, InvalidOid, - NULL, - NULL, NULL, - &numbers, &nnumbers)) - { - /* - * The first MCV stat is for the most common value. - */ - if (nnumbers > 0) - mcvfreq = numbers[0]; - free_attstatsslot(vardata.atttype, NULL, 0, - numbers, nnumbers); - } - } - - /* * Adjust estimated bucketsize upward to account for skewed distribution. */ ! if (avgfreq > 0.0 && mcvfreq > avgfreq) ! estfract *= mcvfreq / avgfreq; /* * Clamp bucketsize to sane range (the above adjustment could easily --- 3654,3663 ---- estfract = 1.0 / ndistinct; /* * Adjust estimated bucketsize upward to account for skewed distribution. */ ! if (avgfreq > 0.0 && *mcv_freq > avgfreq) ! estfract *= *mcv_freq / avgfreq; /* * Clamp bucketsize to sane range (the above adjustment could easily *************** estimate_hash_bucketsize(PlannerInfo *ro *** 3653,3661 **** else if (estfract > 1.0) estfract = 1.0; ! ReleaseVariableStats(vardata); ! return (Selectivity) estfract; } --- 3669,3677 ---- else if (estfract > 1.0) estfract = 1.0; ! *bucketsize_frac = (Selectivity) estfract; ! ReleaseVariableStats(vardata); } diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h index f7ac6f6..2b2d950 100644 *** a/src/include/nodes/relation.h --- b/src/include/nodes/relation.h *************** typedef struct RestrictInfo *** 1697,1702 **** --- 1697,1704 ---- /* cache space for hashclause processing; -1 if not yet set */ Selectivity left_bucketsize; /* avg bucketsize of left side */ Selectivity right_bucketsize; /* avg bucketsize of right side */ + Selectivity left_mcvfreq; /* most common val's freq on left side */ + Selectivity right_mcvfreq; /* most common val's freq on right side */ } RestrictInfo; /* diff --git a/src/include/utils/selfuncs.h b/src/include/utils/selfuncs.h index 9f9d2dc..03ed27b 100644 *** a/src/include/utils/selfuncs.h --- b/src/include/utils/selfuncs.h *************** extern void mergejoinscansel(PlannerInfo *** 204,211 **** extern double estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, List **pgset); ! extern Selectivity estimate_hash_bucketsize(PlannerInfo *root, Node *hashkey, ! double nbuckets); extern List *deconstruct_indexquals(IndexPath *path); extern void genericcostestimate(PlannerInfo *root, IndexPath *path, --- 204,213 ---- extern double estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows, List **pgset); ! extern void estimate_hash_bucket_stats(PlannerInfo *root, ! Node *hashkey, double nbuckets, ! Selectivity *mcv_freq, ! Selectivity *bucketsize_frac); extern List *deconstruct_indexquals(IndexPath *path); extern void genericcostestimate(PlannerInfo *root, IndexPath *path,