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

Commit1a95f12

Browse files
committed
Eliminate a lot of list-management overhead within join_search_one_level
by adding a requirement that build_join_rel add new join RelOptInfos to theappropriate list immediately at creation. Per report from Robert Haas,the list_concat_unique_ptr() calls that this change eliminates were takingthe lion's share of the runtime in larger join problems. This doesn't doanything to fix the fundamental combinatorial explosion in large joinproblems, but it should push out the threshold of pain a bit further.Note: because this changes the order in which joinrel lists are built,it might result in changes in selected plans in cases where differentalternatives have exactly the same costs. There is one example in theregression tests.
1 parentfe83b97 commit1a95f12

File tree

9 files changed

+873
-863
lines changed

9 files changed

+873
-863
lines changed

‎src/backend/nodes/outfuncs.c

Lines changed: 2 additions & 1 deletion
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.372 2009/11/15 02:45:34 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.373 2009/11/28 00:46:18 tgl Exp $
1212
*
1313
* NOTES
1414
* Every node type that can appear in stored rules' parsetrees *must*
@@ -1544,6 +1544,7 @@ _outPlannerInfo(StringInfo str, PlannerInfo *node)
15441544
WRITE_NODE_FIELD(glob);
15451545
WRITE_UINT_FIELD(query_level);
15461546
WRITE_NODE_FIELD(join_rel_list);
1547+
WRITE_INT_FIELD(join_cur_level);
15471548
WRITE_NODE_FIELD(resultRelations);
15481549
WRITE_NODE_FIELD(init_plans);
15491550
WRITE_NODE_FIELD(cte_plan_ids);

‎src/backend/optimizer/geqo/geqo_eval.c

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
* Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
77
* Portions Copyright (c) 1994, Regents of the University of California
88
*
9-
* $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_eval.c,v 1.90 2009/07/19 21:00:43 tgl Exp $
9+
* $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_eval.c,v 1.91 2009/11/2800:46:18 tgl Exp $
1010
*
1111
*-------------------------------------------------------------------------
1212
*/
@@ -88,9 +88,12 @@ geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)
8888
* is one.We can do this by just temporarily setting the link to NULL.
8989
* (If we are dealing with enough join rels, which we very likely are, a
9090
* new hash table will get built and used locally.)
91+
*
92+
* join_rel_level[] shouldn't be in use, so just Assert it isn't.
9193
*/
9294
savelength=list_length(root->join_rel_list);
9395
savehash=root->join_rel_hash;
96+
Assert(root->join_rel_level==NULL);
9497

9598
root->join_rel_hash=NULL;
9699

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

Lines changed: 21 additions & 13 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.190 2009/11/22 14:54:31 heikki Exp $
11+
* $PostgreSQL: pgsql/src/backend/optimizer/path/allpaths.c,v 1.191 2009/11/28 00:46:19 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -898,41 +898,47 @@ make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
898898
RelOptInfo*
899899
standard_join_search(PlannerInfo*root,intlevels_needed,List*initial_rels)
900900
{
901-
List**joinitems;
902901
intlev;
903902
RelOptInfo*rel;
904903

904+
/*
905+
* This function cannot be invoked recursively within any one planning
906+
* problem, so join_rel_level[] can't be in use already.
907+
*/
908+
Assert(root->join_rel_level==NULL);
909+
905910
/*
906911
* We employ a simple "dynamic programming" algorithm: we first find all
907912
* ways to build joins of two jointree items, then all ways to build joins
908913
* of three items (from two-item joins and single items), then four-item
909914
* joins, and so on until we have considered all ways to join all the
910915
* items into one rel.
911916
*
912-
* joinitems[j] is a list of all the j-item rels. Initially we set
913-
* joinitems[1] to represent all the single-jointree-item relations.
917+
* root->join_rel_level[j] is a list of all the j-item rels. Initially we
918+
* set root->join_rel_level[1] to represent all the single-jointree-item
919+
* relations.
914920
*/
915-
joinitems= (List**)palloc0((levels_needed+1)*sizeof(List*));
921+
root->join_rel_level= (List**)palloc0((levels_needed+1)*sizeof(List*));
916922

917-
joinitems[1]=initial_rels;
923+
root->join_rel_level[1]=initial_rels;
918924

919925
for (lev=2;lev <=levels_needed;lev++)
920926
{
921-
ListCell*x;
927+
ListCell*lc;
922928

923929
/*
924930
* Determine all possible pairs of relations to be joined at this
925931
* level, and build paths for making each one from every available
926932
* pair of lower-level relations.
927933
*/
928-
joinitems[lev]=join_search_one_level(root,lev,joinitems);
934+
join_search_one_level(root,lev);
929935

930936
/*
931937
* Do cleanup work on each just-processed rel.
932938
*/
933-
foreach(x,joinitems[lev])
939+
foreach(lc,root->join_rel_level[lev])
934940
{
935-
rel= (RelOptInfo*)lfirst(x);
941+
rel= (RelOptInfo*)lfirst(lc);
936942

937943
/* Find and save the cheapest paths for this rel */
938944
set_cheapest(rel);
@@ -946,11 +952,13 @@ standard_join_search(PlannerInfo *root, int levels_needed, List *initial_rels)
946952
/*
947953
* We should have a single rel at the final level.
948954
*/
949-
if (joinitems[levels_needed]==NIL)
955+
if (root->join_rel_level[levels_needed]==NIL)
950956
elog(ERROR,"failed to build any %d-way joins",levels_needed);
951-
Assert(list_length(joinitems[levels_needed])==1);
957+
Assert(list_length(root->join_rel_level[levels_needed])==1);
958+
959+
rel= (RelOptInfo*)linitial(root->join_rel_level[levels_needed]);
952960

953-
rel=(RelOptInfo*)linitial(joinitems[levels_needed]);
961+
root->join_rel_level=NULL;
954962

955963
returnrel;
956964
}

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

Lines changed: 42 additions & 69 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/optimizer/path/joinrels.c,v 1.102 2009/07/23 17:42:06 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/optimizer/path/joinrels.c,v 1.103 2009/11/28 00:46:19 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -19,10 +19,10 @@
1919
#include"optimizer/paths.h"
2020

2121

22-
staticList*make_rels_by_clause_joins(PlannerInfo*root,
22+
staticvoidmake_rels_by_clause_joins(PlannerInfo*root,
2323
RelOptInfo*old_rel,
2424
ListCell*other_rels);
25-
staticList*make_rels_by_clauseless_joins(PlannerInfo*root,
25+
staticvoidmake_rels_by_clauseless_joins(PlannerInfo*root,
2626
RelOptInfo*old_rel,
2727
ListCell*other_rels);
2828
staticboolhas_join_restriction(PlannerInfo*root,RelOptInfo*rel);
@@ -40,17 +40,23 @@ static bool restriction_is_constant_false(List *restrictlist);
4040
* combination of lower-level rels are created and returned in a list.
4141
* Implementation paths are created for each such joinrel, too.
4242
*
43-
* level: level of rels we want to make this time.
44-
* joinrels[j], 1 <= j < level, is a list of rels containing j items.
43+
* level: level of rels we want to make this time
44+
* root->join_rel_level[j], 1 <= j < level, is a list of rels containing j items
45+
*
46+
* The result is returned in root->join_rel_level[level].
4547
*/
46-
List*
47-
join_search_one_level(PlannerInfo*root,intlevel,List**joinrels)
48+
void
49+
join_search_one_level(PlannerInfo*root,intlevel)
4850
{
49-
List*result_rels=NIL;
50-
List*new_rels;
51+
List**joinrels=root->join_rel_level;
5152
ListCell*r;
5253
intk;
5354

55+
Assert(joinrels[level]==NIL);
56+
57+
/* Set join_cur_level so that new joinrels are added to proper list */
58+
root->join_cur_level=level;
59+
5460
/*
5561
* First, consider left-sided and right-sided plans, in which rels of
5662
* exactly level-1 member relations are joined against initial relations.
@@ -88,9 +94,9 @@ join_search_one_level(PlannerInfo *root, int level, List **joinrels)
8894
*
8995
* See also the last-ditch case below.
9096
*/
91-
new_rels=make_rels_by_clause_joins(root,
92-
old_rel,
93-
other_rels);
97+
make_rels_by_clause_joins(root,
98+
old_rel,
99+
other_rels);
94100
}
95101
else
96102
{
@@ -99,20 +105,10 @@ join_search_one_level(PlannerInfo *root, int level, List **joinrels)
99105
* relation, either directly or by join-order restrictions.
100106
* Cartesian product time.
101107
*/
102-
new_rels=make_rels_by_clauseless_joins(root,
103-
old_rel,
104-
other_rels);
108+
make_rels_by_clauseless_joins(root,
109+
old_rel,
110+
other_rels);
105111
}
106-
107-
/*
108-
* At levels above 2 we will generate the same joined relation in
109-
* multiple ways --- for example (a join b) join c is the same
110-
* RelOptInfo as (b join c) join a, though the second case will add a
111-
* different set of Paths to it. To avoid making extra work for
112-
* subsequent passes, do not enter the same RelOptInfo into our output
113-
* list multiple times.
114-
*/
115-
result_rels=list_concat_unique_ptr(result_rels,new_rels);
116112
}
117113

118114
/*
@@ -168,13 +164,7 @@ join_search_one_level(PlannerInfo *root, int level, List **joinrels)
168164
if (have_relevant_joinclause(root,old_rel,new_rel)||
169165
have_join_order_restriction(root,old_rel,new_rel))
170166
{
171-
RelOptInfo*jrel;
172-
173-
jrel=make_join_rel(root,old_rel,new_rel);
174-
/* Avoid making duplicate entries ... */
175-
if (jrel)
176-
result_rels=list_append_unique_ptr(result_rels,
177-
jrel);
167+
(void)make_join_rel(root,old_rel,new_rel);
178168
}
179169
}
180170
}
@@ -193,7 +183,7 @@ join_search_one_level(PlannerInfo *root, int level, List **joinrels)
193183
* choice but to make cartesian joins.We consider only left-sided and
194184
* right-sided cartesian joins in this case (no bushy).
195185
*/
196-
if (result_rels==NIL)
186+
if (joinrels[level]==NIL)
197187
{
198188
/*
199189
* This loop is just like the first one, except we always call
@@ -211,11 +201,9 @@ join_search_one_level(PlannerInfo *root, int level, List **joinrels)
211201
other_rels=list_head(joinrels[1]);/* consider all initial
212202
* rels */
213203

214-
new_rels=make_rels_by_clauseless_joins(root,
215-
old_rel,
216-
other_rels);
217-
218-
result_rels=list_concat_unique_ptr(result_rels,new_rels);
204+
make_rels_by_clauseless_joins(root,
205+
old_rel,
206+
other_rels);
219207
}
220208

221209
/*----------
@@ -235,19 +223,23 @@ join_search_one_level(PlannerInfo *root, int level, List **joinrels)
235223
* never fail, and so the following sanity check is useful.
236224
*----------
237225
*/
238-
if (result_rels==NIL&&root->join_info_list==NIL)
226+
if (joinrels[level]==NIL&&root->join_info_list==NIL)
239227
elog(ERROR,"failed to build any %d-way joins",level);
240228
}
241-
242-
returnresult_rels;
243229
}
244230

245231
/*
246232
* make_rels_by_clause_joins
247233
* Build joins between the given relation 'old_rel' and other relations
248234
* that participate in join clauses that 'old_rel' also participates in
249235
* (or participate in join-order restrictions with it).
250-
* The join rel nodes are returned in a list.
236+
* The join rels are returned in root->join_rel_level[join_cur_level].
237+
*
238+
* Note: at levels above 2 we will generate the same joined relation in
239+
* multiple ways --- for example (a join b) join c is the same RelOptInfo as
240+
* (b join c) join a, though the second case will add a different set of Paths
241+
* to it. This is the reason for using the join_rel_level mechanism, which
242+
* automatically ensures that each new joinrel is only added to the list once.
251243
*
252244
* 'old_rel' is the relation entry for the relation to be joined
253245
* 'other_rels': the first cell in a linked list containing the other
@@ -256,12 +248,11 @@ join_search_one_level(PlannerInfo *root, int level, List **joinrels)
256248
* Currently, this is only used with initial rels in other_rels, but it
257249
* will work for joining to joinrels too.
258250
*/
259-
staticList*
251+
staticvoid
260252
make_rels_by_clause_joins(PlannerInfo*root,
261253
RelOptInfo*old_rel,
262254
ListCell*other_rels)
263255
{
264-
List*result=NIL;
265256
ListCell*l;
266257

267258
for_each_cell(l,other_rels)
@@ -272,23 +263,17 @@ make_rels_by_clause_joins(PlannerInfo *root,
272263
(have_relevant_joinclause(root,old_rel,other_rel)||
273264
have_join_order_restriction(root,old_rel,other_rel)))
274265
{
275-
RelOptInfo*jrel;
276-
277-
jrel=make_join_rel(root,old_rel,other_rel);
278-
if (jrel)
279-
result=lcons(jrel,result);
266+
(void)make_join_rel(root,old_rel,other_rel);
280267
}
281268
}
282-
283-
returnresult;
284269
}
285270

286271
/*
287272
* make_rels_by_clauseless_joins
288273
* Given a relation 'old_rel' and a list of other relations
289274
* 'other_rels', create a join relation between 'old_rel' and each
290275
* member of 'other_rels' that isn't already included in 'old_rel'.
291-
* The joinrel nodesare returned ina list.
276+
* The joinrelsare returned inroot->join_rel_level[join_cur_level].
292277
*
293278
* 'old_rel' is the relation entry for the relation to be joined
294279
* 'other_rels': the first cell of a linked list containing the
@@ -297,34 +282,22 @@ make_rels_by_clause_joins(PlannerInfo *root,
297282
* Currently, this is only used with initial rels in other_rels, but it would
298283
* work for joining to joinrels too.
299284
*/
300-
staticList*
285+
staticvoid
301286
make_rels_by_clauseless_joins(PlannerInfo*root,
302287
RelOptInfo*old_rel,
303288
ListCell*other_rels)
304289
{
305-
List*result=NIL;
306-
ListCell*i;
290+
ListCell*l;
307291

308-
for_each_cell(i,other_rels)
292+
for_each_cell(l,other_rels)
309293
{
310-
RelOptInfo*other_rel= (RelOptInfo*)lfirst(i);
294+
RelOptInfo*other_rel= (RelOptInfo*)lfirst(l);
311295

312296
if (!bms_overlap(other_rel->relids,old_rel->relids))
313297
{
314-
RelOptInfo*jrel;
315-
316-
jrel=make_join_rel(root,old_rel,other_rel);
317-
318-
/*
319-
* As long as given other_rels are distinct, don't need to test to
320-
* see if jrel is already part of output list.
321-
*/
322-
if (jrel)
323-
result=lcons(jrel,result);
298+
(void)make_join_rel(root,old_rel,other_rel);
324299
}
325300
}
326-
327-
returnresult;
328301
}
329302

330303

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

Lines changed: 3 additions & 1 deletion
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.115 2009/06/11 14:48:59 momjian Exp $
17+
* $PostgreSQL: pgsql/src/backend/optimizer/plan/planmain.c,v 1.116 2009/11/28 00:46:19 tgl Exp $
1818
*
1919
*-------------------------------------------------------------------------
2020
*/
@@ -142,6 +142,8 @@ query_planner(PlannerInfo *root, List *tlist,
142142
palloc0(root->simple_rel_array_size*sizeof(RelOptInfo*));
143143
root->join_rel_list=NIL;
144144
root->join_rel_hash=NULL;
145+
root->join_rel_level=NULL;
146+
root->join_cur_level=0;
145147
root->canon_pathkeys=NIL;
146148
root->left_join_clauses=NIL;
147149
root->right_join_clauses=NIL;

0 commit comments

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