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

Commit8a8a672

Browse files
tglsfdcpull[bot]
authored andcommitted
Make PlaceHolderInfo lookup O(1).
Up to now we've just searched the placeholder_list when we want tofind the PlaceHolderInfo with a given ID. While there's no evidenceof that being a problem in the field, an upcoming patch will addfind_placeholder_info() calls in build_joinrel_tlist(), which seemslikely to make it more of an issue: a joinrel emitting lots ofPlaceHolderVars would incur O(N^2) cost, and we might be buildinga lot of joinrels in complex queries. Hence, add an array thatcan be indexed directly by phid to make the lookups constant-time.Discussion:https://postgr.es/m/1405792.1660677844@sss.pgh.pa.us
1 parent2d5fe5b commit8a8a672

File tree

5 files changed

+50
-14
lines changed

5 files changed

+50
-14
lines changed

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

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -388,8 +388,11 @@ remove_rel_from_query(PlannerInfo *root, int relid, Relids joinrelids)
388388
Assert(!bms_is_member(relid,phinfo->ph_lateral));
389389
if (bms_is_subset(phinfo->ph_needed,joinrelids)&&
390390
bms_is_member(relid,phinfo->ph_eval_at))
391+
{
391392
root->placeholder_list=foreach_delete_current(root->placeholder_list,
392393
l);
394+
root->placeholder_array[phinfo->phid]=NULL;
395+
}
393396
else
394397
{
395398
phinfo->ph_eval_at=bms_del_member(phinfo->ph_eval_at,relid);

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

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -75,6 +75,8 @@ query_planner(PlannerInfo *root,
7575
root->full_join_clauses=NIL;
7676
root->join_info_list=NIL;
7777
root->placeholder_list=NIL;
78+
root->placeholder_array=NULL;
79+
root->placeholder_array_size=0;
7880
root->fkey_list=NIL;
7981
root->initial_rels=NIL;
8082

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

Lines changed: 38 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -71,16 +71,19 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv,
7171
{
7272
PlaceHolderInfo*phinfo;
7373
Relidsrels_used;
74-
ListCell*lc;
7574

7675
/* if this ever isn't true, we'd need to be able to look in parent lists */
7776
Assert(phv->phlevelsup==0);
7877

79-
foreach(lc,root->placeholder_list)
78+
/* Use placeholder_array to look up existing PlaceHolderInfo quickly */
79+
if (phv->phid<root->placeholder_array_size)
80+
phinfo=root->placeholder_array[phv->phid];
81+
else
82+
phinfo=NULL;
83+
if (phinfo!=NULL)
8084
{
81-
phinfo= (PlaceHolderInfo*)lfirst(lc);
82-
if (phinfo->phid==phv->phid)
83-
returnphinfo;
85+
Assert(phinfo->phid==phv->phid);
86+
returnphinfo;
8487
}
8588

8689
/* Not found, so create it */
@@ -115,8 +118,38 @@ find_placeholder_info(PlannerInfo *root, PlaceHolderVar *phv,
115118
phinfo->ph_width=get_typavgwidth(exprType((Node*)phv->phexpr),
116119
exprTypmod((Node*)phv->phexpr));
117120

121+
/*
122+
* Add to both placeholder_list and placeholder_array. Note: because we
123+
* store pointers to the PlaceHolderInfos in two data structures, it'd be
124+
* unsafe to pass the whole placeholder_list structure through
125+
* expression_tree_mutator or the like --- or at least, you'd have to
126+
* rebuild the placeholder_array afterwards.
127+
*/
118128
root->placeholder_list=lappend(root->placeholder_list,phinfo);
119129

130+
if (phinfo->phid >=root->placeholder_array_size)
131+
{
132+
/* Must allocate or enlarge placeholder_array */
133+
intnew_size;
134+
135+
new_size=root->placeholder_array_size ?root->placeholder_array_size*2 :8;
136+
while (phinfo->phid >=new_size)
137+
new_size *=2;
138+
if (root->placeholder_array)
139+
{
140+
root->placeholder_array= (PlaceHolderInfo**)
141+
repalloc(root->placeholder_array,
142+
sizeof(PlaceHolderInfo*)*new_size);
143+
MemSet(root->placeholder_array+root->placeholder_array_size,0,
144+
sizeof(PlaceHolderInfo*)* (new_size-root->placeholder_array_size));
145+
}
146+
else
147+
root->placeholder_array= (PlaceHolderInfo**)
148+
palloc0(new_size*sizeof(PlaceHolderInfo*));
149+
root->placeholder_array_size=new_size;
150+
}
151+
root->placeholder_array[phinfo->phid]=phinfo;
152+
120153
/*
121154
* The PHV's contained expression may contain other, lower-level PHVs. We
122155
* now know we need to get those into the PlaceHolderInfo list, too, so we

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

Lines changed: 2 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -210,15 +210,8 @@ pull_varnos_walker(Node *node, pull_varnos_context *context)
210210

211211
if (phv->phlevelsup==0)
212212
{
213-
ListCell*lc;
214-
215-
foreach(lc,context->root->placeholder_list)
216-
{
217-
phinfo= (PlaceHolderInfo*)lfirst(lc);
218-
if (phinfo->phid==phv->phid)
219-
break;
220-
phinfo=NULL;
221-
}
213+
if (phv->phid<context->root->placeholder_array_size)
214+
phinfo=context->root->placeholder_array[phv->phid];
222215
}
223216
if (phinfo==NULL)
224217
{

‎src/include/nodes/pathnodes.h‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -357,6 +357,11 @@ struct PlannerInfo
357357
/* list of PlaceHolderInfos */
358358
List*placeholder_list;
359359

360+
/* array of PlaceHolderInfos indexed by phid */
361+
structPlaceHolderInfo**placeholder_arraypg_node_attr(read_write_ignore,array_size(placeholder_array_size));
362+
/* allocated size of array */
363+
intplaceholder_array_sizepg_node_attr(read_write_ignore);
364+
360365
/* list of ForeignKeyOptInfos */
361366
List*fkey_list;
362367

0 commit comments

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