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

Commit6730685

Browse files
committed
Improve inheritance_planner()'s performance for large inheritance sets.
Commitc03ad56 introduced a plannerperformance regression for UPDATE/DELETE on large inheritance sets.It required copying the append_rel_list (which is of size proportional tothe number of inherited tables) once for each inherited table, thusresulting in O(N^2) time and memory consumption. While it's difficult toavoid that in general, the extra work only has to be done forappend_rel_list entries that actually reference subquery RTEs, whichinheritance-set entries will not. So we can buy back essentially all ofthe loss in cases without subqueries in FROM; and even for those, the addedwork is mainly proportional to the number of UNION ALL subqueries.Back-patch to 9.2, like the previous commit.Tom Lane and Dean Rasheed, per a complaint from Thomas Munro.
1 parent45a1d77 commit6730685

File tree

1 file changed

+83
-6
lines changed

1 file changed

+83
-6
lines changed

‎src/backend/optimizer/plan/planner.c

Lines changed: 83 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -765,6 +765,8 @@ inheritance_planner(PlannerInfo *root)
765765
{
766766
Query*parse=root->parse;
767767
intparentRTindex=parse->resultRelation;
768+
Bitmapset*subqueryRTindexes;
769+
Bitmapset*modifiableARIindexes;
768770
List*final_rtable=NIL;
769771
intsave_rel_array_size=0;
770772
RelOptInfo**save_rel_array=NULL;
@@ -773,6 +775,7 @@ inheritance_planner(PlannerInfo *root)
773775
List*returningLists=NIL;
774776
List*rowMarks;
775777
ListCell*lc;
778+
Indexrti;
776779

777780
/*
778781
* We generate a modified instance of the original Query for each target
@@ -788,13 +791,54 @@ inheritance_planner(PlannerInfo *root)
788791
* (1) would result in a rangetable of length O(N^2) for N targets, with
789792
* at least O(N^3) work expended here; and (2) would greatly complicate
790793
* management of the rowMarks list.
794+
*
795+
* To begin with, generate a bitmapset of the relids of the subquery RTEs.
796+
*/
797+
subqueryRTindexes=NULL;
798+
rti=1;
799+
foreach(lc,parse->rtable)
800+
{
801+
RangeTblEntry*rte= (RangeTblEntry*)lfirst(lc);
802+
803+
if (rte->rtekind==RTE_SUBQUERY)
804+
subqueryRTindexes=bms_add_member(subqueryRTindexes,rti);
805+
rti++;
806+
}
807+
808+
/*
809+
* Next, we want to identify which AppendRelInfo items contain references
810+
* to any of the aforesaid subquery RTEs. These items will need to be
811+
* copied and modified to adjust their subquery references; whereas the
812+
* other ones need not be touched. It's worth being tense over this
813+
* because we can usually avoid processing most of the AppendRelInfo
814+
* items, thereby saving O(N^2) space and time when the target is a large
815+
* inheritance tree. We can identify AppendRelInfo items by their
816+
* child_relid, since that should be unique within the list.
817+
*/
818+
modifiableARIindexes=NULL;
819+
if (subqueryRTindexes!=NULL)
820+
{
821+
foreach(lc,root->append_rel_list)
822+
{
823+
AppendRelInfo*appinfo= (AppendRelInfo*)lfirst(lc);
824+
825+
if (bms_is_member(appinfo->parent_relid,subqueryRTindexes)||
826+
bms_is_member(appinfo->child_relid,subqueryRTindexes)||
827+
bms_overlap(pull_varnos((Node*)appinfo->translated_vars),
828+
subqueryRTindexes))
829+
modifiableARIindexes=bms_add_member(modifiableARIindexes,
830+
appinfo->child_relid);
831+
}
832+
}
833+
834+
/*
835+
* And now we can get on with generating a plan for each child table.
791836
*/
792837
foreach(lc,root->append_rel_list)
793838
{
794839
AppendRelInfo*appinfo= (AppendRelInfo*)lfirst(lc);
795840
PlannerInfosubroot;
796841
Plan*subplan;
797-
Indexrti;
798842

799843
/* append_rel_list contains all append rels; ignore others */
800844
if (appinfo->parent_relid!=parentRTindex)
@@ -828,9 +872,29 @@ inheritance_planner(PlannerInfo *root)
828872
/*
829873
* The append_rel_list likewise might contain references to subquery
830874
* RTEs (if any subqueries were flattenable UNION ALLs). So prepare
831-
* to apply ChangeVarNodes to that, too.
875+
* to apply ChangeVarNodes to that, too. As explained above, we only
876+
* want to copy items that actually contain such references; the rest
877+
* can just get linked into the subroot's append_rel_list.
878+
*
879+
* If we know there are no such references, we can just use the outer
880+
* append_rel_list unmodified.
832881
*/
833-
subroot.append_rel_list= (List*)copyObject(root->append_rel_list);
882+
if (modifiableARIindexes!=NULL)
883+
{
884+
ListCell*lc2;
885+
886+
subroot.append_rel_list=NIL;
887+
foreach(lc2,root->append_rel_list)
888+
{
889+
AppendRelInfo*appinfo2= (AppendRelInfo*)lfirst(lc2);
890+
891+
if (bms_is_member(appinfo2->child_relid,modifiableARIindexes))
892+
appinfo2= (AppendRelInfo*)copyObject(appinfo2);
893+
894+
subroot.append_rel_list=lappend(subroot.append_rel_list,
895+
appinfo2);
896+
}
897+
}
834898

835899
/*
836900
* Add placeholders to the child Query's rangetable list to fill the
@@ -850,7 +914,7 @@ inheritance_planner(PlannerInfo *root)
850914
* since subquery RTEs couldn't contain any references to the target
851915
* rel.
852916
*/
853-
if (final_rtable!=NIL)
917+
if (final_rtable!=NIL&&subqueryRTindexes!=NULL)
854918
{
855919
ListCell*lr;
856920

@@ -859,7 +923,7 @@ inheritance_planner(PlannerInfo *root)
859923
{
860924
RangeTblEntry*rte= (RangeTblEntry*)lfirst(lr);
861925

862-
if (rte->rtekind==RTE_SUBQUERY)
926+
if (bms_is_member(rti,subqueryRTindexes))
863927
{
864928
Indexnewrti;
865929

@@ -872,7 +936,20 @@ inheritance_planner(PlannerInfo *root)
872936
newrti=list_length(subroot.parse->rtable)+1;
873937
ChangeVarNodes((Node*)subroot.parse,rti,newrti,0);
874938
ChangeVarNodes((Node*)subroot.rowMarks,rti,newrti,0);
875-
ChangeVarNodes((Node*)subroot.append_rel_list,rti,newrti,0);
939+
/* Skip processing unchanging parts of append_rel_list */
940+
if (modifiableARIindexes!=NULL)
941+
{
942+
ListCell*lc2;
943+
944+
foreach(lc2,subroot.append_rel_list)
945+
{
946+
AppendRelInfo*appinfo2= (AppendRelInfo*)lfirst(lc2);
947+
948+
if (bms_is_member(appinfo2->child_relid,
949+
modifiableARIindexes))
950+
ChangeVarNodes((Node*)appinfo2,rti,newrti,0);
951+
}
952+
}
876953
rte=copyObject(rte);
877954
subroot.parse->rtable=lappend(subroot.parse->rtable,
878955
rte);

0 commit comments

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