Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit4867d7f

Browse files
committed
Avoid out-of-memory in a hash join with many duplicate inner keys.
The executor is capable of splitting buckets during a hash join iftoo much memory is being used by a small number of buckets. However,this only helps if a bucket's population is actually divisible; ifall the hash keys are alike, the tuples still end up in the samenew bucket. This can result in an OOM failure if there are enoughinner keys with identical hash values. The planner's cost estimateswill bias it against choosing a hash join in such situations, but notby so much that it will never do so. To mitigate the OOM hazard,explicitly estimate the hash bucket space needed by just the innerside's most common value, and if that would exceed work_mem thenadd disable_cost to the hash cost estimate.This approach doesn't account for the possibility that two or morecommon values would share the same hash value. On the other hand,work_mem is normally a fairly conservative bound, so that eatingtwo 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 thatwould effectively result in disabling hash join whenever we lack stats,which seems like an overreaction given how seldom the problem manifestsin the field.Per a complaint from David Hinkle. Although this could be viewedas a bug fix, the lack of similar complaints weighs against back-patching; indeed we waited for v11 because it seemed already ratherlate in the v10 cycle to be making plan choice changes like this one.Discussion:https://postgr.es/m/32013.1487271761@sss.pgh.pa.us
1 parentd9a622c commit4867d7f

File tree

7 files changed

+100
-49
lines changed

7 files changed

+100
-49
lines changed

‎src/backend/nodes/copyfuncs.c

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2185,6 +2185,8 @@ _copyRestrictInfo(const RestrictInfo *from)
21852185
COPY_SCALAR_FIELD(hashjoinoperator);
21862186
COPY_SCALAR_FIELD(left_bucketsize);
21872187
COPY_SCALAR_FIELD(right_bucketsize);
2188+
COPY_SCALAR_FIELD(left_mcvfreq);
2189+
COPY_SCALAR_FIELD(right_mcvfreq);
21882190

21892191
returnnewnode;
21902192
}

‎src/backend/optimizer/path/costsize.c

Lines changed: 40 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -3028,6 +3028,7 @@ final_cost_hashjoin(PlannerInfo *root, HashPath *path,
30283028
doublehashjointuples;
30293029
doublevirtualbuckets;
30303030
Selectivityinnerbucketsize;
3031+
Selectivityinnermcvfreq;
30313032
ListCell*hcl;
30323033

30333034
/* Mark the path with the correct row estimate */
@@ -3060,32 +3061,37 @@ final_cost_hashjoin(PlannerInfo *root, HashPath *path,
30603061
virtualbuckets= (double)numbuckets* (double)numbatches;
30613062

30623063
/*
3063-
* Determine bucketsize fractionfor inner relation. We usethesmallest
3064-
*bucketsize estimated for any individual hashclause; this is undoubtedly
3065-
* conservative.
3064+
* Determine bucketsize fractionand MCV frequency fortheinner relation.
3065+
*We use the smallest bucketsize or MCV frequency estimated for any
3066+
*individual hashclause; this is undoubtedlyconservative.
30663067
*
30673068
* BUT: if inner relation has been unique-ified, we can assume it's good
30683069
* for hashing. This is important both because it's the right answer, and
30693070
* because we avoid contaminating the cache with a value that's wrong for
30703071
* non-unique-ified paths.
30713072
*/
30723073
if (IsA(inner_path,UniquePath))
3074+
{
30733075
innerbucketsize=1.0 /virtualbuckets;
3076+
innermcvfreq=0.0;
3077+
}
30743078
else
30753079
{
30763080
innerbucketsize=1.0;
3081+
innermcvfreq=1.0;
30773082
foreach(hcl,hashclauses)
30783083
{
30793084
RestrictInfo*restrictinfo=lfirst_node(RestrictInfo,hcl);
30803085
Selectivitythisbucketsize;
3086+
Selectivitythismcvfreq;
30813087

30823088
/*
30833089
* First we have to figure out which side of the hashjoin clause
30843090
* is the inner side.
30853091
*
30863092
* Since we tend to visit the same clauses over and over when
3087-
* planning a large query, we cache thebucketsize estimate in the
3088-
* RestrictInfo node to avoid repeated lookups of statistics.
3093+
* planning a large query, we cache thebucket stats estimates in
3094+
*theRestrictInfo node to avoid repeated lookups of statistics.
30893095
*/
30903096
if (bms_is_subset(restrictinfo->right_relids,
30913097
inner_path->parent->relids))
@@ -3095,12 +3101,14 @@ final_cost_hashjoin(PlannerInfo *root, HashPath *path,
30953101
if (thisbucketsize<0)
30963102
{
30973103
/* not cached yet */
3098-
thisbucketsize=
3099-
estimate_hash_bucketsize(root,
3100-
get_rightop(restrictinfo->clause),
3101-
virtualbuckets);
3102-
restrictinfo->right_bucketsize=thisbucketsize;
3104+
estimate_hash_bucket_stats(root,
3105+
get_rightop(restrictinfo->clause),
3106+
virtualbuckets,
3107+
&restrictinfo->right_mcvfreq,
3108+
&restrictinfo->right_bucketsize);
3109+
thisbucketsize=restrictinfo->right_bucketsize;
31033110
}
3111+
thismcvfreq=restrictinfo->right_mcvfreq;
31043112
}
31053113
else
31063114
{
@@ -3111,19 +3119,36 @@ final_cost_hashjoin(PlannerInfo *root, HashPath *path,
31113119
if (thisbucketsize<0)
31123120
{
31133121
/* not cached yet */
3114-
thisbucketsize=
3115-
estimate_hash_bucketsize(root,
3116-
get_leftop(restrictinfo->clause),
3117-
virtualbuckets);
3118-
restrictinfo->left_bucketsize=thisbucketsize;
3122+
estimate_hash_bucket_stats(root,
3123+
get_leftop(restrictinfo->clause),
3124+
virtualbuckets,
3125+
&restrictinfo->left_mcvfreq,
3126+
&restrictinfo->left_bucketsize);
3127+
thisbucketsize=restrictinfo->left_bucketsize;
31193128
}
3129+
thismcvfreq=restrictinfo->left_mcvfreq;
31203130
}
31213131

31223132
if (innerbucketsize>thisbucketsize)
31233133
innerbucketsize=thisbucketsize;
3134+
if (innermcvfreq>thismcvfreq)
3135+
innermcvfreq=thismcvfreq;
31243136
}
31253137
}
31263138

3139+
/*
3140+
* If the bucket holding the inner MCV would exceed work_mem, we don't
3141+
* want to hash unless there is really no other alternative, so apply
3142+
* disable_cost. (The executor normally copes with excessive memory usage
3143+
* by splitting batches, but obviously it cannot separate equal values
3144+
* that way, so it will be unable to drive the batch size below work_mem
3145+
* when this is true.)
3146+
*/
3147+
if (relation_byte_size(clamp_row_est(inner_path_rows*innermcvfreq),
3148+
inner_path->pathtarget->width)>
3149+
(work_mem*1024L))
3150+
startup_cost+=disable_cost;
3151+
31273152
/*
31283153
* Compute cost of the hashquals and qpquals (other restriction clauses)
31293154
* separately.

‎src/backend/optimizer/prep/prepunion.c

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2067,6 +2067,8 @@ adjust_appendrel_attrs_mutator(Node *node,
20672067
newinfo->scansel_cache=NIL;
20682068
newinfo->left_bucketsize=-1;
20692069
newinfo->right_bucketsize=-1;
2070+
newinfo->left_mcvfreq=-1;
2071+
newinfo->right_mcvfreq=-1;
20702072

20712073
return (Node*)newinfo;
20722074
}

‎src/backend/optimizer/util/restrictinfo.c

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -199,6 +199,8 @@ make_restrictinfo_internal(Expr *clause,
199199

200200
restrictinfo->left_bucketsize=-1;
201201
restrictinfo->right_bucketsize=-1;
202+
restrictinfo->left_mcvfreq=-1;
203+
restrictinfo->right_mcvfreq=-1;
202204

203205
returnrestrictinfo;
204206
}

‎src/backend/utils/adt/selfuncs.c

Lines changed: 48 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -3559,9 +3559,16 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
35593559
}
35603560

35613561
/*
3562-
* Estimate hash bucketsize fraction (ie, number of entries in a bucket
3563-
* divided by total tuples in relation) if the specified expression is used
3564-
* as a hash key.
3562+
* Estimate hash bucket statistics when the specified expression is used
3563+
* as a hash key for the given number of buckets.
3564+
*
3565+
* This attempts to determine two values:
3566+
*
3567+
* 1. The frequency of the most common value of the expression (returns
3568+
* zero into *mcv_freq if we can't get that).
3569+
*
3570+
* 2. The "bucketsize fraction", ie, average number of entries in a bucket
3571+
* divided by total tuples in relation.
35653572
*
35663573
* XXX This is really pretty bogus since we're effectively assuming that the
35673574
* distribution of hash keys will be the same after applying restriction
@@ -3587,29 +3594,58 @@ estimate_num_groups(PlannerInfo *root, List *groupExprs, double input_rows,
35873594
* discourage use of a hash rather strongly if the inner relation is large,
35883595
* which is what we want. We do not want to hash unless we know that the
35893596
* inner rel is well-dispersed (or the alternatives seem much worse).
3597+
*
3598+
* The caller should also check that the mcv_freq is not so large that the
3599+
* most common value would by itself require an impractically large bucket.
3600+
* In a hash join, the executor can split buckets if they get too big, but
3601+
* obviously that doesn't help for a bucket that contains many duplicates of
3602+
* the same value.
35903603
*/
3591-
Selectivity
3592-
estimate_hash_bucketsize(PlannerInfo*root,Node*hashkey,doublenbuckets)
3604+
void
3605+
estimate_hash_bucket_stats(PlannerInfo*root,Node*hashkey,doublenbuckets,
3606+
Selectivity*mcv_freq,
3607+
Selectivity*bucketsize_frac)
35933608
{
35943609
VariableStatDatavardata;
35953610
doubleestfract,
35963611
ndistinct,
35973612
stanullfrac,
3598-
mcvfreq,
35993613
avgfreq;
36003614
boolisdefault;
36013615
AttStatsSlotsslot;
36023616

36033617
examine_variable(root,hashkey,0,&vardata);
36043618

3619+
/* Look up the frequency of the most common value, if available */
3620+
*mcv_freq=0.0;
3621+
3622+
if (HeapTupleIsValid(vardata.statsTuple))
3623+
{
3624+
if (get_attstatsslot(&sslot,vardata.statsTuple,
3625+
STATISTIC_KIND_MCV,InvalidOid,
3626+
ATTSTATSSLOT_NUMBERS))
3627+
{
3628+
/*
3629+
* The first MCV stat is for the most common value.
3630+
*/
3631+
if (sslot.nnumbers>0)
3632+
*mcv_freq=sslot.numbers[0];
3633+
free_attstatsslot(&sslot);
3634+
}
3635+
}
3636+
36053637
/* Get number of distinct values */
36063638
ndistinct=get_variable_numdistinct(&vardata,&isdefault);
36073639

3608-
/* If ndistinct isn't real, punt and return 0.1, per comments above */
3640+
/*
3641+
* If ndistinct isn't real, punt. We normally return 0.1, but if the
3642+
* mcv_freq is known to be even higher than that, use it instead.
3643+
*/
36093644
if (isdefault)
36103645
{
3646+
*bucketsize_frac= (Selectivity)Max(0.1,*mcv_freq);
36113647
ReleaseVariableStats(vardata);
3612-
return (Selectivity)0.1;
3648+
return;
36133649
}
36143650

36153651
/* Get fraction that are null */
@@ -3650,31 +3686,11 @@ estimate_hash_bucketsize(PlannerInfo *root, Node *hashkey, double nbuckets)
36503686
else
36513687
estfract=1.0 /ndistinct;
36523688

3653-
/*
3654-
* Look up the frequency of the most common value, if available.
3655-
*/
3656-
mcvfreq=0.0;
3657-
3658-
if (HeapTupleIsValid(vardata.statsTuple))
3659-
{
3660-
if (get_attstatsslot(&sslot,vardata.statsTuple,
3661-
STATISTIC_KIND_MCV,InvalidOid,
3662-
ATTSTATSSLOT_NUMBERS))
3663-
{
3664-
/*
3665-
* The first MCV stat is for the most common value.
3666-
*/
3667-
if (sslot.nnumbers>0)
3668-
mcvfreq=sslot.numbers[0];
3669-
free_attstatsslot(&sslot);
3670-
}
3671-
}
3672-
36733689
/*
36743690
* Adjust estimated bucketsize upward to account for skewed distribution.
36753691
*/
3676-
if (avgfreq>0.0&&mcvfreq>avgfreq)
3677-
estfract *=mcvfreq /avgfreq;
3692+
if (avgfreq>0.0&&*mcv_freq>avgfreq)
3693+
estfract *=*mcv_freq /avgfreq;
36783694

36793695
/*
36803696
* Clamp bucketsize to sane range (the above adjustment could easily
@@ -3686,9 +3702,9 @@ estimate_hash_bucketsize(PlannerInfo *root, Node *hashkey, double nbuckets)
36863702
elseif (estfract>1.0)
36873703
estfract=1.0;
36883704

3689-
ReleaseVariableStats(vardata);
3705+
*bucketsize_frac= (Selectivity)estfract;
36903706

3691-
return (Selectivity)estfract;
3707+
ReleaseVariableStats(vardata);
36923708
}
36933709

36943710

‎src/include/nodes/relation.h

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1807,6 +1807,8 @@ typedef struct RestrictInfo
18071807
/* cache space for hashclause processing; -1 if not yet set */
18081808
Selectivityleft_bucketsize;/* avg bucketsize of left side */
18091809
Selectivityright_bucketsize;/* avg bucketsize of right side */
1810+
Selectivityleft_mcvfreq;/* left side's most common val's freq */
1811+
Selectivityright_mcvfreq;/* right side's most common val's freq */
18101812
}RestrictInfo;
18111813

18121814
/*

‎src/include/utils/selfuncs.h

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -206,8 +206,10 @@ extern void mergejoinscansel(PlannerInfo *root, Node *clause,
206206
externdoubleestimate_num_groups(PlannerInfo*root,List*groupExprs,
207207
doubleinput_rows,List**pgset);
208208

209-
externSelectivityestimate_hash_bucketsize(PlannerInfo*root,Node*hashkey,
210-
doublenbuckets);
209+
externvoidestimate_hash_bucket_stats(PlannerInfo*root,
210+
Node*hashkey,doublenbuckets,
211+
Selectivity*mcv_freq,
212+
Selectivity*bucketsize_frac);
211213

212214
externList*deconstruct_indexquals(IndexPath*path);
213215
externvoidgenericcostestimate(PlannerInfo*root,IndexPath*path,

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp