要：查詢引擎會在所有可行的查詢訪問路徑中選擇執行代價最低的一條。
本文分享自華為云社區《一文讀懂簡單查詢代價估算【這次高斯不是數學家】-云社區-華為云》，作者： leapdb。
SQL生命周期：詞法分析（Lex） -> 語法分析（YACC） -> 分析重寫 -> 查詢優化（邏輯優化和物理優化） -> 查詢計劃生成 -> 查詢執行。
在物理優化階段，同樣的一條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方式隨機采集的部分樣本數據。我們將其轉化為一個數學問題就是：給定一個常量數組可以分析出來哪些數據特征？找規律哈。
用最樸素的數學知識能想到的是：
還有嗎？這是一個值得不斷思考的問題。
統計信息是不準確的，不可靠的，兩個原因：
如何設計一個數學模型，利用不可靠的統計信息，盡可能準確的估算查詢代價，是一個很有意思的事情。接下來我們通過一個個的具體例子來介紹。
主要內容來自以下鏈接，我們主要對其進行詳細的解讀。
https://www.postgresql.org/docs/14/planner-stats-details.html
https://www.postgresql.org/docs/14/using-explain.html
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 中。
所以，估算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)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)前面 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)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博客_云計算博客_開發者中心-華為云
此部分是關于Undo log的組織形式的一個介紹；主要分為兩部分來對undo log的組織形式進行介紹：文件結構和內存結構。在介紹這兩部分時，先從局部出發，最后再給出各個部分的聯系。
1. 文件結構
首先，在MySQL5.6之前所有的undo log全部存儲在系統表空間中(ibdata1)；但是從5.6開始也可以使用獨立表空間來存儲undo log。
當前版本InnoDB默認有兩個undo tablespace，也可以使用CREATE UNDO TABLESPACE語句動態添加，最大128個；每個undo tablespace至多可以有TRX_SYS_N_RSEGS(128)個回滾段。
1.1 Rollback Segment(回滾段)
InnoDB在undo tablespace中使用回滾段來組織undo log。同時為了保證事務的并發操作，在寫undo log時不產生沖突，InnoDB使用 回滾段 來維護undo log的并發寫入和持久化；而每個回滾段 又有多個undo log slot。通常通過Rollback Segment Header來管理回滾段，Rollback Segment Header通常在回滾段的第一個頁，具體結構如下：
Rollback Segment Header里面最重要的兩部分就是history list與undo slot directory。
其中history list把所有已經提交但還沒有被purge事務的undo log串聯起來，purge線程可以通過此list對沒有事務使用的undo log進行purge。
每個事務在需要記錄undo log時都會申請一個或兩個slot(insert/update分開)，同時把事務的第一個undo page放入對應slot中；所以理論上InnoDB允許的最大事務并發數為128(undo tablespace) * 128(Rollback Segment) * 1024(TRX_RSEG_UNDO_SLOTS)。下面我們進一步介紹undo log在磁盤上如何記錄。
1.2 UndoPage
要想知道undo log如何記錄，我們先要搞清楚一個undo page具體內容，undo page一般分兩種情況：header page和normal page 。
header page除了normal page所包含的信息，還包含一些undo segment信息，后面會對undo segment進行詳細介紹。
我們下面先介紹一下undo header page的詳細分布。
undo header page是事務需要寫undo log時申請的第一個undo page；一個undo header page他同一時刻只隸屬于同一個活躍事務，但是一個undo header page上面的內容可能包含多個已經提交的事務和一個活躍事務。
undo normal page是當活躍事務產生的undo record超過undo header page容量后，單獨再為此事務分配的undo page(參考函數trx_undo_add_page)；此page只隸屬于一個事務，只包含undo page header不包含undo segment header。
1.3 Undo Page Header
每一個undo page都要有header，其中記錄了當前undo page的一些狀態信息，具體內容如下：
1.4 Undo Segment Header
上面只是介紹了一些undo log在文件上的基本結構，下面我們繼續介紹記錄undo log時的文件組織。
1.5 Undo Log Header
當事務開始記錄undo log時，先創建一個undo log header，當update/delete事務結束后，undo log header將會被加入到hisotry list中；insert事務的undo log會被立即釋放。
有關XID的內容暫時不介紹。
有了undo log header后，我們就可以記錄undo record了。
1.6 Undo Record
可以從上面圖中看出，undo record除了存儲這里比較重要的幾個信息，包含前后undo record位置，類型，undo no，table id等；而undo recod中具體存儲的內容我們等到《undo log的分配與記錄》中去介紹。
最后，我們通過下面這幅圖來了解undo log在文件組織上的一個總覽。
2. 主要內存數據結構
為了方便管理和記錄undo log，在內存中有如下關鍵結構體對象：
我們重點對trx_rseg_t結構體的內容進行介紹。
trx_rseg_t主要數據成員：
上面四個數據可以從trx_undo_t中獲取，參考trx_purge_add_update_undo_to_history函數。
下面我們通過一副關系圖來介紹內存中各個關鍵結構體之間的關系；其中實線代表擁有該對象，虛線代表引用該對象。
我們通過之前的介紹了解到；undo log在磁盤和內存中是如何組織的；從中了解到，回滾段不論在磁盤和內存中，都是一個非常關鍵的結構體；InnoDB存儲引擎通過回滾段來對undo log進行組織和管理，所以首先我們需要弄清楚回滾段是如何分配與使用的，之后再闡述undo log具體是如何記錄的。
1. 分配回滾段
當開啟一個事務的時候，需要預先為事務分配一個回滾段。
首先我們將事務分為兩大類：只讀事務與讀寫事務。分別從這兩大類事務來探討如何分配回滾段的。
只讀事務：當事務涉及到對臨時表的讀寫時，我們需要為其分配一個回滾段對其產生的undo log record進行記錄，具體調用鏈路如下：
trx_assign_rseg_temp() -> get_next_temp_rseg() -> (trx_sys->tmp_rsegs)trx_sys->tmp_rsegs 對應的臨時文件為ibtmp1，一般來說有128個回滾段。
讀寫事務：當一個事務被判定為讀寫模式時，會為其分配trx_id以及回滾段，具體調用鏈路如下
trx_assign_rseg_durable() -> get_next_redo_rseg() | ->get_next_redo_rseg_from_trx_sys() -> (trx_sys->rsegs) | ->get_next_redo_rseg_from_undo_spaces() -> (undo_space->rsegs())當InnoDB沒有配置獨立undo表空間時，從trx_sys->rsegs為讀寫事務分配回滾段；否則則從 undo_spaces->rsegs()為其分配回滾段；InnoDB從MySQL 8.0.3開始，獨立表空間個數默認值從0改為2。
trx_sys->rsegs 對應的文件為ibdata1，默認有128個回滾段。
undo_space->rsegs() 對應的文件為undo_001，undo_002...，最多可有128個undo文件，每個文件默認128個回滾段。
具體從rsegs中分配時采用round-robin方式進行分配。
2. 使用回滾段
當發生數據變更時，我們需要使用undo log記錄下變更前的數據記錄；因此需要從回滾段分配中來分配一個undo slot來供事務記錄undo。
記錄undo的入口函數為trx_undo_report_row_operation，其大致流程如下：
接著來看一下 trx_undo_assign_undo 函數流程：
undo header page結構參考之前的《undo log的組織形式》的內容
undo log最小的并發單元為undo slot，所以undo log支持最大的并發事務為：undo tablespace 數 * 回滾段數 * undo slot數。
3. undo log寫入
當分配完undo slot，初始化完undo log對象后，我們就可以記錄真正的undo log record；undo log record也分為一下兩種，insert undo log record與update undo record。
當數據庫需要修改某個數據記錄時，都會寫入一條update undo log record；當插入一條數據記錄時，會寫入一條insert undo log record。
對于insert undo log寫入的入口函數為trx_undo_page_report_insert()
對于update undo log寫入的入口函數為trx_undo_page_report_modify()
在寫入過程中，可能出現undo page空間不足的情況；當出現這種情況，我們需要通過trx_undo_erase_page_end()來清除剛剛寫入的區域，然后通過trx_undo_add_page()申請一個新的undo page加入到undo page list，同時將undo->last_page_no指向新的undo page，最后重試寫入。
完成undo log record的寫入后，通過trx_undo_build_roll_ptr()構建新的回滾指針返回；通過回滾指針我們可以找到相關記錄的undo log record，從而構建出舊版本的數據；回滾指針將會記錄在聚集索引記錄中。
我們通過之前的介紹已經了解到， undo log的組織方式與分配記錄；那么后面我們繼續介紹undo log主要的應用是什么。
undo log的應用主要有兩方面：
我們接下來就詳細介紹上面兩個功能undo log是如何實現的。
1. 崩潰恢復
在InnoDB因為某些原因停止運行后；重啟InnoDB時，可能存在一個不一致的狀態，這個時候我們就需要把MySQL恢復到一個一致的狀態來保證數據庫的可用性。這個恢復過程主要分下面這么幾步：
經過上面這三步后，InnoDB就可以恢復到一個一致的狀態，并且對外提供服務。
下面我們詳細的來介紹這三部分的具體過程：
1.1 undo log的恢復
因為undo log受到redo log的保護，所以我們只需要根據最新的redo log就可以把undo log恢復到最新的狀態；具體的調用過程如下：
recv_recovery_from_checkpoint_start()// 從最新的一個log checkpoint開始讀取redo log并應用。 | -> recv_recovery_begin() // 將redo log讀取到log buffer中，并將其parse到redo hash中 | -> recv_scan_log_recs() // 掃描 log buffer中的redo log，并將redo hash中的redo log應用 | -> recv_apply_hashed_log_recs() // 應用redo log到其對應的page上。 | ->recv_apply_log_rec()->recv_recover_page()->recv_parse_or_apply_log_rec_body() -> MLOG_UNDO_INSERT…
經過上述的流程之后，undo log就可以恢復到InnoDB崩潰前的最新的狀態；雖然undo log已經恢復到最新的狀態，但是InnoDB還沒有恢復到崩潰前的最新狀態；所以下一步我們就需要根據最新的undo log把InnoDB崩潰前的內存結構都恢復出來。
1.2 構建InnoDB崩潰前的狀態
構建InnoDB崩潰前的狀態，主要是恢復崩潰前最新事務系統的狀態；通過該狀態我們可以知道那些事務已經提交，那些事務還未提交，以及那些事務還未開始。
我們從前面兩章的介紹，回滾段不管在內存中還是在文件中都是組織undo log的重要數據結構；所以我們首先需要把回滾段的內存結構恢復出來，然后根據內存中的回滾段，把活躍的事務恢復出來。其具體過程在函數trx_sys_init_at_db_start()中實現，其大致步驟如下：
至此，我們就已經把InnoDB崩潰前的內存和文件狀態都已經恢復出來了；其實這個時候InnoDB已經可以對外提供服務了，(畢竟內存和文件狀態都就緒后我們也就可以保持一致性了)；那么最后一步的事務回滾就可以交給后臺線程來慢慢做事務回滾，不影響主線程對外提供服務了。
1.3 事務回滾
事務需要回滾主要有兩種情況：
那么在回滾時，我們就需要借助undo log中的舊數據來把事務恢復到之前的狀態；其入口函數為row_undo_step()；
其操作就是通過undo log來讀取舊的數據記錄，然后做逆向操作；主要分為下面這么幾類：
2. 多版本并發控制(MVCC)
多版本并發控制簡單的說就是當前事務只能看見已經提交的數據記錄，看不到正在修改的數據記錄。所以我們只要弄清楚那些事務對于當前事務是已經提交的，那些事務對于當前事務是活躍的。
為了實現上述的功能我們先介紹幾個比較關鍵的概念：
trx::id：事務開始的邏輯時間，也叫事務ID，在事務開始時通過trx_start_low()分配。
trx::no：事務結束的邏輯時間，在事務結束的時候通過trx_commit_low()分配。
trx_sys::rw_trx_ids：當前活躍的事務ID；事務在開始時ID會被添加至此數據結構中；事務提交時ID會被從此數據結構中刪除。
在構造一條數據記錄時，我們除了在數據記錄中添加用戶自主添加的數據列，系統還會自動分配一些系統列，具體包括：
DATA_TRX_ID：修改過此行數據記錄的最新事務ID。
DATA_ROLL_PTR：指向這條數據記錄的上一個版本的指針，上一版數據在undo log中。
通過上面幾個數據結構的介紹，我們大概了解了一些基本概念；但是這對于一個事務來判斷那些事務對它是已經提交的，那些事務對它是活躍的還是遠遠不夠的；所以我們接下來介紹MVCC中最重要的一個數據結構：視圖，也就是read view。
2.1 視圖
每一個事務在讀取數據時都會被分配一個視圖，通過視圖就可以來判斷其他事務對數據記錄的可見性。下面我們來具體介紹一下視圖是如何運作的。
分配：主要通過trx_assign_read_view()來給一個事務分配視圖；在事務的隔離級別是Consistent Snapshot 或 Read Repeatable時，事務開始時會給其分配；其他情況下當事務需要讀取數據時將會給其分配一個視圖。
回收：事務結束時，會通過view_close()對其視圖進行回收。
幾個關鍵數據結構：
那么有了上面這些數據我們就可以判斷那些事務對于此視圖是活躍的，那些事務對于此視圖是已經提交的。
那些事務對于此視圖是活躍的：
如果給定一個trx_id滿足上面兩個條件其中之一，那么這個事務對于此視圖就是活躍的。
那些事務對于此視圖是已經提交的：
如果給定一個trx_id滿足上面兩個條件其中之一，那么這個事務對于此視圖就是已經提交的。
2.2 數據可見性
通過上面的介紹，那么一個事務就可以通過此事務的視圖來對數據記錄判斷可見性了。
具體是通過ReadView::changes_visible()來判斷可見性的，具體如下：
假設一個事務為T，trx_id為記錄R中的DATA_TRX_ID：
如果T對R不可見，就需要R中的DATA_ROLL_PTR來構造出上一個數據頁版本，直至記錄可見。
我們通過下面一個例子來說明可見性。
我們通過之前的系列文章已經了解到undo log在磁盤和內存中是如何組織的；undo log是如何分配的；以及undo log是如何使用的。那么undo log會一直記錄下去么？當然不是，有些undo log如果沒用的話是會被回收清理的。
那么下面這將會介紹那些undo log可以清理，以及undo log是怎么進行清理的。
1. 幾個關鍵的數據結構
在介紹undo log 清理之前，先介紹幾個關鍵的數據結構；這幾個數據結構對于undo log的清理實現是至關重要的。
trx_sys->serialisation_list： 里面存放的是正在提交的事務，按照trx_t::no有序的排列；事務會在開始提交時通過 trx_serialisation_number_get() 添加至該數據結構，事務結束提交時通過trx_erase_lists()將該事務從該數據結構中移除。
read_view::m_low_limit_no：擁有該read_view的對象，對于trx_t::no小于read_view::m_low_limit_no的undo log都不在需要；該變量的取值時trx_sys->serialisation_list中最早的一個事務的trx_t::no；因為trx_sys->serialisation_list內有序存放的正在提交的事務，如果一個事務的trx_t::no比該數值還小，那么這個事務一定已經提交了。
TRX_RSEG_HISTORY與TRX_UNDO_HISTORY_NODE：這兩個值我們之前在《undolog的組織形式》里簡單介紹過，這兩個值共同將回滾段中的history list組織起來；在事務提交時，如果是update/delete類型的undo log，將其undo log header以頭插法的方式通過trx_purge_add_update_undo_to_history()加入到該回滾段的history list中，如果是insert類型的undo log其空間會被當場釋放，這是因為insert記錄沒有舊的版本；因此history list中的undo log header是以trx_t::no降序排列的，這里需要注意一下：history list里面的節點是undo log header。下面我們通過一幅圖來具體說明下磁盤上history list的結構。
2. 那些undo log可以清理？
對于一個事務來說，早于read_view::m_low_limit_no的undo log都不需要訪問了；那么如果存在一個read view，其read_view::m_low_limit_no比所有read view的m_low_limit_no都要小，那么小于此read_view::m_low_limit_no的undo log就不在被所有活躍事務所需要了，那么這些undo log就可以清理了。
在read_view初始化時，會使用頭插法通過view_open()插入到一個全局視圖鏈表(MVCC::m_views)中，在事務結束時通過view_close()會從全局視圖鏈表中將此read view移除；因為是順序插入，所以此鏈表中最后一個還沒有close的視圖就可以看做是最老的一個視圖；小于此視圖的undo log可以被清理，一般將此視圖賦值給purge_sys::view。
現在我們已經可以決定那些undo log是可以被清理的，那么下一步我們還需要找到具體那些undo log可以清理。
在事務提交時，此事務對應的回滾段會通過trx_serialisation_number_get()加入到purge_sys::purge_queue中。
purge_sys::purge_queue是一個以回滾段中第一個提交事務的trx_t::no為key的優先級隊列。
如此一來，從purge_sys::purge_queue取出的回滾段中一定包含最老提交的事務，將此事務的trx_t::no與purge_sys::view對比，即可判斷出此事務相關的undo log是否可以被清理。
purge_sys::purge_queue的詳細信息如下圖：
3. undo log怎么清理？
解決了那些undo log可以清理的問題后，下面接著繼續看undo log怎么進行清理的問題。
當放入history list的undo log且不會再被訪問時，需要進行清理操作，另外數據頁上面的標記刪除的操作也需要清理掉，有一些purge線程負責這些操作，去入口函數為srv_do_purge() -> trx_purge()，其大致流程如下：
這里purge undo log record時主要分為兩種情況：清理TRX_UNDO_DEL_MARK_REC記錄或者清理TRX_UNDO_UPD_EXIST_REC記錄
注意：當一個undo tablespace被標記為需要truncate時，不會再有事務從此undo tablespace分配回滾段，而且進行truncate時必須保證該undo tablespace上所有的undo log都已經被purge。
4. 最后
通過上面的介紹，我們知道了undo log那些記錄可以被清理以及是怎么清理的，但是清理undo log過程中還有很多繁雜的細節；比如清理索引時涉及到對B樹的操作，以及舊版本數據的構建，XA事務，BLOB等等；這類內容暫時略過后面有機會繼續介紹。
MySQL 8.0.23's source code
MySQL 8.0 Reference Manual
MySQL Server Team Blog
庖丁解InnoDB之Undo LOG
數據庫故障恢復機制的前世今生
淺析數據庫并發控制機制
Jeremy Cole's github A little fun with InnoDB multi-versioning
The basics of the InnoDB undo logging and history system
MySQL · 引擎特性 · InnoDB undo log 漫游
InnoDB：undo log（1）
InnoDB：undo log（2）
原文鏈接：http://click.aliyun.com/m/1000349864/
本文為阿里云原創內容，未經允許不得轉載。