Skip to content

Commit 9f76d0d

Browse files
tglsfdctglsfdc
committed
Fix GEQO to work again in CVS tip, by being more careful about memory
allocation in best_inner_indexscan(). While at it, simplify GEQO's interface to the main planner --- make_join_rel() offers exactly the API it really wants, whereas calling make_rels_by_clause_joins() and make_rels_by_clauseless_joins() required jumping through hoops. Rewrite gimme_tree for clarity (sometimes iteration is much better than recursion), and approximately halve GEQO's runtime by recognizing that tours of the forms (a,b,c,d,...) and (b,a,c,d,...) are equivalent because of symmetry in make_join_rel().
1 parent 9cecff0 commit 9f76d0d

File tree

7 files changed

+123
-86
lines changed

7 files changed

+123
-86
lines changed

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

Lines changed: 66 additions & 56 deletions
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
* Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
77
* Portions Copyright (c) 1994, Regents of the University of California
88
*
9-
* $Id: geqo_eval.c,v 1.59 2002/06/20 20:29:29 momjian Exp $
9+
* $Header: /cvsroot/pgsql/src/backend/optimizer/geqo/geqo_eval.c,v 1.60 2002/12/16 21:30:29 tgl Exp $
1010
*
1111
*-------------------------------------------------------------------------
1212
*/
@@ -21,6 +21,7 @@
2121

2222
#include "postgres.h"
2323

24+
#include <float.h>
2425
#include <math.h>
2526
#include <limits.h>
2627

@@ -44,6 +45,20 @@ geqo_eval(Query *root, List *initial_rels, Gene *tour, int num_gene)
4445
Cost fitness;
4546
List *savelist;
4647

48+
/*
49+
* Because gimme_tree considers both left- and right-sided trees,
50+
* there is no difference between a tour (a,b,c,d,...) and a tour
51+
* (b,a,c,d,...) --- the same join orders will be considered.
52+
* To avoid redundant cost calculations, we simply reject tours where
53+
* tour[0] > tour[1], assigning them an artificially bad fitness.
54+
*
55+
* (It would be better to tweak the GEQO logic to not generate such tours
56+
* in the first place, but I'm not sure of all the implications in the
57+
* mutation logic.)
58+
*/
59+
if (num_gene >= 2 && tour[0] > tour[1])
60+
return DBL_MAX;
61+
4762
/*
4863
* Create a private memory context that will hold all temp storage
4964
* allocated inside gimme_tree().
@@ -60,11 +75,15 @@ geqo_eval(Query *root, List *initial_rels, Gene *tour, int num_gene)
6075
ALLOCSET_DEFAULT_MAXSIZE);
6176
oldcxt = MemoryContextSwitchTo(mycontext);
6277

63-
/* preserve root->join_rel_list, which gimme_tree changes */
78+
/*
79+
* preserve root->join_rel_list, which gimme_tree changes; without this,
80+
* it'll be pointing at recycled storage after the MemoryContextDelete
81+
* below.
82+
*/
6483
savelist = root->join_rel_list;
6584

6685
/* construct the best path for the given combination of relations */
67-
joinrel = gimme_tree(root, initial_rels, tour, num_gene, 0, NULL);
86+
joinrel = gimme_tree(root, initial_rels, tour, num_gene);
6887

6988
/*
7089
* compute fitness
@@ -86,70 +105,61 @@ geqo_eval(Query *root, List *initial_rels, Gene *tour, int num_gene)
86105

87106
/*
88107
* gimme_tree
89-
* this routine considers only LEFT-SIDED TREES!
108+
* Form planner estimates for a join tree constructed in the specified
109+
* order.
90110
*
91111
* 'root' is the Query
92112
* 'initial_rels' is the list of initial relations (FROM-list items)
93113
* 'tour' is the proposed join order, of length 'num_gene'
94-
* 'rel_count' is number of initial_rels items already joined (initially 0)
95-
* 'old_rel' is the preceding join (initially NULL)
96114
*
97-
* Returns a new join relation incorporating all joins in a left-sided tree.
115+
* Returns a new join relation whose cheapest path is the best plan for
116+
* this join order.
117+
*
118+
* Note that at each step we consider using the next rel as both left and
119+
* right side of a join. However, we cannot build general ("bushy") plan
120+
* trees this way, only left-sided and right-sided trees.
98121
*/
99122
RelOptInfo *
100123
gimme_tree(Query *root, List *initial_rels,
101-
Gene *tour, int num_gene,
102-
int rel_count, RelOptInfo *old_rel)
124+
Gene *tour, int num_gene)
103125
{
104-
RelOptInfo *inner_rel; /* current relation */
105-
int init_rel_index;
126+
RelOptInfo *joinrel;
127+
int cur_rel_index;
128+
int rel_count;
106129

107-
if (rel_count < num_gene)
130+
/*
131+
* Start with the first relation ...
132+
*/
133+
cur_rel_index = (int) tour[0];
134+
135+
joinrel = (RelOptInfo *) nth(cur_rel_index - 1, initial_rels);
136+
137+
/*
138+
* And add on each relation in the specified order ...
139+
*/
140+
for (rel_count = 1; rel_count < num_gene; rel_count++)
108141
{
109-
/* tree not yet finished */
110-
init_rel_index = (int) tour[rel_count];
111-
112-
inner_rel = (RelOptInfo *) nth(init_rel_index - 1, initial_rels);
113-
114-
if (rel_count == 0)
115-
{
116-
/* processing first join with init_rel_index = (int) tour[0] */
117-
rel_count++;
118-
return gimme_tree(root, initial_rels,
119-
tour, num_gene,
120-
rel_count, inner_rel);
121-
}
122-
else
123-
{
124-
/* tree main part */
125-
List *acceptable_rels = makeList1(inner_rel);
126-
List *new_rels;
127-
RelOptInfo *new_rel;
128-
129-
new_rels = make_rels_by_clause_joins(root, old_rel,
130-
acceptable_rels);
131-
/* Shouldn't get more than one result */
132-
Assert(length(new_rels) <= 1);
133-
if (new_rels == NIL)
134-
{
135-
new_rels = make_rels_by_clauseless_joins(root, old_rel,
136-
acceptable_rels);
137-
Assert(length(new_rels) <= 1);
138-
if (new_rels == NIL)
139-
elog(ERROR, "gimme_tree: failed to construct join rel");
140-
}
141-
new_rel = (RelOptInfo *) lfirst(new_rels);
142-
143-
/* Find and save the cheapest paths for this rel */
144-
set_cheapest(new_rel);
145-
146-
/* and recurse... */
147-
rel_count++;
148-
return gimme_tree(root, initial_rels,
149-
tour, num_gene,
150-
rel_count, new_rel);
151-
}
142+
RelOptInfo *inner_rel;
143+
RelOptInfo *new_rel;
144+
145+
cur_rel_index = (int) tour[rel_count];
146+
147+
inner_rel = (RelOptInfo *) nth(cur_rel_index - 1, initial_rels);
148+
149+
/*
150+
* Construct a RelOptInfo representing the previous joinrel joined
151+
* to inner_rel. These are always inner joins. Note that we expect
152+
* the joinrel not to exist in root->join_rel_list yet, and so the
153+
* paths constructed for it will only include the ones we want.
154+
*/
155+
new_rel = make_join_rel(root, joinrel, inner_rel, JOIN_INNER);
156+
157+
/* Find and save the cheapest paths for this rel */
158+
set_cheapest(new_rel);
159+
160+
/* and repeat... */
161+
joinrel = new_rel;
152162
}
153163

154-
return old_rel; /* tree finished ... */
164+
return joinrel;
155165
}

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

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
* Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
10-
* $Id: geqo_main.c,v 1.32 2002/07/20 04:59:10 momjian Exp $
10+
* $Header: /cvsroot/pgsql/src/backend/optimizer/geqo/geqo_main.c,v 1.33 2002/12/16 21:30:29 tgl Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -235,8 +235,7 @@ geqo(Query *root, int number_of_rels, List *initial_rels)
235235

236236
/* root->join_rel_list will be modified during this ! */
237237
best_rel = gimme_tree(root, initial_rels,
238-
best_tour, pool->string_length,
239-
0, NULL);
238+
best_tour, pool->string_length);
240239

241240
/* DBG: show the query plan
242241
print_plan(best_plan, root);

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

Lines changed: 19 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
* Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
77
* Portions Copyright (c) 1994, Regents of the University of California
88
*
9-
* $Header: /cvsroot/pgsql/src/backend/optimizer/geqo/geqo_misc.c,v 1.35 2002/11/06 00:00:44 tgl Exp $
9+
* $Header: /cvsroot/pgsql/src/backend/optimizer/geqo/geqo_misc.c,v 1.36 2002/12/16 21:30:29 tgl Exp $
1010
*
1111
*-------------------------------------------------------------------------
1212
*/
@@ -31,19 +31,25 @@
3131
/*
3232
* avg_pool
3333
*/
34-
static float
34+
static double
3535
avg_pool(Pool *pool)
3636
{
3737
int i;
3838
double cumulative = 0.0;
3939

40-
if (pool->size == 0)
40+
if (pool->size <= 0)
4141
elog(ERROR, "avg_pool: pool_size of zero");
4242

43+
/*
44+
* Since the pool may contain multiple occurrences of DBL_MAX, divide
45+
* by pool->size before summing, not after, to avoid overflow. This
46+
* loses a little in speed and accuracy, but this routine is only used
47+
* for debug printouts, so we don't care that much.
48+
*/
4349
for (i = 0; i < pool->size; i++)
44-
cumulative = cumulative + pool->data[i].worth;
50+
cumulative += pool->data[i].worth / pool->size;
4551

46-
return (float) cumulative / pool->size;
52+
return cumulative;
4753
}
4854

4955
/* print_pool
@@ -72,8 +78,10 @@ print_pool(FILE *fp, Pool *pool, int start, int stop)
7278
fprintf(fp, "%d)\t", i);
7379
for (j = 0; j < pool->string_length; j++)
7480
fprintf(fp, "%d ", pool->data[i].string[j]);
75-
fprintf(fp, "%f\n", pool->data[i].worth);
81+
fprintf(fp, "%g\n", pool->data[i].worth);
7682
}
83+
84+
fflush(fp);
7785
}
7886

7987
/* print_gen
@@ -90,12 +98,14 @@ print_gen(FILE *fp, Pool *pool, int generation)
9098
lowest = pool->size > 1 ? pool->size - 2 : 0;
9199

92100
fprintf(fp,
93-
"%5d | Best: %f Worst: %f Mean: %f Avg: %f\n",
101+
"%5d | Best: %g Worst: %g Mean: %g Avg: %g\n",
94102
generation,
95103
pool->data[0].worth,
96104
pool->data[lowest].worth,
97105
pool->data[pool->size / 2].worth,
98106
avg_pool(pool));
107+
108+
fflush(fp);
99109
}
100110

101111

@@ -116,6 +126,8 @@ print_edge_table(FILE *fp, Edge *edge_table, int num_gene)
116126
}
117127

118128
fprintf(fp, "\n");
129+
130+
fflush(fp);
119131
}
120132

121133
#endif /* GEQO_DEBUG */

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

Lines changed: 20 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
*
1010
*
1111
* IDENTIFICATION
12-
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.129 2002/12/15 16:17:49 tgl Exp $
12+
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.130 2002/12/16 21:30:29 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -1398,6 +1398,7 @@ best_inner_indexscan(Query *root, RelOptInfo *rel,
13981398
List *ilist;
13991399
List *jlist;
14001400
InnerIndexscanInfo *info;
1401+
MemoryContext oldcontext;
14011402

14021403
/*
14031404
* Nestloop only supports inner and left joins.
@@ -1415,15 +1416,27 @@ best_inner_indexscan(Query *root, RelOptInfo *rel,
14151416
}
14161417
/*
14171418
* If there are no indexable joinclauses for this rel, exit quickly.
1418-
* Otherwise, intersect the given outer_relids with index_outer_relids
1419-
* to find the set of outer relids actually relevant for this index.
1420-
* If there are none, again we can fail immediately.
14211419
*/
14221420
if (!rel->index_outer_relids)
14231421
return NULL;
1422+
/*
1423+
* Otherwise, we have to do path selection in the memory context of
1424+
* the given rel, so that any created path can be safely attached to
1425+
* the rel's cache of best inner paths. (This is not currently an
1426+
* issue for normal planning, but it is an issue for GEQO planning.)
1427+
*/
1428+
oldcontext = MemoryContextSwitchTo(GetMemoryChunkContext(rel));
1429+
/*
1430+
* Intersect the given outer_relids with index_outer_relids
1431+
* to find the set of outer relids actually relevant for this index.
1432+
* If there are none, again we can fail immediately.
1433+
*/
14241434
outer_relids = set_intersecti(rel->index_outer_relids, outer_relids);
14251435
if (!outer_relids)
1436+
{
1437+
MemoryContextSwitchTo(oldcontext);
14261438
return NULL;
1439+
}
14271440
/*
14281441
* Look to see if we already computed the result for this set of
14291442
* relevant outerrels. (We include the isouterjoin status in the
@@ -1437,6 +1450,7 @@ best_inner_indexscan(Query *root, RelOptInfo *rel,
14371450
info->isouterjoin == isouterjoin)
14381451
{
14391452
freeList(outer_relids);
1453+
MemoryContextSwitchTo(oldcontext);
14401454
return info->best_innerpath;
14411455
}
14421456
}
@@ -1517,6 +1531,8 @@ best_inner_indexscan(Query *root, RelOptInfo *rel,
15171531
info->best_innerpath = cheapest;
15181532
rel->index_inner_paths = lcons(info, rel->index_inner_paths);
15191533

1534+
MemoryContextSwitchTo(oldcontext);
1535+
15201536
return cheapest;
15211537
}
15221538

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

Lines changed: 10 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v 1.57 2002/06/20 20:29:30 momjian Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v 1.58 2002/12/16 21:30:30 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -18,8 +18,12 @@
1818
#include "optimizer/paths.h"
1919

2020

21-
static RelOptInfo *make_join_rel(Query *root, RelOptInfo *rel1,
22-
RelOptInfo *rel2, JoinType jointype);
21+
static List *make_rels_by_clause_joins(Query *root,
22+
RelOptInfo *old_rel,
23+
List *other_rels);
24+
static List *make_rels_by_clauseless_joins(Query *root,
25+
RelOptInfo *old_rel,
26+
List *other_rels);
2327

2428

2529
/*
@@ -246,7 +250,7 @@ make_rels_by_joins(Query *root, int level, List **joinrels)
246250
* no extra test for overlap for initial rels, since the is_subset test can
247251
* only succeed when other_rel is not already part of old_rel.)
248252
*/
249-
List *
253+
static List *
250254
make_rels_by_clause_joins(Query *root,
251255
RelOptInfo *old_rel,
252256
List *other_rels)
@@ -297,7 +301,7 @@ make_rels_by_clause_joins(Query *root,
297301
* Currently, this is only used with initial rels in other_rels, but it would
298302
* work for joining to joinrels too.
299303
*/
300-
List *
304+
static List *
301305
make_rels_by_clauseless_joins(Query *root,
302306
RelOptInfo *old_rel,
303307
List *other_rels)
@@ -392,7 +396,7 @@ make_jointree_rel(Query *root, Node *jtnode)
392396
* (The join rel may already contain paths generated from other
393397
* pairs of rels that add up to the same set of base rels.)
394398
*/
395-
static RelOptInfo *
399+
RelOptInfo *
396400
make_join_rel(Query *root, RelOptInfo *rel1, RelOptInfo *rel2,
397401
JoinType jointype)
398402
{

‎src/include/optimizer/geqo.h

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
* Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
77
* Portions Copyright (c) 1994, Regents of the University of California
88
*
9-
* $Id: geqo.h,v 1.29 2002/07/20 04:59:10 momjian Exp $
9+
* $Id: geqo.h,v 1.30 2002/12/16 21:30:30 tgl Exp $
1010
*
1111
*-------------------------------------------------------------------------
1212
*/
@@ -74,7 +74,6 @@ extern RelOptInfo *geqo(Query *root, int number_of_rels, List *initial_rels);
7474
extern Cost geqo_eval(Query *root, List *initial_rels,
7575
Gene *tour, int num_gene);
7676
extern RelOptInfo *gimme_tree(Query *root, List *initial_rels,
77-
Gene *tour, int num_gene,
78-
int rel_count, RelOptInfo *old_rel);
77+
Gene *tour, int num_gene);
7978

8079
#endif /* GEQO_H */

0 commit comments

Comments
 (0)