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

Commit8dcf184

Browse files
committed
Fix cost_nestloop and cost_hashjoin to model the behavior of semi and anti
joins a bit better, ie, understand the differing cost functions for matchedand unmatched outer tuples. There is more that could be done in cost_hashjoinbut this already helps a great deal. Per discussions with Robert Haas.
1 parenta41e9ec commit8dcf184

File tree

4 files changed

+388
-97
lines changed

4 files changed

+388
-97
lines changed

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

Lines changed: 297 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -54,7 +54,7 @@
5454
* Portions Copyright (c) 1994, Regents of the University of California
5555
*
5656
* IDENTIFICATION
57-
* $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.207 2009/04/17 15:33:33 tgl Exp $
57+
* $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.208 2009/05/09 22:51:41 tgl Exp $
5858
*
5959
*-------------------------------------------------------------------------
6060
*/
@@ -71,6 +71,7 @@
7171
#include"optimizer/pathnode.h"
7272
#include"optimizer/placeholder.h"
7373
#include"optimizer/planmain.h"
74+
#include"optimizer/restrictinfo.h"
7475
#include"parser/parsetree.h"
7576
#include"utils/lsyscache.h"
7677
#include"utils/selfuncs.h"
@@ -119,6 +120,11 @@ static MergeScanSelCache *cached_scansel(PlannerInfo *root,
119120
RestrictInfo*rinfo,
120121
PathKey*pathkey);
121122
staticboolcost_qual_eval_walker(Node*node,cost_qual_eval_context*context);
123+
staticbooladjust_semi_join(PlannerInfo*root,JoinPath*path,
124+
SpecialJoinInfo*sjinfo,
125+
Selectivity*outer_match_frac,
126+
Selectivity*match_count,
127+
bool*indexed_join_quals);
122128
staticdoubleapprox_tuple_count(PlannerInfo*root,JoinPath*path,
123129
List*quals);
124130
staticvoidset_rel_width(PlannerInfo*root,RelOptInfo*rel);
@@ -1394,11 +1400,15 @@ cost_nestloop(NestPath *path, PlannerInfo *root, SpecialJoinInfo *sjinfo)
13941400
Path*inner_path=path->innerjoinpath;
13951401
Coststartup_cost=0;
13961402
Costrun_cost=0;
1403+
Costinner_run_cost;
13971404
Costcpu_per_tuple;
13981405
QualCostrestrict_qual_cost;
13991406
doubleouter_path_rows=PATH_ROWS(outer_path);
14001407
doubleinner_path_rows=nestloop_inner_path_rows(inner_path);
14011408
doublentuples;
1409+
Selectivityouter_match_frac;
1410+
Selectivitymatch_count;
1411+
boolindexed_join_quals;
14021412

14031413
if (!enable_nestloop)
14041414
startup_cost+=disable_cost;
@@ -1428,13 +1438,66 @@ cost_nestloop(NestPath *path, PlannerInfo *root, SpecialJoinInfo *sjinfo)
14281438
*/
14291439
run_cost+= (outer_path_rows-1)*inner_path->startup_cost;
14301440
}
1431-
run_cost+=outer_path_rows*
1432-
(inner_path->total_cost-inner_path->startup_cost);
1441+
inner_run_cost=inner_path->total_cost-inner_path->startup_cost;
14331442

1434-
/*
1435-
* Compute number of tuples processed (not number emitted!)
1436-
*/
1437-
ntuples=outer_path_rows*inner_path_rows;
1443+
if (adjust_semi_join(root,path,sjinfo,
1444+
&outer_match_frac,
1445+
&match_count,
1446+
&indexed_join_quals))
1447+
{
1448+
doubleouter_matched_rows;
1449+
Selectivityinner_scan_frac;
1450+
1451+
/*
1452+
* SEMI or ANTI join: executor will stop after first match.
1453+
*
1454+
* For an outer-rel row that has at least one match, we can expect the
1455+
* inner scan to stop after a fraction 1/(match_count+1) of the inner
1456+
* rows, if the matches are evenly distributed. Since they probably
1457+
* aren't quite evenly distributed, we apply a fuzz factor of 2.0 to
1458+
* that fraction. (If we used a larger fuzz factor, we'd have to
1459+
* clamp inner_scan_frac to at most 1.0; but since match_count is at
1460+
* least 1, no such clamp is needed now.)
1461+
*/
1462+
outer_matched_rows=rint(outer_path_rows*outer_match_frac);
1463+
inner_scan_frac=2.0 / (match_count+1.0);
1464+
1465+
/* Add inner run cost for outer tuples having matches */
1466+
run_cost+=outer_matched_rows*inner_run_cost*inner_scan_frac;
1467+
1468+
/* Compute number of tuples processed (not number emitted!) */
1469+
ntuples=outer_matched_rows*inner_path_rows*inner_scan_frac;
1470+
1471+
/*
1472+
* For unmatched outer-rel rows, there are two cases. If the inner
1473+
* path is an indexscan using all the joinquals as indexquals, then
1474+
* an unmatched row results in an indexscan returning no rows, which
1475+
* is probably quite cheap. We estimate this case as the same cost
1476+
* to return the first tuple of a nonempty scan. Otherwise, the
1477+
* executor will have to scan the whole inner rel; not so cheap.
1478+
*/
1479+
if (indexed_join_quals)
1480+
{
1481+
run_cost+= (outer_path_rows-outer_matched_rows)*
1482+
inner_run_cost /inner_path_rows;
1483+
/* We won't be evaluating any quals at all for these rows */
1484+
}
1485+
else
1486+
{
1487+
run_cost+= (outer_path_rows-outer_matched_rows)*
1488+
inner_run_cost;
1489+
ntuples+= (outer_path_rows-outer_matched_rows)*
1490+
inner_path_rows;
1491+
}
1492+
}
1493+
else
1494+
{
1495+
/* Normal case; we'll scan whole input rel for each outer row */
1496+
run_cost+=outer_path_rows*inner_run_cost;
1497+
1498+
/* Compute number of tuples processed (not number emitted!) */
1499+
ntuples=outer_path_rows*inner_path_rows;
1500+
}
14381501

14391502
/* CPU costs */
14401503
cost_qual_eval(&restrict_qual_cost,path->joinrestrictinfo,root);
@@ -1731,6 +1794,9 @@ cost_mergejoin(MergePath *path, PlannerInfo *root, SpecialJoinInfo *sjinfo)
17311794
* cpu_tuple_cost plus the cost of evaluating additional restriction
17321795
* clauses that are to be applied at the join.(This is pessimistic since
17331796
* not all of the quals may get evaluated at each tuple.)
1797+
*
1798+
* Note: we could adjust for SEMI/ANTI joins skipping some qual evaluations
1799+
* here, but it's probably not worth the trouble.
17341800
*/
17351801
startup_cost+=qp_qual_cost.startup;
17361802
cpu_per_tuple=cpu_tuple_cost+qp_qual_cost.per_tuple;
@@ -1824,6 +1890,8 @@ cost_hashjoin(HashPath *path, PlannerInfo *root, SpecialJoinInfo *sjinfo)
18241890
intnum_skew_mcvs;
18251891
doublevirtualbuckets;
18261892
Selectivityinnerbucketsize;
1893+
Selectivityouter_match_frac;
1894+
Selectivitymatch_count;
18271895
ListCell*hcl;
18281896

18291897
if (!enable_hashjoin)
@@ -1838,12 +1906,6 @@ cost_hashjoin(HashPath *path, PlannerInfo *root, SpecialJoinInfo *sjinfo)
18381906
qp_qual_cost.startup-=hash_qual_cost.startup;
18391907
qp_qual_cost.per_tuple-=hash_qual_cost.per_tuple;
18401908

1841-
/*
1842-
* Get approx # tuples passing the hashquals. We use approx_tuple_count
1843-
* here because we need an estimate done with JOIN_INNER semantics.
1844-
*/
1845-
hashjointuples=approx_tuple_count(root,&path->jpath,hashclauses);
1846-
18471909
/* cost of source data */
18481910
startup_cost+=outer_path->startup_cost;
18491911
run_cost+=outer_path->total_cost-outer_path->startup_cost;
@@ -1970,18 +2032,78 @@ cost_hashjoin(HashPath *path, PlannerInfo *root, SpecialJoinInfo *sjinfo)
19702032

19712033
/* CPU costs */
19722034

1973-
/*
1974-
* The number of tuple comparisons needed is the number of outer tuples
1975-
* times the typical number of tuples in a hash bucket, which is the inner
1976-
* relation size times its bucketsize fraction. At each one, we need to
1977-
* evaluate the hashjoin quals. But actually, charging the full qual eval
1978-
* cost at each tuple is pessimistic, since we don't evaluate the quals
1979-
* unless the hash values match exactly. For lack of a better idea, halve
1980-
* the cost estimate to allow for that.
1981-
*/
1982-
startup_cost+=hash_qual_cost.startup;
1983-
run_cost+=hash_qual_cost.per_tuple*
1984-
outer_path_rows*clamp_row_est(inner_path_rows*innerbucketsize)*0.5;
2035+
if (adjust_semi_join(root,&path->jpath,sjinfo,
2036+
&outer_match_frac,
2037+
&match_count,
2038+
NULL))
2039+
{
2040+
doubleouter_matched_rows;
2041+
Selectivityinner_scan_frac;
2042+
2043+
/*
2044+
* SEMI or ANTI join: executor will stop after first match.
2045+
*
2046+
* For an outer-rel row that has at least one match, we can expect the
2047+
* bucket scan to stop after a fraction 1/(match_count+1) of the
2048+
* bucket's rows, if the matches are evenly distributed. Since they
2049+
* probably aren't quite evenly distributed, we apply a fuzz factor of
2050+
* 2.0 to that fraction. (If we used a larger fuzz factor, we'd have
2051+
* to clamp inner_scan_frac to at most 1.0; but since match_count is
2052+
* at least 1, no such clamp is needed now.)
2053+
*/
2054+
outer_matched_rows=rint(outer_path_rows*outer_match_frac);
2055+
inner_scan_frac=2.0 / (match_count+1.0);
2056+
2057+
startup_cost+=hash_qual_cost.startup;
2058+
run_cost+=hash_qual_cost.per_tuple*outer_matched_rows*
2059+
clamp_row_est(inner_path_rows*innerbucketsize*inner_scan_frac)*0.5;
2060+
2061+
/*
2062+
* For unmatched outer-rel rows, the picture is quite a lot different.
2063+
* In the first place, there is no reason to assume that these rows
2064+
* preferentially hit heavily-populated buckets; instead assume they
2065+
* are uncorrelated with the inner distribution and so they see an
2066+
* average bucket size of inner_path_rows / virtualbuckets. In the
2067+
* second place, it seems likely that they will have few if any
2068+
* exact hash-code matches and so very few of the tuples in the
2069+
* bucket will actually require eval of the hash quals. We don't
2070+
* have any good way to estimate how many will, but for the moment
2071+
* assume that the effective cost per bucket entry is one-tenth what
2072+
* it is for matchable tuples.
2073+
*/
2074+
run_cost+=hash_qual_cost.per_tuple*
2075+
(outer_path_rows-outer_matched_rows)*
2076+
clamp_row_est(inner_path_rows /virtualbuckets)*0.05;
2077+
2078+
/* Get # of tuples that will pass the basic join */
2079+
if (path->jpath.jointype==JOIN_SEMI)
2080+
hashjointuples=outer_matched_rows;
2081+
else
2082+
hashjointuples=outer_path_rows-outer_matched_rows;
2083+
}
2084+
else
2085+
{
2086+
/*
2087+
* The number of tuple comparisons needed is the number of outer
2088+
* tuples times the typical number of tuples in a hash bucket, which
2089+
* is the inner relation size times its bucketsize fraction. At each
2090+
* one, we need to evaluate the hashjoin quals. But actually,
2091+
* charging the full qual eval cost at each tuple is pessimistic,
2092+
* since we don't evaluate the quals unless the hash values match
2093+
* exactly. For lack of a better idea, halve the cost estimate to
2094+
* allow for that.
2095+
*/
2096+
startup_cost+=hash_qual_cost.startup;
2097+
run_cost+=hash_qual_cost.per_tuple*outer_path_rows*
2098+
clamp_row_est(inner_path_rows*innerbucketsize)*0.5;
2099+
2100+
/*
2101+
* Get approx # tuples passing the hashquals. We use
2102+
* approx_tuple_count here because we need an estimate done with
2103+
* JOIN_INNER semantics.
2104+
*/
2105+
hashjointuples=approx_tuple_count(root,&path->jpath,hashclauses);
2106+
}
19852107

19862108
/*
19872109
* For each tuple that gets through the hashjoin proper, we charge
@@ -2320,6 +2442,156 @@ cost_qual_eval_walker(Node *node, cost_qual_eval_context *context)
23202442
}
23212443

23222444

2445+
/*
2446+
* adjust_semi_join
2447+
* Estimate how much of the inner input a SEMI or ANTI join
2448+
* can be expected to scan.
2449+
*
2450+
* In a hash or nestloop SEMI/ANTI join, the executor will stop scanning
2451+
* inner rows as soon as it finds a match to the current outer row.
2452+
* We should therefore adjust some of the cost components for this effect.
2453+
* This function computes some estimates needed for these adjustments.
2454+
*
2455+
* 'path' is already filled in except for the cost fields
2456+
* 'sjinfo' is extra info about the join for selectivity estimation
2457+
*
2458+
* Returns TRUE if this is a SEMI or ANTI join, FALSE if not.
2459+
*
2460+
* Output parameters (set only in TRUE-result case):
2461+
* *outer_match_frac is set to the fraction of the outer tuples that are
2462+
*expected to have at least one match.
2463+
* *match_count is set to the average number of matches expected for
2464+
*outer tuples that have at least one match.
2465+
* *indexed_join_quals is set to TRUE if all the joinquals are used as
2466+
*inner index quals, FALSE if not.
2467+
*
2468+
* indexed_join_quals can be passed as NULL if that information is not
2469+
* relevant (it is only useful for the nestloop case).
2470+
*/
2471+
staticbool
2472+
adjust_semi_join(PlannerInfo*root,JoinPath*path,SpecialJoinInfo*sjinfo,
2473+
Selectivity*outer_match_frac,
2474+
Selectivity*match_count,
2475+
bool*indexed_join_quals)
2476+
{
2477+
JoinTypejointype=path->jointype;
2478+
Selectivityjselec;
2479+
Selectivitynselec;
2480+
Selectivityavgmatch;
2481+
SpecialJoinInfonorm_sjinfo;
2482+
List*joinquals;
2483+
ListCell*l;
2484+
2485+
/* Fall out if it's not JOIN_SEMI or JOIN_ANTI */
2486+
if (jointype!=JOIN_SEMI&&jointype!=JOIN_ANTI)
2487+
return false;
2488+
2489+
/*
2490+
* Note: it's annoying to repeat this selectivity estimation on each call,
2491+
* when the joinclause list will be the same for all path pairs
2492+
* implementing a given join. clausesel.c will save us from the worst
2493+
* effects of this by caching at the RestrictInfo level; but perhaps it'd
2494+
* be worth finding a way to cache the results at a higher level.
2495+
*/
2496+
2497+
/*
2498+
* In an ANTI join, we must ignore clauses that are "pushed down",
2499+
* since those won't affect the match logic. In a SEMI join, we do not
2500+
* distinguish joinquals from "pushed down" quals, so just use the whole
2501+
* restrictinfo list.
2502+
*/
2503+
if (jointype==JOIN_ANTI)
2504+
{
2505+
joinquals=NIL;
2506+
foreach(l,path->joinrestrictinfo)
2507+
{
2508+
RestrictInfo*rinfo= (RestrictInfo*)lfirst(l);
2509+
2510+
Assert(IsA(rinfo,RestrictInfo));
2511+
if (!rinfo->is_pushed_down)
2512+
joinquals=lappend(joinquals,rinfo);
2513+
}
2514+
}
2515+
else
2516+
joinquals=path->joinrestrictinfo;
2517+
2518+
/*
2519+
* Get the JOIN_SEMI or JOIN_ANTI selectivity of the join clauses.
2520+
*/
2521+
jselec=clauselist_selectivity(root,
2522+
joinquals,
2523+
0,
2524+
jointype,
2525+
sjinfo);
2526+
2527+
/*
2528+
* Also get the normal inner-join selectivity of the join clauses.
2529+
*/
2530+
norm_sjinfo.type=T_SpecialJoinInfo;
2531+
norm_sjinfo.min_lefthand=path->outerjoinpath->parent->relids;
2532+
norm_sjinfo.min_righthand=path->innerjoinpath->parent->relids;
2533+
norm_sjinfo.syn_lefthand=path->outerjoinpath->parent->relids;
2534+
norm_sjinfo.syn_righthand=path->innerjoinpath->parent->relids;
2535+
norm_sjinfo.jointype=JOIN_INNER;
2536+
/* we don't bother trying to make the remaining fields valid */
2537+
norm_sjinfo.lhs_strict= false;
2538+
norm_sjinfo.delay_upper_joins= false;
2539+
norm_sjinfo.join_quals=NIL;
2540+
2541+
nselec=clauselist_selectivity(root,
2542+
joinquals,
2543+
0,
2544+
JOIN_INNER,
2545+
&norm_sjinfo);
2546+
2547+
/* Avoid leaking a lot of ListCells */
2548+
if (jointype==JOIN_ANTI)
2549+
list_free(joinquals);
2550+
2551+
/*
2552+
* jselec can be interpreted as the fraction of outer-rel rows that have
2553+
* any matches (this is true for both SEMI and ANTI cases). And nselec
2554+
* is the fraction of the Cartesian product that matches. So, the
2555+
* average number of matches for each outer-rel row that has at least
2556+
* one match is nselec * inner_rows / jselec.
2557+
*
2558+
* Note: it is correct to use the inner rel's "rows" count here, not
2559+
* PATH_ROWS(), even if the inner path under consideration is an inner
2560+
* indexscan. This is because we have included all the join clauses
2561+
* in the selectivity estimate, even ones used in an inner indexscan.
2562+
*/
2563+
if (jselec>0)/* protect against zero divide */
2564+
{
2565+
avgmatch=nselec*path->innerjoinpath->parent->rows /jselec;
2566+
/* Clamp to sane range */
2567+
avgmatch=Max(1.0,avgmatch);
2568+
}
2569+
else
2570+
avgmatch=1.0;
2571+
2572+
*outer_match_frac=jselec;
2573+
*match_count=avgmatch;
2574+
2575+
/*
2576+
* If requested, check whether the inner path uses all the joinquals
2577+
* as indexquals. (If that's true, we can assume that an unmatched
2578+
* outer tuple is cheap to process, whereas otherwise it's probably
2579+
* expensive.)
2580+
*/
2581+
if (indexed_join_quals)
2582+
{
2583+
List*nrclauses;
2584+
2585+
nrclauses=select_nonredundant_join_clauses(root,
2586+
path->joinrestrictinfo,
2587+
path->innerjoinpath);
2588+
*indexed_join_quals= (nrclauses==NIL);
2589+
}
2590+
2591+
return true;
2592+
}
2593+
2594+
23232595
/*
23242596
* approx_tuple_count
23252597
*Quick-and-dirty estimation of the number of join rows passing

0 commit comments

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