Skip to content

Commit 1d5e7a6

Browse files
tglsfdctglsfdc
committed
Repair logic flaw in cost estimator: cost_nestloop() was estimating CPU
costs using the inner path's parent->rows count as the number of tuples processed per inner scan iteration. This is wrong when we are using an inner indexscan with indexquals based on join clauses, because the rows count in a Relation node reflects the selectivity of the restriction clauses for that rel only. Upshot was that if join clause was very selective, we'd drastically overestimate the true cost of the join. Fix is to calculate correct output-rows estimate for an inner indexscan when the IndexPath node is created and save it in the path node. Change of path node doesn't require initdb, since path nodes don't appear in saved rules.
1 parent d825e55 commit 1d5e7a6

File tree

11 files changed

+83
-63
lines changed

11 files changed

+83
-63
lines changed

‎src/backend/nodes/copyfuncs.c

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.109 2000/03/14 23:06:27 thomas Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.110 2000/03/22 22:08:32 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -1135,6 +1135,7 @@ _copyIndexPath(IndexPath *from)
11351135
Node_Copy(from, newnode, indexqual);
11361136
newnode->indexscandir = from->indexscandir;
11371137
newnode->joinrelids = listCopy(from->joinrelids);
1138+
newnode->rows = from->rows;
11381139

11391140
return newnode;
11401141
}

‎src/backend/nodes/equalfuncs.c

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/nodes/equalfuncs.c,v 1.64 2000/03/01 18:47:43 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/nodes/equalfuncs.c,v 1.65 2000/03/22 22:08:32 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -375,6 +375,9 @@ _equalIndexPath(IndexPath *a, IndexPath *b)
375375
return false;
376376
if (!equali(a->joinrelids, b->joinrelids))
377377
return false;
378+
/* Skip 'rows' because of possibility of floating-point roundoff error.
379+
* It should be derivable from the other fields anyway.
380+
*/
378381
return true;
379382
}
380383

‎src/backend/nodes/outfuncs.c

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
* Portions Copyright (c) 1996-2000, PostgreSQL, Inc
77
* Portions Copyright (c) 1994, Regents of the University of California
88
*
9-
* $Header: /cvsroot/pgsql/src/backend/nodes/outfuncs.c,v 1.111 2000/03/17 02:36:12 tgl Exp $
9+
* $Header: /cvsroot/pgsql/src/backend/nodes/outfuncs.c,v 1.112 2000/03/22 22:08:32 tgl Exp $
1010
*
1111
* NOTES
1212
* Every (plan) node in POSTGRES has an associated "out" routine which
@@ -1019,6 +1019,9 @@ _outIndexPath(StringInfo str, IndexPath *node)
10191019
appendStringInfo(str, " :indexscandir %d :joinrelids ",
10201020
(int) node->indexscandir);
10211021
_outIntList(str, node->joinrelids);
1022+
1023+
appendStringInfo(str, " :rows %.2f ",
1024+
node->rows);
10221025
}
10231026

10241027
/*

‎src/backend/nodes/readfuncs.c

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/nodes/readfuncs.c,v 1.86 2000/03/17 02:36:12 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/nodes/readfuncs.c,v 1.87 2000/03/22 22:08:32 tgl Exp $
1212
*
1313
* NOTES
1414
* Most of the read functions for plan nodes are tested. (In fact, they
@@ -1510,6 +1510,10 @@ _readIndexPath()
15101510
token = lsptok(NULL, &length); /* get :joinrelids */
15111511
local_node->joinrelids = toIntList(nodeRead(true));
15121512

1513+
token = lsptok(NULL, &length); /* get :rows */
1514+
token = lsptok(NULL, &length); /* now read it */
1515+
local_node->rows = atof(token);
1516+
15131517
return local_node;
15141518
}
15151519

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

Lines changed: 20 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -42,7 +42,7 @@
4242
* Portions Copyright (c) 1994, Regents of the University of California
4343
*
4444
* IDENTIFICATION
45-
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.53 2000/03/14 02:23:14 tgl Exp $
45+
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/costsize.c,v 1.54 2000/03/22 22:08:33 tgl Exp $
4646
*
4747
*-------------------------------------------------------------------------
4848
*/
@@ -202,7 +202,7 @@ cost_nonsequential_access(double relpages)
202202
* 'index' is the index to be used
203203
* 'indexQuals' is the list of applicable qual clauses (implicit AND semantics)
204204
* 'is_injoin' is T if we are considering using the index scan as the inside
205-
* of a nestloop join.
205+
* of a nestloop join (hence, some of the indexQuals are join clauses)
206206
*
207207
* NOTE: 'indexQuals' must contain only clauses usable as index restrictions.
208208
* Any additional quals evaluated as qpquals may reduce the number of returned
@@ -281,12 +281,15 @@ cost_index(Path *path, Query *root,
281281
/* CPU costs */
282282
cpu_per_tuple = cpu_tuple_cost + baserel->baserestrictcost;
283283
/*
284-
* Assume that the indexquals will be removed from the list of
285-
* restriction clauses that we actually have to evaluate as qpquals.
286-
* This is not completely right, but it's close.
287-
* For a lossy index, however, we will have to recheck all the quals.
284+
* Normally the indexquals will be removed from the list of restriction
285+
* clauses that we have to evaluate as qpquals, so we should subtract
286+
* their costs from baserestrictcost. For a lossy index, however, we
287+
* will have to recheck all the quals and so mustn't subtract anything.
288+
* Also, if we are doing a join then some of the indexquals are join
289+
* clauses and shouldn't be subtracted. Rather than work out exactly
290+
* how much to subtract, we don't subtract anything in that case either.
288291
*/
289-
if (! index->lossy)
292+
if (! index->lossy && ! is_injoin)
290293
cpu_per_tuple -= cost_qual_eval(indexQuals);
291294

292295
run_cost += cpu_per_tuple * tuples_fetched;
@@ -418,15 +421,12 @@ cost_sort(Path *path, List *pathkeys, double tuples, int width)
418421
* 'outer_path' is the path for the outer relation
419422
* 'inner_path' is the path for the inner relation
420423
* 'restrictlist' are the RestrictInfo nodes to be applied at the join
421-
* 'is_indexjoin' is true if we are using an indexscan for the inner relation
422-
* (not currently needed here; the indexscan adjusts its cost...)
423424
*/
424425
void
425426
cost_nestloop(Path *path,
426427
Path *outer_path,
427428
Path *inner_path,
428-
List *restrictlist,
429-
bool is_indexjoin)
429+
List *restrictlist)
430430
{
431431
Cost startup_cost = 0;
432432
Cost run_cost = 0;
@@ -447,8 +447,15 @@ cost_nestloop(Path *path,
447447
run_cost += outer_path->parent->rows *
448448
(inner_path->total_cost - inner_path->startup_cost);
449449

450-
/* number of tuples processed (not number emitted!) */
451-
ntuples = outer_path->parent->rows * inner_path->parent->rows;
450+
/* Number of tuples processed (not number emitted!). If inner path is
451+
* an indexscan, be sure to use its estimated output row count, which
452+
* may be lower than the restriction-clause-only row count of its parent.
453+
*/
454+
if (IsA(inner_path, IndexPath))
455+
ntuples = ((IndexPath *) inner_path)->rows;
456+
else
457+
ntuples = inner_path->parent->rows;
458+
ntuples *= outer_path->parent->rows;
452459

453460
/* CPU costs */
454461
cpu_per_tuple = cpu_tuple_cost + cost_qual_eval(restrictlist);

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

Lines changed: 21 additions & 1 deletion
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.80 2000/02/15 20:49:16 tgl Exp $
12+
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.81 2000/03/22 22:08:33 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -1454,6 +1454,26 @@ index_innerjoin(Query *root, RelOptInfo *rel, IndexOptInfo *index,
14541454
/* joinrelids saves the rels needed on the outer side of the join */
14551455
pathnode->joinrelids = lfirst(outerrelids_list);
14561456

1457+
/*
1458+
* We must compute the estimated number of output rows for the
1459+
* indexscan. This is less than rel->rows because of the additional
1460+
* selectivity of the join clauses. Since clausegroup may contain
1461+
* both restriction and join clauses, we have to do a set union to
1462+
* get the full set of clauses that must be considered to compute
1463+
* the correct selectivity. (We can't just nconc the two lists;
1464+
* then we might have some restriction clauses appearing twice,
1465+
* which'd mislead restrictlist_selectivity into double-counting
1466+
* their selectivity.)
1467+
*/
1468+
pathnode->rows = rel->tuples *
1469+
restrictlist_selectivity(root,
1470+
LispUnion(rel->baserestrictinfo,
1471+
clausegroup),
1472+
lfirsti(rel->relids));
1473+
/* Like costsize.c, force estimate to be at least one row */
1474+
if (pathnode->rows < 1.0)
1475+
pathnode->rows = 1.0;
1476+
14571477
cost_index(&pathnode->path, root, rel, index, indexquals, true);
14581478

14591479
path_list = lappend(path_list, pathnode);

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

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.37 2000/02/15 20:49:17 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/orindxpath.c,v 1.38 2000/03/22 22:08:33 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -99,7 +99,9 @@ create_or_index_paths(Query *root,
9999
/* We don't actually care what order the index scans in ... */
100100
pathnode->indexscandir = NoMovementScanDirection;
101101

102+
/* This isn't a nestloop innerjoin, so: */
102103
pathnode->joinrelids = NIL; /* no join clauses here */
104+
pathnode->rows = rel->rows;
103105

104106
best_or_subclause_indices(root,
105107
rel,

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

Lines changed: 3 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@
1010
*
1111
*
1212
* IDENTIFICATION
13-
* $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.86 2000/02/18 23:47:21 tgl Exp $
13+
* $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.87 2000/03/22 22:08:34 tgl Exp $
1414
*
1515
*-------------------------------------------------------------------------
1616
*/
@@ -314,7 +314,6 @@ create_indexscan_node(Query *root,
314314
List *ixid;
315315
IndexScan *scan_node;
316316
bool lossy = false;
317-
double plan_rows;
318317

319318
/* there should be exactly one base rel involved... */
320319
Assert(length(best_path->path.parent->relids) == 1);
@@ -350,20 +349,7 @@ create_indexscan_node(Query *root,
350349
* given by scan_clauses, there will normally be some duplications
351350
* between the lists. We get rid of the duplicates, then add back
352351
* if lossy.
353-
*
354-
* If this indexscan is a nestloop-join inner indexscan (as indicated
355-
* by having nonempty joinrelids), then it uses indexqual conditions
356-
* that are not part of the relation's restriction clauses. The rows
357-
* estimate stored in the relation's RelOptInfo will be an overestimate
358-
* because it did not take these extra conditions into account. So,
359-
* in this case we recompute the selectivity of the whole scan ---
360-
* considering both indexqual and qpqual --- rather than using the
361-
* RelOptInfo's rows value. Since clausesel.c assumes it's working on
362-
* minimized (no duplicates) expressions, we have to do that while we
363-
* have the duplicate-free qpqual available.
364352
*/
365-
plan_rows = best_path->path.parent->rows; /* OK unless nestloop inner */
366-
367353
if (length(indxqual) > 1)
368354
{
369355
/*
@@ -383,15 +369,6 @@ create_indexscan_node(Query *root,
383369
qpqual = set_difference(scan_clauses,
384370
lcons(indxqual_expr, NIL));
385371

386-
if (best_path->joinrelids)
387-
{
388-
/* recompute output row estimate using all available quals */
389-
plan_rows = best_path->path.parent->tuples *
390-
clauselist_selectivity(root,
391-
lcons(indxqual_expr, qpqual),
392-
baserelid);
393-
}
394-
395372
if (lossy)
396373
qpqual = lappend(qpqual, copyObject(indxqual_expr));
397374
}
@@ -404,15 +381,6 @@ create_indexscan_node(Query *root,
404381

405382
qpqual = set_difference(scan_clauses, indxqual_list);
406383

407-
if (best_path->joinrelids)
408-
{
409-
/* recompute output row estimate using all available quals */
410-
plan_rows = best_path->path.parent->tuples *
411-
clauselist_selectivity(root,
412-
nconc(listCopy(indxqual_list), qpqual),
413-
baserelid);
414-
}
415-
416384
if (lossy)
417385
qpqual = nconc(qpqual, (List *) copyObject(indxqual_list));
418386
}
@@ -433,10 +401,8 @@ create_indexscan_node(Query *root,
433401
best_path->indexscandir);
434402

435403
copy_path_costsize(&scan_node->scan.plan, &best_path->path);
436-
/* set up rows estimate (just to make EXPLAIN output reasonable) */
437-
if (plan_rows < 1.0)
438-
plan_rows = 1.0;
439-
scan_node->scan.plan.plan_rows = plan_rows;
404+
/* use the indexscan-specific rows estimate, not the parent rel's */
405+
scan_node->scan.plan.plan_rows = best_path->rows;
440406

441407
return scan_node;
442408
}

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

Lines changed: 10 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.61 2000/02/18 23:47:30 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.62 2000/03/22 22:08:35 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -337,8 +337,16 @@ create_index_path(Query *root,
337337
*/
338338
pathnode->indexid = lconsi(index->indexoid, NIL);
339339
pathnode->indexqual = lcons(indexquals, NIL);
340+
340341
pathnode->indexscandir = indexscandir;
342+
343+
/*
344+
* This routine is only used to generate "standalone" indexpaths,
345+
* not nestloop inner indexpaths. So joinrelids is always NIL
346+
* and the number of rows is the same as the parent rel's estimate.
347+
*/
341348
pathnode->joinrelids = NIL; /* no join clauses here */
349+
pathnode->rows = rel->rows;
342350

343351
cost_index(&pathnode->path, root, rel, index, indexquals, false);
344352

@@ -400,8 +408,7 @@ create_nestloop_path(RelOptInfo *joinrel,
400408
pathnode->joinrestrictinfo = restrict_clauses;
401409
pathnode->path.pathkeys = pathkeys;
402410

403-
cost_nestloop(&pathnode->path, outer_path, inner_path,
404-
restrict_clauses, IsA(inner_path, IndexPath));
411+
cost_nestloop(&pathnode->path, outer_path, inner_path, restrict_clauses);
405412

406413
return pathnode;
407414
}

‎src/include/nodes/relation.h

Lines changed: 9 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
* Portions Copyright (c) 1996-2000, PostgreSQL, Inc
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
10-
* $Id: relation.h,v 1.45 2000/02/18 23:47:17 tgl Exp $
10+
* $Id: relation.h,v 1.46 2000/03/22 22:08:29 tgl Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -252,6 +252,12 @@ typedef struct Path
252252
* as the inner path of a nestloop join. These paths have indexquals
253253
* that refer to values of other rels, so those other rels must be
254254
* included in the outer joinrel in order to make a usable join.
255+
*
256+
* 'rows' is the estimated result tuple count for the indexscan. This
257+
* is the same as path.parent->rows for a simple indexscan, but it is
258+
* different for a nestloop inner path, because the additional indexquals
259+
* coming from join clauses make the scan more selective than the parent
260+
* rel's restrict clauses alone would do.
255261
*----------
256262
*/
257263
typedef struct IndexPath
@@ -260,7 +266,8 @@ typedef struct IndexPath
260266
List *indexid;
261267
List *indexqual;
262268
ScanDirection indexscandir;
263-
Relids joinrelids; /* other rels mentioned in indexqual */
269+
Relids joinrelids; /* other rels mentioned in indexqual */
270+
double rows; /* estimated number of result tuples */
264271
} IndexPath;
265272

266273
typedef struct TidPath

‎src/include/optimizer/cost.h

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
* Portions Copyright (c) 1996-2000, PostgreSQL, Inc
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
10-
* $Id: cost.h,v 1.30 2000/02/15 20:49:25 tgl Exp $
10+
* $Id: cost.h,v 1.31 2000/03/22 22:08:30 tgl Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -58,7 +58,7 @@ extern void cost_index(Path *path, Query *root,
5858
extern void cost_tidscan(Path *path, RelOptInfo *baserel, List *tideval);
5959
extern void cost_sort(Path *path, List *pathkeys, double tuples, int width);
6060
extern void cost_nestloop(Path *path, Path *outer_path, Path *inner_path,
61-
List *restrictlist, bool is_indexjoin);
61+
List *restrictlist);
6262
extern void cost_mergejoin(Path *path, Path *outer_path, Path *inner_path,
6363
List *restrictlist,
6464
List *outersortkeys, List *innersortkeys);

0 commit comments

Comments
 (0)