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
参考资料
- https://github.com/pingcap/tidb
- https://www.udacity.com/course/compilers-theory-and-practice–ud168
- https://www.icourse163.org/course/HIT-1002123007
- https://courses.cs.washington.edu/courses/cse401/16wi/lectures/09-AG-SDT-wi16.pdf
- https://courses.cs.washington.edu/courses/cse401/16wi/lectures/10-CYK-Earley-Disambig-wi16.pdf
- https://nlogn.art/wp-content/uploads/2023/04/Language-Implementation-Patterns.pdf
- https://gist.github.com/tkrs/23ab96cf84284ec6848c1c0a16611e21
- https://www.bilibili.com/video/BV1ea41187KK
序
Lexer
NFA/DFA
定义有限状态机 M 描述为 $M = (S, \Sigma, \delta, S_0, F)$
- $S$ 为有限状态集(如下图的 $\{0,1,2,3\}$ 状态);
- $\Sigma$ 为输入的字符集,空字符(通常用 $\epsilon$ 表示)不归属于 $\Sigma$ 中;
- $\delta$ 为状态转移函数,描述由某一状态接受到某字符后的状态变更;
- $S_0$ 为起始状态集,$start$ 箭头所指向的状态 $0$;
- $F$ 为终止状态集,用双圈包裹标记的状态。
而 NFA 与 DFA 的区别为,
- NFA 的转移函数 $\delta = S \times ( \Sigma \cup \epsilon ) $ 的结果集范围等于有限状态集的幂集 $2^{S}$;
- DFA 的转移函数 $\delta = S \times \Sigma $ 结果集范围等于有限状态集;
- 在实际意义上,DFA 状态转移的目标状态只有一种(有限状态集的一个状态点),而 NFA 的目标状态是有多种(幂集中的一个状态集合),故此 NFA 匹配失败时,需要回溯。

TiDB 采用 Tire 进行 token 识别,关键字词汇辅以 HashMap 识别。
Grammar
二义性文法
CYK & Earley
