MySQL·源碼分析·詞法分析及其性能優(yōu)化

《MySQL·源碼分析·詞法分析及其性能優(yōu)化》由會(huì)員分享，可在線閱讀，更多相關(guān)《MySQL·源碼分析·詞法分析及其性能優(yōu)化（8頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、文檔供參考，可復(fù)制、編制，期待您的好評(píng)與關(guān)注！ MySQL · 源碼分析 · 詞法分析及其性能優(yōu)化 本文章來(lái)自于阿里云云棲社區(qū) 摘要：?Table of Contents 1. 簡(jiǎn)介 2. 背景知識(shí) 3. 查找樹的實(shí)現(xiàn) 3.1. 樹的查找 3.2. 樹的產(chǎn)生 4. 試試折半查找 5. 總結(jié) 簡(jiǎn)介 MySQL 支持標(biāo)準(zhǔn)的 SQL 語(yǔ)言，具體實(shí)現(xiàn)的時(shí)候必然要涉及到詞法分析和語(yǔ)法分析。早期的程序可能會(huì)優(yōu)先考慮手工實(shí)現(xiàn)詞法分析和語(yǔ)法分析，現(xiàn)在大多數(shù)場(chǎng)合下都會(huì)采用工具來(lái)簡(jiǎn)化實(shí)現(xiàn)。MySQL、PostgreSQL 等 Table of Contents · 1. 簡(jiǎn)介 · 2. 背景知

2、識(shí) · 3. 查找樹的實(shí)現(xiàn) o 3.1. 樹的查找 o 3.2. 樹的產(chǎn)生 · 4. 試試折半查找 · 5. 總結(jié) 簡(jiǎn)介 MySQL 支持標(biāo)準(zhǔn)的 SQL 語(yǔ)言，具體實(shí)現(xiàn)的時(shí)候必然要涉及到詞法分析和語(yǔ)法分析。早期的程序可能會(huì)優(yōu)先考慮手工實(shí)現(xiàn)詞法分析和語(yǔ)法分析，現(xiàn)在大多數(shù)場(chǎng)合下都會(huì)采用工具來(lái)簡(jiǎn)化實(shí)現(xiàn)。MySQL、PostgreSQL 等采用 C/C++ 實(shí)現(xiàn)的開源數(shù)據(jù)庫(kù)采用的是現(xiàn)代的 yacc/lex 組合，也就是 GNU bison/flex。其他比較流行的工具還有 ANTLR、JavaCC 等等。這些工具大多采用擴(kuò)展的 BNF 語(yǔ)法，并支持很多定制化選項(xiàng)，使得語(yǔ)法比較容易維護(hù)和實(shí)

3、現(xiàn)。MySQL 語(yǔ)法分析器的入口函數(shù)是 MYSQLparse()，詞法分析器的入口函數(shù)為 MYSQLlex()。不過(guò)， MySQL 的詞法分析器是手工打造的，并且為了提高關(guān)鍵字的查找效率做了針對(duì)性的優(yōu)化。這個(gè)博客上有點(diǎn)介紹，建議在閱讀代碼之前先了解一下。 背景知識(shí) MySQL 的語(yǔ)法分析器采用的工具是 bison，對(duì)應(yīng)的語(yǔ)法文件是 sql/sql_yacc.yy。bison 處理語(yǔ)法文件的輸出是 sql/sql_yacc.cc 和 sql/sql_yacc.h。對(duì)應(yīng)的 sql/CMakeLists.txt 中有相關(guān)的 make 規(guī)則： INCLUDE(${CMAKE_SOURCE_DIR

4、}/cmake/bison.cmake) RUN_BISON( ${CMAKE_CURRENT_SOURCE_DIR}/sql_yacc.yy ${CMAKE_CURRENT_BINARY_DIR}/sql_yacc.cc ${CMAKE_CURRENT_BINARY_DIR}/sql_yacc.h ) 實(shí)際在 make 的時(shí)候，這個(gè)過(guò)程比較復(fù)雜。也可以單獨(dú) make 詞法語(yǔ)法分析的部分，例如： $ make -C sql gen_lex_token 閱讀代碼的時(shí)候，可以查找 MYSQLparse，以找到語(yǔ)法分析的代碼路徑。下面是清除掉生成的 yacc 代碼再查找

5、的結(jié)果： $ make -C sql clean $ grep --color=auto -rwIn MYSQLparse sql/ sql/sql_parse.cc:6748:extern int MYSQLparse(class THD *thd); // from sql_yacc.cc sql/sql_parse.cc:6752: This is a wrapper of MYSQLparse(). All the code should call parse_sql() sql/sql_parse.cc:6753: instead of MYSQLparse(). s

6、ql/sql_parse.cc:6858: bool mysql_parse_status= MYSQLparse(thd) != 0; sql/sql_parse.cc:6917: Check that if MYSQLparse() failed either thd->is_error() is set, or an sql/sql_lex.cc:3442: parser before returning an error from MYSQLparse. If your MySQL 手工打造的詞法分析器對(duì)應(yīng)的源代碼文件是 sql/sql_lex.h 和 sql/sql_

7、lex.cc。詞法分析的入口函數(shù)是 MYSQLlex()。解析出一個(gè) token 的函數(shù)為 lex_one_token()。詞法分析出來(lái)的每個(gè) token 都會(huì)對(duì)應(yīng)一個(gè)語(yǔ)法分析器中的終結(jié)符，它們的字符串表示在 sql/lex.h 中。這些符號(hào)被分為兩組，SQL 關(guān)鍵字以及 SQL 函數(shù)，在代碼中對(duì)應(yīng)數(shù)組 symbols[] 和 sql_functions[]。通常而言，在語(yǔ)法/詞法分析過(guò)程中為了判斷某個(gè) token 是否為 SQL 的關(guān)鍵字，可以直接二分查找字符串?dāng)?shù)組?？紤]到關(guān)鍵字列表是固定的一個(gè)集合，MySQL 對(duì)此作了專門的優(yōu)化，用 Trie 樹來(lái)進(jìn)一步提高效率。下一節(jié)介紹這部分代碼的實(shí)現(xiàn)

8、。 查找樹的實(shí)現(xiàn) 查找樹的產(chǎn)生用的是一個(gè)獨(dú)立的小程序 gen_lex_hash[.cc]。CMake 產(chǎn)生的 Makefile 規(guī)則為在文件 sql/CMakeFiles/sql.dir/build.make 中： sql/lex_hash.h: sql/gen_lex_hash $(CMAKE_COMMAND) -E cmake_progress_report /home/x/mysql/CMakeFiles $(CMAKE_PROGRESS_153) @$(CMAKE_COMMAND) -E cmake_echo_color --switch=$(COLOR) --blu

9、e --bold "Generating lex_hash.h" cd /home/x/mysql/sql && ./gen_lex_hash > lex_hash.h 可以看到，它產(chǎn)生的代碼在 sql/lex_hash.h 中。里頭包含了兩個(gè)大數(shù)組：sql_functions_map[] 和 symbols_map[]，以及一個(gè)函數(shù) get_hash_symbol()。 具體的實(shí)現(xiàn)自然分為兩個(gè)部分，一個(gè)是產(chǎn)生樹，另一個(gè)是查找產(chǎn)生的樹。 樹的查找 最主要的函數(shù)就是 get_hash_symbol()，它的調(diào)用和被調(diào)用關(guān)系為： 注：上圖是使用 Graphviz 產(chǎn)生的。 文

10、件 gen_lex_hash.cc 的代碼注釋中有一個(gè)樹的示例： 可以看出，根節(jié)點(diǎn)是按照字符串長(zhǎng)度從小到大排序組織的。對(duì)于每種長(zhǎng)度的字符串，要記錄首字母和尾字母以及下一層節(jié)點(diǎn)的指針。中間節(jié)點(diǎn)除了是按照字符從小到大排序外，其它部分與根節(jié)點(diǎn)相同。葉子節(jié)點(diǎn)就是 symbols 數(shù)組的成員。樹的查找就是一個(gè)自然的遍歷過(guò)程。 樹的產(chǎn)生 理解了上面的樹的結(jié)構(gòu)，就很好理解樹的產(chǎn)生邏輯了。它的做法是讀取關(guān)鍵字?jǐn)?shù)組，產(chǎn)生一個(gè)原始的查找樹（參看函數(shù) generate_find_structs）；然后，調(diào)整這個(gè)樹，產(chǎn)生一個(gè)數(shù)組，也就是不用鏈表表示的樹（參看函數(shù) print_find_structs）。主要

11、的函數(shù)和調(diào)用關(guān)系如下： 其中：insert_symbols 處理的是 SQL 關(guān)鍵字，insert_sql_functions 處理的是函數(shù)名。get_hash_struct_by_len 處理的是樹的根節(jié)點(diǎn)，insert_into_hash 處理的是樹的內(nèi)節(jié)點(diǎn)，遞歸執(zhí)行。 為了更好的理解，可以在處理到輸入數(shù)組不同位置時(shí)，查看當(dāng)時(shí)對(duì)應(yīng)的樹。例如： Table 1:?查找樹的產(chǎn)生 試試折半查找 如果要驗(yàn)證一下這個(gè)優(yōu)化與普通的折半查找的性能差異，需要做一些適當(dāng)?shù)男薷牟判?。測(cè)試中用 perf 之類的工具會(huì)發(fā)現(xiàn)比較函數(shù)會(huì)成為熱點(diǎn)。在修改代碼時(shí)需要注意： 1. symbols、sql

12、_functions 這兩個(gè)數(shù)組不一定是按照順序排列的，需要認(rèn)真確認(rèn)。 2. 查找符號(hào)時(shí)，字符串并沒(méi)有以 ‘\0’ 結(jié)尾，做比較要注意。 3. 要修改的文件 sql/lex_hash.h 是自動(dòng)產(chǎn)生的，需要用自己的代碼替換其中的 get_hash_symbol 函數(shù)。 總結(jié) 本文是基于 MySQL 5.6 做的分析?？梢钥吹?MySQL 對(duì)詞法分析中的關(guān)鍵字查找熱點(diǎn)做了性能改進(jìn)。也可以發(fā)現(xiàn)代碼的結(jié)構(gòu)不是特別清晰，存在一些代碼冗余和明顯的可改進(jìn)之處。 WL#8016: Parser for optimizer hints 在重構(gòu)的過(guò)程中順便將其改掉了。 Footnotes: 1?MySQL: Query Parsing < 2?MySQL Download < 3?Graphviz 4?WL#8016: Parser for optimizer hints < 8 / 8