index condition pushdown

Index condition pushdown(ICP)是直到mysql5.6才引入的特性，主要是为了减少通过二级索引查找主键索引的次数。目前ICP相关的文章也比较多，本文主要从源码角度介绍ICP的实现。讨论之前，我们先再温习下。

以下图片来自mariadb

  • 引入ICP之前 screenshot.png

  • 引入ICP之后 screenshot.png

再来看个例子

  1. CREATE TABLE `t1` (
  2.   `a` int(11) DEFAULT NULL,
  3.   `b` char(8) DEFAULT NULL,
  4.   `c` int(11) DEFAULT '0',
  5.   `pk` int(11) NOT NULL AUTO_INCREMENT,
  6.   PRIMARY KEY (`pk`),
  7.   KEY `idx1` (`a`,`b`)
  8. ) ENGINE=ROCKSDB;
  9. INSERT INTO t1 (a,b) VALUES (1,'a'),(2,'b'),(3,'c');
  10. INSERT INTO t1 (a,b) VALUES (4,'a'),(4,'b'),(4,'c'),(4,'d'),(4,'e'),(4,'f');
  12. set optimizer_switch='index_condition_pushdown=off';
  14. ## 关闭ICP(Using where)
  15. explain select * from t1 where a=4 and b!='e';
  16. +----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
  17. | id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra       |
  18. +----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
  19. |  1 | SIMPLE      | t1    | range | idx1          | idx1 | 14      | NULL |    2 | Using where |
  20. +----+-------------+-------+-------+---------------+------+---------+------+------+-------------+
  22. ## 关闭ICP走cover index(Using where; Using index)
  23. explain select a,b from t1 where a=4 and b!='e';
  24. +----+-------------+-------+------+---------------+------+---------+-------+------+--------------------------+
  25. | id | select_type | table | type | possible_keys | key  | key_len | ref   | rows | Extra                    |
  26. +----+-------------+-------+------+---------------+------+---------+-------+------+--------------------------+
  27. |  1 | SIMPLE      | t1    | ref  | idx1          | idx1 | 5       | const |    4 | Using where; Using index |
  28. +----+-------------+-------+------+---------------+------+---------+-------+------+--------------------------+
  30. set optimizer_switch='index_condition_pushdown=on';
  32. ## 开启ICP(Using index conditione)
  33. explain select * from t1 where a=4 and b!='e';
  34. +----+-------------+-------+-------+---------------+------+---------+------+------+-----------------------+
  35. | id | select_type | table | type  | possible_keys | key  | key_len | ref  | rows | Extra                 |
  36. +----+-------------+-------+-------+---------------+------+---------+------+------+-----------------------+
  37. |  1 | SIMPLE      | t1    | range | idx1          | idx1 | 14      | NULL |    2 | Using index condition |
  38. +----+-------------+-------+-------+---------------+------+---------+------+------+-----------------------+
  40. ## 开启ICP仍然是cover index(Using where; Using index)
  41. explain select a,b from t1 where a=4 and b!='e';
  42. +----+-------------+-------+------+---------------+------+---------+-------+------+--------------------------+
  43. | id | select_type | table | type | possible_keys | key  | key_len | ref   | rows | Extra                    |
  44. +----+-------------+-------+------+---------------+------+---------+-------+------+--------------------------+
  45. |  1 | SIMPLE      | t1    | ref  | idx1          | idx1 | 5       | const |    4 | Using where; Using index |
  46. +----+-------------+-------+------+---------------+------+---------+-------+------+--------------------------+

这里总结下ICP的条件

server层主要负责判断是否符合ICP的条件，符合ICP则把需要的condition push到engine层。 engine层通过二级索引查找数据时，用server层push的condition再做一次判断，如果符合条件才会去查找主索引。

目前mysql支持ICP的引擎有MyISAM和InnoDB,MyRocks引入rocksdb后，也支持了ICP。 server层实现是一样的，engine层我们主要介绍innodb和rocksdb的实现。

server层

关键代码片段如下

  1. make_join_readinfo()
  3. switch (tab->type) {
  4.     case JT_EQ_REF:
  5.     case JT_REF_OR_NULL:
  6.     case JT_REF:
  7.       if (tab->select)
  8.         tab->select->set_quick(NULL);
  9.       delete tab->quick;
  10.       tab->quick=0;
  11.       /* fall through */
  12.     case JT_SYSTEM:
  13.     case JT_CONST:
  14.       /* Only happens with outer joins */
  15.       if (setup_join_buffering(tab, join, options, no_jbuf_after,
  16.                                &icp_other_tables_ok))
  17.         DBUG_RETURN(true);
  18.       if (tab->use_join_cache != JOIN_CACHE::ALG_NONE)
  19.         tab[-1].next_select= sub_select_op;
  21.       if (table->covering_keys.is_set(tab->ref.key) &&
  22.           !table->no_keyread)
  23.         table->set_keyread(TRUE);
  24.       else
  25.         push_index_cond(tab, tab->ref.key, icp_other_tables_ok,
  26.                         &trace_refine_table);
  27.       break;

从代码中看出只有符合的类型range, ref, eq_ref, and ref_or_null 二级索引才可能会push_index_cond。

而这里通过covering_keys来判断并排除使用了cover index的情况。covering_keys是一个bitmap，保存了所有可能用到的覆盖索引。在解析查询列以及条件列时会设置covering_keys，详细可以参考setup_fields，setup_wild，setup_conds。

engine层

innodb

innodb在扫描二级索引时会根据是否有push condition来检查记录是否符合条件(row_search_idx_cond_check) 逻辑如下：

  1. row_search_for_mysql()
  2. ......
  3.   if (prebuilt->idx_cond)
  4.   {
  5.       row_search_idx_cond_check //检查condition
  6.       row_sel_get_clust_rec_for_mysql //检查通过了才会去取主索引数据
  7.   }
  8. ....

典型的堆栈如下

  1. handler::compare_key_icp
  2. innobase_index_cond
  3. row_search_idx_cond_check
  4. row_search_for_mysql
  5. ha_innobase::index_read
  6. ha_innobase::index_first
  7. ha_innobase::rnd_next
  8. handler::ha_rnd_next
  9. rr_sequential
  10. join_init_read_record
  11. sub_select
  12. do_select

rocksdb

rocksdb在扫描二级索引时也会根据是否有push condition来检查记录是否符合条件

逻辑如下

  1. read_row_from_secondary_key()
  2. {
  3.    find_icp_matching_index_rec//push了condition才会检查condition
  4.    get_row_by_rowid//检查通过了才会去取主索引数据
  5. }

典型的堆栈如下

  1. handler::compare_key_icp
  2. myrocks::ha_rocksdb::check_index_cond
  3. myrocks::ha_rocksdb::find_icp_matching_index_rec 
  4. myrocks::ha_rocksdb::read_row_from_secondary_key 
  5. myrocks::ha_rocksdb::index_read_map_impl 
  6. myrocks::ha_rocksdb::read_range_first
  7. handler::multi_range_read_next

other

ICP对cover index作出了严格的限制，而实际上应该可以放开此限制，这样可以减少enging层传第给server层的数据量，至少可以减少server层的内存使用。欢迎指正！