這個鏈接上有點介紹，可以了解個大概：http://blog.imaginea.com/mysql-query-parsing/
關鍵點：
1. SQL解析包括語法分析器和詞法分析器。
簡便的做法是用bison/flex組合。不過MySQL的詞法分析器是手工打造的。
語法分析器的入口函數是MYSQLparse，詞法分析器的入口函數是MYSQLlex。
2. 詞法分析中會檢查token是否為關鍵字。
最直接的做法是弄個大的關鍵字數組，進行折半查找。MySQL在此做了些優化。
本文主要介紹的是這一部分。
考慮到關鍵字是一個只讀的列表，對它做一個只讀的查找樹可以改善查找的性能。
產生查找樹：
1. 讀取關鍵字數組，產生一個Trie樹。
2. 調整這棵樹，並產生一個數組（也就是一個不用鏈表表示的樹）。
使用查找樹：
這個比較簡單，直接看函數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,
};
可以看到，數組表示中存在一定的空間浪費。要是不怕麻煩，我們還可以去搾出一點油水來。
