WIP: 拆解 TiDB Parser & Planner 篇

Parser

Lexer

yylval

yyval

ruleTable & tokenMap & windowFuncTokenMap

Yacc

%union 制定 Lexer 的 yylval

%union {
	offset int // offset
	item interface{}
	ident string
	expr ast.ExprNode
	statement ast.StmtNode
}

https://github.com/mysql/mysql-server/blob/8.0/sql/sql_yacc.yy

https://github.com/pingcap/tidb/blob/master/parser/parser.y

*session.Parse

Planner

Logical Plan

*clientConn.handleStmt -> *TiDBContext.ExecuteStmt -> *session.ExecuteStmt -> *Compiler.Compile

SubstiuteGC

PruneColumns

ResultReorder

BuildKey

Decorrelated

RewriteSemiJoin

RewriteSkewDistinctAggregation

EliminateProjection

EliminateMaxMin

PredicatePushDown

EliminateOuterJoin

ProcessPartition

CollectPredicateColumnsPoint

AggregationPushDown

DeriveTopNFromWindow

PredicateSimplification

OptimizeTopNPushDown

SyncWaitStatsLoadPoint

JoinReorder

SequencePushDown

ResolveExpand

Physical Plan

Cascaded Plan

参考资料

1. https://github.com/pingcap/tidb
2. https://www.udacity.com/course/compilers-theory-and-practice–ud168
3. https://www.icourse163.org/course/HIT-1002123007
4. https://courses.cs.washington.edu/courses/cse401/16wi/lectures/09-AG-SDT-wi16.pdf
5. https://courses.cs.washington.edu/courses/cse401/16wi/lectures/10-CYK-Earley-Disambig-wi16.pdf
6. https://nlogn.art/wp-content/uploads/2023/04/Language-Implementation-Patterns.pdf
7. https://gist.github.com/tkrs/23ab96cf84284ec6848c1c0a16611e21
8. https://www.bilibili.com/video/BV1ea41187KK

序

Lexer

NFA/DFA

定义有限状态机 M 描述为 $M = (S, \Sigma, \delta, S_0, F)$

1. $S$ 为有限状态集（如下图的 $\{0,1,2,3\}$ 状态）；
2. $\Sigma$ 为输入的字符集，空字符（通常用 $\epsilon$ 表示）不归属于 $\Sigma$ 中；
3. $\delta$ 为状态转移函数，描述由某一状态接受到某字符后的状态变更；
4. $S_0$ 为起始状态集，$start$ 箭头所指向的状态 $0$；
5. $F$ 为终止状态集，用双圈包裹标记的状态。

而 NFA 与 DFA 的区别为，

1. NFA 的转移函数 $\delta = S \times ( \Sigma \cup \epsilon ) $ 的结果集范围等于有限状态集的幂集 $2^{S}$；
2. DFA 的转移函数 $\delta = S \times \Sigma $ 结果集范围等于有限状态集；
3. 在实际意义上，DFA 状态转移的目标状态只有一种（有限状态集的一个状态点），而 NFA 的目标状态是有多种（幂集中的一个状态集合），故此 NFA 匹配失败时，需要回溯。

TiDB 采用 Tire 进行 token 识别，关键字词汇辅以 HashMap 识别。

Grammar

二义性文法

CYK & Earley