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

Commitf5bc741

Browse files
committed
Make GEQO's planning deterministic by having it start from a predictable
random number seed each time. This is how it used to work years ago, butwe got rid of the seed reset because it was resetting the main random()sequence and thus having undesirable effects on the rest of the system.To fix, establish a private random number state for each execution ofgeqo(), and initialize the state using the new GUC variable geqo_seed.People who want to experiment with different random searches can do soby changing geqo_seed, but you'll always get the same plan for the samevalue of geqo_seed (if holding all other planner inputs constant, of course).The new state is kept in PlannerInfo by adding a "void *" field reservedfor use by join_search hooks. Most of the rather bulky code changes inthis commit are just arranging to pass PlannerInfo around to all the GEQOfunctions (many of which formerly didn't receive it).Andres Freund, with some editorialization by Tom
1 parentc43feef commitf5bc741

27 files changed

+305
-202
lines changed

‎doc/src/sgml/config.sgml

Lines changed: 18 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
<!-- $PostgreSQL: pgsql/doc/src/sgml/config.sgml,v 1.221 2009/07/03 19:14:25 petere Exp $ -->
1+
<!-- $PostgreSQL: pgsql/doc/src/sgml/config.sgml,v 1.222 2009/07/16 20:55:44 tgl Exp $ -->
22

33
<chapter Id="runtime-config">
44
<title>Server Configuration</title>
@@ -2149,7 +2149,23 @@ archive_command = 'copy "%p" "C:\\server\\archivedir\\%f"' # Windows
21492149
</para>
21502150
</listitem>
21512151
</varlistentry>
2152-
2152+
2153+
<varlistentry id="guc-geqo-seed" xreflabel="geqo_seed">
2154+
<term><varname>geqo_seed</varname> (<type>floating point</type>)</term>
2155+
<indexterm>
2156+
<primary><varname>geqo_seed</> configuration parameter</primary>
2157+
</indexterm>
2158+
<listitem>
2159+
<para>
2160+
Controls the initial value of the random number generator used
2161+
by GEQO to select random paths through the join order search space.
2162+
The value can range from zero (the default) to one. Varying the
2163+
value changes the set of join paths explored, and may result in a
2164+
better or worse best path being found.
2165+
</para>
2166+
</listitem>
2167+
</varlistentry>
2168+
21532169
</variablelist>
21542170
</sect2>
21552171
<sect2 id="runtime-config-query-other">

‎doc/src/sgml/geqo.sgml

Lines changed: 12 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
<!-- $PostgreSQL: pgsql/doc/src/sgml/geqo.sgml,v 1.40 2007/07/21 04:02:41 tgl Exp $ -->
1+
<!-- $PostgreSQL: pgsql/doc/src/sgml/geqo.sgml,v 1.41 2009/07/16 20:55:44 tgl Exp $ -->
22

33
<chapter id="geqo">
44
<chapterinfo>
@@ -49,7 +49,7 @@
4949
methods</firstterm> (e.g., nested loop, hash join, merge join in
5050
<productname>PostgreSQL</productname>) to process individual joins
5151
and a diversity of <firstterm>indexes</firstterm> (e.g.,
52-
B-tree, hash, GiST and GIN in <productname>PostgreSQL</productname>) as
52+
B-tree, hash, GiST and GIN in <productname>PostgreSQL</productname>) as
5353
access paths for relations.
5454
</para>
5555

@@ -88,8 +88,7 @@
8888

8989
<para>
9090
The genetic algorithm (<acronym>GA</acronym>) is a heuristic optimization method which
91-
operates through
92-
nondeterministic, randomized search. The set of possible solutions for the
91+
operates through randomized search. The set of possible solutions for the
9392
optimization problem is considered as a
9493
<firstterm>population</firstterm> of <firstterm>individuals</firstterm>.
9594
The degree of adaptation of an individual to its environment is specified
@@ -116,7 +115,7 @@
116115
According to the <systemitem class="resource">comp.ai.genetic</> <acronym>FAQ</acronym> it cannot be stressed too
117116
strongly that a <acronym>GA</acronym> is not a pure random search for a solution to a
118117
problem. A <acronym>GA</acronym> uses stochastic processes, but the result is distinctly
119-
non-random (better than random).
118+
non-random (better than random).
120119
</para>
121120

122121
<figure id="geqo-diagram">
@@ -260,9 +259,13 @@
260259
<para>
261260
This process is inherently nondeterministic, because of the randomized
262261
choices made during both the initial population selection and subsequent
263-
<quote>mutation</> of the best candidates. Hence different plans may
264-
be selected from one run to the next, resulting in varying run time
265-
and varying output row order.
262+
<quote>mutation</> of the best candidates. To avoid surprising changes
263+
of the selected plan, each run of the GEQO algorithm restarts its
264+
random number generator with the current <xref linkend="guc-geqo-seed">
265+
parameter setting. As long as <varname>geqo_seed</> and the other
266+
GEQO parameters are kept fixed, the same plan will be generated for a
267+
given query (and other planner inputs such as statistics). To experiment
268+
with different search paths, try changing <varname>geqo_seed</>.
266269
</para>
267270

268271
</sect2>
@@ -330,7 +333,7 @@
330333
url="news://comp.ai.genetic"></ulink>)
331334
</para>
332335
</listitem>
333-
336+
334337
<listitem>
335338
<para>
336339
<ulink url="http://www.red3d.com/cwr/evolve.html">

‎src/backend/optimizer/geqo/Makefile

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
#
66
# Copyright (c) 1994, Regents of the University of California
77
#
8-
# $PostgreSQL: pgsql/src/backend/optimizer/geqo/Makefile,v 1.20 2008/02/19 10:30:07 petere Exp $
8+
# $PostgreSQL: pgsql/src/backend/optimizer/geqo/Makefile,v 1.21 2009/07/16 20:55:44 tgl Exp $
99
#
1010
#-------------------------------------------------------------------------
1111

@@ -14,7 +14,7 @@ top_builddir = ../../../..
1414
include$(top_builddir)/src/Makefile.global
1515

1616
OBJS =geqo_copy.o geqo_eval.o geqo_main.o geqo_misc.o\
17-
geqo_mutation.o geqo_pool.o geqo_recombination.o\
17+
geqo_mutation.o geqo_pool.ogeqo_random.ogeqo_recombination.o\
1818
geqo_selection.o\
1919
geqo_erx.o geqo_pmx.o geqo_cx.o geqo_px.o geqo_ox1.o geqo_ox2.o
2020

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

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@
55
* Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
66
* Portions Copyright (c) 1994, Regents of the University of California
77
*
8-
* $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_copy.c,v 1.19 2009/01/01 17:23:43 momjian Exp $
8+
* $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_copy.c,v 1.20 2009/07/16 20:55:44 tgl Exp $
99
*
1010
*-------------------------------------------------------------------------
1111
*/
@@ -42,7 +42,8 @@
4242
*
4343
*/
4444
void
45-
geqo_copy(Chromosome*chromo1,Chromosome*chromo2,intstring_length)
45+
geqo_copy(PlannerInfo*root,Chromosome*chromo1,Chromosome*chromo2,
46+
intstring_length)
4647
{
4748
inti;
4849

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

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
* CX operator according to Oliver et al
77
* (Proc 2nd Int'l Conf on GA's)
88
*
9-
* $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_cx.c,v 1.10 2003/11/29 22:39:49 pgsql Exp $
9+
* $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_cx.c,v 1.11 2009/07/16 20:55:44 tgl Exp $
1010
*
1111
*-------------------------------------------------------------------------
1212
*/
@@ -44,7 +44,8 @@
4444
* cycle crossover
4545
*/
4646
int
47-
cx(Gene*tour1,Gene*tour2,Gene*offspring,intnum_gene,City*city_table)
47+
cx(PlannerInfo*root,Gene*tour1,Gene*tour2,Gene*offspring,
48+
intnum_gene,City*city_table)
4849
{
4950

5051
inti,
@@ -62,7 +63,7 @@ cx(Gene *tour1, Gene *tour2, Gene *offspring, int num_gene, City *city_table)
6263
}
6364

6465
/* choose random cycle starting position */
65-
start_pos=geqo_randint(num_gene-1,0);
66+
start_pos=geqo_randint(root,num_gene-1,0);
6667

6768
/* child inherits first city */
6869
offspring[start_pos]=tour1[start_pos];

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

Lines changed: 26 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
* geqo_erx.c
44
* edge recombination crossover [ER]
55
*
6-
* $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_erx.c,v 1.20 2005/10/15 02:49:19 momjian Exp $
6+
* $PostgreSQL: pgsql/src/backend/optimizer/geqo/geqo_erx.c,v 1.21 2009/07/16 20:55:44 tgl Exp $
77
*
88
*-------------------------------------------------------------------------
99
*/
@@ -36,11 +36,11 @@
3636
#include"optimizer/geqo_random.h"
3737

3838

39-
staticintgimme_edge(Genegene1,Genegene2,Edge*edge_table);
40-
staticvoidremove_gene(Genegene,Edgeedge,Edge*edge_table);
41-
staticGenegimme_gene(Edgeedge,Edge*edge_table);
39+
staticintgimme_edge(PlannerInfo*root,Genegene1,Genegene2,Edge*edge_table);
40+
staticvoidremove_gene(PlannerInfo*root,Genegene,Edgeedge,Edge*edge_table);
41+
staticGenegimme_gene(PlannerInfo*root,Edgeedge,Edge*edge_table);
4242

43-
staticGeneedge_failure(Gene*gene,intindex,Edge*edge_table,intnum_gene);
43+
staticGeneedge_failure(PlannerInfo*root,Gene*gene,intindex,Edge*edge_table,intnum_gene);
4444

4545

4646
/* alloc_edge_table
@@ -50,7 +50,7 @@ static Gene edge_failure(Gene *gene, int index, Edge *edge_table, int num_gene);
5050
*/
5151

5252
Edge*
53-
alloc_edge_table(intnum_gene)
53+
alloc_edge_table(PlannerInfo*root,intnum_gene)
5454
{
5555
Edge*edge_table;
5656

@@ -70,7 +70,7 @@ alloc_edge_table(int num_gene)
7070
*
7171
*/
7272
void
73-
free_edge_table(Edge*edge_table)
73+
free_edge_table(PlannerInfo*root,Edge*edge_table)
7474
{
7575
pfree(edge_table);
7676
}
@@ -89,7 +89,8 @@ free_edge_table(Edge *edge_table)
8989
*
9090
*/
9191
float
92-
gimme_edge_table(Gene*tour1,Gene*tour2,intnum_gene,Edge*edge_table)
92+
gimme_edge_table(PlannerInfo*root,Gene*tour1,Gene*tour2,
93+
intnum_gene,Edge*edge_table)
9394
{
9495
inti,
9596
index1,
@@ -121,11 +122,11 @@ gimme_edge_table(Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table)
121122
* twice per edge
122123
*/
123124

124-
edge_total+=gimme_edge(tour1[index1],tour1[index2],edge_table);
125-
gimme_edge(tour1[index2],tour1[index1],edge_table);
125+
edge_total+=gimme_edge(root,tour1[index1],tour1[index2],edge_table);
126+
gimme_edge(root,tour1[index2],tour1[index1],edge_table);
126127

127-
edge_total+=gimme_edge(tour2[index1],tour2[index2],edge_table);
128-
gimme_edge(tour2[index2],tour2[index1],edge_table);
128+
edge_total+=gimme_edge(root,tour2[index1],tour2[index2],edge_table);
129+
gimme_edge(root,tour2[index2],tour2[index1],edge_table);
129130
}
130131

131132
/* return average number of edges per index */
@@ -147,7 +148,7 @@ gimme_edge_table(Gene *tour1, Gene *tour2, int num_gene, Edge *edge_table)
147148
* 0 if edge was already registered and edge_table is unchanged
148149
*/
149150
staticint
150-
gimme_edge(Genegene1,Genegene2,Edge*edge_table)
151+
gimme_edge(PlannerInfo*root,Genegene1,Genegene2,Edge*edge_table)
151152
{
152153
inti;
153154
intedges;
@@ -189,13 +190,13 @@ gimme_edge(Gene gene1, Gene gene2, Edge *edge_table)
189190
*
190191
*/
191192
int
192-
gimme_tour(Edge*edge_table,Gene*new_gene,intnum_gene)
193+
gimme_tour(PlannerInfo*root,Edge*edge_table,Gene*new_gene,intnum_gene)
193194
{
194195
inti;
195196
intedge_failures=0;
196197

197-
new_gene[0]= (Gene)geqo_randint(num_gene,1);/* choose int between 1
198-
* andnum_gene */
198+
/* choose int between 1 and num_gene */
199+
new_gene[0]= (Gene)geqo_randint(root,num_gene,1);
199200

200201
for (i=1;i<num_gene;i++)
201202
{
@@ -204,18 +205,18 @@ gimme_tour(Edge *edge_table, Gene *new_gene, int num_gene)
204205
* table
205206
*/
206207

207-
remove_gene(new_gene[i-1],edge_table[(int)new_gene[i-1]],edge_table);
208+
remove_gene(root,new_gene[i-1],edge_table[(int)new_gene[i-1]],edge_table);
208209

209210
/* find destination for the newly entered point */
210211

211212
if (edge_table[new_gene[i-1]].unused_edges>0)
212-
new_gene[i]=gimme_gene(edge_table[(int)new_gene[i-1]],edge_table);
213+
new_gene[i]=gimme_gene(root,edge_table[(int)new_gene[i-1]],edge_table);
213214

214215
else
215216
{/* cope with fault */
216217
edge_failures++;
217218

218-
new_gene[i]=edge_failure(new_gene,i-1,edge_table,num_gene);
219+
new_gene[i]=edge_failure(root,new_gene,i-1,edge_table,num_gene);
219220
}
220221

221222
/* mark this node as incorporated */
@@ -235,7 +236,7 @@ gimme_tour(Edge *edge_table, Gene *new_gene, int num_gene)
235236
*
236237
*/
237238
staticvoid
238-
remove_gene(Genegene,Edgeedge,Edge*edge_table)
239+
remove_gene(PlannerInfo*root,Genegene,Edgeedge,Edge*edge_table)
239240
{
240241
inti,
241242
j;
@@ -277,7 +278,7 @@ remove_gene(Gene gene, Edge edge, Edge *edge_table)
277278
*
278279
*/
279280
staticGene
280-
gimme_gene(Edgeedge,Edge*edge_table)
281+
gimme_gene(PlannerInfo*root,Edgeedge,Edge*edge_table)
281282
{
282283
inti;
283284
Genefriend;
@@ -340,7 +341,7 @@ gimme_gene(Edge edge, Edge *edge_table)
340341

341342

342343
/* random decision of the possible candidates to use */
343-
rand_decision=(int)geqo_randint(minimum_count-1,0);
344+
rand_decision=geqo_randint(root,minimum_count-1,0);
344345

345346

346347
for (i=0;i<edge.unused_edges;i++)
@@ -368,7 +369,7 @@ gimme_gene(Edge edge, Edge *edge_table)
368369
*
369370
*/
370371
staticGene
371-
edge_failure(Gene*gene,intindex,Edge*edge_table,intnum_gene)
372+
edge_failure(PlannerInfo*root,Gene*gene,intindex,Edge*edge_table,intnum_gene)
372373
{
373374
inti;
374375
Genefail_gene=gene[index];
@@ -401,7 +402,7 @@ edge_failure(Gene *gene, int index, Edge *edge_table, int num_gene)
401402
if (four_count!=0)
402403
{
403404

404-
rand_decision=(int)geqo_randint(four_count-1,0);
405+
rand_decision=geqo_randint(root,four_count-1,0);
405406

406407
for (i=1;i <=num_gene;i++)
407408
{
@@ -423,7 +424,7 @@ edge_failure(Gene *gene, int index, Edge *edge_table, int num_gene)
423424
elseif (remaining_edges!=0)
424425
{
425426
/* random decision of the gene with remaining edges */
426-
rand_decision=(int)geqo_randint(remaining_edges-1,0);
427+
rand_decision=geqo_randint(root,remaining_edges-1,0);
427428

428429
for (i=1;i <=num_gene;i++)
429430
{

0 commit comments

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