SQL引擎執行查詢主要經曆了詞法文法解析、查詢重寫、查詢規劃和計劃執行等步驟。其中,在查詢規劃過程中,為了生成可執行的最優計劃,首先要生成路徑,而由于路徑存在多樣性,是以需要對路徑進行淘汰選擇。目前優化器進行路徑的選擇主要是基于估算的代價,是以這種優化器也被稱為基于代價的優化器(Cost Based Optimization,CBO)。相對于邏輯優化,這種優化方法是實體優化:根據資料的分布(統計資訊)情況來對查詢執行路徑進行評估,從可選的路徑中選擇一個執行代價最小的路徑進行執行,例如是否選擇索引SeqScan vs. IndexScan,選擇哪個索引,兩表關聯選擇什麼樣的連接配接順序,選擇怎樣的具體算法等。
在代價估算時,需要使用基表或連接配接表的行數,而在很多時候,優化器無法獲得準确的行數值,是以需要對行數進行估算(Cardinality Estimation),然後再計算代價。
統計資訊
統計資訊是實體優化的依據,來源于表資訊的統計。其中描述基表資料的特征包括唯一值、MCV(Most Common Value)值等,用于行數估算。
Table-Level表級别統計資訊,存儲在系統表pg_class
relptuples總元組數:描述表對應的元組數
relpages總頁面數:描述表對應的磁盤頁數。
Column-Level列級别統計資訊,存儲在系統表pg_statistics,也可以使用視圖pg_stats檢視資料
Starelid:表的oid
Staattnum:表屬性編号
stadistinct:用于描述字段裡唯一的非NULL 資料值的數目,一般用于估算集合分組之後的大小,Join結果集大小。
stanullfrac:用于描述目前列中NULL值在總數中的占比。
屬性組{stakind1, stanumbers1, stavalues1}構成PG_STATISTIC表的一個卡槽,在PG_STATISTIC表中有5個卡槽。一般情況下,第一個卡槽存儲MCV(Most Common Value)資訊:描述出現頻率大于一定百分比的值的集合,按照出現的頻率進行排序,通常用于表征哪些值上出現了傾斜。第二個卡槽存儲Histogram直方圖資訊,描述除了NULL值、MCV值以外的值的分布情況,一般用于估算選擇率。
以MCV卡槽為例屬性“stakind1”辨別卡槽類型為MCV,其中“1”為“STATISTIC_KIND_MCV”的枚舉值;屬性stanumbers1與屬性stavalues1記錄MCV的具體内容,其中stavalues1記錄key值,stanumbers1記錄key對應的頻次。
系統表pg_statistics的定義在檔案pg_statistic.h中。
#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
統計資訊通過analyze指令獲得。
表tt的oid為40960,有10000行資料占用345個pages頁。第1列unique1的分布情況可以從直方圖資訊擷取,直方圖有100個區間,并且沒有空值和MCV。第16列string4的分布情況可以通過MCV資訊擷取,這一列有4個distinct值”AAAAxx” ,”HHHHxx” , “OOOOxx” , “VVVVxx” ,4個值的分布頻次都有0.25。
行數估計
行數估算是代價估算的基礎,來源于基表統計資訊的推算,估算基表baserel、Join中間結果集joinrel、Aggregation中結果集大小,為代價估算做準備。
SQL查詢常常帶有where限制(過濾條件),比如SELECT * FROM tt WHERE string4 = 'AAAAxx'。知道了限制條件的選擇率,也就是知道了通過掃描路徑要掃描出來的結果所占的比例或者通過連接配接操作所獲得的元組所占的比例,通過這個比例就可以推算出中間結果和最終結果的數量,進而使用這些數量來計算代價。
這裡重點分析基表的簡單查詢——基于OpExpr類型的選擇率計算,處理函數在clause_selectivity。如果是過濾條件就調用restriction_selectivity函數來獲得OpExpr表達式的選擇率,如果是連接配接條件則調用join_selectivity函數來獲得選擇率。
SELECT * FROM tt WHERE string4 = 'AAAAxx'為過濾條件,調用restriction_selectivity進行選擇率估算。
restriction_selectivity函數識别出string4 = 'AAAAxx'是形如Var = Const的等值限制,操作符的限制選擇性計算函數存儲在系統表PG_OPERATOR,opno = 93對應的選擇率計算函數為eqsel,通過eqsel函數調用var_eq_const函數進行選擇率估算。在該過程中,var_eq_const函數會讀取PG_STATISTIC表中string4列分布資訊,并利用MCV資訊直接傳回選擇率為0.25。
函數set_baserel_size_estimates計算估計行數。
函數調用關系: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