## 前言 從MySQL5.6版本開始支持InnoDB引擎的全文索引，語法層面上大多數兼容之前MyISAM的全文索引模式。所謂全文索引，是一種通過建立倒排索引，快速匹配文檔的方式。MySQL支持三種模式的全文檢索模式： 1. 自然語言模式（[IN NATURAL LANGUAGE MODE](http://dev.mysql.com/doc/refman/5.7/en/fulltext-natural-language.html)），即通過MATCH AGAINST 傳遞某個特定的字符串來進行檢索。 2. 布爾模式（[IN BOOLEAN MODE](http://dev.mysql.com/doc/refman/5.7/en/fulltext-boolean.html)），可以為檢索的字符串增加操作符，例如“+”表示必須包含，“-”表示不包含，“*”表示通配符（這種情況， 即使傳遞的字符串較小或出現在停詞中，也不會被過濾掉），其他還有很多特殊的布爾操作符，可以通過如下參數控制： ~~~ mysql> show variables like '%ft_boolean_syntax%'; +-------------------+----------------+ | Variable_name | Value | +-------------------+----------------+ | ft_boolean_syntax | + -><()~*:""&| | +-------------------+----------------+ 1 row in set (0.00 sec) ~~~ 3. 查詢擴展模式（[WITH QUERY EXPANSION](http://dev.mysql.com/doc/refman/5.7/en/fulltext-query-expansion.html)）, 這種模式是自然語言模式下的一個變種，會執行兩次檢索，第一次使用給定的短語進行檢索，第二次是結合第一次相關性比較高的行進行檢索。 目前MySQL支持在CHAR、VARCHAR、TEXT類型的列上定義全文索引。 本文只是簡單的分析了全文索引涉及到的代碼模塊以及5.7的一些新特性，源碼部分基于MySQL5.7.8-rc版本，更細節的部分并未深入。 ## 創建全文索引 如下例所示，一個簡單的創建帶全文索引表的SQL： ~~~ create table t1 (a int auto_increment primary key, b text, fulltext(b)); ~~~ 磁盤上會產生多個文件： ~~~ $ls -lh /u01/my57/data/test/ total 1.3M FTS_000000000000010b_0000000000000154_INDEX_1.ibd FTS_000000000000010b_0000000000000154_INDEX_2.ibd FTS_000000000000010b_0000000000000154_INDEX_3.ibd FTS_000000000000010b_0000000000000154_INDEX_4.ibd FTS_000000000000010b_0000000000000154_INDEX_5.ibd FTS_000000000000010b_0000000000000154_INDEX_6.ibd FTS_000000000000010b_BEING_DELETED_CACHE.ibd FTS_000000000000010b_BEING_DELETED.ibd FTS_000000000000010b_CONFIG.ibd FTS_000000000000010b_DELETED_CACHE.ibd FTS_000000000000010b_DELETED.ibd t1.frm t1.ibd ~~~ 除了t1.frm和t1.ibd外，共分為以下幾類表 1. FTS_000000000000010b_0000000000000154_INDEX_1~6.ibd這6個文件用于存儲倒排索引，存儲的是分詞和位置以及document ID，根據分詞的第一個字符值進行分區，映射到不同的文件中； 文件的命名規則為FTS_{TABLE_ID}_{INDEX_ID}_INDEX_{N}.ibd 2. FTS_000000000000010b_DELETED.ibd 包含已經被刪除的DOC_ID，但還沒從全文索引數據中刪掉； FTS_000000000000010b_DELETED_CACHE.ibd 是前者的內存緩存（但是搜索了下代碼，只有當`fts_cache_t::deleted_doc_ids`被使用時，才會在sync時轉儲到該表中，但并沒有發現任何地方使用這個對象） 3. FTS_000000000000010b_BEING_DELETED_CACHE.ibd 和 FTS_000000000000010b_BEING_DELETED.ibd，包含了已經被刪除索引記錄并且正在從全文索引中移除的DOC ID，前者是后者的內存版本，這兩個表主要用于輔助進行OPTIMIZE TABLE時將DELETED/DELETED_CACHED表中的記錄轉儲到其中。 4. FTS_000000000000010b_CONFIG.ibd，包含全文索引的內部信息，最重要的存儲是FTS_SYNCED_DOC_ID，表示已經解析并刷到磁盤的doc id， 在崩潰恢復時，可以根據這個值判斷哪些該重新解析并加入到索引cache中。 建全文索引輔助表函數參考： ~~~ ha_innobase::create |--> create_table_info_t::create_table |--> fts_create_common_tables ~~~ 當對一個已經存在的表上創建全文索引時，InnoDB采用了fork多個線程進行并發構建全文索引項的方法，并發度由參數?`innodb_ft_sort_pll_degree`?控制。因此在restore一個全文索引表時，我們建議先建表、導入數據，再在表上創建全文索引。 參考函數：`row_merge_read_clustered_index --> row_fts_start_psort` 線程回調函數為`fts_parallel_tokenization`。 當表上存在全文索引時，就會隱式的建立一個名為FTS_DOC_ID的列，并在其上創建一個唯一索引，用于標識分詞出現的記錄行。你也可以顯式的創建一個名為FTS_DOC_ID的列，但需要和隱式創建的列類型保持一致。 為了維護表上的全文索引信息，全文索引模塊定義了大量的類來進行管理，總的來說如下圖所示：  圖1\. 全文索引模塊 ## 普通DML及查詢操作 ### 插入 我們可以通過INNODB_FT_INDEX_CACHE來檢查插入記錄的分詞： ~~~ mysql> insert into t1 values (NULL, 'hello, welcome to mysql world'); Query OK, 1 row affected (1.87 sec) mysql> set global innodb_ft_aux_table = 'test/t1'; Query OK, 0 rows affected (0.00 sec) mysql> select * from INNODB_FT_INDEX_CACHE; +---------+--------------+-------------+-----------+--------+----------+ | WORD | FIRST_DOC_ID | LAST_DOC_ID | DOC_COUNT | DOC_ID | POSITION | +---------+--------------+-------------+-----------+--------+----------+ | hello | 2 | 2 | 1 | 2 | 0 | | mysql | 2 | 2 | 1 | 2 | 18 | | welcome | 2 | 2 | 1 | 2 | 7 | | world | 2 | 2 | 1 | 2 | 24 | +---------+--------------+-------------+-----------+--------+----------+ 4 rows in set (0.00 sec) ~~~ 在插入一條記錄時，對應的堆棧如下： ~~~ row_insert_for_mysql |--> row_insert_for_mysql_using_ins_graph |--> fts_trx_add_op // state = FTS_INSERT ~~~ 在向原表上插入完成記錄后，會去判斷表上是否有全文索引（DICT_TF2_FTS），如果有的話，則將插入記錄對應的doc id提取出來(`fts_get_doc_id_from_row`)，并緩存到事務對象中。 ### 刪除 刪除操作不會直接從全文索引里直接刪除，因此依然可以從INNODB_FT_INDEX_CACHE中查到分詞信息。 相關堆棧： ~~~ ha_innobase::delete_row |--> row_update_for_mysql |--> row_update_for_mysql_using_upd_graph |--> row_fts_update_or_delete |--> fts_trx_add_op // state = FTS_DELETE ~~~ ### 更新 更新非全文索引列，不會修改FTS_DOC_ID列的值。如果更新了全文索引列，在InnoDB的實現是刪除老的DOC，并插入新的DOC。 堆棧為： ~~~ ha_innobase::update_row |--> row_update_for_mysql |--> row_update_for_mysql_using_upd_graph |--> row_fts_update_or_delete |--> row_fts_do_update |--> fts_trx_add_op // state = FTS_DELETE |--> fts_trx_add_op // state = FTS_INSERT ~~~ 可見所有DML的操作，都走接口函數`fts_trx_add_op`，劃分為兩種操作: FTS_INSERT及FTS_DELETE；當前事務涉及的doc id被存儲到`trx->fts_trx`中，在執行SQL的過程中并沒有更新全文索引，而是在事務提交時進行的。 在緩存操作時，維護了兩個結構，一個是`trx->fts_trx->savepoints`，維護了事務全局的全文索引操作，另外一個是`trx->fts_trx->last_stmt`，維護的是當前SQL操作的doc id，前者在事務結束時處理，后者在SQL結束時清空。 ### 查詢 對于全文索引的查詢，采用新的接口函數，分為兩步: 1. 根據檢索詞搜集符合條件的doc id。 ~~~ JOIN::optimize |--> init_ftfuncs |--> Item_func_match::init_search |--> ha_innobase::ft_init_ext |--> fts_query ~~~ 在搜集滿足查詢條件的doc id時，首先讀取DELETED表中記錄的doc id，這些doc id隨后被用做過濾。 2. 根據搜集到的doc id，找到對應的記錄，使用的索引是`dict_table_t::fts_doc_id_index`，也就是建立在隱藏列FTS_DOC_ID上的唯一索引。 ~~~ sub_select |--> join_ft_read_first |--> ha_innobase::ft_init |--> ha_innobase::ft_read |--> join_ft_read_next |--> ha_innobase::ft_read ~~~ 通常查詢返回的結果是根據rank排序的，InnoDB的全文檢索排序規則和sphinx類似，基于 BM25 和 TF-IDF算法。 rank的計算算法如下： ~~~ ${IDF} = log10( ${total_records} / ${matching_records} ) // total_records表示總的行記錄數，matching_records表示匹配到檢索字的行記錄數 ${TF} 表示單詞在文檔中出現的次數 ${rank} = ${TF} * ${IDF} * ${IDF} ~~~ IDF的計算參閱函數：`fts_query_calculate_idf` ranking計算：`fts_query_calculate_ranking` 如果使用多個單詞匹配，則把各個單詞各自的rank累加起來。官方博客有[一篇文章](http://mysqlserverteam.com/rankings-with-innodb-full-text-search/)專門對此進行了介紹。 ## 事務操作 事務內回滾 正在事務內回滾某個語句，或者回滾到某個savepoint時，需要將對應的操作記錄也要刪除。維護了`trx->fts_trx->last_stmt`，在單條SQL結束時釋放(`trx_mark_sql_stat_end`)。如果SQL回滾，就根據last_stmt中維護的doc id從全局savepoints中清理掉本條SQL的doc id。 相關堆棧： ~~~ innobase_rollback --> trx_rollback_last_sql_stat_for_mysql |--> fts_savepoint_rollback_last_stmt |--> fts_undo_last_stmt |--> trx_mark_sql_stat_end |--> fts_savepoint_laststmt_refresh ~~~ 回滾到savepoint ~~~ innobase_rollback_to_savepoint |--> fts_savepoint_rollback ~~~ 事務提交 相關堆棧： ~~~ trx_commit_low |--> fts_commit // 處理trx->fts_trx->savepoints中緩存的全文索引操作 |--> fts_commit_table |--> fts_add |--> fts_add_doc_by_id |--> fts_delete |--> trx_commit_in_memory |--> trx_finalize_for_fts |--> trx_finalize_for_fts_table ~~~ 在調用fts_commit時，會根據不同的操作類型，調用fts_add增加全文索引項，調用fts_delete刪除全文索引項。 由于在插入記錄時，先分詞、分解成多個詞插入輔助表中，因此一條insert可能產生多個小的插入，這種寫入放大可能是不可承受的。InnoDB采用了一種優化的方案：創建一個內存cache，臨時緩存插入操作，當cache滿時再批量刷到磁盤，這樣做的好處是： * 避免重復存儲相同的單詞； * cache size 通過參數`innodb_ft_cache_size`控制； * 查詢會將cache和磁盤數據進行merge。 在事務提交時，調用函數`fts_add_doc_by_id`： * 首先根據doc id，使用doc_id所在的索引進行查詢，找到剛剛插入的記錄項對應的聚集索引記錄； * 遍歷表上全部的聚集索引，根據全文索引對應的`fts_get_doc_t`(`fts_cache_t::get_docs`)構建`fts_doc_t`，對文檔根據選擇的parser進行分詞(`fts_tokenize_document`函數或者`fts_tokenize_document_next`)，具體的文檔存儲到`fts_doc_t::text`中； * 將上一步獲得的分詞加入到cache中（`fts_cache_add_doc`）； * 如果當前cache的大小超過配置的`innodb_ft_cache_size`，或者全局cache的大小超過`innodb_ft_total_cache_size`(`fts_need_sync`被設置為true)，則進行一次sync，將該表緩存的數據刷到全文索引文件中(fts_sync)，并清空cache。 和插入相似，刪除操作也可能產生大量小的刪除操作，為了避免這種情況，維持一個表，來記錄被刪除的doc id，但記錄依然存在于原文件中。刪除操作的提交函數為`fts_delete`，將被刪除的記錄doc_id插入到DELETED輔助表中。 事務模塊涉及的幾個關鍵類包括：  圖2\. 全文索引事務模塊 ## 同步緩存 在滿足一定條件時，全文索引需要進行一次sync操作，將數據同步到全文索引文件中，大概包含以下集中情況需要sync： * cache數據占用的內存超過限制； * 后臺線程`fts_optimize_thread`在shutdown調用，將所有表進行一次sync； * `ha_innobase::optimize`調用（執行optimize table）； * `row_merge_read_clustered_index`：創建一個新的臨時表并讀入數據后，進行一次sync調用。 同步操作的入口函數為fts_sync，大體流程為： * 針對每個索引，調用函數`fts_sync_index`：通過函數`fts_select_index`計算寫入的索引文件，再將分詞節點信息寫入到文件（函數`fts_write_node`）, 倒排索引的記錄內容使用結構體`fts_node_t`進行描述，存儲結構如下圖所示：  圖3\. 倒排索引結點存儲結構 * 調用`fts_sync_commit`提交sync操作： * 更新CONFIG表記錄的最大SYNC的DOC ID（`fts_cmp_set_sync_doc_id`）； * 若`fts_cache_t::deleted_doc_ids`不為空，將其加入到DELETED_CACHE輔助表中（`fts_sync_add_deleted_cache`）； * 清空cache 并重新初始化。 ## Optimize table 當你修改了某些配置（例如最小token size時），或者希望重組全文索引時，可以執行optimize table。由于原始optimize table操作會產生整個表的重建，耗時太久，因此InnoDB引入了一個參數`innodb_optimize_fulltext_only`來控制該行為。當開啟該選項時，如果執行optimize table，就只優化全文索引，而不會去重建表，入口函數為ha_innobase::optimize： ~~~ ha_innobase::optimize |--> fts_sync_table |--> fts_optimize_table ~~~ 首先調用函數`fts_sync_table`，將表上在內存中cache的數據刷到全文索引文件中； 然后調用函數`fts_optimize_table`，我們主要分析集中在第二步。 `fts_optimize_table`函數流程如下： * 如果BEGING_DELETED表中沒有數據（例如第一次調用optimized table），則將DELETED表中的數據轉儲到BEING_DELETED表中，相當于拿到了一個快照，執行的SQL操作為： ~~~ static const char* fts_init_delete_sql = "BEGIN\n" "\n" "INSERT INTO $BEING_DELETED\n" "SELECT doc_id FROM $DELETED;\n" "\n" "INSERT INTO $BEING_DELETED_CACHE\n" "SELECT doc_id FROM $DELETED_CACHE;\n"; ~~~ 參考函數：`fts_optimize_create_deleted_doc_id_snapshot` * 從BEING_DELETED/BEING_DELETED_CACHE表中讀取已經被刪除的doc id，這些doc id在隨后的索引優化中將被忽略掉。 參考函數：`fts_optimize_read_deleted_doc_id_snapshot` * 調用`fts_optimize_indexes`?對每個索引進行優化，相關堆棧如下： ~~~ fts_optimize_indexes |--> fts_optimize_index |--> fts_optimize_index_read_words // 讀入需要進行優化的分詞，一輪優化的個數不超過innodb_ft_num_word_optimize的配置值 // 緩存的分詞數據采用zlib進行壓縮 |--> fts_optimize_words // 讀取分詞，將已經刪除的doc id從其中清除，并回寫到db |--> fts_index_fetch_nodes // 逐個讀取分詞對應的全文索引項 |--> fts_optimize_compact |--> fts_optimize_word // 判斷是否包含被刪除的doc id，并重組記錄 |--> fts_optimize_write_word // 將記錄寫回索引，具體操作為先刪除老的記錄，再插入新的記錄 |--> fts_config_set_index_value //更新CONFIG表的FTS_LAST_OPTIMIZED_WORD列，記錄最近重組優化的分詞 |--> fts_optimize_index_completed // 若上述步驟將讀取的分詞全部處理完了，則本輪optimize操作完成 ~~~ * 當在所有索引上完成optimize后，調用fts_optimize_purge_snapshot，主要操作包括： * 從DELETE和DELETE_CACHE表中將doc id刪除，參考函數fts_optimize_purge_deleted_doc_ids ~~~ static const char* fts_delete_doc_ids_sql = "BEGIN\n" "\n" "DELETE FROM $DELETED WHERE doc_id = :doc_id1;\n" "DELETE FROM $DELETED_CACHE WHERE doc_id = :doc_id2;\n"; ~~~ * 從BEING_DELETED及BEING_DELETED_CACHE中刪除對應的doc id。 ~~~ static const char* fts_end_delete_sql = "BEGIN\n" "\n" "DELETE FROM $BEING_DELETED;\n" "DELETE FROM $BEING_DELETED_CACHE;\n"; ~~~ 參考函數：?`fts_optimize_purge_deleted_doc_id_snapshot` ## 后臺線程 InnoDB啟動時，會創建一個后臺線程，線程函數為`fts_optimize_thread`，工作隊列為`fts_optimize_wq`，其主要目的是在滿足一定條件時，對表自動進行optimize操作。 在如下兩種情況，會向`fts_optimize_wq`中增加元組： * `fts_optimize_add_table`: 創建或打開一個新的帶全文索引的表時，創建一個類型為`FTS_MSG_ADD_TABLE`并包含表對象指針的MSG，加入到`fts_optimize_wq`中，這些表禁止被從數據詞典中驅逐； * `fts_optimize_remove_table`: 刪除表、DDL、釋放表對象(`dict_mem_table_free`)、刪除全文索引(`fts_drop_index`)等操作時，會創建一個類型為`FTS_MSG_DEL_TABLE的MEG`，加入到`fts_optimize_wq`隊列中。 fts optimize線程對于FTS_MSG_ADD_TABLE類型的會將相應的表加入到調度隊列，對于FTS_MSG_DEL_TABLE，則從調度隊列中刪除。其調度隊列的成員類型為`fts_slot_t`。 當表上刪除的數據量超過一千萬(FTS_OPTIMIZE_THRESHOLD)行時，就會觸發一次自動optimize table，但兩次optimize的間隔不應低于300秒（FTS_OPTIMIZE_INTERVAL_IN_SECS）。 ## 監控 我們可以通過幾個INFORMATION_SCHEMA下的全文索引表來監控全文索引狀態。 ~~~ mysql> show tables like '%ft%'; +-------------------------------------+ | Tables_in_information_schema (%ft%) | +-------------------------------------+ | INNODB_FT_CONFIG | | INNODB_FT_BEING_DELETED | | INNODB_FT_DELETED | | INNODB_FT_DEFAULT_STOPWORD | | INNODB_FT_INDEX_TABLE | | INNODB_FT_INDEX_CACHE | +-------------------------------------+ 6 rows in set (0.00 sec) ~~~ 想要從information_schema表中查詢信息，需要先設置變量`innodb_ft_aux_table`，值為你要查詢表的”dbname/tablename”。 ## 全文索引停詞 停詞(STOP WORD)用于在分詞時忽略那些常見的不重要的單詞，InnoDB目前內建的停詞可以從information_schema.INNODB_FT_DEFAULT_STOPWORD讀取，用戶也可以自己定義停詞列表，方法很簡單：創建一個和nformation_schema.INNODB_FT_DEFAULT_STOPWORD一模一樣的表，將你想要的停詞加入到其中，然后設置`innodb_ft_server_stopword_table`值為你創建的表名：”dbname/tabname”。 你也可以使用會話級別的參數`innodb_ft_user_stopword_table`來指定你想要的停詞表，和上述創建規則一致，具體的參閱[官方文檔](http://dev.mysql.com/doc/refman/5.7/en/fulltext-stopwords.html)。 另外配置項`innodb_ft_min_token_size`及`innodb_ft_max_token_size`?用于表示一個單詞的字符長度范圍，在這個范圍的連續字符串才會被當作一個單詞。然而如果使用ngram解析器的話，有效單詞長度受參數`ngram_token_size`控制。 可以關閉參數`innodb_ft_enable_stopword`，這樣在分詞時也會把預設的停詞考慮進去。 ## InnoDB全文索引插件 從MySQL 5.7.3開始InnoDB支持全文索引插件，用戶可以以Plugin的模式來定義自己的分詞規則，或是引入社區開發的全文索引解析器，例如某些專業領域的分詞，可能具有不同的規則。 全文索引插件有兩種角色：第一種是替換內建的parser，讀取輸入文檔，進行解析后，將分詞傳送給server；另一種角色是作為內建parser的協作者，可以把輸入文檔處理過后，再傳送給內建parser。 如果你已經有一個基于MYISAM的全文索引插件了，也可以根據[這篇官方文檔](http://mysqlserverteam.com/innodb-supports-plugin-parser-in-fulltext-index/)的介紹，將其修改成InnoDB全文索引插件。 ## InnoDB N-gram parser 從MySQL5.7.6版本開始提供了一種內建的全文索引ngram parser，可以很好的支持CJK字符集（中文、日文、韓文），CJK有個共同點就是單詞不像英語習慣那樣根據空格進行分解的，因此傳統的內建分詞方式無法準確的對類似中文進行分詞。 ngram parser內建在代碼中，該解析器默安裝，你可以通過指定索引屬性（`WITH PARSER ngram`）來利用該parser，例如： ~~~ mysql> create table ft_test(id int, content text, fulltext (content) with parser ngram); Query OK, 0 rows affected (0.26 sec) ~~~ N-Gram使用一種特殊的方式來進行分詞，舉個簡單的例子，假設要對單詞’abcd’進行分詞，那么其分詞結果為： ~~~ N=1 : 'a', 'b', 'c', 'd'; N=2 : 'ab', 'bc', 'cd'; N=3 : 'abc', 'bcd'; N=4 : 'abcd'; ~~~ N取決于`ngram_token_size`的設置，默認值為2。 對于停詞的處理，N-Gram和默認的parser不同，即只要每個token包含了（而不是精確匹配）停詞，就不對其進行索引；另外空格總是作為一個停詞，因此在分詞取token時，空格會被忽略掉。 在執行查詢時，用戶傳遞的搜索詞也會基于N-Gram進行分解后進行檢索。 具體的例子可以參閱[官方博客](http://mysqlserverteam.com/innodb-full-text-n-gram-parser/)的描述。 除了N-gram parser外，官方也支持了另外一種名為[MeCab Parser](http://mysqlserverteam.com/innodb-full-text-mecab-parser/)的插件，主要用于日語分詞，但需要手動安裝。