993
MYSQL · 新特性 · MySQL 8.0對Parser所做的改進
背景介紹
眾所周知，MySQL Parser是利用C/C++實現的開源yacc/lex組合，也就是 GNU bison/flex。Flex負責生成tokens， Bison負責語法解析。開始介紹MySQL 8.0的新特新之前，我們先簡單了解一下通用的兩種Parser。一種是Bottom-up parser，另外一種是Top-down parser。
Bottom-up parser
Bottom-up解析是從parse tree底層開始向上構造，然後將每個token移進（shift），進而規約（reduce）為較大的token，最終按照語法規則的定義將所有token規約（reduce）成為一個token。移進過程是有先後順序的，如果按照某種順序不能將所有token規約為一個token，解析器將會回溯重新選定規約順序。如果在規約（reduce）的過程中出現了既可以移進生成一個新的token，也可以規約為一個token，這種情況就是我們通常所說的shift/reduce conflicts.
Top-down parser
Top-down解析是從parse tree的頂層開始向下構造曆。這種解析的方法是假定輸入的解析字符串是符合當前定義的語法規則，按照規則的定義自頂開始逐漸向下遍曆。遍曆的過程中如果出現了不滿足語法內部的邏輯定義，解析器就會報出語法錯誤。
如果願意詳細了解這兩種parser的卻別，可以參考https://qntm.org/top。
MySQL8.0對parser所做的改進
Bison是一個bottom-up的parser。但是由於曆史原因，MySQL的語法輸入是按照Top-down的方式來書寫的。這樣的方式導致MySQL的parser語法上有包含了很多的reduce/shift conflicts；另外由於一些空的或者冗餘的規則定義也使得的MySQL parser越來越複雜。為了應對未來越來越多的語法規則，以及優化MySQL parser的解析性能，MySQL 8.0對MySQL parser做了非常大的改進。當前的MySQL 8.0.1 Milestone release的代碼中對於Parser的改進仍未全部完成，還有幾個相關的worklog在繼續。
改進之後，MySQL parser可以達到如下狀態：
- MySQL parser將會成為一個不涉及狀態信息（即：不包含執行狀態的上下文信息）的bottom-up parser；
- 減少parse tree上的中間節點，減少冗餘規則
- 更少的reduce/shift conflicts
- 語法解析階段，隻包含以下簡單操作：
- 創建parse tree node
- 返回解析的最終狀態信息
- 有限的訪問係統變量
- MySQL parser執行流程將會由
SQL input -> lex. scanner -> parser -> AST (SELECT_LEX, Items etc) -> executor
變成
SQL input -> lex. scanner -> parser -> parse tree -> AST -> executor
下麵我們通過看一個MySQL 8.0 中對SELECT statement所做的修改來看一下MySQL parser的改進。
SELECT statement可以說是MySQL中用處非常廣泛的一個語句，比如CREATE VIEW, SELECT, CREATE TABLE, UNION, SUBQUERY等操作。 通過下圖我們看一下MySQL8.0之前的版本是如何支持這些語法規則的。
MySQL8.0中對於這些語法規則的支持如下圖：
通過如上兩個圖的對比，顯然MySQL8.0的parser清爽了許多。當然我們也清晰的看到MySQL8.0中對於MySQL parser所做的改進。相同的語法規則隻有一處定義，消除了過去版本中按照top-down方式書寫的冗餘語法定義。當然通過這樣的簡化也可以看到實際的效果， shift/reduce conflicts也減少了很多：
下麵我們看看MySQL 8.0是如何將所有的SELECT statement操作定義為一個Query specification，並為所有其他操作所引用的：
Parse tree上所有的node都定義為Parse_tree_node的子類。Parse_tree_node的結構體定義如下：
typedef Parse_tree_node_tmpl<Parse_context> Parse_tree_node;
template<typename Context>
class Parse_tree_node_tmpl
{
...
private:
/*
False right after the node allocation. The contextualize/contextualize_
function turns it into true.
*/
#ifndef DBUG_OFF
bool contextualized;
#endif//DBUG_OFF
/*
這個變量是由於當前仍舊有未完成的相關worklog，parser的refactor還沒有徹底完成。當前的parser中還有一部分上下文依賴的關係沒有獨立出來。
等到整個parse refactor完成之後該變量就會被移除。
*/
bool transitional;
public:
/*
Memory allocation operator are overloaded to use mandatory MEM_ROOT
parameter for cheap thread-local allocation.
Note: We don't process memory allocation errors in refactored semantic
actions: we defer OOM error processing like other error parse errors and
process them all at the contextualization stage of the resulting parse
tree.
*/
static void *operator new(size_t size, MEM_ROOT *mem_root) throw ()
{ return alloc_root(mem_root, size); }
static void operator delete(void *ptr,size_t size) { TRASH(ptr, size); }
static void operator delete(void *ptr, MEM_ROOT *mem_root) {}
protected:
Parse_tree_node()
{
#ifndef DBUG_OFF
contextualized= false;
transitional= false;
#endif//DBUG_OFF
}
public:
...
/*
True if contextualize/contextualized function has done:
*/
#ifndef DBUG_OFF
bool is_contextualized() const { return contextualized; }
#endif//DBUG_OFF
/*
這個函數是需要被所有子類繼承的，所有子類需要定義屬於自己的上下文環境。通過調用子類的重載函數，進而初始化每個Parse tree node。
*/
virtual bool contextualize(THD *thd);
/**
my_parse_error() function replacement for deferred reporting of parse
errors
@param thd current THD
@param pos location of the error in lexical scanner buffers
*/
void error(THD *thd) const;
};
當前MySQL8.0的源碼中執行流程為：
mysql_parse
|
parse_sql
|
MYSQLparse
|
Parse_tree_node::contextualize() /* 經過Bison進行語法解析之後生成相應的Parse tree node。然後調用contextualize對Parse tree node進行上下文初始化。
初始化上下文後形成一個AST(Abstract Syntax Tree)節點。*/
接下來我們以SELECT statement來看一下PT_SELECT_STMT::contexualize()做些什麼工作：
class PT_select_stmt : public Parse_tree_node
{
bool contextualize(Parse_context *pc)
{
// 這裏初始化Parse_tree_node
if (super::contextualize(pc))
return true;
pc->thd->lex->sql_command= m_sql_command;
// 調用PT_query_specification來進行上下文初始化
return m_qe->contextualize(pc) ||
contextualize_safe(pc, m_into);
}
private:
PT_query_expression *m_qe；//通過m_qe來引用query_expression
}
class PT_query_expression : public Parse_tree_node
{
...
bool contextualize(Parse_context *pc)
{
// 判斷是否需要獨立的名空間
pc->select->set_braces(m_parentheses || pc->select->braces);
m_body->set_containing_qe(this);
if (Parse_tree_node::contextualize(pc) ||
// 初始化SELECT主體上下文
m_body->contextualize(pc))
return true;
// 這裏會初始化ORDER, LIMIT子句
if (!contextualized && contextualize_order_and_limit(pc))
return true;
// 這裏會對SELECT表達式裏包含的存儲過程或者UDF繼續進行上下文初始化
if (contextualize_safe(pc, m_procedure_analyse))
return true;
if (m_procedure_analyse && pc->select->master_unit()->outer_select() != NULL)
my_error(ER_WRONG_USAGE, MYF(0), "PROCEDURE", "subquery");
if (m_lock_type.is_set && !pc->thd->lex->is_explain())
{
pc->select->set_lock_for_tables(m_lock_type.lock_type);
pc->thd->lex->safe_to_cache_query= m_lock_type.is_safe_to_cache_query;
}
}
...
private：
bool contextualized;
PT_query_expression_body *m_body; /* 這個類包含了SELECT語句的主要部分，select_list, FROM, GROUP BY, HINTs等子句。
這裏m_body變量其實是PT_query_expression_body的子類 PT_query_expression_body_primary */
PT_order *m_order; // ORDER BY node
PT_limit_clause *m_limit; // LIMIT node
PT_procedure_analyse *m_procedure_analyse; //存儲過程相關
Default_constructible_locking_clause m_lock_type;
bool m_parentheses;
}
class PT_query_expression_body_primary : public PT_query_expression_body
{
{
if (PT_query_expression_body::contextualize(pc) ||
m_query_primary->contextualize(pc))
return true;
return false;
}
private：
PT_query_primary *m_query_primary; // 這裏是SELECT表達式的定義類PT_query_specification的父類
}
// PT_query_specification是SELECT表達式的定義類，它定義了SELECT表達式中絕大部分子句
class PT_query_specification : public PT_query_primary
{
typedef PT_query_primary super;
private:
PT_hint_list *opt_hints;
Query_options options;
PT_item_list *item_list;
PT_into_destination *opt_into1;
Mem_root_array_YY<PT_table_reference *> from_clause; // empty list for DUAL
Item *opt_where_clause;
PT_group *opt_group_clause;
Item *opt_having_clause;
bool PT_query_specification::contextualize(Parse_context *pc)
{
if (super::contextualize(pc))
return true;
pc->select->parsing_place= CTX_SELECT_LIST;
if (options.query_spec_options & SELECT_HIGH_PRIORITY)
{
Yacc_state *yyps= &pc->thd->m_parser_state->m_yacc;
yyps->m_lock_type= TL_READ_HIGH_PRIORITY;
yyps->m_mdl_type= MDL_SHARED_READ;
}
if (options.save_to(pc))
return true;
// 這裏開始初始化SELECT list項
if (item_list->contextualize(pc))
return true;
// Ensure we're resetting parsing place of the right select
DBUG_ASSERT(pc->select->parsing_place == CTX_SELECT_LIST);
pc->select->parsing_place= CTX_NONE;
// 初始化SELECT INTO子句
if (contextualize_safe(pc, opt_into1))
return true;
// 初始化FROM子句
if (!from_clause.empty())
{
if (contextualize_array(pc, &from_clause))
return true;
pc->select->context.table_list=
pc->select->context.first_name_resolution_table=
pc->select->table_list.first;
}
// 初始化WHERE條件
if (itemize_safe(pc, &opt_where_clause) ||
// 初始化GROUP子句
contextualize_safe(pc, opt_group_clause) ||
// 初始化HAVING子句
itemize_safe(pc, &opt_having_clause))
return true;
pc->select->set_where_cond(opt_where_clause);
pc->select->set_having_cond(opt_having_clause);
// 初始化HINTs
if (opt_hints != NULL)
{
if (pc->thd->lex->sql_command == SQLCOM_CREATE_VIEW)
{ // Currently this also affects ALTER VIEW.
push_warning_printf(pc->thd, Sql_condition::SL_WARNING,
ER_WARN_UNSUPPORTED_HINT,
ER_THD(pc->thd, ER_WARN_UNSUPPORTED_HINT),
"CREATE or ALTER VIEW");
}
else if (opt_hints->contextualize(pc))
return true;
}
return false;
}
綜上我們以SELECT statement為例對MySQL8.0在MySQL parser方麵所做的改進進行了簡單介紹。這樣的改進對於MySQL parser也許是一小步，但對於MySQL未來的可擴展確實是邁出了一大步。Parse tree獨立出來，通過Parse tree再來構建AST，這樣的方式下將簡化MySQL對於Parse tree的操作，最大的受益者就是Prepared statement。等到MySQL parse的所有worklog完成之後，MySQL用戶期盼多年的global prepared statement也就順其自然實現了。
當然MySQL parser的改進讓我們已經看到Oracle MySQL在對MySQL optimizier方麵對於PARSER，optimizer， executor三個階段的鬆解耦工作已經展開了。未來期待Optimizer生成的plan也可以像當前的parser一樣成為一個純粹的Plan，執行上下文與Plan也可以獨立開來。隻有到了executor階段才生成相應的執行上下文。這樣一來對於MySQL optimizer未來的可擴展勢必會起到如虎添翼的作用。
最後更新：2017-04-21 09:01:15