postgresQL索引扫描成本学习

postgresQL索引扫描成本学习

内幕探索第三章 索引扫描成本学习笔记

Although PostgreSQL supports some index methods, such as BTree, GiST, GIN and BRIN, the cost of the index scan is estimated using the common cost function: cost_index().

In this subsection, we explore how to estimate the index scan cost of the following query:

testdb=# SELECT id, data FROM tbl WHERE data < 240;

Before estimating the cost, the numbers of the index pages and index tuples, Nindex,pageNindex,page and Nindex,tupleNindex,tuple, are shown below:

testdb=# SELECT relpages, reltuples FROM pg_class WHERE relname = 'tbl_data_idx';relpages | reltuples 
----------+-----------30 |     10000
(1 row)

N i n d e x , t u p l e = 10000 , N i n d e x , p a g e = 30 N_{index,tuple}=10000 , N_{index,page}=30 Nindex,tuple​=10000,Nindex,page​=30

Start-Up Cost 启动成本

The start-up cost of the index scan is the cost to read the index pages to access to the first tuple in the target table, and it is defined by the following equation:

索引扫描的启动成本是通过读索引页来获取到目标表第一条tuple所花费的成本。
{ c e i l ( l o g 2 ( N i n d e x , t u p l e ) ) + ( H i n d e x + 1 ) × 50 } × c p u _ o p e r a t o r _ c o s t {{ceil(log_{2}(N_{index,tuple}))+(H_{index}+1)×50}}×{cpu_operator_cost} {ceil(log2​(Nindex,tuple​))+(Hindex​+1)×50}×cpu_operator_cost

where Hindex is the height of the index tree.

In this case, Nindex,tuple is 10000; Hindex is 1(bt_); cpu_operator_costcpu_operator_cost is 0.0025 (by default).

Thus,‘start-up cost’={ceil(log2(10000))+(1+1)×50}×0.0025=0.285.

这里Hindex 索引高度可以通过bt_metap计算.

taria=# select * from  bt_metap('idx_t1_id');magic  | version | root | level | fastroot | fastlevel | oldest_xact | last_cleanup_num_tuples | allequalimage 
--------+---------+------+-------+----------+-----------+-------------+-------------------------+---------------340322 |       4 |    1 |     0 |        1 |         0 |           0 |                      -1 | t
(1 row)

Run Cost 运行成本

The run cost of the index scan is the sum of the cpu costs and the IO (input/output) costs of both the table and the index:

运行成本是表和索引在cpu和io花费上的消耗总和。
( i n d e x c p u c o s t + t a b l e c p u c o s t ) + ( i n d e x I O c o s t + t a b l e I O c o s t ) (index cpu cost+table cpu cost)+(index IO cost+ table IO cost) (index cpu cost+table cpu cost)+(index IO cost+table IO cost)
If the Index-Only Scans, ‘table cpu cost’‘table cpu cost’ and ‘table IO cost’‘table IO cost’ are not estimated.

The first three costs (i.e. index cpu cost, table cpu cost and index IO cost) are shown in below:

index cpu cost = Selectivity × Nindex,tuple × (cpu_index_tuple_cost + qual_op_cost)table cpu cost = Selectivity × Ntuple × cpu_tuple_costindex IO cost = ceil(Selectivity × Nindex,page) × random_page_cost

    /** CPU cost: any complex expressions in the indexquals will need to be* evaluated once at the start of the scan to reduce them to runtime keys* to pass to the index AM (see nodeIndexscan.c).  We model the per-tuple* CPU costs as cpu_index_tuple_cost plus one cpu_operator_cost per* indexqual operator.  Because we have numIndexTuples as a per-scan* number, we have to multiply by num_sa_scans to get the correct result* for ScalarArrayOpExpr cases.  Similarly add in costs for any index* ORDER BY expressions.** Note: this neglects the possible costs of rechecking lossy operators.* Detecting that that might be needed seems more expensive than it's* worth, though, considering all the other inaccuracies here ...*/qual_op_cost = cpu_operator_cost * (list_length(indexQuals) + list_length(indexOrderBys));
indexTotalCost += numIndexTuples * num_sa_scans * (cpu_index_tuple_cost + qual_op_cost);

书上说qual_op_cost粗略的讲是索引求值的代价（the evaluation cost of index），默认值0.0025，这里取自源码计算方式。

Selectivity

testdb=# d countriesTable &#untries"Column   | Type | Modifiers 
-----------+------+-----------country   | text | continent | text | 
Indexes:"continent_idx" btree (continent)testdb=# SELECT continent, count(*) AS "number of countries", 
testdb-#     (count(*)/(SELECT count(*) FROM countries)::real) AS "number of countries / all countries"
testdb-#       FROM countries GROUP BY continent ORDER BY "number of countries" DESC;continent   | number of countries | number of countries / all countries 
---------------+---------------------+-------------------------------------Africa        |                  53 |                   0.274611398963731Europe        |                  47 |                   0.243523316062176Asia          |                  44 |                   0.227979274611399North America |                  23 |                   0.119170984455959Oceania       |                  14 |                  0.0725388601036269South America |                  12 |                  0.0621761658031088
(6 rows)

Let us consider the following query which has a WHERE clause, ‘continent = ‘Asia’’:

testdb=# SELECT * FROM countries WHERE continent = 'Asia';

In this case, the planner estimates the index scan cost using the MCV of the ‘continent’ column. The most_common_vals and most_common_freqs of this column are shown below:

testdb=# x
Expanded display is on.
testdb=# SELECT most_common_vals, most_common_freqs FROM pg_stats 
testdb-#                  WHERE tablename = 'countries' AND attname='continent';
-[ RECORD 1 ]-----+-------------------------------------------------------------
most_common_vals  | {Africa,Europe,Asia,"North America",Oceania,"South America"}
most_common_freqs | {0.274611,0.243523,0.227979,0.119171,0.0725389,0.0621762}

If the MCV cannot be used, the value of the histogram_bounds of the target column is used to estimate the cost.

• histogram_bounds is a list of values that divide the column’s values into groups of approximately equal population.

默认情况，直方图会把列上的值划分为100个buckets，每个buckets存几乎等数量的tuple。

By default, the histogram_bounds is divided into 100 buckets. Figure 3.7 illustrates the buckets and the corresponding histogram_bounds in this example. Buckets are numbered starting from 0, and every bucket stores (approximately) the same number of tuples. The values of histogram_bounds are the bounds of the corresponding buckets. For example, the 0th value of histogram_bounds is 1, which means that it is the minimum value of the tuples stored in bucket_0; the 1st value is 100 and this is the minimum value of the tuples stored in bucket_1, and so on.

关于直方图选择率的计算，官网的例子：

SELECT histogram_bounds FROM pg_stats
WHERE tablename='tenk1' AND attname='unique1';histogram_bounds
------------------------------------------------------{0,993,1997,3050,4040,5036,5957,7057,8029,9016,9995}

Next the fraction of the histogram occupied by “< 1000” is worked out. This is the selectivity. The histogram divides the range into equal frequency buckets, so all we have to do is locate the bucket that our value is in and count part of it and all of the ones before. The value 1000 is clearly in the second bucket (993-1997). Assuming a linear distribution of values inside each bucket, we can calculate the selectivity as:

selectivity = (1 + (1000 - bucket[2].min)/(bucket[2].max - bucket[2].min))/num_buckets= (1 + (1000 - 993)/(1997 - 993))/10= 0.100697

书上的例子：

testdb=# SELECT histogram_bounds FROM pg_stats WHERE tablename = 'tbl' AND attname = 'data';histogram_bounds
---------------------------------------------------------------------------------------------------{1,100,200,300,400,500,600,700,800,900,1000,1100,1200,1300,1400,1500,1600,1700,1800,1900,2000,2100,
2200,2300,2400,2500,2600,2700,2800,2900,3000,3100,3200,3300,3400,3500,3600,3700,3800,3900,4000,4100,
4200,4300,4400,4500,4600,4700,4800,4900,5000,5100,5200,5300,5400,5500,5600,5700,5800,5900,6000,6100,
6200,6300,6400,6500,6600,6700,6800,6900,7000,7100,7200,7300,7400,7500,7600,7700,7800,7900,8000,8100,
8200,8300,8400,8500,8600,8700,8800,8900,9000,9100,9200,9300,9400,9500,9600,9700,9800,9900,10000}
(1 row)

By default, the histogram_bounds is divided into 100 buckets. Figure 3.7 illustrates the buckets and the corresponding histogram_bounds in this example. Buckets are numbered starting from 0, and every bucket stores (approximately) the same number of tuples. The values of histogram_bounds are the bounds of the corresponding buckets. For example, the 0th value of histogram_bounds is 1, which means that it is the minimum value of the tuples stored in bucket_0; the 1st value is 100 and this is the minimum value of the tuples stored in bucket_1, and so on.

Fig. 3.7. Buckets and histogram_bounds.

Next, the calculation of the selectivity using the example in this subsection will be shown. The query has a WHERE clause ‘data < 240’ and the value ‘240’ is in the second bucket. In this case, the selectivity can be derived by applying linear interpolation; thus, the selectivity of the column ‘data’ in this query is calculated using the following equation:
S e l e c t i v i t y = 2 + ( 240 − h b [ 2 ] ) / ( h b [ 3 ] − h b [ 2 ] ) 100 = 2 + ( 240 − 200 ) / ( 300 − 200 ) 100 = 2 + 40 / 100 100 = 0.024 Selectivity = frac{2+(240−hb[2])/(hb[3]−hb[2])}{100} = frac{2 + (240−200)/(300−200)}{100}=frac{2+40/100}{100}=0.024 Selectivity=1002+(240−hb[2])/(hb[3]−hb[2])​=1002+(240−200)/(300−200)​=1002+40/100​=0.024

‘table IO cost’ is defined by the following equation:
t a b l e I O c o s t = m a x _ I O _ c o s t + i n d e x C o r r e l a t i o n 2 × ( m i n _ I O _ c o s t − m a x _ I O _ c o s t ) . table IO cost = max_IO_cost+indexCorrelation^2×(min_IO_cost−max_IO_cost). table IO cost=max_IO_cost+indexCorrelation2×(min_IO_cost−max_IO_cost).
max_IO_costmax_IO_cost is the worst case of the IO cost, that is, the cost of randomly scanning all table pages; this cost is defined by the following equation:
m a x _ I O _ c o s t = N p a g e × r a n d o m _ p a g e _ c o s t . max_IO_cost=Npage×random_page_cost. max_IO_cost=Npage×random_page_cost.
min_IO_costmin_IO_cost is the best case of the IO cost, that is, the cost of sequentially scanning the selected table pages; this cost is defined by the following equation:
m i n _ I O _ c o s t = 1 × r a n d o m _ p a g e _ c o s t + ( c e i l ( S e l e c t i v i t y × N p a g e ) − 1 ) × s e q _ p a g e _ c o s t min_IO_cost=1×random_page_cost+(ceil(Selectivity×Npage)−1)×seq_page_cost min_IO_cost=1×random_page_cost+(ceil(Selectivity×Npage)−1)×seq_page_cost

Index Correlation

Index correlation is a statistical correlation between physical row ordering and logical ordering of the column values (cited from the official document). This ranges from −1−1 to +1+1.

索引相关性是列值在物理和逻辑上的顺序相关性。如下：

testdb=# d tbl_corrTable "public.tbl_corr"Column  |  Type   | Modifiers 
----------+---------+-----------col      | text    | col_asc  | integer | col_desc | integer | col_rand | integer | data     | text    |
Indexes:"tbl_corr_asc_idx" btree (col_asc)"tbl_corr_desc_idx" btree (col_desc)"tbl_corr_rand_idx" btree (col_rand)testdb=# SELECT col,col_asc,col_desc,col_rand 
testdb-#                         FROM tbl_corr;col    | col_asc | col_desc | col_rand 
----------+---------+----------+----------Tuple_1  |       1 |       12 |        3Tuple_2  |       2 |       11 |        8Tuple_3  |       3 |       10 |        5Tuple_4  |       4 |        9 |        9Tuple_5  |       5 |        8 |        7Tuple_6  |       6 |        7 |        2Tuple_7  |       7 |        6 |       10Tuple_8  |       8 |        5 |       11Tuple_9  |       9 |        4 |        4Tuple_10 |      10 |        3 |        1Tuple_11 |      11 |        2 |       12Tuple_12 |      12 |        1 |        6
(12 rows)testdb=# SELECT tablename,attname, correlation FROM pg_stats WHERE tablename = 'tbl_corr';tablename | attname  | correlation 
-----------+----------+-------------tbl_corr  | col_asc  |           1tbl_corr  | col_desc |          -1tbl_corr  | col_rand |    0.125874
(3 rows)

testdb=# SELECT * FROM tbl_corr WHERE col_asc BETWEEN 2 AND 4;
testdb=# SELECT * FROM tbl_corr WHERE col_rand BETWEEN 2 AND 4;

This way, the index correlation is a statistical correlation that reflects the influence of random access caused by the twist between the index ordering and the physical tuple ordering in the table in estimating the index scan cost.

索引相关性体现了索引顺序和物理元祖顺序的扭曲程度对随机访问性能的影响。

Reference

.html
.php/news/viewone/1/717
.2/row-estimation-examples.html