MySQL源碼解析之執行計劃

• MySQL執行計劃介紹
• MySQL執行計劃代碼概覽
• MySQL執行計劃總結

一、MySQL執行計劃介紹

在MySQL中，執行計劃的實現是基於JOIN和QEP_TAB這兩個對象。其中JOIN類表示一個查詢語句塊的優化和執行，每個select查詢語句（即Query_block對象）在處理的時候，都會被當做JOIN對象，其定義在sql/sql_optimizer.h。

QEP_TAB是Query Execution Plan Table的縮寫，這裡的表Table對象主要包含物化表、臨時表、派生表、常量表等。JOIN::optimize()是優化執行器的統一入口，在這裡會把一個查詢語句塊Query_block最終優化成QEP_TAB。

在MySQL-8.0.22版本之後，又引入訪問方式AccessPath和執行迭代器Iterator對象，再結合JOIN和QEP_TAB對象，最終得到整個解析計劃的執行路徑。

二、MySQL執行計劃代碼概覽

本文主要基於MySQL-8.0.25版本，進行說明。

優化器的入口函數：bool JOIN::optimize()，對應代碼文件sql/sql_optimizer.cc。

// 主要功能是把一個查詢塊Query_block優化成一個QEP_TAB，得到AccessPath
bool JOIN::optimize() { 
	...
	// 下麵主要是為了可以藉助INFORMATION_SCHEMA.OPTIMIZER_TRACE表，跟蹤優化器的執行狀態和執行步驟
	Opt_trace_context *const trace = &thd->opt_trace;
	Opt_trace_object trace_wrapper(trace);
	Opt_trace_object trace_optimize(trace, "join_optimization");
	trace_optimize.add_select_number(Query_block->select_number);
	Opt_trace_array trace_steps(trace, "steps");
	...
	// 視窗函數裝配優化
	if (has_windows && Window::setup_windows2(thd, m_windows))
	...
	// 拷貝Query_block上的條件副本到JOIN結構關聯的成員對象，為後續優化做準備
	if (Query_block->get_optimizable_conditions(thd, &where_cond, &having_cond))
	...
	// 統計抽象語法樹中的葉節點表，其中leaf_tables是在Query_block::setup_tables中進行裝配
	tables_list = Query_block->leaf_tables;
	...
	// 分區裁剪
	if (Query_block->partitioned_table_count && prune_table_partitions()) {
	...
	// 嘗試把聚合函數COUNT()、MIN()、MAX()對應的值，替換成常量
	if (optimize_aggregated_query(thd, Query_block, *fields, where_cond,
																&outcome)) {
	...
	// 採用超圖演算法生成執行計劃，註意超圖演算法通過set optimizer_switch="hypergraph_optimizer=on"方式啟用
	if (thd->lex->using_hypergraph_optimizer) {
		FindBestQueryPlan(thd, Query_block, /*trace=*/nullptr);
		// 如果Join優化器是超圖演算法，處理結束直接返回
		return false;
	}
	...

下麵代碼主要涉及Join優化器連接方式為左深樹的情況，主要用到join_tab數組來進行組織關聯

根據代價計算表的連接方式，核心函數make_join_plan()，實現非常複雜。比較關鍵的函數是bool Optimize_table_order::choose_table_order()

其主要思想是通過貪婪搜索Optimize_table_order::greedy_search，根據最小的連接代價，進行有限的窮舉搜索（細節參考Optimize_table_order::best_extension_by_limited_search）

最終找到近似最優解的連接排列組合

	if (make_join_plan()) {
	...
	// 語句塊謂詞條件下推，提升過濾性能
	if (make_join_Query_block(this, where_cond)) {
	...
	// 優化order by/distinct語句
	if (optimize_distinct_group_order()) return true;
	...
	// 分配QEP_TAB數組
	if (alloc_qep(tables)) return (error = 1); /* purecov: inspected */
	...
	// 執行計劃細化，優化子查詢和半連接的情況，具體策略可以參考mariadb的文檔：
	// https:// mariadb.com/kb/en/optimization-strategies/
	// 關鍵代碼是setup_semijoin_dups_elimination，主要對半連接關聯的策略進行裝配
	if (make_join_readinfo(this, no_jbuf_after))
	...
	// 為處理group by/order by創建開闢臨時表空間
	if (make_tmp_tables_info()) return true;
	...
	// 生成訪問方式AccessPath，供後續迭代器Iterator訪問使用
	create_access_paths();
	...
	return false;
}

三、MySQL執行計劃總結

MySQL的執行計劃是整個資料庫最核心的模塊，其代碼也在不斷地迭代更新過程中。執行計劃中優化器的好壞和背後的搜索策略、數學模型緊密相關。MySQL支持的搜索策略有窮舉搜索、貪婪搜索，對應的Join優化器有左深樹演算法和超圖演算法，整個優化過程主要是基於CBO策略進行優化。

執行計劃運行的過程，實際上就是一個動態規劃的過程。這個過程的優劣，快慢決定了MySQL和主流商業資料庫的差距。只有深入地理解MySQL優化器的運行原理，才能幫助我們積極有效地探索更高性能優化的可能。
最後由於筆者知識水平有限，疏漏之處，還望斧正。

Enjoy GreatSQL