MySQL源碼解析之執(zhí)行計劃
一、MySQL執(zhí)行計劃介紹
在MySQL中，執(zhí)行計劃的實現(xiàn)是基于JOIN和QEP_TAB?這兩個對象。其中JOIN類表示一個查詢語句塊的優(yōu)化和執(zhí)行，每個select查詢語句（即Query_block對象）在處理的時候，都會被當做JOIN對象，其定義在sql/sql_optimizer.h。
QEP_TAB是Query Execution Plan Table?的縮寫，這里的表Table對象主要包含物化表、臨時表、派生表、常量表等。JOIN::optimize()?是優(yōu)化執(zhí)行器的統(tǒng)一入口，在這里會把一個查詢語句塊Query_block?最終優(yōu)化成QEP_TAB。
在MySQL-8.0.22版本之后，又引入訪問方式AccessPath?和執(zhí)行迭代器Iterator對象，再結(jié)合JOIN和QEP_TAB對象，最終得到整個解析計劃的執(zhí)行路徑。
二、MySQL執(zhí)行計劃代碼概覽
本文主要基于MySQL-8.0.25版本，進行說明。
優(yōu)化器的入口函數(shù)：bool JOIN::optimize()?，對應(yīng)代碼文件sql/sql_optimizer.cc。
// 主要功能是把一個查詢塊Query_block優(yōu)化成一個QEP_TAB，得到AccessPath
bool JOIN::optimize() {
...
// 下面主要是為了可以借助INFORMATION_SCHEMA.OPTIMIZER_TRACE表，跟蹤優(yōu)化器的執(zhí)行狀態(tài)和執(zhí)行步驟
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");
...
// 窗口函數(shù)裝配優(yōu)化
if (has_windows && Window::setup_windows2(thd, m_windows))
...
// 拷貝Query_block上的條件副本到JOIN結(jié)構(gòu)關(guān)聯(lián)的成員對象，為后續(xù)優(yōu)化做準備
if (Query_block->get_optimizable_conditions(thd, &where_cond, &having_cond))
...
// 統(tǒng)計抽象語法樹中的葉節(jié)點表，其中l(wèi)eaf_tables是在Query_block::setup_tables中進行裝配
tables_list = Query_block->leaf_tables;
...
// 分區(qū)裁剪
if (Query_block->partitioned_table_count && prune_table_partitions()) {
...
// 嘗試把聚合函數(shù)COUNT()、MIN()、MAX()對應(yīng)的值，替換成常量
if (optimize_aggregated_query(thd, Query_block, *fields, where_cond,
&outcome)) {
...
// 采用超圖算法生成執(zhí)行計劃，注意超圖算法通過set optimizer_switch="hypergraph_optimizer=on"方式啟用
if (thd->lex->using_hypergraph_optimizer) {
FindBestQueryPlan(thd, Query_block, /*trace=*/nullptr);
// 如果Join優(yōu)化器是超圖算法，處理結(jié)束直接返回
return false;
}
...
下面代碼主要涉及Join優(yōu)化器連接方式為左深樹的情況，主要用到j(luò)oin_tab數(shù)組來進行組織關(guān)聯(lián)。
根據(jù)代價計算表的連接方式，核心函數(shù)make_join_plan()?，實現(xiàn)非常復(fù)雜。比較關(guān)鍵的函數(shù)是bool Optimize_table_order::choose_table_order()。
其主要思想是通過貪婪搜索Optimize_table_order::greedy_search?，根據(jù)最小的連接代價，進行有限的窮舉搜索（細節(jié)參考Optimize_table_order::best_extension_by_limited_search）最終找到近似最優(yōu)解的連接排列組合。
if (make_join_plan()) {
...
// 語句塊謂詞條件下推，提升過濾性能
if (make_join_Query_block(this, where_cond)) {
...
// 優(yōu)化order by/distinct語句
if (optimize_distinct_group_order()) return true;
...
// 分配QEP_TAB數(shù)組
if (alloc_qep(tables)) return (error = 1); /* purecov: inspected */
...
// 執(zhí)行計劃細化，優(yōu)化子查詢和半連接的情況，具體策略可以參考mariadb的文檔：
// https:// mariadb.com/kb/en/optimization-strategies/
// 關(guān)鍵代碼是setup_semijoin_dups_elimination，主要對半連接關(guān)聯(lián)的策略進行裝配
if (make_join_readinfo(this, no_jbuf_after))
...
// 為處理group by/order by創(chuàng)建開辟臨時表空間
if (make_tmp_tables_info()) return true;
...
// 生成訪問方式AccessPath，供后續(xù)迭代器Iterator訪問使用
create_access_paths();
...
return false;
}
三、MySQL執(zhí)行計劃總結(jié)
MySQL的執(zhí)行計劃是整個數(shù)據(jù)庫最核心的模塊，其代碼也在不斷地迭代更新過程中。執(zhí)行計劃中優(yōu)化器的好壞和背后的搜索策略、數(shù)學模型緊密相關(guān)。MySQL支持的搜索策略有窮舉搜索、貪婪搜索，對應(yīng)的Join優(yōu)化器有左深樹算法和超圖算法，整個優(yōu)化過程主要是基于CBO策略進行優(yōu)化。
執(zhí)行計劃運行的過程，實際上就是一個動態(tài)規(guī)劃的過程。這個過程的優(yōu)劣，快慢決定了MySQL和主流商業(yè)數(shù)據(jù)庫的差距。只有深入地理解MySQL優(yōu)化器的運行原理，才能幫助我們積極有效地探索更高性能優(yōu)化的可能。
