內(nèi)容來源：《PostgreSQL技術(shù)內(nèi)幕：查詢優(yōu)化深度探索》，電子工業(yè)出版社，作者：張樹杰毡熏。

優(yōu)化器進行物理優(yōu)化需要計算各種物理路徑的代價，而代價估算嚴重依賴統(tǒng)計信息侣诵。統(tǒng)計信息是否能準確地描述表中的數(shù)據(jù)分布情況是決定代價的準確性的重要條件之一痢法。

通過統(tǒng)計信息，代價估算時就可以了解一個表有多少行數(shù)據(jù)窝趣、用了多少個數(shù)據(jù)頁面疯暑、某個值出現(xiàn)的頻率等，然后根據(jù)這些信息計算出一個約束條件能夠過濾掉多少數(shù)據(jù)哑舒，這種約束條件過濾出的數(shù)據(jù)占總數(shù)據(jù)量的比例成為“選擇率”妇拯。

選擇率 = 約束條件過濾后的元組數(shù)/約束條件過濾前的總元組數(shù)。

統(tǒng)計信息

PostgreSQL支持多種形式的統(tǒng)計信息洗鸵，包括單列的統(tǒng)計信息和多列（擴展）的統(tǒng)計信息越锈，單列的統(tǒng)計信息是指對每個表的每一個屬性（列）都在PG_STATISTIC系統(tǒng)表中產(chǎn)生一個對應(yīng)的統(tǒng)計信息元組，這個元組負責從多個角度描繪這個屬性中的數(shù)據(jù)分布膘滨。

STATISTIC_KIND_MCV壳猜、STATISTIC_KIND_HISTOGRAM勾徽、STATISTIC_KIND_CORRELATION是統(tǒng)計模塊常用的三種統(tǒng)計方式。

使用基于單列的統(tǒng)計信息來對基于單個列的約束條件（例如a=1）進行選擇率的估計统扳，誤差范圍是可控的喘帚，但是對于引用了多個列的約束條件（例如a=1 or b=2 and c=3），如果還使用單列的統(tǒng)計信息進行估算咒钟，就需要將這個約束條件拆分成多個獨立的子約束條件吹由，對每個字約束條件信息選擇率估算，并且假設(shè)這些子約束條件的選擇率是獨立的朱嘴，然后基于概率的方法對總的選擇率進行估算倾鲫。由于實際應(yīng)用中并不能保證它們是獨立的，因此可能估算的誤差較大萍嬉，PostgreSQL對統(tǒng)計信息進行了擴展乌昔，支持多列的統(tǒng)計信息用來計算各個列之間的依賴度。

獲得了統(tǒng)計信息之后悼做，在代價估算的時候就可以利用這些統(tǒng)計信息進行計算疯特。

PG_STATISTIC系統(tǒng)表

PG_CLASS系統(tǒng)表會保存兩個統(tǒng)計信息：relpages和reltuples。relpages記錄了當前表用了多少個頁面贿堰，reltuples記錄了當前表共有多少條元組。PG_STATISTIC系統(tǒng)表保存單列的統(tǒng)計信息啡彬，如果用戶要給某個表生成統(tǒng)計信息羹与，則可以使用ANALYZE語句對一個表進行統(tǒng)計分析，這樣就能給這個表生成統(tǒng)計信息并且保存在PG_STATISTIC系統(tǒng)表中庶灿。

• starelid：對應(yīng)表的OID

• staattnum：對應(yīng)列的編號

• stanullfrac：NULL值的比例

• stawidth：該列的平均寬度

• stadistinct：該列去重之后的數(shù)據(jù)的個數(shù)或比例

  • =0纵搁，代表未知或者未計算的情況
  • >0，代表消除重復(fù)值之后的個數(shù)
  • <0往踢，其絕對值是去重之后的個數(shù)占總個數(shù)的比例

• stakind：統(tǒng)計信息的形式

  #define STATISTIC_KIND_MCV  1
  #define STATISTIC_KIND_HISTOGRAM  2
  #define STATISTIC_KIND_CORRELATION  3
  #define STATISTIC_KIND_MCELEM  4
  #define STATISTIC_KIND_DECHIST  5
  #define STATISTIC_KIND_RANGE_LENGTH_HISTOGRAM  6
  #define STATISTIC_KIND_BOUNDS_HISTOGRAM  7
  
  

• staop：統(tǒng)計過程中涉及的操作符

• stanumbers：存在統(tǒng)計信息的高頻值數(shù)組或者存放相關(guān)系數(shù)

• stavalues：統(tǒng)計值的數(shù)組

PG_STATISTIC_EXT系統(tǒng)表

PG_STATISTIC_EXT系統(tǒng)表保存的是多列的統(tǒng)計信息腾誉，用戶需要顯式地使用CREATE STATISTICS語句對一個表創(chuàng)建多列統(tǒng)計信息。

單列統(tǒng)計信息生成

統(tǒng)計信息的生成主要在analyze_rel函數(shù)->do_analyze_rel函數(shù)中趣效。統(tǒng)計信息的生成過程主要分成兩部分：數(shù)據(jù)采樣和數(shù)據(jù)統(tǒng)計。

采樣

兩階段采樣算法：第一個階段使用S算法對表中的頁面進行隨機采樣猪贪，第二個階段使用Z算法（Vitter）算法在第一階段采樣出來的頁面的基礎(chǔ)上對元組進行采樣跷敬。

實現(xiàn)代碼在acquire_sample_rows函數(shù)中。

統(tǒng)計方法

通過兩階段采樣獲得樣本之后热押，就要對這些樣本進行統(tǒng)計西傀，對表的列屬性分別進行統(tǒng)計，如果表上有索引桶癣，還會對索引進行單獨的統(tǒng)計拥褂。

目前PostgreSQL的統(tǒng)計方法有7種，但是PG_STATISTIC表中的槽只有5個牙寞。PostgreSQL根據(jù)列屬性的類型以及該類型可以使用的方法來決定采用的統(tǒng)計方法饺鹃。選擇統(tǒng)計方法的代碼在std_typanalyze函數(shù)中實現(xiàn)。

多列統(tǒng)計信息生成

如果用戶創(chuàng)建了多列統(tǒng)計信息項碎税，那么在對一個表做單列統(tǒng)計信息時尤慰，也會嘗試同時調(diào)用BuildRelationExtStatistics函數(shù)創(chuàng)建多列統(tǒng)計信息。

統(tǒng)計信息模塊會根據(jù)用戶指定的統(tǒng)計類型來生成統(tǒng)計信息雷蹂，如果用戶沒有指定具體的統(tǒng)計類型伟端，則統(tǒng)計模塊會默認對STATS_EXT_NDISTINCT類型和STATS_EXT_DEPENDENCIES類型都進行統(tǒng)計。

STATS_EXT_NDISTINCT

與單列統(tǒng)計信息中的stadistinct類似匪煌，記錄的是基于多列的去重之后的數(shù)據(jù)量责蝠。

STATS_EXT_DEPENDENCIES

函數(shù)依賴：兩個屬性之間滿足函數(shù)依賴的值占總體數(shù)量的比例，也可以擴展到多個屬性萎庭。

選擇率

選擇率的估算需要借助于統(tǒng)計信息（包括直方圖霜医、高頻值、NULL值率等）驳规。

例如肴敛，執(zhí)行SQL語句SELECT * FROM STUDENT WHERE sname='ww' AND (ssex IS NOT NULL OR sno>5)，其中sname='ww' AND (ssex IS NOT NULL OR sno>5)是由3個約束條件拼接起來的一個完整的約束條件吗购，對于這個約束會分別計算sname='ww'医男、(ssex IS NOT NULL)和(sno>5)三個子約束條件的選擇率，然后根據(jù)其中的AND運算符和OR運算符再計算總的選擇率捻勉。

其中sname='ww'的選擇率的計算過程如下：

• 獲得sname列對應(yīng)的stanullfrac=0.142857镀梭。
• 獲得高頻值數(shù)組[0.285714,0.285714]，計算高頻值的總比例=0.285714+0.285714=0.571428踱启。
• 因為sname='ww'既不是高頻值报账，也不是NULL值研底，所有的元組的總比例是1，因此可以先去除NULL值和高頻值透罢，計算其余的元組所占的比例=1-0.142857-0.571428=0.285714榜晦。
• 計算除了NULL值和高頻值，剩下還有幾個值：其中元組數(shù)量=7琐凭，stadistinct=-0.571429芽隆，可以獲得去除NULL值并去重之后，還剩7×0.571429=4個元組统屈，這4個元組中還有兩個高頻值胚吁，從4個元組中去除兩個高頻值，也就是說還有兩個值愁憔。
• 假設(shè)兩個值平均分配選擇率腕扶，可以獲得sname='ww'的選擇率是0.285714/2=0.142857。

其中(ssex IS NOT NULL)的選擇率的計算過程如下：

• 獲得ssex列對應(yīng)的stanullfrac=0.142857吨掌，這些對應(yīng)的是NULL值的選擇率半抱。
• 非NULL值的選擇率為1-stanullfrac=1-0.142857=0.857142。

其中(sno>5)的選擇率計算過程如下：

• 根據(jù)sno屬性的直方圖[1,2,3,4,5,6,7]計算sno<=5的選擇率膜宋，因為直方圖是左閉右開區(qū)間窿侈，即[1,2)，[2,3)...因此sno<5共占了4個桶秋茫，共有6個桶史简，所以選擇率是0.66666666，雖然sno=5則位于[5,6)這個桶內(nèi)肛著，但由于5是邊界值圆兵，所以這部分選擇率沒有被計算入內(nèi)。
• 根據(jù)sno<=5的選擇率計算sno>5的選擇率=1-0.66666666=0.33333333枢贿。

在計算了每個子約束條件獨立的選擇率之后殉农，就可以根據(jù)AND運算符和OR運算符計算它們的綜合的選擇率。AND和OR運算符的選擇率計算是基于概率的局荚，已知基于獨立事件的概率的加法和乘法的公式為：

P(A+B) = P(A) + P(B) - P(AB)
P(AB) = P(A) × P(B)

可以首先獲得約束條件(ssex IS NOT NULL OR sno>5)的選擇率為：

P(ssex IS NOT NULL OR sno>5)
= P(ssex IS NOT NULL) + P(sno>5) - P(ssex IS NOT NULL AND sno>5)
= P(ssex IS NOT NULL) + P(sno>5) - P(ssex IS NOT NULL) × P(sno>5)
= 0.857142 + 0.333333 - 0.857142 × 0.333333
= 0.90476

然后可以獲得sname='ww' AND (ssex IS NOT NULL OR sno>5)的總的選擇率為：

P(`sname='ww' AND (ssex IS NOT NULL OR sno>5))
= P(sname='ww') × P(ssex IS NOT NULL OR sno>5)
= 0.142857 × 0.90476
= 0.129252

統(tǒng)計信息并不能覆蓋計算選擇率計算的所有情況超凳，并不是所有的約束條件都能使用統(tǒng)計信息進行選擇率的計算。PostgreSQL設(shè)定了大量的選擇率的默認值耀态，部分選擇率的默認值如下表：

實際計算中，計算過程會比實例中更復(fù)雜桨醋。選擇率的計算函數(shù)為clauselist_selectivity棚瘟。

clauselist_selectivity主要考慮了三種情況：

• 使用函數(shù)依賴計算選擇率
• 子約束條件的選擇率
• 基于范圍的約束條件的選擇率修正

OpExpr的選擇率

OpExpr這種類型的約束條件是比較常用的約束條件，treat_as_join_clause函數(shù)對這種約束條件進行了分類喜最，分成了連接條件和過濾條件偎蘸。

• 如果varRelid有值，有可能是一個參數(shù)化路徑瞬内，這是認為OpExpr是過濾條件
• 如果sjinfo==NULL迷雪，可能是生成掃描路徑，這時認為OpExpr是過濾條件
• 其它情況：如果OpExpr中只引用了一個表虫蝶，按照過濾條件的方法來獲得選擇率章咧，如果OpEXpr中引用了多個表，則按照連接條件來獲取選擇率能真。

如果是過濾條件就調(diào)用restriction_selectivity函數(shù)來獲得OpExpr表達式的選擇率赁严，如果是連接條件則調(diào)用join_selectivity函數(shù)來獲得選擇率。

在PostgreSQL中粉铐，操作符保存在PG_OPERATOR系統(tǒng)表中疼约，PG_OPERATOR系統(tǒng)表有兩個屬性：

• oprrest：這個屬性指定一個函數(shù)，把OpExpr當作過濾條件蝙泼，求取它的選擇率程剥。
• oprjoin：這個屬性指定一個函數(shù)，把OpExpr當作連接條件踱承，求取它的選擇率倡缠。

代價

知道了約束條件的選擇率，也就是知道了通過掃描路徑要掃描出來的結(jié)果所占的比例或者通過連接操作所獲得的元組所占的比例茎活，通過這個比例就可以推算出中間結(jié)果和最終結(jié)果的數(shù)量昙沦，進而使用這些數(shù)量來計算代價。

代價基準單位

在實際應(yīng)用中载荔，數(shù)據(jù)庫用戶的硬件環(huán)境千差萬別盾饮，如CPU頻率、內(nèi)存的大小和磁盤的IO速率等因素都會影響執(zhí)行計劃的實際執(zhí)行效率懒熙，因此在代價估算的過程中丘损，我們無法獲得絕對真實的代價。

在代價估算的過程中工扎，我們只是想從多個路徑中找到一個代價最小的路徑徘钥，只要這些路徑的代價是可以相互比較的就可以了。因此肢娘，可以設(shè)定一個相對的代價作為單位1呈础，同一個查詢中所有的物理路徑都基于這個相對的單位來計算代價舆驶，這樣計算出來的代價就是可以比較的，也就能用來對路徑進行挑選了而钞。

基于頁面的IO基準代價

PostgreSQL采用順序讀寫一個頁面的IO代價作為單位1沙廉，用DEFAULT_SEQ_PAGE_COST來表示。

#define DEFAULT_SEQ_PAGE_COST  1.0
#define DEFAULT_RANDOM_PAGE_COST  4.0

順序IO和隨機IO是相對應(yīng)的臼节，基準代價相差4倍撬陵。造成這種差距主要的原因：

• 機械硬盤的尋道時間
• 磁盤本身的緩存

可以通過GUC參數(shù)自己配置這些值：

double seq_page_cost = DEFAULT_SEQ_PAGE_COST;
double random_page_cost = DEFAULT_RANDOM_PAGE_COST;

由于不同的數(shù)據(jù)文件可以存儲在不同的磁盤介質(zhì)上，PostgreSQL允許用戶在創(chuàng)建表空間的時候指定順序IO和隨機IO的基準代價网缝。

基于元組的CPU基準代價

讀取頁面并不是查詢的最終目標巨税，查詢的最終目標是將元組以要求的形式展示出來，因此就產(chǎn)生了從頁面讀取元組以及對元組處理的代價粉臊，這部分代價不同于讀取頁面的IO代價垢夹，這是頁面已經(jīng)在主存中了，從主存中的頁面獲取元組不會產(chǎn)生磁盤IO维费，它的代價主要產(chǎn)生在CPU的計算上果元。

PostgreSQL定義了DEFAULT_CPU_TUPLE_COST來表示處理元組的代價，使用DEFAULT_CPU_INDEX_TUPLE_COST來表示處理一條索引元組的代價犀盟。

#define DEFAULT_CPU_TUPLE_COST  0.01
#define DEFAULT_CPU_INDEX_TUPLE_COST 0.005

可以通過GUC參數(shù)調(diào)整這兩個基準代價：

double cpu_tuple_cost = DEFAULT_CPU_TUPLE_COST;
double cpu_index_tuple_cost = DEFAULT_CPU_INDEX_TUPLE_COST;

基于表達式的CPU基準代價

在執(zhí)行計劃的過程中而晒，不止處理元組需要消耗CPU資源，在投影阅畴、約束條件中包含大量的表達式倡怎，對這些表達式求值同樣需要消耗CPU資源，因此PostgreSQL把表達式的求值代價獨立出來贱枣。使用DEFAULT_CPU_OPERATOR_COST來作為計算表達式的基準代價监署。

#define DEFAULT_CPU_OPERATOR_COST  0.0025
double cpu_operator_cost = DEFAULT_CPU_OPERATOR_COST;

并行查詢產(chǎn)生的基準代價

Gather進程和Worker進程在并行查詢的過程中需要通信，因此需要考慮進程間通信所需的初始化代價纽哥，以及Worker進程向Gather進程投遞元組的代價钠乏。

#define DEFAULT_PARALLEL_TUPLE_COST 0.1
#define DEFAULT_PARALLEL_SETUP_COST  1000.0

double parallel_tuple_cost = DEFAULT_PARALLEL_TUPLE_COST;
double parallel_setup_cost = DEFAULT_PARALLEL_SETUP_COST;

緩存對代價的影響

數(shù)據(jù)庫本身有緩存系統(tǒng)，磁盤也有緩存春塌，當讀取一個緩存的數(shù)據(jù)頁面時是不會產(chǎn)生磁盤IO的晓避，因此如果對每個頁面都計算磁盤IO的代價，代價的計算結(jié)果就會失真只壳，所以我們還需要對緩存中的頁面數(shù)量有一個估計俏拱，目前PostgreSQL用effective_cache_size參數(shù)來表示。

#define DEFAULT_EFFECTIVE_CACHE_SIZE  524288 /* measured in pages */
int effective_cache_size = DEFAULT_EFFECTIVE_CACHE_SIZE;

啟動代價和整體代價

PostgreSQL將代價分成了兩個部分：啟動代價(Startup Cost)和執(zhí)行代價(Run cost)吼句，兩者的總和是整體代價(Total Cost)锅必。

Total Cost = Startup Cost + Run Cost

在Path結(jié)構(gòu)體中用startup_cost和total_cost兩個變量來表示啟動代價和整體代價，startup_cost是值從語句開始執(zhí)行到查詢引擎返回第一條元組的代價（準備好獲取第一條元組的代價）惕艳，total_cost是SQL語句從開始執(zhí)行到結(jié)束的所有代價搞隐。

表達式代價的計算

表達式的代價基準是cpu_operator_cost分蓖，不同的表達式需要輔以基準單位進行計算，表達式代價主要包括以下方面：

• 對投影列的表達式進行計算產(chǎn)生的代價
• 對約束條件中的表達式進行計算產(chǎn)生的代價
• 對函數(shù)參數(shù)中的表達式進行計算產(chǎn)生的代價
• 對聚集函數(shù)中的表達式進行計算產(chǎn)生的代價
• 子計劃等執(zhí)行計算產(chǎn)生的代價

表達式代價的計算是通過cost_qual_eval函數(shù)（針對表達式列表）或cost_qual_eval_node函數(shù)（針對單個表達式）來計算的尔许。cost_qual_eval函數(shù)和cost_qual_eval_node函數(shù)都調(diào)用了遞歸函數(shù)cost_qual_eval_walker。cost_qual_eval_node函數(shù)遞歸處理表達式并且將表達式的估算代價逐層累加到QualCost數(shù)據(jù)結(jié)構(gòu)中终娃。