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

Commite2fa76d

Browse files
committed
Use parameterized paths to generate inner indexscans more flexibly.
This patch fixes the planner so that it can generate nestloop-with-inner-indexscan plans even with one or more levels of joining betweenthe indexscan and the nestloop join that is supplying the parameter.The executor was fixed to handle such cases some time ago, but theplanner was not ready. This should improve our plans in many situationswhere join ordering restrictions formerly forced complete table scans.There is probably a fair amount of tuning work yet to be done, becauseof various heuristics that have been added to limit the number ofparameterized paths considered. However, we are not going to find outwhat needs to be adjusted until the code gets some real-world use, soit's time to get it in there where it can be tested easily.Note API change for index AM amcostestimate functions. I'm not aware ofany non-core index AMs, but if there are any, they will need minoradjustments.
1 parentb376ec6 commite2fa76d

26 files changed

+3883
-2291
lines changed

‎doc/src/sgml/indexam.sgml

Lines changed: 12 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -289,7 +289,7 @@ amcanreturn (Relation indexRelation);
289289
void
290290
amcostestimate (PlannerInfo *root,
291291
IndexPath *path,
292-
RelOptInfo *outer_rel,
292+
double loop_count,
293293
Cost *indexStartupCost,
294294
Cost *indexTotalCost,
295295
Selectivity *indexSelectivity,
@@ -928,7 +928,7 @@ amrestrpos (IndexScanDesc scan);
928928
void
929929
amcostestimate (PlannerInfo *root,
930930
IndexPath *path,
931-
RelOptInfo *outer_rel,
931+
double loop_count,
932932
Cost *indexStartupCost,
933933
Cost *indexTotalCost,
934934
Selectivity *indexSelectivity,
@@ -958,16 +958,15 @@ amcostestimate (PlannerInfo *root,
958958
</varlistentry>
959959

960960
<varlistentry>
961-
<term><parameter>outer_rel</></term>
961+
<term><parameter>loop_count</></term>
962962
<listitem>
963963
<para>
964-
If the index is being considered for use in a join inner indexscan,
965-
the planner's information about the outer side of the join. Otherwise
966-
<symbol>NULL</>. When non-<symbol>NULL</>, some of the qual clauses
967-
will be join clauses for joins
968-
with this rel rather than being simple restriction clauses. Also,
969-
the cost estimator should expect that the index scan will be repeated
970-
for each row of the outer rel.
964+
The number of repetitions of the index scan that should be factored
965+
into the cost estimates. This will typically be greater than one when
966+
considering a parameterized scan for use in the inside of a nestloop
967+
join. Note that the cost estimates should still be for just one scan;
968+
a larger <parameter>loop_count</> means that it may be appropriate
969+
to allow for some caching effects across multiple scans.
971970
</para>
972971
</listitem>
973972
</varlistentry>
@@ -1062,8 +1061,8 @@ amcostestimate (PlannerInfo *root,
10621061
</para>
10631062

10641063
<para>
1065-
In the join case, the returned numbers should be averages expected for
1066-
any one scan of the index.
1064+
When <parameter>loop_count</> is greater than one, the returned numbers
1065+
should be averages expected forany one scan of the index.
10671066
</para>
10681067

10691068
<procedure>
@@ -1121,7 +1120,7 @@ cost_qual_eval(&amp;index_qual_cost, path-&gt;indexquals, root);
11211120
</programlisting>
11221121

11231122
However, the above does not account for amortization of index reads
1124-
across repeated index scans in the join case.
1123+
across repeated index scans.
11251124
</para>
11261125
</step>
11271126

‎src/backend/nodes/bitmapset.c

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -335,6 +335,83 @@ bms_is_subset(const Bitmapset *a, const Bitmapset *b)
335335
return true;
336336
}
337337

338+
/*
339+
* bms_subset_compare - compare A and B for equality/subset relationships
340+
*
341+
* This is more efficient than testing bms_is_subset in both directions.
342+
*/
343+
BMS_Comparison
344+
bms_subset_compare(constBitmapset*a,constBitmapset*b)
345+
{
346+
BMS_Comparisonresult;
347+
intshortlen;
348+
intlonglen;
349+
inti;
350+
351+
/* Handle cases where either input is NULL */
352+
if (a==NULL)
353+
{
354+
if (b==NULL)
355+
returnBMS_EQUAL;
356+
returnbms_is_empty(b) ?BMS_EQUAL :BMS_SUBSET1;
357+
}
358+
if (b==NULL)
359+
returnbms_is_empty(a) ?BMS_EQUAL :BMS_SUBSET2;
360+
/* Check common words */
361+
result=BMS_EQUAL;/* status so far */
362+
shortlen=Min(a->nwords,b->nwords);
363+
for (i=0;i<shortlen;i++)
364+
{
365+
bitmapwordaword=a->words[i];
366+
bitmapwordbword=b->words[i];
367+
368+
if ((aword& ~bword)!=0)
369+
{
370+
/* a is not a subset of b */
371+
if (result==BMS_SUBSET1)
372+
returnBMS_DIFFERENT;
373+
result=BMS_SUBSET2;
374+
}
375+
if ((bword& ~aword)!=0)
376+
{
377+
/* b is not a subset of a */
378+
if (result==BMS_SUBSET2)
379+
returnBMS_DIFFERENT;
380+
result=BMS_SUBSET1;
381+
}
382+
}
383+
/* Check extra words */
384+
if (a->nwords>b->nwords)
385+
{
386+
longlen=a->nwords;
387+
for (;i<longlen;i++)
388+
{
389+
if (a->words[i]!=0)
390+
{
391+
/* a is not a subset of b */
392+
if (result==BMS_SUBSET1)
393+
returnBMS_DIFFERENT;
394+
result=BMS_SUBSET2;
395+
}
396+
}
397+
}
398+
elseif (a->nwords<b->nwords)
399+
{
400+
longlen=b->nwords;
401+
for (;i<longlen;i++)
402+
{
403+
if (b->words[i]!=0)
404+
{
405+
/* b is not a subset of a */
406+
if (result==BMS_SUBSET2)
407+
returnBMS_DIFFERENT;
408+
result=BMS_SUBSET1;
409+
}
410+
}
411+
}
412+
returnresult;
413+
}
414+
338415
/*
339416
* bms_is_member - is X a member of A?
340417
*/

‎src/backend/nodes/outfuncs.c

Lines changed: 5 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1475,9 +1475,12 @@ _outPathInfo(StringInfo str, const Path *node)
14751475
WRITE_ENUM_FIELD(pathtype,NodeTag);
14761476
appendStringInfo(str," :parent_relids ");
14771477
_outBitmapset(str,node->parent->relids);
1478+
WRITE_FLOAT_FIELD(rows,"%.0f");
14781479
WRITE_FLOAT_FIELD(startup_cost,"%.2f");
14791480
WRITE_FLOAT_FIELD(total_cost,"%.2f");
14801481
WRITE_NODE_FIELD(pathkeys);
1482+
WRITE_BITMAPSET_FIELD(required_outer);
1483+
WRITE_NODE_FIELD(param_clauses);
14811484
}
14821485

14831486
/*
@@ -1515,11 +1518,9 @@ _outIndexPath(StringInfo str, const IndexPath *node)
15151518
WRITE_NODE_FIELD(indexqualcols);
15161519
WRITE_NODE_FIELD(indexorderbys);
15171520
WRITE_NODE_FIELD(indexorderbycols);
1518-
WRITE_BOOL_FIELD(isjoininner);
15191521
WRITE_ENUM_FIELD(indexscandir,ScanDirection);
15201522
WRITE_FLOAT_FIELD(indextotalcost,"%.2f");
15211523
WRITE_FLOAT_FIELD(indexselectivity,"%.4f");
1522-
WRITE_FLOAT_FIELD(rows,"%.0f");
15231524
}
15241525

15251526
staticvoid
@@ -1530,8 +1531,6 @@ _outBitmapHeapPath(StringInfo str, const BitmapHeapPath *node)
15301531
_outPathInfo(str, (constPath*)node);
15311532

15321533
WRITE_NODE_FIELD(bitmapqual);
1533-
WRITE_BOOL_FIELD(isjoininner);
1534-
WRITE_FLOAT_FIELD(rows,"%.0f");
15351534
}
15361535

15371536
staticvoid
@@ -1628,7 +1627,6 @@ _outUniquePath(StringInfo str, const UniquePath *node)
16281627
WRITE_ENUM_FIELD(umethod,UniquePathMethod);
16291628
WRITE_NODE_FIELD(in_operators);
16301629
WRITE_NODE_FIELD(uniq_exprs);
1631-
WRITE_FLOAT_FIELD(rows,"%.0f");
16321630
}
16331631

16341632
staticvoid
@@ -1691,6 +1689,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node)
16911689
WRITE_NODE_FIELD(parse);
16921690
WRITE_NODE_FIELD(glob);
16931691
WRITE_UINT_FIELD(query_level);
1692+
WRITE_BITMAPSET_FIELD(all_baserels);
16941693
WRITE_NODE_FIELD(join_rel_list);
16951694
WRITE_INT_FIELD(join_cur_level);
16961695
WRITE_NODE_FIELD(init_plans);
@@ -1738,6 +1737,7 @@ _outRelOptInfo(StringInfo str, const RelOptInfo *node)
17381737
WRITE_NODE_FIELD(cheapest_startup_path);
17391738
WRITE_NODE_FIELD(cheapest_total_path);
17401739
WRITE_NODE_FIELD(cheapest_unique_path);
1740+
WRITE_NODE_FIELD(cheapest_parameterized_paths);
17411741
WRITE_UINT_FIELD(relid);
17421742
WRITE_UINT_FIELD(reltablespace);
17431743
WRITE_ENUM_FIELD(rtekind,RTEKind);
@@ -1752,8 +1752,6 @@ _outRelOptInfo(StringInfo str, const RelOptInfo *node)
17521752
WRITE_NODE_FIELD(baserestrictinfo);
17531753
WRITE_NODE_FIELD(joininfo);
17541754
WRITE_BOOL_FIELD(has_eclass_joins);
1755-
WRITE_BITMAPSET_FIELD(index_outer_relids);
1756-
WRITE_NODE_FIELD(index_inner_paths);
17571755
}
17581756

17591757
staticvoid
@@ -1854,16 +1852,6 @@ _outRestrictInfo(StringInfo str, const RestrictInfo *node)
18541852
WRITE_OID_FIELD(hashjoinoperator);
18551853
}
18561854

1857-
staticvoid
1858-
_outInnerIndexscanInfo(StringInfostr,constInnerIndexscanInfo*node)
1859-
{
1860-
WRITE_NODE_TYPE("INNERINDEXSCANINFO");
1861-
WRITE_BITMAPSET_FIELD(other_relids);
1862-
WRITE_BOOL_FIELD(isouterjoin);
1863-
WRITE_NODE_FIELD(cheapest_startup_innerpath);
1864-
WRITE_NODE_FIELD(cheapest_total_innerpath);
1865-
}
1866-
18671855
staticvoid
18681856
_outPlaceHolderVar(StringInfostr,constPlaceHolderVar*node)
18691857
{
@@ -3015,9 +3003,6 @@ _outNode(StringInfo str, const void *obj)
30153003
caseT_RestrictInfo:
30163004
_outRestrictInfo(str,obj);
30173005
break;
3018-
caseT_InnerIndexscanInfo:
3019-
_outInnerIndexscanInfo(str,obj);
3020-
break;
30213006
caseT_PlaceHolderVar:
30223007
_outPlaceHolderVar(str,obj);
30233008
break;

‎src/backend/optimizer/README

Lines changed: 113 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -78,10 +78,10 @@ ways. All the Paths made for a given relation are placed in its
7878
RelOptInfo.pathlist. (Actually, we discard Paths that are obviously
7979
inferior alternatives before they ever get into the pathlist --- what
8080
ends up in the pathlist is the cheapest way of generating each potentially
81-
useful sort ordering of the relation.) Also create a RelOptInfo.joininfo
82-
list including all the join clauses that involve this relation. For
83-
example, the WHERE clause "tab1.col1 = tab2.col1" generates entries in
84-
both tab1 and tab2's joininfo lists.
81+
useful sort orderingand parameterizationof the relation.) Also create a
82+
RelOptInfo.joininfolist including all the join clauses that involve this
83+
relation. Forexample, the WHERE clause "tab1.col1 = tab2.col1" generates
84+
entries inboth tab1 and tab2's joininfo lists.
8585

8686
If we have only a single base relation in the query, we are done.
8787
Otherwise we have to figure out how to join the base relations into a
@@ -173,12 +173,12 @@ for it or the cheapest path with the desired ordering (if that's cheaper
173173
than applying a sort to the cheapest other path).
174174

175175
If the query contains one-sided outer joins (LEFT or RIGHT joins), or
176-
IN or EXISTS WHERE clauses that were converted tojoins, then some of
177-
the possible join orders may be illegal. These are excluded by having
178-
join_is_legal consult a side list of such "special" joins to see
179-
whether a proposed join is illegal. (The same consultation allows it
180-
tosee which join style should be applied for a valid join, ie,
181-
JOIN_INNER,JOIN_LEFT, etc.)
176+
IN or EXISTS WHERE clauses that were converted tosemijoins or antijoins,
177+
then some ofthe possible join orders may be illegal. These are excluded
178+
by havingjoin_is_legal consult a side list of such "special" joins to see
179+
whether a proposed join is illegal. (The same consultation allows it to
180+
see which join style should be applied for a valid join, ie, JOIN_INNER,
181+
JOIN_LEFT, etc.)
182182

183183

184184
Valid OUTER JOIN Optimizations
@@ -526,12 +526,11 @@ multi-column index generates a list with one element per index column.
526526
are two possible sort orders and two possible PathKey lists it can
527527
generate.)
528528

529-
Note that a bitmap scan or multi-pass indexscan (OR clause scan) has NIL
530-
pathkeys since we can say nothing about the overall order of its result.
531-
Also, an indexscan on an unordered type of index generates NIL pathkeys.
532-
However, we can always create a pathkey by doing an explicit sort. The
533-
pathkeys for a Sort plan's output just represent the sort key fields and
534-
the ordering operators used.
529+
Note that a bitmap scan has NIL pathkeys since we can say nothing about
530+
the overall order of its result. Also, an indexscan on an unordered type
531+
of index generates NIL pathkeys. However, we can always create a pathkey
532+
by doing an explicit sort. The pathkeys for a Sort plan's output just
533+
represent the sort key fields and the ordering operators used.
535534

536535
Things get more interesting when we consider joins. Suppose we do a
537536
mergejoin between A and B using the mergeclause A.X = B.Y. The output
@@ -668,4 +667,102 @@ Currently this happens only for queries involving multiple window functions
668667
with different orderings, for which extra sorts are needed anyway.
669668

670669

670+
Parameterized Paths
671+
-------------------
672+
673+
The naive way to join two relations using a clause like WHERE A.X = B.Y
674+
is to generate a nestloop plan like this:
675+
676+
NestLoop
677+
Filter: A.X = B.Y
678+
-> Seq Scan on A
679+
-> Seq Scan on B
680+
681+
We can make this better by using a merge or hash join, but it still
682+
requires scanning all of both input relations. If A is very small and B is
683+
very large, but there is an index on B.Y, it can be enormously better to do
684+
something like this:
685+
686+
NestLoop
687+
-> Seq Scan on A
688+
-> Index Scan using B_Y_IDX on B
689+
Index Condition: B.Y = A.X
690+
691+
Here, we are expecting that for each row scanned from A, the nestloop
692+
plan node will pass down the current value of A.X into the scan of B.
693+
That allows the indexscan to treat A.X as a constant for any one
694+
invocation, and thereby use it as an index key. This is the only plan type
695+
that can avoid fetching all of B, and for small numbers of rows coming from
696+
A, that will dominate every other consideration. (As A gets larger, this
697+
gets less attractive, and eventually a merge or hash join will win instead.
698+
So we have to cost out all the alternatives to decide what to do.)
699+
700+
It can be useful for the parameter value to be passed down through
701+
intermediate layers of joins, for example:
702+
703+
NestLoop
704+
-> Seq Scan on A
705+
Hash Join
706+
Join Condition: B.Y = C.W
707+
-> Seq Scan on B
708+
-> Index Scan using C_Z_IDX on C
709+
Index Condition: C.Z = A.X
710+
711+
If all joins are plain inner joins then this is unnecessary, because
712+
it's always possible to reorder the joins so that a parameter is used
713+
immediately below the nestloop node that provides it. But in the
714+
presence of outer joins, join reordering may not be possible, and then
715+
this option can be critical. Before version 9.2, Postgres used ad-hoc
716+
methods for planning and executing such queries, and those methods could
717+
not handle passing parameters down through multiple join levels.
718+
719+
To plan such queries, we now use a notion of a "parameterized path",
720+
which is a path that makes use of a join clause to a relation that's not
721+
scanned by the path. In the example just above, we would construct a
722+
path representing the possibility of doing this:
723+
724+
-> Index Scan using C_Z_IDX on C
725+
Index Condition: C.Z = A.X
726+
727+
This path will be marked as being parameterized by relation A. (Note that
728+
this is only one of the possible access paths for C; we'd still have a
729+
plain unparameterized seqscan, and perhaps other possibilities.) The
730+
parameterization marker does not prevent joining the path to B, so one of
731+
the paths generated for the joinrel {B C} will represent
732+
733+
Hash Join
734+
Join Condition: B.Y = C.W
735+
-> Seq Scan on B
736+
-> Index Scan using C_Z_IDX on C
737+
Index Condition: C.Z = A.X
738+
739+
This path is still marked as being parameterized by A. When we attempt to
740+
join {B C} to A to form the complete join tree, such a path can only be
741+
used as the inner side of a nestloop join: it will be ignored for other
742+
possible join types. So we will form a join path representing the query
743+
plan shown above, and it will compete in the usual way with paths built
744+
from non-parameterized scans.
745+
746+
To limit planning time, we have to avoid generating an unreasonably large
747+
number of parameterized paths. We do this by only generating parameterized
748+
relation scan paths for index scans, and then only for indexes for which
749+
suitable join clauses are available. There are also heuristics in join
750+
planning that try to limit the number of parameterized paths considered.
751+
752+
In particular, there's been a deliberate policy decision to favor hash
753+
joins over merge joins for parameterized join steps (those occurring below
754+
a nestloop that provides parameters to the lower join's inputs). While we
755+
do not ignore merge joins entirely, joinpath.c does not fully explore the
756+
space of potential merge joins with parameterized inputs. Also, add_path
757+
treats parameterized paths as having no pathkeys, so that they compete
758+
only on cost and don't get preference for producing a special sort order.
759+
This creates additional bias against merge joins, since we might discard
760+
a path that could have been useful for performing a merge without an
761+
explicit sort step. Since a parameterized path must ultimately be used
762+
on the inside of a nestloop, where its sort order is uninteresting, these
763+
choices do not affect any requirement for the final output order of a
764+
query --- they only make it harder to use a merge join at a lower level.
765+
The savings in planning work justifies that.
766+
767+
671768
-- bjm & tgl

0 commit comments

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