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

Commit5b7b551

Browse files
committed
Revise parameterized-path mechanism to fix assorted issues.
This patch adjusts the treatment of parameterized paths so that all pathswith the same parameterization (same set of required outer rels) for thesame relation will have the same rowcount estimate. We cache the rowcountestimates to ensure that property, and hopefully save a few cycles too.Doing this makes it practical for add_path_precheck to operate withouta rowcount estimate: it need only assume that paths with differentparameterizations never dominate each other, which is close enough totrue anyway for coarse filtering, because normally a more-parameterizedpath should yield fewer rows thanks to having more join clauses to apply.In add_path, we do the full nine yards of comparing rowcount estimatesalong with everything else, so that we can discard parameterized paths thatdon't actually have an advantage. This fixes some issues I'd found withadd_path rejecting parameterized paths on the grounds that they were moreexpensive than not-parameterized ones, even though they yielded many fewerrows and hence would be cheaper once subsequent joining was considered.To make the same-rowcounts assumption valid, we have to require that anyparameterized path enforce *all* join clauses that could be obtained fromthe particular set of outer rels, even if not all of them are useful forindexing. This is required at both base scans and joins. It's a goodthing anyway since the net impact is that join quals are checked at thelowest practical level in the join tree. Hence, discard the originalrather ad-hoc mechanism for choosing parameterization joinquals, and builda better one that has a more principled rule for when clauses can be moved.The original rule was actually buggy anyway for lack of knowledge aboutwhich relations are part of an outer join's outer side; getting this rightrequires adding an outer_relids field to RestrictInfo.
1 parentcd1f4db commit5b7b551

30 files changed

+1787
-776
lines changed

‎contrib/file_fdw/file_fdw.c

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -468,7 +468,6 @@ fileGetForeignPaths(PlannerInfo *root,
468468
total_cost,
469469
NIL,/* no pathkeys */
470470
NULL,/* no outer rel either */
471-
NIL,
472471
NIL));/* no fdw_private data */
473472

474473
/*

‎src/backend/nodes/copyfuncs.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1844,6 +1844,7 @@ _copyRestrictInfo(const RestrictInfo *from)
18441844
COPY_SCALAR_FIELD(pseudoconstant);
18451845
COPY_BITMAPSET_FIELD(clause_relids);
18461846
COPY_BITMAPSET_FIELD(required_relids);
1847+
COPY_BITMAPSET_FIELD(outer_relids);
18471848
COPY_BITMAPSET_FIELD(nullable_relids);
18481849
COPY_BITMAPSET_FIELD(left_relids);
18491850
COPY_BITMAPSET_FIELD(right_relids);

‎src/backend/nodes/equalfuncs.c

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -815,6 +815,7 @@ _equalRestrictInfo(const RestrictInfo *a, const RestrictInfo *b)
815815
COMPARE_SCALAR_FIELD(is_pushed_down);
816816
COMPARE_SCALAR_FIELD(outerjoin_delayed);
817817
COMPARE_BITMAPSET_FIELD(required_relids);
818+
COMPARE_BITMAPSET_FIELD(outer_relids);
818819
COMPARE_BITMAPSET_FIELD(nullable_relids);
819820

820821
/*

‎src/backend/nodes/outfuncs.c

Lines changed: 23 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1461,19 +1461,25 @@ _outFromExpr(StringInfo str, const FromExpr *node)
14611461
*
14621462
* Note we do NOT print the parent, else we'd be in infinite recursion.
14631463
* We can print the parent's relids for identification purposes, though.
1464+
* We also do not print the whole of param_info, since it's printed by
1465+
* _outRelOptInfo; it's sufficient and less cluttering to print just the
1466+
* required outer relids.
14641467
*/
14651468
staticvoid
14661469
_outPathInfo(StringInfostr,constPath*node)
14671470
{
14681471
WRITE_ENUM_FIELD(pathtype,NodeTag);
14691472
appendStringInfo(str," :parent_relids ");
14701473
_outBitmapset(str,node->parent->relids);
1474+
appendStringInfo(str," :required_outer ");
1475+
if (node->param_info)
1476+
_outBitmapset(str,node->param_info->ppi_req_outer);
1477+
else
1478+
_outBitmapset(str,NULL);
14711479
WRITE_FLOAT_FIELD(rows,"%.0f");
14721480
WRITE_FLOAT_FIELD(startup_cost,"%.2f");
14731481
WRITE_FLOAT_FIELD(total_cost,"%.2f");
14741482
WRITE_NODE_FIELD(pathkeys);
1475-
WRITE_BITMAPSET_FIELD(required_outer);
1476-
WRITE_NODE_FIELD(param_clauses);
14771483
}
14781484

14791485
/*
@@ -1727,6 +1733,7 @@ _outRelOptInfo(StringInfo str, const RelOptInfo *node)
17271733
WRITE_INT_FIELD(width);
17281734
WRITE_NODE_FIELD(reltargetlist);
17291735
WRITE_NODE_FIELD(pathlist);
1736+
WRITE_NODE_FIELD(ppilist);
17301737
WRITE_NODE_FIELD(cheapest_startup_path);
17311738
WRITE_NODE_FIELD(cheapest_total_path);
17321739
WRITE_NODE_FIELD(cheapest_unique_path);
@@ -1817,6 +1824,16 @@ _outPathKey(StringInfo str, const PathKey *node)
18171824
WRITE_BOOL_FIELD(pk_nulls_first);
18181825
}
18191826

1827+
staticvoid
1828+
_outParamPathInfo(StringInfostr,constParamPathInfo*node)
1829+
{
1830+
WRITE_NODE_TYPE("PARAMPATHINFO");
1831+
1832+
WRITE_BITMAPSET_FIELD(ppi_req_outer);
1833+
WRITE_FLOAT_FIELD(ppi_rows,"%.0f");
1834+
WRITE_NODE_FIELD(ppi_clauses);
1835+
}
1836+
18201837
staticvoid
18211838
_outRestrictInfo(StringInfostr,constRestrictInfo*node)
18221839
{
@@ -1830,6 +1847,7 @@ _outRestrictInfo(StringInfo str, const RestrictInfo *node)
18301847
WRITE_BOOL_FIELD(pseudoconstant);
18311848
WRITE_BITMAPSET_FIELD(clause_relids);
18321849
WRITE_BITMAPSET_FIELD(required_relids);
1850+
WRITE_BITMAPSET_FIELD(outer_relids);
18331851
WRITE_BITMAPSET_FIELD(nullable_relids);
18341852
WRITE_BITMAPSET_FIELD(left_relids);
18351853
WRITE_BITMAPSET_FIELD(right_relids);
@@ -3001,6 +3019,9 @@ _outNode(StringInfo str, const void *obj)
30013019
caseT_PathKey:
30023020
_outPathKey(str,obj);
30033021
break;
3022+
caseT_ParamPathInfo:
3023+
_outParamPathInfo(str,obj);
3024+
break;
30043025
caseT_RestrictInfo:
30053026
_outRestrictInfo(str,obj);
30063027
break;

‎src/backend/optimizer/README

Lines changed: 34 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -751,6 +751,32 @@ possible join types. So we will form a join path representing the query
751751
plan shown above, and it will compete in the usual way with paths built
752752
from non-parameterized scans.
753753

754+
While all ordinary paths for a particular relation generate the same set
755+
of rows (since they must all apply the same set of restriction clauses),
756+
parameterized paths typically generate fewer rows than less-parameterized
757+
paths, since they have additional clauses to work with. This means we
758+
must consider the number of rows generated as an additional figure of
759+
merit. A path that costs more than another, but generates fewer rows,
760+
must be kept since the smaller number of rows might save work at some
761+
intermediate join level. (It would not save anything if joined
762+
immediately to the source of the parameters.)
763+
764+
To keep cost estimation rules relatively simple, we make an implementation
765+
restriction that all paths for a given relation of the same parameterization
766+
(i.e., the same set of outer relations supplying parameters) must have the
767+
same rowcount estimate. This is justified by insisting that each such path
768+
apply *all* join clauses that are available with the named outer relations.
769+
Different paths might, for instance, choose different join clauses to use
770+
as index clauses; but they must then apply any other join clauses available
771+
from the same outer relations as filter conditions, so that the set of rows
772+
returned is held constant. This restriction doesn't degrade the quality of
773+
the finished plan: it amounts to saying that we should always push down
774+
movable join clauses to the lowest possible evaluation level, which is a
775+
good thing anyway. The restriction is useful in particular to support
776+
pre-filtering of join paths in add_path_precheck. Without this rule we
777+
could never reject a parameterized path in advance of computing its rowcount
778+
estimate, which would greatly reduce the value of the pre-filter mechanism.
779+
754780
To limit planning time, we have to avoid generating an unreasonably large
755781
number of parameterized paths. We do this by only generating parameterized
756782
relation scan paths for index scans, and then only for indexes for which
@@ -763,14 +789,14 @@ a nestloop that provides parameters to the lower join's inputs). While we
763789
do not ignore merge joins entirely, joinpath.c does not fully explore the
764790
space of potential merge joins with parameterized inputs. Also, add_path
765791
treats parameterized paths as having no pathkeys, so that they compete
766-
only on cost and don't get preference for producing a special sort order.
767-
This creates additional bias against merge joins, since we might discard
768-
a path that could have been useful for performing a merge without an
769-
explicit sort step. Since a parameterized path must ultimately be used
770-
on the inside of a nestloop, where its sort order is uninteresting, these
771-
choices do not affect any requirement for the final output order of a
772-
query --- they only make it harder to use a merge join at a lower level.
773-
The savings in planning work justifies that.
792+
only on cost androwcount; theydon't get preference for producing a
793+
special sort order.This creates additional bias against merge joins,
794+
since we might discarda path that could have been useful for performing
795+
a merge without anexplicit sort step. Since a parameterized path must
796+
ultimately be usedon the inside of a nestloop, where its sort order is
797+
uninteresting, thesechoices do not affect any requirement for the final
798+
output order of aquery --- they only make it harder to use a merge join
799+
at a lower level.The savings in planning work justifies that.
774800

775801

776802
-- bjm & tgl

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

Lines changed: 57 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -67,8 +67,7 @@ static void set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
6767
Indexrti,RangeTblEntry*rte);
6868
staticvoidgenerate_mergeappend_paths(PlannerInfo*root,RelOptInfo*rel,
6969
List*live_childrels,
70-
List*all_child_pathkeys,
71-
Relidsrequired_outer);
70+
List*all_child_pathkeys);
7271
staticList*accumulate_append_subpath(List*subpaths,Path*path);
7372
staticvoidset_dummy_rel_pathlist(RelOptInfo*rel);
7473
staticvoidset_subquery_pathlist(PlannerInfo*root,RelOptInfo*rel,
@@ -375,7 +374,7 @@ static void
375374
set_plain_rel_pathlist(PlannerInfo*root,RelOptInfo*rel,RangeTblEntry*rte)
376375
{
377376
/* Consider sequential scan */
378-
add_path(rel,create_seqscan_path(root,rel));
377+
add_path(rel,create_seqscan_path(root,rel,NULL));
379378

380379
/* Consider index scans */
381380
create_index_paths(root,rel);
@@ -717,7 +716,7 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
717716
{
718717
Path*childpath= (Path*)lfirst(lcp);
719718
List*childkeys=childpath->pathkeys;
720-
Relidschildouter=childpath->required_outer;
719+
Relidschildouter=PATH_REQ_OUTER(childpath);
721720

722721
/* Unsorted paths don't contribute to pathkey list */
723722
if (childkeys!=NIL)
@@ -777,25 +776,31 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
777776
* (Note: this is correct even if we have zero or one live subpath due to
778777
* constraint exclusion.)
779778
*/
780-
add_path(rel, (Path*)create_append_path(rel,subpaths));
779+
add_path(rel, (Path*)create_append_path(rel,subpaths,NULL));
781780

782781
/*
783782
* Build unparameterized MergeAppend paths based on the collected list of
784783
* child pathkeys.
785784
*/
786-
generate_mergeappend_paths(root,rel,live_childrels,
787-
all_child_pathkeys,NULL);
785+
generate_mergeappend_paths(root,rel,live_childrels,all_child_pathkeys);
788786

789787
/*
790-
* Build Append and MergeAppend paths for each parameterization seen
791-
* among the child rels. (This may look pretty expensive, but in most
792-
* cases of practical interest, the child relations will tend to expose
793-
* the same parameterizations and pathkeys, so that not that many cases
794-
* actually get considered here.)
788+
* Build Append paths for each parameterization seen among the child rels.
789+
* (This may look pretty expensive, but in most cases of practical
790+
* interest, the child rels will expose mostly the same parameterizations,
791+
* so that not that many cases actually get considered here.)
792+
*
793+
* The Append node itself cannot enforce quals, so all qual checking must
794+
* be done in the child paths. This means that to have a parameterized
795+
* Append path, we must have the exact same parameterization for each
796+
* child path; otherwise some children might be failing to check the
797+
* moved-down quals. To make them match up, we can try to increase the
798+
* parameterization of lesser-parameterized paths.
795799
*/
796800
foreach(l,all_child_outers)
797801
{
798802
Relidsrequired_outer= (Relids)lfirst(l);
803+
boolok= true;
799804
ListCell*lcr;
800805

801806
/* Select the child paths for an Append with this parameterization */
@@ -812,13 +817,24 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
812817
TOTAL_COST);
813818
Assert(cheapest_total!=NULL);
814819

820+
/* Children must have exactly the desired parameterization */
821+
if (!bms_equal(PATH_REQ_OUTER(cheapest_total),required_outer))
822+
{
823+
cheapest_total=reparameterize_path(root,cheapest_total,
824+
required_outer,1.0);
825+
if (cheapest_total==NULL)
826+
{
827+
ok= false;
828+
break;
829+
}
830+
}
831+
815832
subpaths=accumulate_append_subpath(subpaths,cheapest_total);
816833
}
817-
add_path(rel, (Path*)create_append_path(rel,subpaths));
818834

819-
/* And build parameterized MergeAppend paths */
820-
generate_mergeappend_paths(root,rel,live_childrels,
821-
all_child_pathkeys,required_outer);
835+
if (ok)
836+
add_path(rel,(Path*)
837+
create_append_path(rel,subpaths,required_outer));
822838
}
823839

824840
/* Select cheapest paths */
@@ -830,18 +846,28 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
830846
*Generate MergeAppend paths for an append relation
831847
*
832848
* Generate a path for each ordering (pathkey list) appearing in
833-
* all_child_pathkeys. If required_outer isn't NULL, accept paths having
834-
* those relations as required outer relations.
849+
* all_child_pathkeys.
835850
*
836851
* We consider both cheapest-startup and cheapest-total cases, ie, for each
837852
* interesting ordering, collect all the cheapest startup subpaths and all the
838853
* cheapest total paths, and build a MergeAppend path for each case.
854+
*
855+
* We don't currently generate any parameterized MergeAppend paths. While
856+
* it would not take much more code here to do so, it's very unclear that it
857+
* is worth the planning cycles to investigate such paths: there's little
858+
* use for an ordered path on the inside of a nestloop. In fact, it's likely
859+
* that the current coding of add_path would reject such paths out of hand,
860+
* because add_path gives no credit for sort ordering of parameterized paths,
861+
* and a parameterized MergeAppend is going to be more expensive than the
862+
* corresponding parameterized Append path. If we ever try harder to support
863+
* parameterized mergejoin plans, it might be worth adding support for
864+
* parameterized MergeAppends to feed such joins. (See notes in
865+
* optimizer/README for why that might not ever happen, though.)
839866
*/
840867
staticvoid
841868
generate_mergeappend_paths(PlannerInfo*root,RelOptInfo*rel,
842869
List*live_childrels,
843-
List*all_child_pathkeys,
844-
Relidsrequired_outer)
870+
List*all_child_pathkeys)
845871
{
846872
ListCell*lcp;
847873

@@ -864,30 +890,22 @@ generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
864890
cheapest_startup=
865891
get_cheapest_path_for_pathkeys(childrel->pathlist,
866892
pathkeys,
867-
required_outer,
893+
NULL,
868894
STARTUP_COST);
869895
cheapest_total=
870896
get_cheapest_path_for_pathkeys(childrel->pathlist,
871897
pathkeys,
872-
required_outer,
898+
NULL,
873899
TOTAL_COST);
874900

875901
/*
876902
* If we can't find any paths with the right order just use the
877-
* cheapest-total path; we'll have to sort it later. We can
878-
* use the cheapest path for the parameterization, though.
903+
* cheapest-total path; we'll have to sort it later.
879904
*/
880905
if (cheapest_startup==NULL||cheapest_total==NULL)
881906
{
882-
if (required_outer)
883-
cheapest_startup=cheapest_total=
884-
get_cheapest_path_for_pathkeys(childrel->pathlist,
885-
NIL,
886-
required_outer,
887-
TOTAL_COST);
888-
else
889-
cheapest_startup=cheapest_total=
890-
childrel->cheapest_total_path;
907+
cheapest_startup=cheapest_total=
908+
childrel->cheapest_total_path;
891909
Assert(cheapest_total!=NULL);
892910
}
893911

@@ -909,12 +927,14 @@ generate_mergeappend_paths(PlannerInfo *root, RelOptInfo *rel,
909927
add_path(rel, (Path*)create_merge_append_path(root,
910928
rel,
911929
startup_subpaths,
912-
pathkeys));
930+
pathkeys,
931+
NULL));
913932
if (startup_neq_total)
914933
add_path(rel, (Path*)create_merge_append_path(root,
915934
rel,
916935
total_subpaths,
917-
pathkeys));
936+
pathkeys,
937+
NULL));
918938
}
919939
}
920940

@@ -958,7 +978,7 @@ set_dummy_rel_pathlist(RelOptInfo *rel)
958978
/* Discard any pre-existing paths; no further need for them */
959979
rel->pathlist=NIL;
960980

961-
add_path(rel, (Path*)create_append_path(rel,NIL));
981+
add_path(rel, (Path*)create_append_path(rel,NIL,NULL));
962982

963983
/* Select cheapest path (pretty easy in this case...) */
964984
set_cheapest(rel);
@@ -1112,7 +1132,7 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
11121132
pathkeys=convert_subquery_pathkeys(root,rel,subroot->query_pathkeys);
11131133

11141134
/* Generate appropriate path */
1115-
add_path(rel,create_subqueryscan_path(rel,pathkeys));
1135+
add_path(rel,create_subqueryscan_path(root,rel,pathkeys,NULL));
11161136

11171137
/* Select cheapest path (pretty easy in this case...) */
11181138
set_cheapest(rel);

0 commit comments

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