SQL引擎執(zhí)行查詢主要經(jīng)歷了詞法語法解析、查詢重寫、查詢規(guī)劃和計劃執(zhí)行等步驟。其中，在查詢規(guī)劃過程中，為了生成可執(zhí)行的最優(yōu)計劃，首先要生成路徑，而由于路徑存在多樣性，因此需要對路徑進行淘汰選擇。目前優(yōu)化器進行路徑的選擇主要是基于估算的代價，因此這種優(yōu)化器也被稱為基于代價的優(yōu)化器（Cost Based Optimization，?CBO）。相對于邏輯優(yōu)化，這種優(yōu)化方法是物理優(yōu)化：根據(jù)數(shù)據(jù)的分布（統(tǒng)計信息）情況來對查詢執(zhí)行路徑進行評估，從可選的路徑中選擇一個執(zhí)行代價最小的路徑進行執(zhí)行，例如是否選擇索引SeqScan vs. IndexScan，選擇哪個索引，兩表關聯(lián)選擇什么樣的連接順序，選擇怎樣的具體算法等。

在代價估算時，需要使用基表或連接表的行數(shù)，而在很多時候，優(yōu)化器無法獲得準確的行數(shù)值，因此需要對行數(shù)進行估算（Cardinality Estimation），然后再計算代價。

統(tǒng)計信息

統(tǒng)計信息是物理優(yōu)化的依據(jù)，來源于表信息的統(tǒng)計。其中描述基表數(shù)據(jù)的特征包括唯一值、MCV（Most Common Value）值等，用于行數(shù)估算。

Table-Level表級別統(tǒng)計信息，存儲在系統(tǒng)表pg_class

relptuples總元組數(shù)：描述表對應的元組數(shù)

relpages總頁面數(shù)：描述表對應的磁盤頁數(shù)。

Column-Level列級別統(tǒng)計信息，存儲在系統(tǒng)表pg_statistics，也可以使用視圖pg_stats查看數(shù)據(jù)

Starelid：表的oid

Staattnum：表屬性編號

stadistinct：用于描述字段里唯一的非 NULL 數(shù)據(jù)值的數(shù)目，一般用于估算集合分組之后的大小，Join結果集大小。

stanullfrac：用于描述當前列中NULL值在總數(shù)中的占比。

屬性組{stakind1, stanumbers1, stavalues1}構成PG_STATISTIC表的一個卡槽，在PG_STATISTIC表中有5個卡槽。一般情況下，第一個卡槽存儲MCV（Most Common Value）信息：描述出現(xiàn)頻率大于一定百分比的值的集合，按照出現(xiàn)的頻率進行排序，通常用于表征哪些值上出現(xiàn)了傾斜。第二個卡槽存儲Histogram直方圖信息,描述除了NULL值、MCV值以外的值的分布情況，一般用于估算選擇率。

以MCV卡槽為例屬性“stakind1”標識卡槽類型為MCV，其中“1”為“STATISTIC_KIND_MCV”的枚舉值；屬性stanumbers1與屬性stavalues1記錄MCV的具體內容，其中stavalues1記錄key值，stanumbers1記錄key對應的頻次。

系統(tǒng)表pg_statistics的定義在文件pg_statistic.h中。

統(tǒng)計信息通過analyze命令獲得。

表tt的oid為40960，有10000行數(shù)據(jù)占用345個pages頁。第1列unique1的分布情況可以從直方圖信息獲取，直方圖有100個區(qū)間，并且沒有空值和MCV。第16列string4的分布情況可以通過MCV信息獲取，這一列有4個distinct值”AAAAxx” ,”HHHHxx” , “OOOOxx” , “VVVVxx” ，4個值的分布頻次都有0.25。

行數(shù)估計

行數(shù)估算是代價估算的基礎，來源于基表統(tǒng)計信息的推算，估算基表baserel、Join中間結果集joinrel、Aggregation中結果集大小，為代價估算做準備。

SQL查詢常常帶有where約束（過濾條件），比如SELECT * FROM tt WHERE string4 = 'AAAAxx'。知道了約束條件的選擇率，也就是知道了通過掃描路徑要掃描出來的結果所占的比例或者通過連接操作所獲得的元組所占的比例，通過這個比例就可以推算出中間結果和最終結果的數(shù)量，進而使用這些數(shù)量來計算代價。

這里重點分析基表的簡單查詢——基于OpExpr類型的選擇率計算，處理函數(shù)在clause_selectivity。如果是過濾條件就調用restriction_selectivity函數(shù)來獲得OpExpr表達式的選擇率，如果是連接條件則調用join_selectivity函數(shù)來獲得選擇率。

SELECT * FROM tt WHERE string4 = 'AAAAxx'為過濾條件，調用restriction_selectivity進行選擇率估算。

restriction_selectivity函數(shù)識別出string4 = 'AAAAxx'是形如Var = Const的等值約束，操作符的約束選擇性計算函數(shù)存儲在系統(tǒng)表PG_OPERATOR，opno = 93對應的選擇率計算函數(shù)為eqsel，通過eqsel函數(shù)調用var_eq_const函數(shù)進行選擇率估算。在該過程中，var_eq_const函數(shù)會讀取PG_STATISTIC表中string4列分布信息，并利用MCV信息直接返回選擇率為0.25。

函數(shù)set_baserel_size_estimates計算估計行數(shù)。

函數(shù)調用關系：standard_planner-> subquery_planner-> grouping_planner-> query_planner-> make_one_rel-> set_base_rel_sizes-> set_rel_size-> set_plain_rel_size-> set_baserel_size_estimates-> clauselist_selectivity-> clause_selectivity-> restriction_selectivity-> OidFunctionCall4Coll-> eqsel->var_eq_const