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

Commite6f7edb

Browse files
committed
Install some slightly realistic cost estimation for bitmap index scans.
1 parent2f8c7c8 commite6f7edb

File tree

8 files changed

+195
-31
lines changed

8 files changed

+195
-31
lines changed

‎src/backend/nodes/outfuncs.c

Lines changed: 3 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.247 2005/04/19 22:35:14 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/nodes/outfuncs.c,v 1.248 2005/04/21 02:28:01 tgl Exp $
1212
*
1313
* NOTES
1414
* Every node type that can appear in stored rules' parsetrees *must*
@@ -1024,6 +1024,8 @@ _outIndexPath(StringInfo str, IndexPath *node)
10241024
WRITE_NODE_FIELD(indexquals);
10251025
WRITE_BOOL_FIELD(isjoininner);
10261026
WRITE_ENUM_FIELD(indexscandir,ScanDirection);
1027+
WRITE_FLOAT_FIELD(indextotalcost,"%.2f");
1028+
WRITE_FLOAT_FIELD(indexselectivity,"%.4f");
10271029
WRITE_FLOAT_FIELD(rows,"%.0f");
10281030
}
10291031

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

Lines changed: 152 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -49,7 +49,7 @@
4949
* Portions Copyright (c) 1994, Regents of the University of California
5050
*
5151
* IDENTIFICATION
52-
* $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.142 2005/04/19 22:35:15 tgl Exp $
52+
* $PostgreSQL: pgsql/src/backend/optimizer/path/costsize.c,v 1.143 2005/04/21 02:28:01 tgl Exp $
5353
*
5454
*-------------------------------------------------------------------------
5555
*/
@@ -103,6 +103,7 @@ boolenable_hashjoin = true;
103103

104104

105105
staticboolcost_qual_eval_walker(Node*node,QualCost*total);
106+
staticSelectivitycost_bitmap_qual(Node*bitmapqual,Cost*totalCost);
106107
staticSelectivityapprox_selectivity(Query*root,List*quals,
107108
JoinTypejointype);
108109
staticSelectivityjoin_in_selectivity(JoinPath*path,Query*root);
@@ -126,7 +127,7 @@ clamp_row_est(double nrows)
126127
if (nrows<1.0)
127128
nrows=1.0;
128129
else
129-
nrows=ceil(nrows);
130+
nrows=rint(nrows);
130131

131132
returnnrows;
132133
}
@@ -232,6 +233,10 @@ cost_nonsequential_access(double relpages)
232233
* 'is_injoin' is T if we are considering using the index scan as the inside
233234
*of a nestloop join (hence, some of the indexQuals are join clauses)
234235
*
236+
* cost_index() takes an IndexPath not just a Path, because it sets a few
237+
* additional fields of the IndexPath besides startup_cost and total_cost.
238+
* These fields are needed if the IndexPath is used in a BitmapIndexScan.
239+
*
235240
* NOTE: 'indexQuals' must contain only clauses usable as index restrictions.
236241
* Any additional quals evaluated as qpquals may reduce the number of returned
237242
* tuples, but they won't reduce the number of tuples we have to fetch from
@@ -241,7 +246,7 @@ cost_nonsequential_access(double relpages)
241246
* it was a list of bare clause expressions.
242247
*/
243248
void
244-
cost_index(Path*path,Query*root,
249+
cost_index(IndexPath*path,Query*root,
245250
IndexOptInfo*index,
246251
List*indexQuals,
247252
boolis_injoin)
@@ -286,6 +291,14 @@ cost_index(Path *path, Query *root,
286291
PointerGetDatum(&indexSelectivity),
287292
PointerGetDatum(&indexCorrelation));
288293

294+
/*
295+
* Save amcostestimate's results for possible use by cost_bitmap_scan.
296+
* We don't bother to save indexStartupCost or indexCorrelation, because
297+
* a bitmap scan doesn't care about either.
298+
*/
299+
path->indextotalcost=indexTotalCost;
300+
path->indexselectivity=indexSelectivity;
301+
289302
/* all costs for touching index itself included here */
290303
startup_cost+=indexStartupCost;
291304
run_cost+=indexTotalCost-indexStartupCost;
@@ -396,8 +409,8 @@ cost_index(Path *path, Query *root,
396409

397410
run_cost+=cpu_per_tuple*tuples_fetched;
398411

399-
path->startup_cost=startup_cost;
400-
path->total_cost=startup_cost+run_cost;
412+
path->path.startup_cost=startup_cost;
413+
path->path.total_cost=startup_cost+run_cost;
401414
}
402415

403416
/*
@@ -417,19 +430,151 @@ cost_bitmap_scan(Path *path, Query *root, RelOptInfo *baserel,
417430
{
418431
Coststartup_cost=0;
419432
Costrun_cost=0;
433+
CostindexTotalCost;
434+
SelectivityindexSelectivity;
435+
Costcpu_per_tuple;
436+
Costcost_per_page;
437+
doubletuples_fetched;
438+
doublepages_fetched;
439+
doubleT;
420440

421441
/* Should only be applied to base relations */
422442
Assert(IsA(baserel,RelOptInfo));
423443
Assert(baserel->relid>0);
424444
Assert(baserel->rtekind==RTE_RELATION);
425445

426-
/* XXX lots to do here */
427-
run_cost+=10;
446+
if (!enable_indexscan)/* XXX use a separate enable flag? */
447+
startup_cost+=disable_cost;
448+
449+
/*
450+
* Estimate total cost of obtaining the bitmap, as well as its total
451+
* selectivity.
452+
*/
453+
indexTotalCost=0;
454+
indexSelectivity=cost_bitmap_qual(bitmapqual,&indexTotalCost);
455+
456+
startup_cost+=indexTotalCost;
457+
458+
/*
459+
* The number of heap pages that need to be fetched is the same as the
460+
* Mackert and Lohman formula for the case T <= b (ie, no re-reads
461+
* needed).
462+
*/
463+
tuples_fetched=clamp_row_est(indexSelectivity*baserel->tuples);
464+
465+
T= (baserel->pages>1) ? (double)baserel->pages :1.0;
466+
pages_fetched= (2.0*T*tuples_fetched) / (2.0*T+tuples_fetched);
467+
if (pages_fetched>T)
468+
pages_fetched=T;
469+
470+
/*
471+
* For small numbers of pages we should charge random_page_cost apiece,
472+
* while if nearly all the table's pages are being read, it's more
473+
* appropriate to charge 1.0 apiece. The effect is nonlinear, too.
474+
* For lack of a better idea, interpolate like this to determine the
475+
* cost per page.
476+
*/
477+
cost_per_page=random_page_cost-
478+
(random_page_cost-1.0)*sqrt(pages_fetched /T);
479+
480+
run_cost+=pages_fetched*cost_per_page;
481+
482+
/*
483+
* Estimate CPU costs per tuple.
484+
*
485+
* Often the indexquals don't need to be rechecked at each tuple ...
486+
* but not always, especially not if there are enough tuples involved
487+
* that the bitmaps become lossy. For the moment, just assume they
488+
* will be rechecked always.
489+
*/
490+
startup_cost+=baserel->baserestrictcost.startup;
491+
cpu_per_tuple=cpu_tuple_cost+baserel->baserestrictcost.per_tuple;
492+
493+
run_cost+=cpu_per_tuple*tuples_fetched;
428494

429495
path->startup_cost=startup_cost;
430496
path->total_cost=startup_cost+run_cost;
431497
}
432498

499+
/*
500+
* cost_bitmap_qual
501+
*Recursively examine the AND/OR/IndexPath tree for a bitmap scan
502+
*
503+
* Total execution costs are added to *totalCost (so caller must be sure
504+
* to initialize that to zero). Estimated total selectivity of the bitmap
505+
* is returned as the function result.
506+
*/
507+
staticSelectivity
508+
cost_bitmap_qual(Node*bitmapqual,Cost*totalCost)
509+
{
510+
Selectivityresult;
511+
Selectivitysubresult;
512+
ListCell*l;
513+
514+
if (and_clause(bitmapqual))
515+
{
516+
/*
517+
* We estimate AND selectivity on the assumption that the inputs
518+
* are independent. This is probably often wrong, but we don't
519+
* have the info to do better.
520+
*
521+
* The runtime cost of the BitmapAnd itself is estimated at 100x
522+
* cpu_operator_cost for each tbm_intersect needed. Probably too
523+
* small, definitely too simplistic?
524+
*
525+
* This must agree with make_bitmap_and in createplan.c.
526+
*/
527+
result=1.0;
528+
foreach(l, ((BoolExpr*)bitmapqual)->args)
529+
{
530+
subresult=cost_bitmap_qual((Node*)lfirst(l),totalCost);
531+
result *=subresult;
532+
if (l!=list_head(((BoolExpr*)bitmapqual)->args))
533+
*totalCost+=100.0*cpu_operator_cost;
534+
}
535+
}
536+
elseif (or_clause(bitmapqual))
537+
{
538+
/*
539+
* We estimate OR selectivity on the assumption that the inputs
540+
* are non-overlapping, since that's often the case in "x IN (list)"
541+
* type situations. Of course, we clamp to 1.0 at the end.
542+
*
543+
* The runtime cost of the BitmapOr itself is estimated at 100x
544+
* cpu_operator_cost for each tbm_union needed. Probably too
545+
* small, definitely too simplistic? We are aware that the tbm_unions
546+
* are optimized out when the inputs are BitmapIndexScans.
547+
*
548+
* This must agree with make_bitmap_or in createplan.c.
549+
*/
550+
result=0.0;
551+
foreach(l, ((BoolExpr*)bitmapqual)->args)
552+
{
553+
subresult=cost_bitmap_qual((Node*)lfirst(l),totalCost);
554+
result+=subresult;
555+
if (l!=list_head(((BoolExpr*)bitmapqual)->args)&&
556+
!IsA((Node*)lfirst(l),IndexPath))
557+
*totalCost+=100.0*cpu_operator_cost;
558+
}
559+
result=Min(result,1.0);
560+
}
561+
elseif (IsA(bitmapqual,IndexPath))
562+
{
563+
IndexPath*ipath= (IndexPath*)bitmapqual;
564+
565+
/* this must agree with create_bitmap_subplan in createplan.c */
566+
*totalCost+=ipath->indextotalcost;
567+
result=ipath->indexselectivity;
568+
}
569+
else
570+
{
571+
elog(ERROR,"unrecognized node type: %d",nodeTag(bitmapqual));
572+
result=0.0;/* keep compiler quiet */
573+
}
574+
575+
returnresult;
576+
}
577+
433578
/*
434579
* cost_tidscan
435580
* Determines and returns the cost of scanning a relation using TIDs.

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

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
*
1010
*
1111
* IDENTIFICATION
12-
* $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.174 2005/04/20 21:48:04 tgl Exp $
12+
* $PostgreSQL: pgsql/src/backend/optimizer/path/indxpath.c,v 1.175 2005/04/21 02:28:01 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -1710,7 +1710,7 @@ make_innerjoin_index_path(Query *root,
17101710
/* Like costsize.c, force estimate to be at least one row */
17111711
pathnode->rows=clamp_row_est(pathnode->rows);
17121712

1713-
cost_index(&pathnode->path,root,index,indexquals, true);
1713+
cost_index(pathnode,root,index,indexquals, true);
17141714

17151715
return (Path*)pathnode;
17161716
}

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

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/optimizer/path/orindxpath.c,v 1.67 2005/03/27 06:29:36 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/optimizer/path/orindxpath.c,v 1.68 2005/04/21 02:28:01 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -353,7 +353,7 @@ best_or_subclause_index(Query *root,
353353
IndexOptInfo*index= (IndexOptInfo*)lfirst(ilist);
354354
List*indexclauses;
355355
List*indexquals;
356-
Pathsubclause_path;
356+
IndexPathsubclause_path;
357357

358358
/*
359359
* Ignore partial indexes that do not match the query. If predOK
@@ -402,13 +402,13 @@ best_or_subclause_index(Query *root,
402402

403403
cost_index(&subclause_path,root,index,indexquals, false);
404404

405-
if (!found||subclause_path.total_cost<*retTotalCost)
405+
if (!found||subclause_path.path.total_cost<*retTotalCost)
406406
{
407407
*retIndexInfo=index;
408408
*retIndexClauses=flatten_clausegroups_list(indexclauses);
409409
*retIndexQuals=indexquals;
410-
*retStartupCost=subclause_path.startup_cost;
411-
*retTotalCost=subclause_path.total_cost;
410+
*retStartupCost=subclause_path.path.startup_cost;
411+
*retTotalCost=subclause_path.path.total_cost;
412412
found= true;
413413
}
414414
}

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

Lines changed: 16 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,7 @@
1010
*
1111
*
1212
* IDENTIFICATION
13-
* $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.180 2005/04/19 22:35:16 tgl Exp $
13+
* $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.181 2005/04/21 02:28:01 tgl Exp $
1414
*
1515
*-------------------------------------------------------------------------
1616
*/
@@ -976,10 +976,12 @@ create_bitmap_subplan(Query *root, Node *bitmapqual)
976976
linitial(iscan->indxqualorig),
977977
linitial(iscan->indxstrategy),
978978
linitial(iscan->indxsubtype));
979-
/* XXX this cost is wrong: */
980-
copy_path_costsize(&bscan->scan.plan,&ipath->path);
981-
/* use the indexscan-specific rows estimate, not the parent rel's */
982-
bscan->scan.plan.plan_rows=ipath->rows;
979+
/* this must agree with cost_bitmap_qual in costsize.c */
980+
bscan->scan.plan.startup_cost=0.0;
981+
bscan->scan.plan.total_cost=ipath->indextotalcost;
982+
bscan->scan.plan.plan_rows=
983+
clamp_row_est(ipath->indexselectivity*ipath->path.parent->tuples);
984+
bscan->scan.plan.plan_width=0;/* meaningless */
983985
plan= (Plan*)bscan;
984986
}
985987
else
@@ -2068,8 +2070,9 @@ make_bitmap_and(List *bitmapplans)
20682070
ListCell*subnode;
20692071

20702072
/*
2071-
* Compute cost as sum of subplan costs, plus10x cpu_operator_cost
2073+
* Compute cost as sum of subplan costs, plus100x cpu_operator_cost
20722074
* (a pretty arbitrary amount, agreed) for each tbm_intersect needed.
2075+
* This must agree with cost_bitmap_qual in costsize.c.
20732076
*/
20742077
plan->startup_cost=0;
20752078
plan->total_cost=0;
@@ -2085,7 +2088,10 @@ make_bitmap_and(List *bitmapplans)
20852088
plan->plan_rows=subplan->plan_rows;
20862089
}
20872090
else
2091+
{
2092+
plan->total_cost+=cpu_operator_cost*100.0;
20882093
plan->plan_rows=Min(plan->plan_rows,subplan->plan_rows);
2094+
}
20892095
plan->total_cost+=subplan->total_cost;
20902096
}
20912097

@@ -2106,10 +2112,12 @@ make_bitmap_or(List *bitmapplans)
21062112
ListCell*subnode;
21072113

21082114
/*
2109-
* Compute cost as sum of subplan costs, plus10x cpu_operator_cost
2115+
* Compute cost as sum of subplan costs, plus100x cpu_operator_cost
21102116
* (a pretty arbitrary amount, agreed) for each tbm_union needed.
21112117
* We assume that tbm_union can be optimized away for BitmapIndexScan
21122118
* subplans.
2119+
*
2120+
* This must agree with cost_bitmap_qual in costsize.c.
21132121
*/
21142122
plan->startup_cost=0;
21152123
plan->total_cost=0;
@@ -2122,7 +2130,7 @@ make_bitmap_or(List *bitmapplans)
21222130
if (subnode==list_head(bitmapplans))/* first node? */
21232131
plan->startup_cost=subplan->startup_cost;
21242132
elseif (!IsA(subplan,BitmapIndexScan))
2125-
plan->total_cost+=cpu_operator_cost*10;
2133+
plan->total_cost+=cpu_operator_cost*100.0;
21262134
plan->total_cost+=subplan->total_cost;
21272135
plan->plan_rows+=subplan->plan_rows;/* ignore overlap */
21282136
}

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

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $PostgreSQL: pgsql/src/backend/optimizer/util/pathnode.c,v 1.116 2005/04/19 22:35:17 tgl Exp $
11+
* $PostgreSQL: pgsql/src/backend/optimizer/util/pathnode.c,v 1.117 2005/04/21 02:28:01 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -466,7 +466,7 @@ create_index_path(Query *root,
466466
*/
467467
pathnode->rows=index->rel->rows;
468468

469-
cost_index(&pathnode->path,root,index,indexquals, false);
469+
cost_index(pathnode,root,index,indexquals, false);
470470

471471
returnpathnode;
472472
}

0 commit comments

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