摘要：查詢引擎會在所有可行的查詢通路路徑中選擇執行代價最低的一條。

本文分享自華為雲社群《一文讀懂簡單查詢代價估算【這次高斯不是數學家】-雲社群-華為雲》，作者： leapdb。

查詢代價估算——如何選擇一條最優的執行路徑

SQL生命周期：詞法分析（Lex） -> 文法分析（YACC） -> 分析重寫 -> 查詢優化（邏輯優化和實體優化） -> 查詢計劃生成 -> 查詢執行。

詞法分析：描述詞法分析器的*.l檔案經Lex工具編譯生成lex.yy.c，再由C編譯器生成可執行的詞法分析器。基本功能就是将一堆字元串根據設定的保留關鍵字和非保留關鍵字，轉化成相應的辨別符（Tokens）。
文法分析：文法規則描述檔案*.y經YACC工具編譯生成gram.c，再由C編譯器生成可執行的文法分析器。基本功能就是将一堆辨別符（Tokens）根據設定的文法規則，轉化成原始文法樹。
分析重寫：查詢分析将原始文法樹轉換為查詢文法樹（各種transform）;查詢重寫根據pg_rewrite中的規則改寫表和視圖，最終得到查詢文法樹。
查詢優化：經過邏輯優化和實體優化（生成最優路徑）。
查詢計劃生成：将最優的查詢路徑轉化為查詢計劃。
查詢執行：通過執行器去執行查詢計劃生成查詢的結果集。

在實體優化階段，同樣的一條SQL語句可以産生很多種查詢路徑，例如：多表JOIN操作，不同的JOIN順序産生不同的執行路徑，也導緻中間結果元組規模的不同。查詢引擎會在所有可行的查詢通路路徑中選擇執行代價最低的一條。

通常我們依據 COST = COST（CPU） + COST（IO）這一公式來選擇最優執行計劃。這裡最主要的問題是如何确定滿足某個條件的元組數量，基本方法就是依據統計資訊和一定的統計模型。某條件的查詢代價 = tuple_num * per_tuple_cost。

統計資訊主要是pg_class中的relpages和reltuples，以及pg_statistics中的distinct， nullfrac， mcv， histgram等。

為何需要這些統計資訊，有了這些夠不夠？

統計資訊的收集來自analyze指令通過random方式随機采集的部分樣本資料。我們将其轉化為一個數學問題就是：給定一個常量數組可以分析出來哪些資料特征？找規律哈。

用最樸素的數學知識能想到的是：

是不是空數組
是不是常量數組
是不是unique無重複
是不是有序
是不是單調的，等差，等比
出現次數最多的數字有哪些
資料的分布規律（打點方式描繪資料增長趨勢）

還有嗎？這是一個值得不斷思考的問題。

如何依據統計資訊估算查詢代價

統計資訊是不準确的，不可靠的，兩個原因：

統計資訊隻來自部分采樣資料，不能精準描述全局特征。
統計資訊是曆史資料，實際資料随時可能在變化。

如何設計一個數學模型，利用不可靠的統計資訊，盡可能準确的估算查詢代價，是一個很有意思的事情。接下來我們通過一個個的具體例子來介紹。

主要内容來自以下連結，我們主要對其進行詳細的解讀。

https://www.postgresql.org/docs/14/planner-stats-details.html

https://www.postgresql.org/docs/14/using-explain.html

最簡單的表的行數估算（使用relpages和reltuples）

SELECT relpages, reltuples FROM pg_class WHERE relname = 'tenk1'; ---采樣估算有358個頁面，10000條元組
 relpages | reltuples
----------+-----------
      358 |     10000

EXPLAIN SELECT * FROM tenk1; ---查詢估算該表有10000條元組
                         QUERY PLAN
-------------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..458.00 rows=10000 width=244)

【思考】查詢計劃中估算的rows=10000就直接是pg_class->reltuples嗎？

統計資訊是曆史資料，表的元組數在随時變化。例如：analyze資料采樣時有10個頁面，存在50條元組;實際執行時有20個頁面，可能存在多少條元組？用你最樸素的情感想一想是不是，很可能是100條元組對不對？

表大小的估算方法在函數 estimate_rel_size -> table_relation_estimate_size -> heapam_estimate_rel_size 中。

先通過表實體檔案的大小計算實際頁面數actual_pages = file_size / BLOCKSIZE
計算頁面的元組密度
a. 如果相關頁大于0，密度 = reltuples / （雙）重頁
b. 如果relpages為空，density = （BLCKSZ - SizeOfPageHeaderData） / tuple_width，頁面大小 / 元組寬度。
估算表元組個數 = 頁面元組密度 * 實際頁面數 actual_pages =

是以，估算rows的10000 = （10000 / 358） * 358，曆史頁面密度 * 新的頁面數，以推算目前元組數。

最簡單的範圍比較(使用直方圖)

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}

 EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000; ---估算小于1000的有1007條
                                   QUERY PLAN
--------------------------------------------------------------------------------
 Bitmap Heap Scan on tenk1  (cost=24.06..394.64 rows=1007 width=244)
   Recheck Cond: (unique1 < 1000)
   ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)
         Index Cond: (unique1 < 1000)

查詢引擎在查詢文法樹的WHERE子句中識别出比較條件，再到pg_operator中根據操作符和資料類型找到oprrest為scalarltsel，這是通用的标量資料類型的小于操作符的代價估算函數。最終是在 scalarineqsel -> ineq_histogram_selectivity 中進行直方圖代價估算。

在PG中采用的是等高直方圖，也叫等頻直方圖。将樣本範圍劃分成N等份的若幹個子區間，取所有子區間的邊界值，構成直方圖。

使用：使用時認為子區間（也叫桶）内的值是線性單調分布的，也認為直方圖的覆寫範圍就是整個資料列的範圍。是以，隻需計算出在直方圖中的占比，既是總體中的占比。

【思考】以上的兩點假設靠譜嗎？有沒有更合理的辦法？

選擇率 = (前面桶的總數 + 目标值在目前桶中的範圍 / 目前桶的區間範圍) / 桶的總數
selectivity = (1 + (1000 - bucket[2].min) / (bucket[2].max - bucket[2].min)) / num_buckets
            = (1 + (1000 - 993) / (1997 - 993)) / 10
            = 0.100697
估算元組數 = 基表元組數 * 條件選擇率
rows = rel_cardinality * selectivity
     = 10000 * 0.100697
     = 1007  (rounding off)

最簡單的等值比較（使用MCV）

SELECT null_frac, n_distinct, most_common_vals, most_common_freqs FROM pg_stats WHERE tablename='tenk1' AND attname='stringu1';
null_frac         | 0
n_distinct        | 676
most_common_vals  | {EJAAAA,BBAAAA,CRAAAA,FCAAAA,FEAAAA,GSAAAA,JOAAAA,MCAAAA,NAAAAA,WGAAAA}
most_common_freqs | {0.00333333,0.003,0.003,0.003,0.003,0.003,0.003,0.003,0.003,0.003}

EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'CRAAAA'; ---
                        QUERY PLAN
----------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..483.00 rows=30 width=244)
   Filter: (stringu1 = 'CRAAAA'::name)

查詢引擎在查詢文法樹的WHERE子句中識别出比較條件，再到pg_operator中根據操作符和資料類型找到oprrest為eqsel，這是通用的等值比較操作符的代價估算函數。最終是在 eqsel_internal -> var_eq_const 中進行MCV代價估算。

MCV是在樣本中選取重複次數最多的前100個組成，并計算每個值在樣本中的占比。使用時，就簡單的認為這個占比就是在全局中的占比。

【思考】将樣本中占比就這樣簡單的認為是在全局中的占比，這樣合理嗎？有沒有更好的辦法？

CRAAAA位于MCV中的第3項，占比是0.003
selectivity = mcf[3]
            = 0.003
rows = 10000 * 0.003
     = 30

接下來，我們在看一個不在MCV中的等值比較。

EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'xxx'; ---查找不存在于MCV中的值
                        QUERY PLAN
----------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..483.00 rows=15 width=244)
   Filter: (stringu1 = 'xxx'::name)

通常MCV用于等值比較，直方圖用于範圍比較。“不存在于MCV中的值”，認為它們共享“不存在于MCV中的機率”，即：選擇率 = （1 - MCV機率總和） / （不在MCV中的值的distinct個數）。

【思考】這樣判斷不在MCV中的方法合理嗎？有沒有更好的方法？

selectivity = (1 - sum(mvf)) / (num_distinct - num_mcv)
            = (1 - (0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003 +
                    0.003 + 0.003 + 0.003 + 0.003)) / (676 - 10)
            = 0.0014559
rows = 10000 * 0.0014559
     = 15  (rounding off)

複雜一點的範圍比較（同時使用MCV和直方圖）

前面 unique < 1000 的例子，在 scalarineqsel 函數中隻利用到了直方圖，是因為unique列沒有重複值，也就不存在MCV。下面我們用一個不是unique的普通列再看一下範圍比較。

這個範圍包括兩部分，重複次數比較多的值（在MCV中）和重複次數比較少的值（覆寫在直方圖裡），又由于計算直方圖時去掉了MCV的值，是以MCV和直方圖互相獨立可以聯合使用。

SELECT null_frac, n_distinct, most_common_vals, most_common_freqs FROM pg_stats WHERE tablename='tenk1' AND attname='stringu1';
null_frac         | 0
n_distinct        | 676
most_common_vals  | {EJAAAA,BBAAAA,CRAAAA,FCAAAA,FEAAAA,GSAAAA,JOAAAA,MCAAAA,NAAAAA,WGAAAA}
most_common_freqs | {0.00333333,0.003,0.003,0.003,0.003,0.003,0.003,0.003,0.003,0.003}

SELECT histogram_bounds FROM pg_stats WHERE tablename='tenk1' AND attname='stringu1';
                                histogram_bounds
--------------------------------------------------------------------------------
 {AAAAAA,CQAAAA,FRAAAA,IBAAAA,KRAAAA,NFAAAA,PSAAAA,SGAAAA,VAAAAA,XLAAAA,ZZAAAA}

EXPLAIN SELECT * FROM tenk1 WHERE stringu1 < 'IAAAAA'; ---查找一個不存在于MCV中的值
                         QUERY PLAN
------------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..483.00 rows=3077 width=244)
   Filter: (stringu1 < 'IAAAAA'::name)

小于IAAAAA的值在MCV中有前6個，是以把它們的frac累加起來，就是小于IAAAAA且重複次數較多的人的機率

selectivity = sum(relevant mvfs)
            = 0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003
            = 0.01833333

還有一部分小于IAAAAA但重複次數較少的人的機率可以通過直方圖進行範圍計算。前面使用unique1列進行等值比較時，因為unique限制列不存在MCV，隻有直方圖。是以，隻計算在直方圖中桶的覆寫占比就是選擇率了。這裡還要考慮落在直方圖中值的整體占比 histogram_fraction = 1 - sum（mcv_frac），直方圖桶的覆寫占比 * 整個直方圖整體占比就是在直方圖中的選擇率了。

selectivity = mcv_selectivity + histogram_selectivity * histogram_fraction
            = 0.01833333 + ((2 + ('IAAAAA'-'FRAAAA')/('IBAAAA'-'FRAAAA')) / 10) * (1 - sum(mvfs))
            = 0.01833333 + 0.298387 * 0.96966667
            = 0.307669

rows        = 10000 * 0.307669
            = 3077  (rounding off)

【思考】在這個特殊的例子中，從MCV中計算出來的選擇率為0.01833333，遠小于從直方圖中計算出來的選擇率0.28933593，是因為該列中數值分布的太平緩了（統計資訊顯示MCV中的這些值出現的頻率比其他值要高，這可能是因為采樣導緻的錯誤）。在大多數存在明顯重複值多的場景下，從MCV中計算出的選擇率會比較明顯，因為重複值的出現機率是比較準确的。

多條件聯合查詢的例子

EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000 AND stringu1 = 'xxx';
                                   QUERY PLAN
--------------------------------------------------------------------------------
 Bitmap Heap Scan on tenk1  (cost=23.80..396.91 rows=1 width=244)
   Recheck Cond: (unique1 < 1000)
   Filter: (stringu1 = 'xxx'::name)
   ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)
         Index Cond: (unique1 < 1000)

多條件的選擇率計算其實也很簡單，就按條件本身的邏輯運算來。

兩個條件是與的關系，屬于互相獨立事件，就相乘就可以了。

selectivity = selectivity(unique1 < 1000) * selectivity(stringu1 = 'xxx')
            = 0.100697 * 0.0014559
            = 0.0001466

rows        = 10000 * 0.0001466
            = 1  (rounding off)

一個使用JOIN的例子

EXPLAIN SELECT * FROM tenk1 t1, tenk2 t2
WHERE t1.unique1 < 50 AND t1.unique2 = t2.unique2;
                                      QUERY PLAN
--------------------------------------------------------------------------------------
 Nested Loop  (cost=4.64..456.23 rows=50 width=488)
   ->  Bitmap Heap Scan on tenk1 t1  (cost=4.64..142.17 rows=50 width=244)
         Recheck Cond: (unique1 < 50)
         ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..4.63 rows=50 width=0)
               Index Cond: (unique1 < 50)
   ->  Index Scan using tenk2_unique2 on tenk2 t2  (cost=0.00..6.27 rows=1 width=244)
         Index Cond: (unique2 = t1.unique2)

unique1 < 50這個限制在nested-loop join之前被執行，還是使用直方圖計算，類似前面的簡單範圍查找的例子，隻不過這次50落在第一個桶中。

selectivity = (0 + (50 - bucket[1].min)/(bucket[1].max - bucket[1].min))/num_buckets
            = (0 + (50 - 0)/(993 - 0))/10
            = 0.005035

rows        = 10000 * 0.005035
            = 50  (rounding off)

JOIN限制t1.unique2 = t2.unique2的選擇率估算，還是先到pg_operator中查找“等于”操作符的oprjoin，是eqjoinsel。JOIN的話，兩邊的統計資訊都要參考。

SELECT tablename, null_frac,n_distinct, most_common_vals FROM pg_stats
WHERE tablename IN ('tenk1', 'tenk2') AND attname='unique2';

tablename  | null_frac | n_distinct | most_common_vals
-----------+-----------+------------+------------------
 tenk1     |         0 |         -1 |
 tenk2     |         0 |         -1 |

對于unique列沒有MCV，是以這裡我們隻能依賴distinct和nullfrac來計算選擇率。

【*】選擇率 = 兩邊的非空機率相乘，再除以最大JOIN條數。
selectivity = (1 - null_frac1) * (1 - null_frac2) * min(1/num_distinct1, 1/num_distinct2)
            = (1 - 0) * (1 - 0) / max(10000, 10000)
            = 0.0001
【*】JOIN的函數估算就是兩邊輸入數量的笛卡爾積，再乘以選擇率
rows = (outer_cardinality * inner_cardinality) * selectivity
     = (50 * 10000) * 0.0001
     = 50

如果存在MCV，則分成兩部分計算選擇率：在MCV中的部分和不在MCV中的部分。

更詳細的資訊

表大小的估算：src/後端/optimizer/util/plancat.c

一般邏輯子句的選擇率估算：src/backend/optimizer/path/clausesel.c

操作符函數的選擇率估算：src/backend/utils/adt/selfuncs.c.

點選下方，第一時間了解華為雲新鮮技術~

華為雲部落格_大資料部落格_AI部落格_雲計算部落格_開發者中心-華為雲