MySQL的词法分析漫谈
UPDATE: MySQL 词法分析及其性能优化
这个链接上有点介绍，可以了解个大概：Introduction
关键点：
- SQL解析包括语法分析器和词法分析器。
简便的做法是用bison/flex组合。不过MySQL的词法分析器是手工打造的。 语法分析器的入口函数是MYSQLparse，词法分析器的入口函数是MYSQLlex。
- 词法分析中会检查token是否为关键字。
最直接的做法是弄个大的关键字数组，进行折半查找。MySQL在此做了些优化。 本文主要介绍的是这一部分。
考虑到关键字是一个只读的列表，对它做一个只读的查找树可以改善查找的性能。
产生查找树：
- 读取关键字数组，产生一个Trie树。
- 调整这棵树，并产生一个数组（也就是一个不用链表表示的树）。
使用查找树：
这个比较简单，直接看函数get_hash_symbol好了。
产生查找树，相关的Makefile规则：
In `sql/CMakeFiles/sql.dir/build.make':
sql/lex_hash.h: sql/gen_lex_hash
$(CMAKE_COMMAND) -E cmake_progress_report /home/zedware/Workspace/mysql/CMakeFiles $(CMAKE_PROGRESS_153)
@$(CMAKE_COMMAND) -E cmake_echo_color --switch=$(COLOR) --blue --bold "Generating lex_hash.h"
cd /home/zedware/Workspace/mysql/sql && ./gen_lex_hash > lex_hash.h
容易发现，最主要的函数就是`get_hash_symbol’，它主要的调用关系为：
/* sql/lex_hash.h */
get_hash_symbol->sql_functions_map
get_hash_symbol->symbols_map
/* sql/sql_lex.cc */
find_keyword->get_hash_symbol
is_keyword->get_hash_symbol
is_lex_native_function->get_hash_symbol
文件”gen_lex_hash.cc”注释中的树的示例：
+-----------+-+-+-+
| len |1|2|3|
+-----------+-+-+-+
|first_char |0|0|a|
|last_char |0|0|d|
|link |0|0|+|
|
V
+----------+-+-+-+--+
| 1 char|a|b|c|d |
+----------+-+-+-+--+
|first_char|d|0|0|0 |
|last_char |n|0|0|-1|
|link |+|0|0|+ |
| |
| V
| symbols[2] ( "DAY" )
V
+----------+--+-+-+-+-+-+-+-+-+-+--+
| 2 char|d |e|f|j|h|i|j|k|l|m|n |
+----------+--+-+-+-+-+-+-+-+-+-+--+
|first_char|0 |0|0|0|0|0|0|0|0|0|0 |
|last_char |-1|0|0|0|0|0|0|0|0|0|-1|
|link |+ |0|0|0|0|0|0|0|0|0|+ |
| |
V V
symbols[0] ( "ADD" ) symbols[1] ( "AND" )
如果你还记得Trie树，理解起来会容易一点。下面是不同的输入数组对应的树。
i=0
+-----------+-+--+
| len |1| 2|
+-----------+-+--+
|first_char |0|-1|
|last_char |0| 0|
|char_tails |0| x|
|ithis |0| 0|
|iresult |0| 0|
|
&&
static SYMBOL symbols[] = {
{ "&&", SYM(AND_AND_SYM)},
static uchar symbols_map[8]= {
0, 0, 1, 0, <=== 1 == symbols[]数组的元素个数，表示没找到
0, 0, 0, 0, <=== symbols[0]
};
i=1
+-----------+--+--+
| len | 1| 2|
+-----------+--+--+
|first_char |-1|-1|
|last_char | 0| 0|
|char_tails | x| x|
|ithis | 0| 0|
|iresult | 1| 0|
| |
< &&
static SYMBOL symbols[] = {
{ "&&", SYM(AND_AND_SYM)},
{ "<", SYM(LT)},
static uchar symbols_map[8]= {
0, 0, 1, 0, <=== 1 < symbols[]数组的元素个数2，戫示找到的就是symbols[1]
0, 0, 0, 0, <=== symbols[0]
};
i=2
+-----------+--+--+
| len | 1| 2|
+-----------+--+--+
|first_char |-1| &|
|last_char | 0| <|
|char_tails | x| ^|
|ithis | 0| 0|
|iresult | 1| x|
| |
< |
|
+----------+--+--+ +--+
| 1 char| &| |...| <|
+----------+--+--+ +--+
|first_char|-1| 0| |-1|
|last_char | 0| 0| | 0|
|char_tails| 0| 0| | x|
|ithis | 0| 0| | 0|
|iresult | 0| 0| | 2|
| |
&& <=
static SYMBOL symbols[] = {
{ "&&", SYM(AND_AND_SYM)},
{ "<", SYM(LT)},
{ "<=", SYM(LE)},
static uchar symbols_map[100]= {
0, 0, 1, 0,
'&', '<', 2, 0,
0, 0, 0, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 3, 0,
0, 0, 2, 0,
};
i=3
+-----------+--+--+
| len | 1| 2|
+-----------+--+--+
|first_char |-1| &|
|last_char | 0| <|
|char_tails | x| ^|
|ithis | 0| 0|
|iresult | 1| x|
| |
< |
|
+----------+--+--+ +--+
| 1 char| &| |...| <|
+----------+--+--+ +--+
|first_char|-1| 0| |-1|
|last_char | 0| 0| | 0|
|char_tails| 0| 0| | x|
|ithis | 0| 0| | 0|
|iresult | 0| 0| | p|
| |
&& |
|
+----------+--+--+
| 2 char| =| >|
+----------+--+--+
|first_char|-1|-1|
|last_char | 0| 0|
|char_tails| x| x|
|ithis | 0| 0|
|iresult | 2| 3|
| |
<= <>
static SYMBOL symbols[] = {
{ "&&", SYM(AND_AND_SYM)},
{ "<", SYM(LT)},
{ "<=", SYM(LE)},
{ "<>", SYM(NE)},
static uchar symbols_map[108]= {
0, 0, 1, 0,
'&', '<', 2, 0,
0, 0, 0, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
0, 0, 4, 0,
'=', '>', 25, 0,
0, 0, 2, 0,
0, 0, 3, 0,
};
可以看到，数组表示中存在一定的空间浪费。要是不怕麻烦，我们还可以去榨出一点油水来。
Written on June 11, 2014