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

Commit52579d5

Browse files
committed
Fix GEQO to not assume its join order heuristic always works.
Back in commit400e2c9 I rewrote GEQO'sgimme_tree function to improve its heuristic for modifying the given tourinto a legal join order. In what can only be called a fit of hubris,I supposed that this new heuristic would *always* find a legal join order,and ripped out the old logic that allowed gimme_tree to sometimes fail.The folly of this is exposed by bug #12760, in which the "greedy" clumpingbehavior of merge_clump() can lead it into a dead end which could only berecovered from by un-clumping. We have no code for that and wouldn't knowexactly what to do with it if we did. Rather than try to improve theheuristic rules still further, let's just recognize that it *is* aheuristic and probably must always have failure cases. So, put back thecode removed in the previous commit to allow for failure (but comment ita bit better this time).It's possible that this code was actually fully correct at the time andhas only been broken by the introduction of LATERAL. But having seen thisexample I no longer have much faith in that proposition, so back-patch toall supported branches.
1 parent0d36d9f commit52579d5

File tree

3 files changed

+49
-9
lines changed

3 files changed

+49
-9
lines changed

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

Lines changed: 21 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -49,6 +49,9 @@ static bool desirable_join(PlannerInfo *root,
4949
* geqo_eval
5050
*
5151
* Returns cost of a query tree as an individual of the population.
52+
*
53+
* If no legal join order can be extracted from the proposed tour,
54+
* returns DBL_MAX.
5255
*/
5356
Cost
5457
geqo_eval(PlannerInfo*root,Gene*tour,intnum_gene)
@@ -101,12 +104,19 @@ geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)
101104
joinrel=gimme_tree(root,tour,num_gene);
102105

103106
/*
104-
* compute fitness
107+
* compute fitness, if we found a valid join
105108
*
106109
* XXX geqo does not currently support optimization for partial result
107110
* retrieval --- how to fix?
108111
*/
109-
fitness=joinrel->cheapest_total_path->total_cost;
112+
if (joinrel)
113+
{
114+
Path*best_path=joinrel->cheapest_total_path;
115+
116+
fitness=best_path->total_cost;
117+
}
118+
else
119+
fitness=DBL_MAX;
110120

111121
/*
112122
* Restore join_rel_list to its former state, and put back original
@@ -131,7 +141,8 @@ geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)
131141
* 'tour' is the proposed join order, of length 'num_gene'
132142
*
133143
* Returns a new join relation whose cheapest path is the best plan for
134-
* this join order.
144+
* this join order. NB: will return NULL if join order is invalid and
145+
* we can't modify it into a valid order.
135146
*
136147
* The original implementation of this routine always joined in the specified
137148
* order, and so could only build left-sided plans (and right-sided and
@@ -144,7 +155,10 @@ geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)
144155
* postpones joins that are illegal or seem unsuitable according to some
145156
* heuristic rules. This allows correct bushy plans to be generated at need,
146157
* and as a nice side-effect it seems to materially improve the quality of the
147-
* generated plans.
158+
* generated plans. Note however that since it's just a heuristic, it can
159+
* still fail in some cases. (In particular, we might clump together
160+
* relations that actually mustn't be joined yet due to LATERAL restrictions;
161+
* since there's no provision for un-clumping, this must lead to failure.)
148162
*/
149163
RelOptInfo*
150164
gimme_tree(PlannerInfo*root,Gene*tour,intnum_gene)
@@ -161,9 +175,8 @@ gimme_tree(PlannerInfo *root, Gene *tour, int num_gene)
161175
* to; if there is none then it becomes a new clump of its own. When we
162176
* enlarge an existing clump we check to see if it can now be merged with
163177
* any other clumps. After the tour is all scanned, we forget about the
164-
* heuristics and try to forcibly join any remaining clumps. Some forced
165-
* joins might still fail due to semantics, but we should always be able
166-
* to find some join order that works.
178+
* heuristics and try to forcibly join any remaining clumps. If we are
179+
* unable to merge all the clumps into one, fail.
167180
*/
168181
clumps=NIL;
169182

@@ -205,7 +218,7 @@ gimme_tree(PlannerInfo *root, Gene *tour, int num_gene)
205218

206219
/* Did we succeed in forming a single join relation? */
207220
if (list_length(clumps)!=1)
208-
elog(ERROR,"failed to join all relations together");
221+
returnNULL;
209222

210223
return ((Clump*)linitial(clumps))->joinrel;
211224
}

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

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -261,6 +261,9 @@ geqo(PlannerInfo *root, int number_of_rels, List *initial_rels)
261261

262262
best_rel=gimme_tree(root,best_tour,pool->string_length);
263263

264+
if (best_rel==NULL)
265+
elog(ERROR,"geqo failed to make a valid plan");
266+
264267
/* DBG: show the query plan */
265268
#ifdefNOT_USED
266269
print_plan(best_plan,root);

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

Lines changed: 25 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -92,13 +92,37 @@ random_init_pool(PlannerInfo *root, Pool *pool)
9292
{
9393
Chromosome*chromo= (Chromosome*)pool->data;
9494
inti;
95+
intbad=0;
9596

96-
for (i=0;i<pool->size;i++)
97+
/*
98+
* We immediately discard any invalid individuals (those that geqo_eval
99+
* returns DBL_MAX for), thereby not wasting pool space on them.
100+
*
101+
* If we fail to make any valid individuals after 10000 tries, give up;
102+
* this probably means something is broken, and we shouldn't just let
103+
* ourselves get stuck in an infinite loop.
104+
*/
105+
i=0;
106+
while (i<pool->size)
97107
{
98108
init_tour(root,chromo[i].string,pool->string_length);
99109
pool->data[i].worth=geqo_eval(root,chromo[i].string,
100110
pool->string_length);
111+
if (pool->data[i].worth<DBL_MAX)
112+
i++;
113+
else
114+
{
115+
bad++;
116+
if (i==0&&bad >=10000)
117+
elog(ERROR,"geqo failed to make a valid plan");
118+
}
101119
}
120+
121+
#ifdefGEQO_DEBUG
122+
if (bad>0)
123+
elog(DEBUG1,"%d invalid tours found while selecting %d pool entries",
124+
bad,pool->size);
125+
#endif
102126
}
103127

104128
/*

0 commit comments

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