摘要：在先前的源碼閱讀系列文章四中，我們介紹了語句，想必大家已經(jīng)了解了是如何寫入數(shù)據(jù)，本篇文章介紹一下語句是如何執(zhí)行。最終語句被解析成結(jié)構(gòu)對(duì)于本文所提到的語句會(huì)被解析為，被解析為字段，被解析為字段。的實(shí)現(xiàn)會(huì)不斷獲取每個(gè)返回的，把結(jié)果寫入。

在先前的 TiDB 源碼閱讀系列文章（四） 中，我們介紹了 Insert 語句，想必大家已經(jīng)了解了 TiDB 是如何寫入數(shù)據(jù)，本篇文章介紹一下 Select 語句是如何執(zhí)行。相比 Insert，Select 語句的執(zhí)行流程會(huì)更復(fù)雜，本篇文章會(huì)第一次進(jìn)入優(yōu)化器、Coprocessor 模塊進(jìn)行介紹。

表結(jié)構(gòu)沿用上篇文章的：

CREATE TABLE t {
  id   VARCHAR(31),
  name VARCHAR(50),
  age  int,
  key id_idx (id)
};

Select 語句只會(huì)講解最簡單的情況：全表掃描+過濾，暫時(shí)不考慮索引等復(fù)雜情況，更復(fù)雜的情況會(huì)在后續(xù)章節(jié)中介紹。語句為：

SELECT name FROM t WHERE age > 10;

相比 Insert 的處理流程，Select 的處理流程中有 3 個(gè)明顯的不同：

需要經(jīng)過 Optimize

Insert 是比較簡單語句，在查詢計(jì)劃這塊并不能做什么事情（對(duì)于 Insert into Select 語句這種，實(shí)際上只對(duì) Select 進(jìn)行優(yōu)化），而 Select 語句可能會(huì)無比復(fù)雜，不同的查詢計(jì)劃之間性能天差地別，需要非常仔細(xì)的進(jìn)行優(yōu)化。

需要和存儲(chǔ)引擎中的計(jì)算模塊交互

Insert 語句只涉及對(duì) Key-Value 的 Set 操作，Select 語句可能要查詢大量的數(shù)據(jù)，如果通過 KV 接口操作存儲(chǔ)引擎，會(huì)過于低效，必須要通過計(jì)算下推的方式，將計(jì)算邏輯發(fā)送到存儲(chǔ)節(jié)點(diǎn)，就近進(jìn)行處理。

需要對(duì)客戶端返回結(jié)果集數(shù)據(jù)

Insert 語句只需要返回是否成功以及插入了多少行即可，而 Select 語句需要返回結(jié)果集。

本篇文章會(huì)重點(diǎn)說明這些不同的地方，而相同的步驟會(huì)盡量化簡。

Select 語句的語法解析規(guī)則在 這里。相比 Insert 語句，要復(fù)雜很多，大家可以對(duì)著 MySQL 文檔 看一下具體的解析實(shí)現(xiàn)。需要特別注意的是 From 字段，這里可能會(huì)非常復(fù)雜，其語法定義是遞歸的。

最終語句被解析成 ast.SelectStmt 結(jié)構(gòu)：

type SelectStmt struct {
        dmlNode
        resultSetNode
        // SelectStmtOpts wraps around select hints and switches.
        *SelectStmtOpts
        // Distinct represents whether the select has distinct option.
        Distinct bool
        // From is the from clause of the query.
        From *TableRefsClause
        // Where is the where clause in select statement.
        Where ExprNode
        // Fields is the select expression list.
        Fields *FieldList
        // GroupBy is the group by expression list.
        GroupBy *GroupByClause
        // Having is the having condition.
        Having *HavingClause
        // OrderBy is the ordering expression list.
        OrderBy *OrderByClause
        // Limit is the limit clause.
        Limit *Limit
        // LockTp is the lock type
        LockTp SelectLockType
        // TableHints represents the level Optimizer Hint
        TableHints [](#)*TableOptimizerHint
}

對(duì)于本文所提到的語句 SELECT name FROM t WHERE age > 10;? name 會(huì)被解析為 Fields，WHERE age > 10 被解析為 Where 字段，FROM t 被解析為 From 字段。

在 planBuilder.buildSelect() 方法中，我們可以看到 ast.SelectStmt 是如何轉(zhuǎn)換成一個(gè) plan 樹，最終的結(jié)果是一個(gè) LogicalPlan，每一個(gè)語法元素都被轉(zhuǎn)換成一個(gè)邏輯查詢計(jì)劃單元，例如 WHERE c > 10 會(huì)被處理為一個(gè) plan.LogicalSelection 的結(jié)構(gòu)：

????if sel.Where != nil {
????????p = b.buildSelection(p, sel.Where, nil)
????????if b.err != nil 
????????????return nil
????????}
????}??

具體的結(jié)構(gòu)如下：

// LogicalSelection represents a where or having predicate.
type LogicalSelection struct {
    baseLogicalPlan

    // Originally the WHERE or ON condition is parsed into a single expression,
    // but after we converted to CNF(Conjunctive normal form), it can be
    // split into a list of AND conditions.
    Conditions []expression.Expression
}

其中最重要的就是這個(gè) Conditions 字段，代表了 Where 語句需要計(jì)算的表達(dá)式，這個(gè)表達(dá)式求值結(jié)果為 True 的時(shí)候，表明這一行符合條件。

其他字段的 AST 轉(zhuǎn) LogicalPlan 讀者可以執(zhí)行研究一下，經(jīng)過個(gè)這個(gè) buildSelect() 函數(shù)后，AST 變成一個(gè) Plan 的樹狀結(jié)構(gòu)樹，下一步會(huì)在這個(gè)結(jié)構(gòu)上進(jìn)行優(yōu)化。

讓我們回到 plan.Optimize() 函數(shù)，Select 語句得到的 Plan 是一個(gè) LogicalPlan，所以 這里 可以進(jìn)入 doOptimize 這個(gè)函數(shù)，這個(gè)函數(shù)比較短，其內(nèi)容如下：

func doOptimize(flag uint64, logic LogicalPlan) (PhysicalPlan, error) {
    logic, err := logicalOptimize(flag, logic)
    if err != nil {
        return nil, errors.Trace(err)
    }
    if !AllowCartesianProduct && existsCartesianProduct(logic) {
        return nil, errors.Trace(ErrCartesianProductUnsupported)
    }
    physical, err := dagPhysicalOptimize(logic)
    if err != nil {
        return nil, errors.Trace(err)
    }
    finalPlan := eliminatePhysicalProjection(physical)
    return finalPlan, nil
}

大家可以關(guān)注來兩個(gè)步驟：logicalOptimize 和 dagPhysicalOptimize，分別代表邏輯優(yōu)化和物理優(yōu)化，這兩種優(yōu)化的基本概念和區(qū)別本文不會(huì)描述，請(qǐng)大家自行研究（這個(gè)是數(shù)據(jù)庫的基礎(chǔ)知識(shí)）。下面分別介紹一下這兩個(gè)函數(shù)做了什么事情。

邏輯優(yōu)化由一系列優(yōu)化規(guī)則組成，對(duì)于這些規(guī)則會(huì)按順序不斷應(yīng)用到傳入的 LogicalPlan Tree 中，見 logicalOptimize() 函數(shù)：

func logicalOptimize(flag uint64, logic LogicalPlan) (LogicalPlan, error) {
    var err error
    for i, rule := range optRuleList {
        // The order of flags is same as the order of optRule in the list.
        // We use a bitmask to record which opt rules should be used. If the i-th bit is 1, it means we should
        // apply i-th optimizing rule.
        if flag&(1<
目前 TiDB 已經(jīng)支持下列優(yōu)化規(guī)則：
var optRuleList = []logicalOptRule{
    &columnPruner{}, 
    &maxMinEliminator{},
    &projectionEliminater{},
    &buildKeySolver{},
    &decorrelateSolver{},
    &ppdSolver{},
    &aggregationOptimizer{},
    &pushDownTopNOptimizer{},
}
這些規(guī)則并不會(huì)考慮數(shù)據(jù)的分布，直接無腦的操作 Plan 樹，因?yàn)榇蠖鄶?shù)規(guī)則應(yīng)用之后，一定會(huì)得到更好的 Plan（不過上面有一個(gè)規(guī)則并不一定會(huì)更好，讀者可以想一下是哪個(gè)）。
這里選一個(gè)規(guī)則介紹一下，其他優(yōu)化規(guī)則請(qǐng)讀者自行研究或者是等到后續(xù)文章。
columnPruner（列裁剪） 規(guī)則，會(huì)將不需要的列裁剪掉，考慮這個(gè) SQL: select c from t; 對(duì)于 from t 這個(gè)全表掃描算子（也可能是索引掃描）來說，只需要對(duì)外返回 c 這一列的數(shù)據(jù)即可，這里就是通過列裁剪這個(gè)規(guī)則實(shí)現(xiàn)，整個(gè) Plan 樹從樹根到葉子節(jié)點(diǎn)遞歸調(diào)用這個(gè)規(guī)則，每層節(jié)點(diǎn)只保留上面節(jié)點(diǎn)所需要的列即可。
經(jīng)過邏輯優(yōu)化，我們可以得到這樣一個(gè)查詢計(jì)劃：

其中 FROM t 變成了 DataSource 算子，WHERE age > 10 變成了 Selection 算子，這里留一個(gè)思考題，SELECT name 中的列選擇去哪里了？
物理優(yōu)化
在物理優(yōu)化階段，會(huì)考慮數(shù)據(jù)的分布，決定如何選擇物理算子，比如對(duì)于 FROM t WHERE age > 10 這個(gè)語句，假設(shè)在 age 字段上有索引，需要考慮是通過 TableScan + Filter 的方式快還是通過 IndexScan 的方式比較快，這個(gè)選擇取決于統(tǒng)計(jì)信息，也就是 age > 10 這個(gè)條件究竟能過濾掉多少數(shù)據(jù)。
我們看一下 dagPhysicalOptimize 這個(gè)函數(shù)：
func dagPhysicalOptimize(logic LogicalPlan) (PhysicalPlan, error) {
    logic.preparePossibleProperties()
    logic.deriveStats()
    t, err := logic.convert2PhysicalPlan(&requiredProp{taskTp: rootTaskType, expectedCnt: math.MaxFloat64})
    if err != nil {
        return nil, errors.Trace(err)
    }
    p := t.plan()
    p.ResolveIndices()
    return p, nil
}
這里的 convert2PhysicalPlan 會(huì)遞歸調(diào)用下層節(jié)點(diǎn)的 convert2PhysicalPlan 方法，生成物理算子并且估算其代價(jià)，然后從中選擇代價(jià)最小的方案，這兩個(gè)函數(shù)比較重要：
// convert2PhysicalPlan implements LogicalPlan interface.
func (p *baseLogicalPlan) convert2PhysicalPlan(prop *requiredProp) (t task, err error) {
    // Look up the task with this prop in the task map.
    // It"s used to reduce double counting.
    t = p.getTask(prop)
    if t != nil {
        return t, nil
    }
    t = invalidTask
    if prop.taskTp != rootTaskType {
        // Currently all plan cannot totally push down.
        p.storeTask(prop, t)
        return t, nil
    }
    for _, pp := range p.self.genPhysPlansByReqProp(prop) {
        t, err = p.getBestTask(t, pp)
        if err != nil {
            return nil, errors.Trace(err)
        }
    }
    p.storeTask(prop, t)
    return t, nil
}

func (p *baseLogicalPlan) getBestTask(bestTask task, pp PhysicalPlan) (task, error) {
    tasks := make([]task, 0, len(p.children))
    for i, child := range p.children {
        childTask, err := child.convert2PhysicalPlan(pp.getChildReqProps(i))
        if err != nil {
            return nil, errors.Trace(err)
        }
        tasks = append(tasks, childTask)
    }
    resultTask := pp.attach2Task(tasks...)
    if resultTask.cost() < bestTask.cost() {
        bestTask = resultTask
    }
    return bestTask, nil
}
上面兩個(gè)方法的返回值都是一個(gè)叫 task 的結(jié)構(gòu)，而不是物理計(jì)劃，這里引入一個(gè)概念，叫 Task，TiDB 的優(yōu)化器會(huì)將 PhysicalPlan 打包成為 Task。Task 的定義在 task.go 中，我們看一下注釋：
// task is a new version of `PhysicalPlanInfo`. It stores cost information for a task.
// A task may be CopTask, RootTask, MPPTask or a ParallelTask.
type task interface {
    count() float64
    addCost(cost float64)
    cost() float64
    copy() task
    plan() PhysicalPlan
    invalid() bool
}
在 TiDB 中，Task 的定義是能在單個(gè)節(jié)點(diǎn)上不依賴于和其他節(jié)點(diǎn)進(jìn)行數(shù)據(jù)交換即可進(jìn)行的一些列操作，目前只實(shí)現(xiàn)了兩種 Task：

CopTask 是需要下推到存儲(chǔ)引擎（TiKV）上進(jìn)行計(jì)算的物理計(jì)劃，每個(gè)收到請(qǐng)求的 TiKV 節(jié)點(diǎn)都會(huì)做相同的操作
RootTask 是保留在 TiDB 中進(jìn)行計(jì)算的那部分物理計(jì)劃

如果了解過 TiDB 的 Explain 結(jié)果，那么可以看到每個(gè) Operator 都會(huì)標(biāo)明屬于哪種 Task，比如下面這個(gè)例子：

整個(gè)流程是一個(gè)樹形動(dòng)態(tài)規(guī)劃的算法，大家有興趣可以跟一下相關(guān)的代碼自行研究或者等待后續(xù)的文章。
經(jīng)過整個(gè)優(yōu)化過程，我們已經(jīng)得到一個(gè)物理查詢計(jì)劃，這個(gè) SELECT name FROM t WHERE age > 10; 語句能夠指定出來的查詢計(jì)劃大概是這樣子的：

讀者可能會(huì)比較奇怪，為什么只剩下這樣一個(gè)這一個(gè)物理算子？WHERR age > 10 哪里去了？實(shí)際上 age > 10 這個(gè)過濾條件被合并進(jìn)了 PhysicalTableScan，因?yàn)?age > 10 這個(gè)表達(dá)式可以下推到 TiKV 上進(jìn)行計(jì)算，所以會(huì)把 TableScan 和 Filter 這樣兩個(gè)操作合在一起。哪些表達(dá)式會(huì)被下推到 TiKV 上的 Coprocessor 模塊進(jìn)行計(jì)算呢？對(duì)于這個(gè) Query 是在下面 這個(gè)地方 進(jìn)行識(shí)別：
// PredicatePushDown implements LogicalPlan PredicatePushDown interface.
func (ds *DataSource) PredicatePushDown(predicates []expression.Expression) ([]expression.Expression, LogicalPlan) {
    _, ds.pushedDownConds, predicates = expression.ExpressionsToPB(ds.ctx.GetSessionVars().StmtCtx, predicates, ds.ctx.GetClient())
    return predicates, ds
}
在 expression.ExpressionsToPB 這個(gè)方法中，會(huì)把能下推 TiKV 上的表達(dá)式識(shí)別出來（TiKV 還沒有實(shí)現(xiàn)所有的表達(dá)式，特別是內(nèi)建函數(shù)只實(shí)現(xiàn)了一部分），放到 DataSource.pushedDownConds 字段中。接下來我們看一下 DataSource 是如何轉(zhuǎn)成 PhysicalTableScan，見 DataSource.convertToTableScan() 方法。這個(gè)方法會(huì)構(gòu)建出 PhysicalTableScan，并且調(diào)用 addPushDownSelection() 方法，將一個(gè) PhysicalSelection 加到 PhysicalTableScan 之上，一起放進(jìn) copTask 中。
這個(gè)查詢計(jì)劃是一個(gè)非常簡單計(jì)劃，不過我們可以用這個(gè)計(jì)劃來說明 TiDB 是如何執(zhí)行查詢操作。
Executing
一個(gè)查詢計(jì)劃如何變成一個(gè)可執(zhí)行的結(jié)構(gòu)以及如何驅(qū)動(dòng)這個(gè)結(jié)構(gòu)執(zhí)行查詢已經(jīng)在前面的兩篇文章中做了描述，這里不再敷述，這一節(jié)我會(huì)重點(diǎn)介紹如何具體的執(zhí)行過程以及 TiDB 的分布式執(zhí)行框架。
Coprocessor 框架
Coprocessor 這個(gè)概念是從 HBase 中借鑒而來，簡單來說是一段注入在存儲(chǔ)引擎中的計(jì)算邏輯，等待 SQL 層發(fā)來的計(jì)算請(qǐng)求（序列化后的物理執(zhí)行計(jì)劃），處理本地?cái)?shù)據(jù)并返回計(jì)算結(jié)果。在 TiDB 中，計(jì)算是以 Region 為單位進(jìn)行，SQ
L 層會(huì)分析出要處理的數(shù)據(jù)的 Key Range，再將這些 Key Range 根據(jù) PD 中拿到的 Region 信息劃分成若干個(gè) Key Range，最后將這些請(qǐng)求發(fā)往對(duì)應(yīng)的 Region。
SQL 層會(huì)將多個(gè) Region 返回的結(jié)果進(jìn)行匯總，在經(jīng)過所需的 Operator 處理，生成最終的結(jié)果集。
DistSQL
請(qǐng)求的分發(fā)與匯總會(huì)有很多復(fù)雜的處理邏輯，比如出錯(cuò)重試、獲取路由信息、控制并發(fā)度以及結(jié)果返回順序，為了避免這些復(fù)雜的邏輯與 SQL 層耦合在一起，TiDB 抽象了一個(gè)統(tǒng)一的分布式查詢接口，稱為 DistSQL API，位于 distsql 這個(gè)包中。
其中最重要的方法是 SelectDAG 這個(gè)函數(shù)：
// SelectDAG sends a DAG request, returns SelectResult.
// In kvReq, KeyRanges is required, Concurrency/KeepOrder/Desc/IsolationLevel/Priority are optional.
func SelectDAG(goCtx goctx.Context, ctx context.Context, kvReq *kv.Request, fieldTypes []*types.FieldType) (SelectResult, error) {
    // kvReq 中包含了計(jì)算所涉及的數(shù)據(jù)的 KeyRanges
    // 這里通過 TiKV Client 向 TiKV 集群發(fā)送計(jì)算請(qǐng)求
    resp := ctx.GetClient().Send(goCtx, kvReq)
    if resp == nil {
        err := errors.New("client returns nil response")
        return nil, errors.Trace(err)
    }

    if kvReq.Streaming {
        return &streamResult{
            resp:       resp,
            rowLen:     len(fieldTypes),
            fieldTypes: fieldTypes,
            ctx:        ctx,
        }, nil
    }
    // 這里將結(jié)果進(jìn)行了封裝
    return &selectResult{
        label:      "dag",
        resp:       resp,
        results:    make(chan newResultWithErr, kvReq.Concurrency),
        closed:     make(chan struct{}),
        rowLen:     len(fieldTypes),
        fieldTypes: fieldTypes,
        ctx:        ctx,
    }, nil
}
TiKV Client 中的具體邏輯我們暫時(shí)跳過，這里只關(guān)注 SQL 層拿到了這個(gè) selectResult 后如何讀取數(shù)據(jù)，下面這個(gè)接口是關(guān)鍵。
// SelectResult is an iterator of coprocessor partial results.
type SelectResult interface {
    // NextRaw gets the next raw result.
    NextRaw(goctx.Context) ([]byte, error)
    // NextChunk reads the data into chunk.
    NextChunk(goctx.Context, *chunk.Chunk) error
    // Close closes the iterator.
    Close() error
    // Fetch fetches partial results from client.
    // The caller should call SetFields() before call Fetch().
    Fetch(goctx.Context)
    // ScanKeys gets the total scan row count.
    ScanKeys() int64
selectResult 實(shí)現(xiàn)了 SelectResult 這個(gè)接口，代表了一次查詢的所有結(jié)果的抽象，計(jì)算是以 Region 為單位進(jìn)行，所以這里全部結(jié)果會(huì)包含所有涉及到的 Region 的結(jié)果。調(diào)用 Chunk 方法可以讀到一個(gè) Chunk 的數(shù)據(jù)，通過不斷調(diào)用 NextChunk 方法，直到 Chunk 的 NumRows 返回 0 就能拿到所有結(jié)果。NextChunk 的實(shí)現(xiàn)會(huì)不斷獲取每個(gè) Region 返回的 SelectResponse，把結(jié)果寫入 Chunk。
Root Executor
能推送到 TiKV 上的計(jì)算請(qǐng)求目前有 TableScan、IndexScan、Selection、TopN、Limit、PartialAggregation 這樣幾個(gè)，其他更復(fù)雜的算子，還是需要在單個(gè) tidb-server 上進(jìn)行處理。所以整個(gè)計(jì)算是一個(gè)多 tikv-server 并行處理 + 單個(gè) tidb-server 進(jìn)行匯總的模式。
總結(jié)
Select 語句的處理過程中最復(fù)雜的地方有兩點(diǎn)，一個(gè)是查詢優(yōu)化，一個(gè)是如何分布式地執(zhí)行，這兩部分后續(xù)都會(huì)有文章來更進(jìn)一步介紹。下一篇文章會(huì)脫離具體的 SQL 邏輯，介紹一下如何看懂某一個(gè)特定的模塊。
作者：申礫