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

Commit9a586fe

Browse files
committed
Nab some low-hanging fruit: replace the planner's base_rel_list and
other_rel_list with a single array indexed by rangetable index.This reduces find_base_rel from O(N) to O(1) without any real penalty.While find_base_rel isn't one of the major bottlenecks in any profileI've seen so far, it was starting to creep up on the radar screenfor complex queries --- so might as well fix it.
1 parent9ab4d98 commit9a586fe

File tree

5 files changed

+142
-109
lines changed

5 files changed

+142
-109
lines changed

‎src/backend/nodes/outfuncs.c

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.253 2005/06/05 22:32:54 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.254 2005/06/06 04:13:35 tgl Exp $
1212
*
1313
* NOTES
1414
* Every node type that can appear in stored rules' parsetrees *must*
@@ -1150,9 +1150,8 @@ _outPlannerInfo(StringInfo str, PlannerInfo *node)
11501150
{
11511151
WRITE_NODE_TYPE("PLANNERINFO");
11521152

1153+
/* NB: this isn't a complete set of fields */
11531154
WRITE_NODE_FIELD(parse);
1154-
WRITE_NODE_FIELD(base_rel_list);
1155-
WRITE_NODE_FIELD(other_rel_list);
11561155
WRITE_NODE_FIELD(join_rel_list);
11571156
WRITE_NODE_FIELD(equi_key_list);
11581157
WRITE_NODE_FIELD(in_info_list);

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

Lines changed: 48 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.131 2005/06/05 22:32:55 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.132 2005/06/06 04:13:35 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -88,9 +88,33 @@ make_one_rel(PlannerInfo *root)
8888
rel=make_fromexpr_rel(root,root->parse->jointree);
8989

9090
/*
91-
* The result should join all the query's base rels.
91+
* The result should join alland onlythe query's base rels.
9292
*/
93-
Assert(bms_num_members(rel->relids)==list_length(root->base_rel_list));
93+
#ifdefUSE_ASSERT_CHECKING
94+
{
95+
intnum_base_rels=0;
96+
Indexrti;
97+
98+
for (rti=1;rti<root->base_rel_array_size;rti++)
99+
{
100+
RelOptInfo*brel=root->base_rel_array[rti];
101+
102+
if (brel==NULL)
103+
continue;
104+
105+
Assert(brel->relid==rti);/* sanity check on array */
106+
107+
/* ignore RTEs that are "other rels" */
108+
if (brel->reloptkind!=RELOPT_BASEREL)
109+
continue;
110+
111+
Assert(bms_is_member(rti,rel->relids));
112+
num_base_rels++;
113+
}
114+
115+
Assert(bms_num_members(rel->relids)==num_base_rels);
116+
}
117+
#endif
94118

95119
returnrel;
96120
}
@@ -104,16 +128,29 @@ make_one_rel(PlannerInfo *root)
104128
staticvoid
105129
set_base_rel_pathlists(PlannerInfo*root)
106130
{
107-
ListCell*l;
131+
Indexrti;
108132

109-
foreach(l,root->base_rel_list)
133+
/*
134+
* Note: because we call expand_inherited_rtentry inside the loop,
135+
* it's quite possible for the base_rel_array to be enlarged while
136+
* the loop runs. Hence don't try to optimize the loop.
137+
*/
138+
for (rti=1;rti<root->base_rel_array_size;rti++)
110139
{
111-
RelOptInfo*rel= (RelOptInfo*)lfirst(l);
112-
Indexrti=rel->relid;
140+
RelOptInfo*rel=root->base_rel_array[rti];
113141
RangeTblEntry*rte;
114142
List*inheritlist;
115143

116-
Assert(rti>0);/* better be base rel */
144+
/* there may be empty slots corresponding to non-baserel RTEs */
145+
if (rel==NULL)
146+
continue;
147+
148+
Assert(rel->relid==rti);/* sanity check on array */
149+
150+
/* ignore RTEs that are "other rels" */
151+
if (rel->reloptkind!=RELOPT_BASEREL)
152+
continue;
153+
117154
rte=rt_fetch(rti,root->parse->rtable);
118155

119156
if (rel->rtekind==RTE_SUBQUERY)
@@ -246,10 +283,9 @@ set_inherited_rel_pathlist(PlannerInfo *root, RelOptInfo *rel,
246283
childOID=childrte->relid;
247284

248285
/*
249-
* Make a RelOptInfo for the child so we can do planning. Do NOT
250-
* attach the RelOptInfo to the query's base_rel_list, however,
251-
* since the child is not part of the main join tree. Instead,
252-
* the child RelOptInfo is added to other_rel_list.
286+
* Make a RelOptInfo for the child so we can do planning.
287+
* Mark it as an "other rel" since it will not be part of the
288+
* main join tree.
253289
*/
254290
childrel=build_other_rel(root,childRTindex);
255291

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

Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@
1414
*
1515
*
1616
* IDENTIFICATION
17-
* $PostgreSQL: pgsql/src/backend/optimizer/plan/planmain.c,v 1.82 2005/06/05 22:32:56 tgl Exp $
17+
* $PostgreSQL: pgsql/src/backend/optimizer/plan/planmain.c,v 1.83 2005/06/06 04:13:35 tgl Exp $
1818
*
1919
*-------------------------------------------------------------------------
2020
*/
@@ -106,12 +106,15 @@ query_planner(PlannerInfo *root, List *tlist, double tuple_fraction,
106106
&constant_quals);
107107

108108
/*
109-
* init planner lists to empty
109+
* Init planner lists to empty. We create the base_rel_array with a
110+
* size that will be sufficient if no pullups or inheritance additions
111+
* happen ... otherwise it will be enlarged as needed.
110112
*
111113
* NOTE: in_info_list was set up by subquery_planner, do not touch here
112114
*/
113-
root->base_rel_list=NIL;
114-
root->other_rel_list=NIL;
115+
root->base_rel_array_size=list_length(parse->rtable)+1;
116+
root->base_rel_array= (RelOptInfo**)
117+
palloc0(root->base_rel_array_size*sizeof(RelOptInfo*));
115118
root->join_rel_list=NIL;
116119
root->equi_key_list=NIL;
117120

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

Lines changed: 71 additions & 83 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/optimizer/util/relnode.c,v 1.67 2005/06/05 22:32:56 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/optimizer/util/relnode.c,v 1.68 2005/06/06 04:13:36 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -25,7 +25,8 @@
2525

2626
staticRelOptInfo*make_reloptinfo(PlannerInfo*root,intrelid,
2727
RelOptKindreloptkind);
28-
staticvoidbuild_joinrel_tlist(PlannerInfo*root,RelOptInfo*joinrel);
28+
staticvoidbuild_joinrel_tlist(PlannerInfo*root,RelOptInfo*joinrel,
29+
RelOptInfo*input_rel);
2930
staticList*build_joinrel_restrictlist(PlannerInfo*root,
3031
RelOptInfo*joinrel,
3132
RelOptInfo*outer_rel,
@@ -43,78 +44,60 @@ static void subbuild_joinrel_joinlist(RelOptInfo *joinrel,
4344
/*
4445
* build_base_rel
4546
* Construct a new base relation RelOptInfo, and put it in the query's
46-
*base_rel_list.
47+
*base_rel_array.
4748
*/
4849
void
4950
build_base_rel(PlannerInfo*root,intrelid)
5051
{
51-
ListCell*l;
52-
RelOptInfo*rel;
52+
Assert(relid>0);
5353

5454
/* Rel should not exist already */
55-
foreach(l,root->base_rel_list)
56-
{
57-
rel= (RelOptInfo*)lfirst(l);
58-
if (relid==rel->relid)
59-
elog(ERROR,"rel already exists");
60-
}
61-
62-
/* It should not exist as an "other" rel, either */
63-
foreach(l,root->other_rel_list)
64-
{
65-
rel= (RelOptInfo*)lfirst(l);
66-
if (relid==rel->relid)
67-
elog(ERROR,"rel already exists as \"other\" rel");
68-
}
55+
if (relid<root->base_rel_array_size&&
56+
root->base_rel_array[relid]!=NULL)
57+
elog(ERROR,"rel already exists");
6958

7059
/* No existing RelOptInfo for this base rel, so make a new one */
71-
rel=make_reloptinfo(root,relid,RELOPT_BASEREL);
72-
73-
/* and add it to the list */
74-
root->base_rel_list=lcons(rel,root->base_rel_list);
60+
(void)make_reloptinfo(root,relid,RELOPT_BASEREL);
7561
}
7662

7763
/*
7864
* build_other_rel
7965
* Returns relation entry corresponding to 'relid', creating a new one
8066
* if necessary. This is for 'other' relations, which are much like
81-
* base relations except that theylive ina differentlist.
67+
* base relations except that theyhavea differentRelOptKind.
8268
*/
8369
RelOptInfo*
8470
build_other_rel(PlannerInfo*root,intrelid)
8571
{
86-
ListCell*l;
8772
RelOptInfo*rel;
8873

74+
Assert(relid>0);
75+
8976
/* Already made? */
90-
foreach(l,root->other_rel_list)
77+
if (relid<root->base_rel_array_size)
9178
{
92-
rel= (RelOptInfo*)lfirst(l);
93-
if (relid==rel->relid)
79+
rel=root->base_rel_array[relid];
80+
if (rel)
81+
{
82+
/* it should not exist as a base rel */
83+
if (rel->reloptkind==RELOPT_BASEREL)
84+
elog(ERROR,"rel already exists as base rel");
85+
/* otherwise, A-OK */
9486
returnrel;
95-
}
96-
97-
/* It should not exist as a base rel */
98-
foreach(l,root->base_rel_list)
99-
{
100-
rel= (RelOptInfo*)lfirst(l);
101-
if (relid==rel->relid)
102-
elog(ERROR,"rel already exists as base rel");
87+
}
10388
}
10489

10590
/* No existing RelOptInfo for this other rel, so make a new one */
10691
/* presently, must be an inheritance child rel */
10792
rel=make_reloptinfo(root,relid,RELOPT_OTHER_CHILD_REL);
10893

109-
/* and add it to the list */
110-
root->other_rel_list=lcons(rel,root->other_rel_list);
111-
11294
returnrel;
11395
}
11496

11597
/*
11698
* make_reloptinfo
117-
* Construct a RelOptInfo for the specified rangetable index.
99+
* Construct a RelOptInfo for the specified rangetable index,
100+
* and enter it into base_rel_array.
118101
*
119102
* Common code for build_base_rel and build_other_rel.
120103
*/
@@ -172,31 +155,40 @@ make_reloptinfo(PlannerInfo *root, int relid, RelOptKind reloptkind)
172155
break;
173156
}
174157

158+
/* Add the finished struct to the base_rel_array */
159+
if (relid >=root->base_rel_array_size)
160+
{
161+
intoldsize=root->base_rel_array_size;
162+
intnewsize;
163+
164+
newsize=Max(oldsize*2,relid+1);
165+
root->base_rel_array= (RelOptInfo**)
166+
repalloc(root->base_rel_array,newsize*sizeof(RelOptInfo*));
167+
MemSet(root->base_rel_array+oldsize,0,
168+
(newsize-oldsize)*sizeof(RelOptInfo*));
169+
root->base_rel_array_size=newsize;
170+
}
171+
172+
root->base_rel_array[relid]=rel;
173+
175174
returnrel;
176175
}
177176

178177
/*
179178
* find_base_rel
180-
* Find a base or other relation entry, which must already exist
181-
* (since we'd have no idea which list to add it to).
179+
* Find a base or other relation entry, which must already exist.
182180
*/
183181
RelOptInfo*
184182
find_base_rel(PlannerInfo*root,intrelid)
185183
{
186-
ListCell*l;
187184
RelOptInfo*rel;
188185

189-
foreach(l,root->base_rel_list)
190-
{
191-
rel= (RelOptInfo*)lfirst(l);
192-
if (relid==rel->relid)
193-
returnrel;
194-
}
186+
Assert(relid>0);
195187

196-
foreach(l,root->other_rel_list)
188+
if (relid<root->base_rel_array_size)
197189
{
198-
rel=(RelOptInfo*)lfirst(l);
199-
if (relid==rel->relid)
190+
rel=root->base_rel_array[relid];
191+
if (rel)
200192
returnrel;
201193
}
202194

@@ -308,8 +300,13 @@ build_join_rel(PlannerInfo *root,
308300
* Create a new tlist containing just the vars that need to be output
309301
* from this join (ie, are needed for higher joinclauses or final
310302
* output).
303+
*
304+
* NOTE: the tlist order for a join rel will depend on which pair of
305+
* outer and inner rels we first try to build it from. But the
306+
* contents should be the same regardless.
311307
*/
312-
build_joinrel_tlist(root,joinrel);
308+
build_joinrel_tlist(root,joinrel,outer_rel);
309+
build_joinrel_tlist(root,joinrel,inner_rel);
313310

314311
/*
315312
* Construct restrict and join clause lists for the new joinrel. (The
@@ -344,48 +341,39 @@ build_join_rel(PlannerInfo *root,
344341
* Builds a join relation's target list.
345342
*
346343
* The join's targetlist includes all Vars of its member relations that
347-
* will still be needed above the join.
348-
*
349-
* In a former lifetime, this just merged the tlists of the two member
350-
* relations first presented. While we could still do that, working from
351-
* lists of Vars would mean doing a find_base_rel lookup for each Var.
352-
* It seems more efficient to scan the list of base rels and collect the
353-
* needed vars directly from there.
344+
* will still be needed above the join. This subroutine adds all such
345+
* Vars from the specified input rel's tlist to the join rel's tlist.
354346
*
355347
* We also compute the expected width of the join's output, making use
356348
* of data that was cached at the baserel level by set_rel_width().
357349
*/
358350
staticvoid
359-
build_joinrel_tlist(PlannerInfo*root,RelOptInfo*joinrel)
351+
build_joinrel_tlist(PlannerInfo*root,RelOptInfo*joinrel,
352+
RelOptInfo*input_rel)
360353
{
361354
Relidsrelids=joinrel->relids;
362-
ListCell*rels;
355+
ListCell*vars;
363356

364-
joinrel->reltargetlist=NIL;
365-
joinrel->width=0;
366-
367-
foreach(rels,root->base_rel_list)
357+
foreach(vars,input_rel->reltargetlist)
368358
{
369-
RelOptInfo*baserel= (RelOptInfo*)lfirst(rels);
370-
ListCell*vars;
359+
Var*var= (Var*)lfirst(vars);
360+
RelOptInfo*baserel;
361+
intndx;
362+
363+
/* We can't run into any child RowExprs here */
364+
Assert(IsA(var,Var));
371365

372-
if (!bms_is_member(baserel->relid,relids))
373-
continue;
366+
/* Get the Var's original base rel */
367+
baserel=find_base_rel(root,var->varno);
374368

375-
foreach(vars,baserel->reltargetlist)
369+
/* Is it still needed above this joinrel? */
370+
ndx=var->varattno-baserel->min_attr;
371+
if (bms_nonempty_difference(baserel->attr_needed[ndx],relids))
376372
{
377-
Var*var= (Var*)lfirst(vars);
378-
intndx=var->varattno-baserel->min_attr;
379-
380-
/* We can't run into any child RowExprs here */
381-
Assert(IsA(var,Var));
382-
383-
if (bms_nonempty_difference(baserel->attr_needed[ndx],relids))
384-
{
385-
joinrel->reltargetlist=lappend(joinrel->reltargetlist,var);
386-
Assert(baserel->attr_widths[ndx]>0);
387-
joinrel->width+=baserel->attr_widths[ndx];
388-
}
373+
/* Yup, add it to the output */
374+
joinrel->reltargetlist=lappend(joinrel->reltargetlist,var);
375+
Assert(baserel->attr_widths[ndx]>0);
376+
joinrel->width+=baserel->attr_widths[ndx];
389377
}
390378
}
391379
}

0 commit comments

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