从MySQL5.6版本开始支持InnoDB引擎的全文索引,语法层面上大多数兼容之前MyISAM的全文索引模式。所谓全文索引,是一种通过建立倒排索引,快速匹配文档的方式。MySQL支持三种模式的全文检索模式:
- mysql> show variables like '%ft_boolean_syntax%';
- +-------------------+----------------+
- | Variable_name | Value |
- +-------------------+----------------+
- | ft_boolean_syntax | + -><()~*:""&| |
- +-------------------+----------------+
- 1 row in set (0.00 sec)
目前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外,共分为以下几类表
被使用时,才会在sync时转储到该表中,但并没有发现任何地方使用这个对象)
- fts_cache_t::deleted_doc_ids
建全文索引辅助表函数参考:
- ha_innobase::create
- |--> create_table_info_t::create_table
- |--> fts_create_common_tables
当对一个已经存在的表上创建全文索引时,InnoDB采用了fork多个线程进行并发构建全文索引项的方法,并发度由参数
控制。因此在restore一个全文索引表时,我们建议先建表、导入数据,再在表上创建全文索引。
- innodb_ft_sort_pll_degree
参考函数:
线程回调函数为
- row_merge_read_clustered_index --> row_fts_start_psort
。
- fts_parallel_tokenization
当表上存在全文索引时,就会隐式的建立一个名为FTS_DOC_ID的列,并在其上创建一个唯一索引,用于标识分词出现的记录行。你也可以显式的创建一个名为FTS_DOC_ID的列,但需要和隐式创建的列类型保持一致。
为了维护表上的全文索引信息,全文索引模块定义了大量的类来进行管理,总的来说如下图所示:
图1. 全文索引模块
我们可以通过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_INSERT及FTS_DELETE;当前事务涉及的doc id被存储到
- fts_trx_add_op
中,在执行SQL的过程中并没有更新全文索引,而是在事务提交时进行的。
- trx->fts_trx
在缓存操作时,维护了两个结构,一个是
,维护了事务全局的全文索引操作,另外一个是
- trx->fts_trx->savepoints
,维护的是当前SQL操作的doc id,前者在事务结束时处理,后者在SQL结束时清空。
- trx->fts_trx->last_stmt
对于全文索引的查询,采用新的接口函数,分为两步:
在搜集满足查询条件的doc id时,首先读取DELETED表中记录的doc id,这些doc id随后被用做过滤。
- JOIN::optimize
- |--> init_ftfuncs
- |--> Item_func_match::init_search
- |--> ha_innobase::ft_init_ext
- |--> fts_query
,也就是建立在隐藏列FTS_DOC_ID上的唯一索引。
- dict_table_t::fts_doc_id_index
- 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的计算参阅函数:
ranking计算:
- fts_query_calculate_idf
- fts_query_calculate_ranking
如果使用多个单词匹配,则把各个单词各自的rank累加起来。官方博客有一篇文章专门对此进行了介绍。
事务内回滚
正在事务内回滚某个语句,或者回滚到某个savepoint时,需要将对应的操作记录也要删除。维护了
,在单条SQL结束时释放(
- trx->fts_trx->last_stmt
)。如果SQL回滚,就根据last_stmt中维护的doc id从全局savepoints中清理掉本条SQL的doc id。
- trx_mark_sql_stat_end
相关堆栈:
- 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满时再批量刷到磁盘,这样做的好处是:
控制;
- innodb_ft_cache_size
在事务提交时,调用函数
:
- fts_add_doc_by_id
(
- fts_get_doc_t
)构建
- fts_cache_t::get_docs
,对文档根据选择的parser进行分词(
- fts_doc_t
函数或者
- fts_tokenize_document
),具体的文档存储到
- fts_tokenize_document_next
中;
- fts_doc_t::text
);
- fts_cache_add_doc
,或者全局cache的大小超过
- innodb_ft_cache_size
(
- innodb_ft_total_cache_size
被设置为true),则进行一次sync,将该表缓存的数据刷到全文索引文件中(fts_sync),并清空cache。
- fts_need_sync
和插入相似,删除操作也可能产生大量小的删除操作,为了避免这种情况,维持一个表,来记录被删除的doc id,但记录依然存在于原文件中。删除操作的提交函数为
,将被删除的记录doc_id插入到DELETED辅助表中。
- fts_delete
事务模块涉及的几个关键类包括:
图2. 全文索引事务模块
在满足一定条件时,全文索引需要进行一次sync操作,将数据同步到全文索引文件中,大概包含以下集中情况需要sync:
在shutdown调用,将所有表进行一次sync;
- fts_optimize_thread
调用(执行optimize table);
- ha_innobase::optimize
:创建一个新的临时表并读入数据后,进行一次sync调用。
- row_merge_read_clustered_index
同步操作的入口函数为fts_sync,大体流程为:
:通过函数
- fts_sync_index
计算写入的索引文件,再将分词节点信息写入到文件(函数
- fts_select_index
), 倒排索引的记录内容使用结构体
- fts_write_node
进行描述,存储结构如下图所示:
- fts_node_t
图3. 倒排索引结点存储结构
提交sync操作:
- fts_sync_commit
);
- fts_cmp_set_sync_doc_id
不为空,将其加入到DELETED_CACHE辅助表中(
- fts_cache_t::deleted_doc_ids
);
- fts_sync_add_deleted_cache
当你修改了某些配置(例如最小token size时),或者希望重组全文索引时,可以执行optimize table。由于原始optimize table操作会产生整个表的重建,耗时太久,因此InnoDB引入了一个参数
来控制该行为。当开启该选项时,如果执行optimize table,就只优化全文索引,而不会去重建表,入口函数为ha_innobase::optimize:
- innodb_optimize_fulltext_only
- ha_innobase::optimize
- |--> fts_sync_table
- |--> fts_optimize_table
首先调用函数
,将表上在内存中cache的数据刷到全文索引文件中; 然后调用函数
- fts_sync_table
,我们主要分析集中在第二步。
- fts_optimize_table
函数流程如下:
- fts_optimize_table
- 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
- 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操作完成
- 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";
参考函数:
- 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
,其主要目的是在满足一定条件时,对表自动进行optimize操作。
- fts_optimize_wq
在如下两种情况,会向
中增加元组:
- fts_optimize_wq
: 创建或打开一个新的带全文索引的表时,创建一个类型为
- fts_optimize_add_table
并包含表对象指针的MSG,加入到
- FTS_MSG_ADD_TABLE
中,这些表禁止被从数据词典中驱逐;
- fts_optimize_wq
: 删除表、DDL、释放表对象(
- fts_optimize_remove_table
)、删除全文索引(
- 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表中查询信息,需要先设置变量
,值为你要查询表的”dbname/tablename”。
- innodb_ft_aux_table
停词(STOP WORD)用于在分词时忽略那些常见的不重要的单词,InnoDB目前内建的停词可以从information_schema.INNODB_FT_DEFAULT_STOPWORD读取,用户也可以自己定义停词列表,方法很简单:创建一个和nformation_schema.INNODB_FT_DEFAULT_STOPWORD一模一样的表,将你想要的停词加入到其中,然后设置
值为你创建的表名:”dbname/tabname”。
- innodb_ft_server_stopword_table
你也可以使用会话级别的参数
来指定你想要的停词表,和上述创建规则一致,具体的参阅官方文档。
- innodb_ft_user_stopword_table
另外配置项
及
- innodb_ft_min_token_size
用于表示一个单词的字符长度范围,在这个范围的连续字符串才会被当作一个单词。然而如果使用ngram解析器的话,有效单词长度受参数
- innodb_ft_max_token_size
控制。
- ngram_token_size
可以关闭参数
,这样在分词时也会把预设的停词考虑进去。
- innodb_ft_enable_stopword
从MySQL 5.7.3开始InnoDB支持全文索引插件,用户可以以Plugin的模式来定义自己的分词规则,或是引入社区开发的全文索引解析器,例如某些专业领域的分词,可能具有不同的规则。
全文索引插件有两种角色:第一种是替换内建的parser,读取输入文档,进行解析后,将分词传送给server;另一种角色是作为内建parser的协作者,可以把输入文档处理过后,再传送给内建parser。
如果你已经有一个基于MYISAM的全文索引插件了,也可以根据这篇官方文档的介绍,将其修改成InnoDB全文索引插件。
从MySQL5.7.6版本开始提供了一种内建的全文索引ngram parser,可以很好的支持CJK字符集(中文、日文、韩文),CJK有个共同点就是单词不像英语习惯那样根据空格进行分解的,因此传统的内建分词方式无法准确的对类似中文进行分词。
ngram parser内建在代码中,该解析器默安装,你可以通过指定索引属性(
)来利用该parser,例如:
- WITH PARSER ngram
- 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取决于
的设置,默认值为2。
- ngram_token_size
对于停词的处理,N-Gram和默认的parser不同,即只要每个token包含了(而不是精确匹配)停词,就不对其进行索引;另外空格总是作为一个停词,因此在分词取token时,空格会被忽略掉。
在执行查询时,用户传递的搜索词也会基于N-Gram进行分解后进行检索。 具体的例子可以参阅官方博客的描述。
除了N-gram parser外,官方也支持了另外一种名为MeCab Parser的插件,主要用于日语分词,但需要手动安装。
来源: http://mysql.taobao.org/monthly/2015/10/01/