MySQL · 源碼分析 · Derived table代碼分析

在具體介紹MySQL的derived table之前，先介紹一下子查詢的概念。

在MySQL中，包含2種類型的子查詢：

• From字句中的子查詢，例如

select * from (select * from t1) tt;           

tt是一個抽象的表概念，内部就是一個子查詢，在PG的概念中叫做sublink，MySQL則叫做derived table、view

• 其他位置的子查詢，如投影列中、條件中、having中，甚至group by/order by中。。例如

select * from t1 where t1.c1 in (select c2 from t1);           

這是一個在where條件中IN子查詢，在PG中叫做subquery，MySQL中稱為subselect

無論哪種類型的子查詢，都有相關和非相關兩種，這篇文章主要介紹非相關的derived table，是MySQL在5.6/5.7中就已經支援的SQL文法，在8.0中又添加了對于具有相關性的derived table(lateral table)的支援，不過這篇文章先從基本說起，代碼基于MySQL 8.0.18。

背景

在介紹derived table在MySQL中的實作之前，需要先大概了解下MySQL中描述一條查詢的邏輯文法樹結構，和傳統實作中的邏輯算子樹略有不同的是，MySQL沒有顯式在代碼中有對算子做統一規範的描述，結構相對不正規但也算清晰，有3個最為核心的類需要先明确：

1. SELECT_LEX_UNIT

MySQL中對于一個query expression的描述結構，其中可以包含union/union all等多個query block的集合運算，同時SELECT_LEX_UNIT也根據query的結構形成遞歸包含關系

2. SELECT_LEX

MySQL中對于一個query block的描述結構，就是我們最為熟悉的SPJ + group by + order by + select list...這樣的一個查詢塊，一個SELECT_LEX_UNIT中可能包含多個SELECT_LEX，而SELECT_LEX内部則也可能嵌套包含其他SELECT_LEX_UNIT

3. Item

MySQL中對于expression的描述結構，例如on條件/where條件/having/投影列等，都是用這個類來描述一個個表達式的，Item系統是MySQL SQL層代碼中最為複雜的子系統之一，例如Item_sum描述sum函數/Item_like描述LIKE字元比對函數。。。Item系統構成了表達式樹

舉個具體的例子如下圖：

可以看到，圖中用括号圈起來的部分，就是一個UNIT，而每個SELECT token開始的一個查詢塊，就是一個SELECT_LEX，而在外層的SELECT_LEX中，會嵌套子查詢，用一個SELECT_LEX_UNIT描述，子查詢中可以是任意查詢形态，再包含多個SELECT_LEX，進而形成SELECT_LEX_UNIT -> SELECT_LEX -> SELECT_LEX_UNIT -> SELECT_LEX ... 這種互相嵌套的結構

這篇介紹的derived table就是圖中FROM字句中的tt，對應SELECT_LEX_UNIT2和内部的SELECT_LEX3/4.

Derived table處理流程

MySQL對于一條查詢語句的處理基本分為3個階段，分别是prepare -> optimize -> execute，我們從3個階段分别看下對于derived table的處理。

Prepare階段

這個查詢的處理在經過parse，基本就構成了最初級的抽象文法樹(AST)，即這種SELECT_LEX_UNIT作為root的嵌套結構，prepare階段主要完成2件事情

1. 負責對AST對resolve，包括所有涉及的tables/columns，以及每一個查詢中的表達式(Item)
2. 基于啟發式規則，完成一些query transformation，包括将子查詢轉換為semi-join，outer join簡化為inner join，derived table展開到上層，消除常量表達式等等。。。

這一階段的transformation是完全基于啟發式的，不考慮代價因素。這裡專注于對derived table的處理流程，MySQL中對于derived table隻有兩種處理方式

1. 展開到外層query block中，等于消除掉了
2. 物化為一個臨時表供外層讀取

代碼主體邏輯如下：

-> SELECT_LEX_UNIT::prepare
   頂層query expression的處理，全局入口
-> open_tables_for_query
   需要通路dd dictionary,擷取查詢中涉及的所有表的中繼資料資訊，包括schema、statistics等，但對于derived table，是一個查詢内定義的邏輯表，并沒有中繼資料，這裡會跳過開表動作
-> SELECT_LEX::prepare
   對一個query block做處理
  -> resolve_placeholder_tables
     derived_table和view在查詢中都屬于placeholder，對其做處理
    -> resolve_derived
      -> 建立Query_result_union對象，在執行derived子查詢時，用來向臨時表裡寫入結果資料
      -> 調用内層嵌套SELECT_LEX_UNIT::prepare，對derived table對應的子查詢做遞歸處理
        -> SELECT_LEX::prepare
          -> 判斷derived中的子查詢是否允許merge到外層，當滿足如下任一條件時，“有可能”可以merge到外層：
             1. derived table屬于最外層查詢
             2. 屬于最外層的子查詢之中，且query是一個SELECT查詢
            -> resolve_placeholder_tables 嵌套處理derived table這個子查詢内部的derived table...
            ... 處理query block中其他的各個元件，包括condition/group by/rollup/distinct/order by...
            -> transform_scalar_subqueries_to_join_with_derived
               如果可能，将标量子查詢轉換為derived table，這個transform是為了MySQL的secondary engine而實作的，由于heat wave對于子查詢的處理能力有限
               要盡可能将子查詢轉換為join，提升執行效率
            ... 一系列對子查詢（Item中的）處理，這裡先略過
            -> apply_local_transforms 做最後的一些查詢變換
               1. 簡化join，把嵌套的join表序列盡可能展開，去掉無用的join，outer join轉inner join等
               2. 對分區表做靜态剪枝
        -> 至此derived table對應的子查詢部分resolve完成
    -> 判斷目前derived table是否可以merge到外層，除了上面提到的基本限制外，對查詢的結構要同時滿足如下的要求：
        1. derived 中沒有union
        2. 沒有group by + 沒有having + 沒有distinct + 有table + 沒有window + 沒有limit
        可以看到MySQL對于derived 子查詢merge的處理能力非常有限，隻有最簡單的SPJ查詢可以展開到外層
    -> 确定可以展開到外層後，merge_derived 執行展開動作
       -> 再做一系列的檢檢視是否可以merge
          1. 外層query block是否允許merge，例如CREATE VIEW/SHOW CREATE這樣的指令，不允許做merge
          2. 基于啟發式，檢查derived子查詢的投影列是否有子查詢，有則不做merge，這裡就是認為使用者這麼定義derived table
             意思就是要做物化而不是展開的，是以不merge到外層
          3. 如果外層有straight_join，而derived子查詢中有semi-join/anti-join，則不允許merge
          4. 外層表的數量達到MySQL能處理的最大值 (61個)
       -> 通過檢查後，開始merge，這裡有一系列複雜操作，不過總體原理很簡單：
          1. 把内層join清單合并到外層中
          2. 把where條件與外層的where條件做AND組合
          3. 把投影列合并到外層投影列中
          當然代碼上會涉及大量内部描述結構的修正，具體可以參考merge_derived的實作
    -> 對于不能展開的，采用物化方式執行，setup_materialized_derived
      -> setup_materialized_derived_tmp_table
        -> Query_result_union::create_result_table 建立一個存放物化結構的臨時表，表列就是内層子查詢的投影列
          -> create_tmp_table 建立SQL層的TABLE表對象，注意這裡并不建立實際的存儲引擎層的表
  -> resolve_placeholder_tables 處理完成
  -> check_view_privileges 如果是view，還有一些權限檢查
  ... 其他query block中元件的處理

           

到這裡derived table在prepare階段的處理就完成了，基本思路非常簡單，就是如果可以merge，就merge到外層，否則建立一個臨時表對象，後續物化使用。

Optimize階段

到了優化階段，MySQL主要處理無法merge到外層的derived子查詢，也就是要物化的那一類，代碼流程邏輯如下：

JOIN::optimize
  -> 對于沒有merged的derived_table，調用optimize_derived先進行優化
    -> SELECT_LEX_UNIT::optimize
       ...對内層query expression做完整的優化，因為是要物化執行，必須走完優化流程
       這裡的優化和MySQL對一個正常query expression的優化一緻，涉及大量代碼，這篇文章就不介紹了
       優化的結果會建構由Iterator組成的執行器結構，是标準的volcano執行模型，root是一個MaterializeIterator
    -> materializable_is_const判斷derived table是否是一個隻包含0/1行的const table
       這裡判斷依據前面步驟中optimize結果對于輸出行數的估計estimatd_rowcount，如果估計值<=1，則認為是const
    -> 如果判斷是const table，則直接進行求值
       這是MySQL優化流程非常詭異的地方，在優化期間，它會對認為求值結果很簡單的子查詢（包括table/subquery）直接進行計算
      -> create_materialized_table
        -> instantiate_tmp_table 真正建立存儲引擎層的表，之前隻是create_tmp_table建立了SQL層的TABLE對象
           MySQL8.0中對于臨時結果表預設使用TempTable引擎
      -> materialize_derived
        -> 找到derived table對應的SELECT_LEX_UNIT
        -> SELECT_LEX_UNIT::exec 觸發volcano執行模型，開始物化derived table
           這個是MySQL執行一個query expression的标準方法，由于在prepare階段建立了Query_result_union對象
           也建立了存儲資料的引擎表，執行中對調用Query_result_union::send_data，将結果寫入物化表中
    -> 如果不是const table，這裡不做執行，隻生成Iterator subtree
  -> 外層優化完成，derived table對應的Iterator tree會挂在外層Iterator tree上，在外層執行時觸發物化流程           

可以看到，由于省略了對于query block優化的内容，整個過程變得非常簡單，關于優化的邏輯實際就是MySQL的整個CBO優化器，後續會專門寫文章介紹。

Execute階段

執行階段就是典型的volcano模型，iterator不斷遞歸調用，從root開始觸發子tree的執行，對于物化的derived table來說，對應的子樹以MaterializeIterator作為root，執行流程如下：

MaterializeIterator::Init 完成物化流程
  -> 如果還沒有建立引擎層的表，調用create_materialized_table
    -> instantiate_tmp_table 上面已經講到了這個方法
    -> MaterializeQueryBlock
       對于MaterializeIterator來說，所有需要物化的query block放在m_query_blocks_to_materialize這個數組中
       依次調用MaterializeQueryBlock執行物化操作
      -> 擷取query block對應的subquery_iterator，也就是這個qb對應執行樹的root iterator
      -> subquery_iterator->init()
      -> 循環調用subquery_iterator->read() 觸發執行流程
         每擷取一行，調用ha_write_row寫入到物化表中
    -> m_table_iterator->init() 
       在内部所有query block的物化都完成後，結果已經寫入了建立的物化表中，這個m_table_iterator用來從表中讀資料
MaterializeIterator::Read 從物化表中讀物化結果，傳遞給上層iterator
  -> m_table_iterator->Read()            

總結

到這裡對于derived table的大體處理流程已經講完了，由于涉及代碼細節非常多，介紹的粒度還是比較粗的，感興趣的同學可以在進一步研究源碼時作為outline。

總得來說，相比Item中的subquery，MySQL對于derived table的處理還是要更簡單清晰一些的，subquery無論從優化邏輯還是執行方式，都會更加多樣複雜，下一篇會專門介紹subquery。

順便聊兩句Steinar H. Gunderson從Oracle離職時對于MySQL的吐槽問題。。。估計隻要是MySQL的核心開發人員，或多或少都會有些感同身受的，就是MySQL在計算層的混亂性（innodb的代碼個人感覺還是很不錯的，規範又高效）。這點社群的Norvald. H. Ryeng 也在一次talk中給出了曆史性原因的解釋，包括功能添加的随意性和初始設計的理論規範性差等等，這點從這篇介紹derived table的文章中就能略探一二：

1. 優化以query block為機關，内部單獨優化，各個query block之間是獨立的，這和傳統的全局一個query tree做優化完全不同，也阻止了一些高效的跨query block的transformation（aggregation pushdown, condition pullup...）
2. 對于derived table的子查詢，先優化子查詢，再優化外層，而對于條件中的子查詢，是先優化外層，再優化子查詢，順序相反
3. 在優化中會對一些子查詢完成計算

這隻是子查詢相關的一些槽點，其他還有很多。。。但無論如何，借着網際網路的東風，MySQL仍然成為了當今最受歡迎的開源關系型資料庫。

社群對計算層的重構由來已久，目前基本已經完成執行層的重寫，還有prepare與optimize的完全解耦，但優化器的重構才剛剛開始（Gunderson是iterator執行器重構和hypergraph優化器的主要實作人員，也是計算層的主開發，他的離開會嚴重影響社群後續的發展。。），後續MySQL的優化器能夠改造到什麼程度，還要看Oracle對于MySQL的戰略重視和資源投入情況了。