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

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注