RDBMS-H2源码剖析-SQL词法解析 #10
Description
前言
上一章给大家详细讲解了H2的SQL预编译处理机制，本章我们就继续学习H2在处理预编译语句时是如何调用org.h2.command.Parser来执行SQL解析动作的。
SQL的执行过程
在H2，或者大部分RDBMS中，SQL的执行过程主要分为6个阶段，如下所示：
- 词法解析（Lexical Analysis）；
- 语法解析（Syntax Analysis）；
- 语义解析（Semantic Analysis）；
- 优化（Optimization）；
- 执行（Execution）；
- 结果返回（Result Return）；
简单来说，当我们在执行SQL语句时，SQL解析器会首先调用词法解析器对SQL语句进行词法解析，将SQL中的字符流统一解析为一系列与之相对应的Token序列（比如关键字Token、标识符Token、结束Token、字面量Token，以及参数标记Token等）；然后调用语法解析器将Token序列转换为抽象语法树（AST），并检查语法的正确性，使变得更加结构化；接着调用语义解析器进来验证SQL语义的正确性；最后再进行优化查询计划（查询优化器生成多个执行计划，并选择成本最低的一个，优化步骤可能包括重新排列连接顺序、选择合适的索引等）、执行查询计划（执行引擎按照执行计划访问数据、进行计算、排序、过滤等操作），以及执行结果返回等动作。
FSM有穷自动机
在正式讲解H2的词法解析器的工作原理之前，有必要先讲一下FSM有穷自动机，因为H2的词法解析采用的是确定性有限自动机（Deterministic Finite Automaton, DFA）。FSM全称为Finite State Machine，顾名思义即有穷自动机，有时候也称之为有穷状态机。FSM有2个分类，如下所示：
- 确定性有限状态机（Deterministic Finite Automaton，DFA）；
- 非确定性有限状态机（Non-deterministic Finite Automaton，NFA）；
DFA的特征有6个，如下所示：
- 唯一的后续状态：DFA在任何给定状态和输入下都只有一个确定的后续状态；
- 有限的状态集合：DFA的所有状态构成一个有限集合；
- 输入字母表：DFA接受的输入符号来自一个有限的字母表；
- 转换函数：定义了在每个状态下接收到某个输入符号时转移到的下一个状态；
- 初始状态：DFA有一个唯一的初始状态，从该状态开始处理输入字符流；
- 接收状态集合：DFA有一个或多个接收状态，表示当DFA处理完输入字符流后，如果停留在这些状态之一，则输入字符流被接受；
为了便于大家理解，我们先来看一个简单的DFA示例，这个DFA的主要任务就是将字符流解析为对应的字母和数字Token，如下所示：
public class FSMParser {
enum State {
/**
* 初始状态
*/
START,
/**
* 数字状态
*/
NUMBER,
/**
* 字母状态
*/
LETTER;
}
/**
* 当前状态,初始状态为START
*/
private State currentState = State.START;
private StringBuilder currentToken = new StringBuilder();
/**
* token序列集合
*/
private List<String> tokens = new ArrayList<>();
/**
* 状态转换函数
*
* @param str
*/
public void process(String str) {
for (int i = 0; i < str.length(); i++) {
// 解析当前字符
char input = str.charAt(i);
switch (currentState) {
// START状态
case START:
if (Character.isDigit(input)) {
currentToken.append(input);
currentState = State.NUMBER;
} else if (Character.isLetter(input)) {
currentToken.append(input);
currentState = State.LETTER;
}
break;
// 数字状态
case NUMBER:
if (Character.isDigit(input)) {
currentToken.append(input);
} else {
tokens.add("数字: " + currentToken.toString());
currentToken.setLength(0);
currentState = State.START;
i--;
}
break;
// 字符状态
case LETTER:
if (Character.isLetter(input)) {
currentToken.append(input);
} else {
tokens.add("字符: " + currentToken.toString());
currentToken.setLength(0);
currentState = State.START;
i--;
}
break;
default:
break;
}
}
if (currentToken.length() <= 0) {
return;
}
// 处理结束后，生成最后一个token
switch (currentState) {
case NUMBER:
tokens.add("数字: " + currentToken.toString());
break;
case LETTER:
tokens.add("字符: " + currentToken.toString());
break;
default:
break;
}
}
}上述DFA示例中，总共包含3种状态，分别是开始状态（START）、数字状态（NUMBER）、字母状态（LETTER）。状态机的初始状态为START。在此大家需要注意，有穷自动机中的“有穷”指的就是状态机的状态是有限的。这个DFA接受的输入字母表为：{a-zA-Z,0-9}。
在状态转换函数 process 中，会依次遍历输入字母表中的所有字符。首先会进入到状态START中。如果读取的字符为字母，则状态机转换为LETTER状态并将字符流转换为字母Token，直至检查到的字符不为字母时，将Token序列添加到集合中，并将状态机的状态再次转换为START状态。在处理完一个Token后，继续处理下一个字符，判断是否进入到NUMBER状态或LETTER状态，直至遍历完输入字母表中的所有字符，即表示解析完成。
H2的词法解析
在H2的org.h2.engine.SessionLocal#prepareLoca方法中，如果无法从SmallLRUCache中返回Command命令时（真实的预编译对象），则会创建一个org.h2.command.Parser实例，并调用其prepareCommand->parse方法解析SQL。Parser解析器会在执行语法解析前调用词法解析器的org.h2.command.Tokenizer#initialize方法执行词法解析。
org.h2.command.ParserBase#initialize方法的核心逻辑：
final void initialize(String sql, ArrayList<Token> tokens, boolean stopOnCloseParen) {
if (sql == null) {// sql如果为null，则设置为空串
sql = "";
}
sqlCommand = sql;// 传入的SQL绑定到成员变量sqlCommand上
if (tokens == null) {// tokens为null进入这里
BitSet usedParameters = new BitSet();
// identifiersToUpper和identifiersToLower对应DBSettings中的identifiersToLower和identifiersToUpper，主要是把标识符转换为大小写问题
// nonKeywords为session中的非关键字集合
// 这里是进行调用词法解析器Tokenizer进行词法解析，解析为Token对象
this.tokens = new Tokenizer(
// 数据库实例
database,
// 是否将标识符转换为大写
identifiersToUpper,
// 是否将标识符转换为小写
identifiersToLower,
// 非关键字的位集合（BitSet）
nonKeywords).
// 执行词法解析动作
tokenize(sql,
// 遇到闭合括号时是否停止分割,默认为false
stopOnCloseParen, usedParameters);
if (parameters == null) {
int l = usedParameters.length();
if (l > Constants.MAX_PARAMETER_INDEX) {
throw DbException.getInvalidValueException("parameter index", l);
}
if (l > 0) {
parameters = new ArrayList<>(l);
for (int i = 0; i < l; i++) {
/*
* We need to create parameters even when they aren't
* actually used, for example, VALUES ?1, ?3 needs
* parameters ?1, ?2, and ?3.
*/
parameters.add(new Parameter(i));
}
} else {
parameters = new ArrayList<>();
}
}
} else {
this.tokens = tokens;
}
// 重设token索引
resetTokenIndex();
}H2的词法解析（状态转换）动作发生在org.h2.command.Tokenizer#tokenize函数中。假设待解析的DML为：
SELECT * FROM T_USER WHERE ID = 1Tokenizer最终的解析结果为：
KeywordToken(SELECT)、KeywordToken(*)、KeywordToken(FROM)、IdentifierToken(T_USER)、
KeywordToken(WHERE)、IdentifierToken(ID)、KeywordToken(=)、IntegerToken(1)、EndOfInputToken在H2中，org.h2.command.Token主要有6个大类，如下所示：
- IdentifierToken：标识符Token；
- KeywordToken：关键字Token；
- EndOfInputToken：输入结束Token；
- LiteralToken：字面量Token（比如：'2023-01-01'）；
- KeywordOrIdentifierToken：关键字或标识符Token；
- ParameterToken：参数标记Token（比如：占位符？）；
在org.h2.command.Tokenizer#tokenize状态转换函数中，有限的状态集合主要是{符号、数字、字母}等3种状态，而输入字母表的第一个字符为字母‘s’，那么也就意味着状态为字母，进入到字母状态。
org.h2.command.Tokenizer#tokenize方法的核心逻辑：
ArrayList<Token> tokenize(String sql, boolean stopOnCloseParen, BitSet parameters) {
// tokens集合，即：接收状态（终止状态）集合
ArrayList<Token> tokens = new ArrayList<>();
int end = sql.length() - 1;// 获取SQL语句最后一个字符的索引位
boolean foundUnicode = false;
int lastParameter = 0;
loop:
for (int i = 0; i <= end; ) {// 依次解析SQL语句中的每一个字符，即：解析输入字母表
char c = sql.charAt(i);// 读取当前索引位字符
Token token;
// 处理不同的字符，并调用相应的解析方法解析标识符或关键字
// 这里的case语句中，每个case分支对应一个字符，即：一个状态,有限的状态=有穷状态集
switch (c) {
// 省却掉其他状态判断... ...
case 'S':
case 's':
i = readS(sql, end, i, tokens);
continue loop;
default:
if (c <= ' ') {
// 如果是空格时，递增开始索引，continue当前循环
i++;
continue loop;
} else {
int tokenStart = i;
int cp = Character.isHighSurrogate(c) ? sql.codePointAt(i++) : c;
if (Character.isSpaceChar(cp)) {
i++;
continue loop;
}
if (Character.isJavaIdentifierStart(cp)) {
i = readIdentifier(sql, end, tokenStart, i, tokens);
continue loop;
}
throw DbException.getSyntaxError(sql, tokenStart);
}
}
tokens.add(token);
i++;
}
if (foundUnicode) {
processUescape(sql, tokens);
}
tokens.add(new Token.EndOfInputToken(end + 1));
return tokens;
}在状态转换函数中，会根据不同的字符类型进入到不同的状态转换逻辑中。输入字母表的第一个字符为‘s’，Tokenizer在匹配到后，便会调用org.h2.command.Tokenizer#readS方法解析所有's'打头的标识符或关键字（比如：SECOND、SELECT、标识符等）。
org.h2.command.Tokenizer#readS方法的核心逻辑：
private int readS(String sql, int end, int tokenStart, ArrayList<Token> tokens) {
// 根据当前索引，找到标识符的结束索引位
int endIndex = findIdentifierEnd(sql, end, tokenStart);
int length = endIndex - tokenStart;
int type;
if (eq("SECOND", sql, tokenStart, length)) {
type = SECOND;
} else if (eq("SELECT", sql, tokenStart, length)) {
type = SELECT;
} else if (eq("SESSION_USER", sql, tokenStart, length)) {
type = SESSION_USER;
} else if (eq("SET", sql, tokenStart, length)) {
type = SET;
} else if (eq("SOME", sql, tokenStart, length)) {
type = SOME;
} else if (eq("SYMMETRIC", sql, tokenStart, length)) {
type = SYMMETRIC;
} else if (eq("SYSTEM_USER", sql, tokenStart, length)) {
type = SYSTEM_USER;
} else {
type = IDENTIFIER;
}
// 解析关键字或标识符为token并添加到token列表中
return readIdentifierOrKeyword(sql, tokenStart, tokens, endIndex, type);
}org.h2.command.Tokenizer#findIdentifierEnd方法用于解析识符的结束索引位：
org.h2.command.Tokenizer#findIdentifierEnd方法的核心逻辑：
private int findIdentifierEnd(String sql, int end, int i) {
i++;
for (; ; ) {
int cp;
// todo 非java标识符和符号#时退出循环，意味着找到了标识符
if (i > end || (!Character.isJavaIdentifierPart(cp = sql.codePointAt(i))
&& (cp != '#' || !provider.getMode().supportPoundSymbolForColumnNames))) {
break;
}
// todo 返回指定的unicode代码点需要几个char字符来表示，比如：表情符号😀(emoji)需要2个char来表示
i += Character.charCount(cp);
}
return i;
}findIdentifierEnd方法的功能是找到一个SQL语句中标识符的结束位置（这里从‘s’开始，找到的标识符为SELECT，结束索引位为6）。标识符是指在SQL语句中用于表示表名、列名、变量名等的合法名称。Java中的合法标识符由字母、数字、下划线（_）和美元符号（$）组成。该方法遍历SQL，并从指定的索引位开始查找，直到遇到一个非标识符字符和非符号 # 为止（比如：空格）。返回的标识符的结束索引位并不是简单的递增1，而是递增的指定unocode代码点所需要的char数量，因为一些特殊字符，比如emoji符号通常需要2个char来表示，以便于确保正确的跳过那些需要多个char表示的字符。
当成功解析出结束索引位后，Tokenizer会拿解析出来的标识符去匹配所有满足大小写 s 打头的关键字，以便于明确最终解析出来的Token类型，如果都不匹配时，Tokenizer则认为目标标识符是一个IDENTIFIER类型。org.h2.command.Tokenizer#readS方法最后会调用readIdentifierOrKeyword方法，该方法的主要任务就是根据传入的token type生成对应的Token，并将其添加到Token集合中。
org.h2.command.Tokenizer#readIdentifierOrKeyword方法的核心逻辑：
private int readIdentifierOrKeyword(String sql, int tokenStart, ArrayList<Token> tokens, int endIndex, int type) {
Token token;
// 解析为标识符token
if (type == IDENTIFIER) {
token = new Token.IdentifierToken(tokenStart, extractIdentifier(sql, tokenStart, endIndex), false, false);
} else if (nonKeywords != null && nonKeywords.get(type)) {
token = new Token.KeywordOrIdentifierToken(tokenStart, type, extractIdentifier(sql, tokenStart, endIndex));
}
// 解析为关键字token
else {
token = new Token.KeywordToken(tokenStart, type);
}
// 将token添加到tokens列表中
tokens.add(token);
return endIndex;
}当解析完KeywordToken(SELECT)后，Tokenizer又会回到状态转换函数的开始位置，继续遍历输入字母表中的下一个字符，处理下一个Token。如果当前字符是空格时，则递增开始索引，continue当前循环，继续向下遍历，直至解析完所有的Token序列后，添加一个EndOfInputToken（结束Token）表示词法解析结束。