Skip to content

Commit e4ff52c

Browse files
tglsfdcpull[bot]
tglsfdc
authored and
pull[bot]
committed
Make PlaceHolderInfo lookup O(1).
Up to now we've just searched the placeholder_list when we want to find the PlaceHolderInfo with a given ID. While there's no evidence of that being a problem in the field, an upcoming patch will add find_placeholder_info() calls in build_joinrel_tlist(), which seems likely to make it more of an issue: a joinrel emitting lots of PlaceHolderVars would incur O(N^2) cost, and we might be building a lot of joinrels in complex queries. Hence, add an array that can be indexed directly by phid to make the lookups constant-time. Discussion: https://postgr.es/m/1405792.1660677844@sss.pgh.pa.us
1 parent 9be4c4e commit e4ff52c

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
Relids rels_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-
return phinfo;
85+
Assert(phinfo->phid == phv->phid);
86+
return phinfo;
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+
int new_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+
struct PlaceHolderInfo **placeholder_array pg_node_attr(read_write_ignore, array_size(placeholder_array_size));
362+
/* allocated size of array */
363+
int placeholder_array_size pg_node_attr(read_write_ignore);
364+
360365
/* list of ForeignKeyOptInfos */
361366
List *fkey_list;
362367

0 commit comments

Comments
 (0)