SQL中的where条件,在数据库中提取与应用浅析

3月 3rd, 2013

1        问题描述

一条SQL,在数据库中是如何执行的呢?相信很多人都会对这个问题比较感兴趣。当然,要完整描述一条SQL在数据库中的生命周期,这是一个非常巨大的问题,涵盖了SQL的词法解析、语法解析、权限检查、查询优化、SQL执行等一系列的步骤,简短的篇幅是绝对无能为力的。因此,本文挑选了其中的部分内容,也是我一直都想写的一个内容,做重点介绍:

 

给定一条SQL,如何提取其中的where条件?where条件中的每个子条件,在SQL执行的过程中有分别起着什么样的作用?

 

通过本文的介绍,希望读者能够更好地理解查询条件对于SQL语句的影响;撰写出更为优质的SQL语句;更好地理解一些术语,例如:MySQL 5.6中一个重要的优化——Index Condition Pushdown,究竟push down了什么?

 

本文接下来的内容,安排如下:

  1. 简单介绍关系型数据库中数据的组织形式;
  2. 给定一条SQL,如何提取其中的where条件;
  3. 最后做一个小的总结;

 

2        关系型数据库中的数据组织

 

关系型数据库中,数据组织涉及到两个最基本的结构:表与索引。表中存储的是完整记录,一般有两种组织形式:堆表(所有的记录无序存储),或者是聚簇索引表(所有的记录,按照记录主键进行排序存储)。索引中存储的是完整记录的一个子集,用于加速记录的查询速度,索引的组织形式,一般均为B+树结构。

 

有了这些基本知识之后,接下来让我们创建一张测试表,为表新增几个索引,然后插入几条记录,最后看看表的完整数据组织、存储结构式怎么样的。(注意:下面的实例,使用的表的结构为堆表形式,这也是Oracle/DB2/PostgreSQL等数据库采用的表组织形式,而不是InnoDB引擎所采用的聚簇索引表。其实,表结构采用何种形式并不重要,最重要的是理解下面章节的核心,在任何表结构中均适用)

 

create table t1 (a int primary key, b int, c int, d int, e varchar(20));

 

create index idx_t1_bcd on t1(b, c, d);

 

insert into t1 values (4,3,1,1,’d’);

insert into t1 values (1,1,1,1,’a’);

insert into t1 values (8,8,8,8,’h’):

insert into t1 values (2,2,2,2,’b’);

insert into t1 values (5,2,3,5,’e’);

insert into t1 values (3,3,2,2,’c’);

insert into t1 values (7,4,5,5,’g’);

insert into t1 values (6,6,4,4,’f’);

 

t1表的存储结构如下图所示(只画出了idx_t1_bcd索引与t1表结构,没有包括t1表的主键索引):

 

t1表的组织结构图

 

 

简单分析一下上图,idx_t1_bcd索引上有[b,c,d]三个字段(注意:若是InnoDB类的聚簇索引表,idx_t1_bcd上还会包括主键a字段),不包括[a,e]字段。idx_t1_bcd索引,首先按照b字段排序,b字段相同,则按照c字段排序,以此类推。记录在索引中按照[b,c,d]排序,但是在堆表上是乱序的,不按照任何字段排序。

 

3        SQL的where条件提取

 

在有了以上的t1表之后,接下来就可以在此表上进行SQL查询了,获取自己想要的数据。例如,考虑以下的一条SQL:

 

select * from t1 where b >= 2 and b < 8 and c > 1 and d != 4 and e != ‘a’;

 

一条比较简单的SQL,一目了然就可以发现where条件使用到了[b,c,d,e]四个字段,而t1表的idx_t1_bcd索引,恰好使用了[b,c,d]这三个字段,那么走idx_t1_bcd索引进行条件过滤,应该是一个不错的选择。接下来,让我们抛弃数据库的思想,直接思考这条SQL的几个关键性问题:

 

l         此SQL,覆盖索引idx_t1_bcd上的哪个范围?

 

起始范围:记录[2,2,2]是第一个需要检查的索引项。索引起始查找范围由b >= 2,c > 1决定。

终止范围:记录[8,8,8]是第一个不需要检查的记录,而之前的记录均需要判断。索引的终止查找范围由b < 8决定;

 

2        在确定了查询的起始、终止范围之后,SQL中还有哪些条件可以使用索引idx_t1_bcd过滤?

 

根据SQL,固定了索引的查询范围[(2,2,2),(8,8,8))之后,此索引范围中并不是每条记录都是满足where查询条件的。例如:(3,1,1)不满足c > 1的约束;(6,4,4)不满足d != 4的约束。而c,d列,均可在索引idx_t1_bcd中过滤掉不满足条件的索引记录的。

因此,SQL中还可以使用c > 1 and d != 4条件进行索引记录的过滤。

 

3        在确定了索引中最终能够过滤掉的条件之后,还有哪些条件是索引无法过滤的?

 

此问题的答案显而易见,e != ‘a’这个查询条件,无法在索引idx_t1_bcd上进行过滤,因为索引并未包含e列。e列只在堆表上存在,为了过滤此查询条件,必须将已经满足索引查询条件的记录回表,取出表中的e列,然后使用e列的查询条件e != ‘a’进行最终的过滤。

 

在理解以上的问题解答的基础上,做一个抽象,可总结出一套放置于所有SQL语句而皆准的where查询条件的提取规则:

 

所有SQLwhere条件,均可归纳为3大类:Index Key (First Key & Last Key)Index FilterTable Filter

 

接下来,让我们来详细分析者3大类分别是如何定义,以及如何提取的。

 

l         Index Key

 

用于确定SQL查询在索引中的连续范围(起始范围+结束范围)的查询条件,被称之为Index Key。由于一个范围,至少包含一个起始与一个终止,因此Index Key也被拆分为Index First Key和Index Last Key,分别用于定位索引查找的起始,以及索引查询的终止条件。

 

Index First Key

 

用于确定索引查询的起始范围。提取规则:从索引的第一个键值开始,检查其在where条件中是否存在,若存在并且条件是=、>=,则将对应的条件加入Index First Key之中,继续读取索引的下一个键值,使用同样的提取规则;若存在并且条件是>,则将对应的条件加入Index First Key中,同时终止Index First Key的提取;若不存在,同样终止Index First Key的提取。

针对上面的SQL,应用这个提取规则,提取出来的Index First Key为(b >= 2, c > 1)。由于c的条件为 >,提取结束,不包括d。

 

Index Last Key

 

Index Last Key的功能与Index First Key正好相反,用于确定索引查询的终止范围。提取规则:从索引的第一个键值开始,检查其在where条件中是否存在,若存在并且条件是=、<=,则将对应条件加入到Index Last Key中,继续提取索引的下一个键值,使用同样的提取规则;若存在并且条件是 < ,则将条件加入到Index Last Key中,同时终止提取;若不存在,同样终止Index Last Key的提取。

针对上面的SQL,应用这个提取规则,提取出来的Index Last Key为(b < 8),由于是 < 符号,因此提取b之后结束。

 

2         Index Filter

 

在完成Index Key的提取之后,我们根据where条件固定了索引的查询范围,但是此范围中的项,并不都是满足查询条件的项。在上面的SQL用例中,(3,1,1),(6,4,4)均属于范围中,但是又均不满足SQL的查询条件。

Index Filter的提取规则:同样从索引列的第一列开始,检查其在where条件中是否存在:若存在并且where条件仅为 =,则跳过第一列继续检查索引下一列,下一索引列采取与索引第一列同样的提取规则;若where条件为 >=、>、<、<= 其中的几种,则跳过索引第一列,将其余where条件中索引相关列全部加入到Index Filter之中;若索引第一列的where条件包含 =、>=、>、<、<= 之外的条件,则将此条件以及其余where条件中索引相关列全部加入到Index Filter之中;若第一列不包含查询条件,则将所有索引相关条件均加入到Index Filter之中。

针对上面的用例SQL,索引第一列只包含 >=、< 两个条件,因此第一列可跳过,将余下的c、d两列加入到Index Filter中。因此获得的Index Filter为 c > 1 and d != 4 。

 

3         Table Filter

 

Table Filter是最简单,最易懂,也是提取最为方便的。提取规则:所有不属于索引列的查询条件,均归为Table Filter之中。

同样,针对上面的用例SQL,Table Filter就为 e != ‘a’。

 

3.1 Index Key/Index Filter/Table Filter小结 

 

SQL语句中的where条件,使用以上的提取规则,最终都会被提取到Index Key (First Key & Last Key),Index Filter与Table Filter之中。

 

Index First Key,只是用来定位索引的起始范围,因此只在索引第一次Search Path(沿着索引B+树的根节点一直遍历,到索引正确的叶节点位置)时使用,一次判断即可;

 

Index Last Key,用来定位索引的终止范围,因此对于起始范围之后读到的每一条索引记录,均需要判断是否已经超过了Index Last Key的范围,若超过,则当前查询结束;

 

Index Filter,用于过滤索引查询范围中不满足查询条件的记录,因此对于索引范围中的每一条记录,均需要与Index Filter进行对比,若不满足Index Filter则直接丢弃,继续读取索引下一条记录;

 

Table Filter,则是最后一道where条件的防线,用于过滤通过前面索引的层层考验的记录,此时的记录已经满足了Index First Key与Index Last Key构成的范围,并且满足Index Filter的条件,回表读取了完整的记录,判断完整记录是否满足Table Filter中的查询条件,同样的,若不满足,跳过当前记录,继续读取索引的下一条记录,若满足,则返回记录,此记录满足了where的所有条件,可以返回给前端用户。

 

 

4        结语

 

在读完、理解了以上内容之后,详细大家对于数据库如何提取where中的查询条件,如何将where中的查询条件提取为Index Key,Index Filter,Table Filter有了深刻的认识。以后在撰写SQL语句时,可以对照表的定义,尝试自己提取对应的where条件,与最终的SQL执行计划对比,逐步强化自己的理解。

 

同时,我们也可以回答文章开始提出的一个问题:MySQL 5.6中引入的Index Condition Pushdown,究竟是将什么Push Down到索引层面进行过滤呢?对了,答案是Index Filter。在MySQL 5.6之前,并不区分Index Filter与Table Filter,统统将Index First Key与Index Last Key范围内的索引记录,回表读取完整记录,然后返回给MySQL Server层进行过滤。而在MySQL 5.6之后,Index Filter与Table Filter分离,Index Filter下降到InnoDB的索引层面进行过滤,减少了回表与返回MySQL Server层的记录交互开销,提高了SQL的执行效率。

 

  1. jametong
    3月 3rd, 201321:41

    可以对比Tapio的《Index Design》的那本书再看看,应该会有更多收获。

    • hedengcheng
      3月 3rd, 201322:49

      旺旺,这本书我还没看过,有时间读读。我这些,还是在原来做Oscar数据库的索引实现以及执行器的时候总结的算法。

  2. fair_jm
    3月 3rd, 201322:45

    看完了 虽然我是个菜鸟 但是文章写的简单易懂 大体还是了解了 谢谢作者的奉献^_^

    • hedengcheng
      3月 3rd, 201322:48

      呵呵,能看的明白就好!以后都会这么写。

  3. 李大玉
    3月 4th, 201309:36

    为ICP提供了理论支持!!!!感谢作者!

  4. seven
    3月 4th, 201310:32

    一直有一件事情,不是太清楚。向大神请教一下:
    Table Filter,则是最后一道where条件的防线,用于过滤通过前面索引的层层考验的记录,此时的记录已经满足了Index First Key与Index Last Key构成的范围,并且满足Index Filter的条件,回表读取了完整的记录,判断完整记录是否满足Table Filter中的查询条件,同样的,若不满足,跳过当前记录,继续读取索引的下一条记录,若满足,则返回记录,此记录满足了where的所有条件,可以返回给前端用户。

    以上语句中的回表读取了完整的记录,这些记录应该是满足索引条件后的所有记录,那么是不是把满足index key范围和index filter的所有数据加载在内存中还是另外产生一个文件或者还是原来的文件中?如果是原来的文件中,回表去根据table Filter 条件是如何确定只在满足index key范围和index filter以后的记录中去查找的呢而不是所有记录?

    • qingfeng
      3月 4th, 201320:29

      应该是temp table,在内存中还是switch到file system,看temp table的大小。

    • hedengcheng
      3月 5th, 201309:28

      数据库中读取数据,都是one by one的方式,一条数据读完之后,再继续读取下一条。只有极少数情况下,才会将满足条件的记录一次性从索引中全部读取出来。

    • lexin
      10月 27th, 201516:34

      回表去根据table Filter 条件是如何确定只在满足index key范围和index filter以后的记录中去查找的呢而不是所有记录?
      —–
      过程应该是 扫描使用到的索引,根据index key找到B+树的开始的索引节点和结束的索引节点;然后使用 index filter 来过滤,符合条件的,就回表进行 table filter。并不存在先获得所有的满足 index key 和 index filter的一个集合,然后根据这个集合去回表。就像博主说的,是one by one的方式。

  5. PSJay
    3月 4th, 201314:49

    文中所说的 Index First/Last Key 的提取规则是普适性的还是针对示例总结的?

    • hedengcheng
      3月 5th, 201309:27

      普适性的,跟什么数据库无关

  6. qingfeng
    3月 4th, 201320:27

    描述的很清晰。ICP看上去的确很不错,具体性能提高如何还要测试下。

  7. zhoujy
    3月 12th, 201316:58

    针对上面的用例SQL,索引第一列只包含 >=、 1 and d != 4 。
    样本SQL:
    root@localhost : test 04:50:29>explain select * from t1 where b > 4 and b 1 and d != 4 and e != ‘a’\G;
    *************************** 1. row ***************************
    id: 1
    select_type: SIMPLE
    table: t1
    type: range
    possible_keys: idx_t1_bcd
    key: idx_t1_bcd
    key_len: 5
    ref: NULL
    rows: 1
    Extra: Using where
    1 row in set (0.00 sec)

    root@localhost : test 04:50:35>explain select * from t1 where b >= 4 and b 1 and d != 4 and e != ‘a’\G;
    *************************** 1. row ***************************
    id: 1
    select_type: SIMPLE
    table: t1
    type: range
    possible_keys: idx_t1_bcd
    key: idx_t1_bcd
    key_len: 10
    ref: NULL
    rows: 2
    Extra: Using where
    1 row in set (0.00 sec)

    按照执行计划里面看出,第2个sql 第一列 “>=” 之后会让c的索引也用起来,这样的话。 获得的Index Filter 应该只有 d != 4 吧。
    还是他们没有关系,按照你说的规则去看。不知道理解错了没,求解释哈。

  8. 上海浪客
    5月 21st, 201323:34

    现在才看到这篇文章,相见恨晚!
    hander.h中有一个cond_push(const COND *cond)虚函数,看了看mysql自带的存储引擎,只有ha_ndbcluster中实现了这个虚函数。
    也就是说其他存储引擎都是把所有数据从文件里返给msyql server,然后mysql server自己根据where条件进行筛选,最后返给client。这样岂不是有比较大的io压力?
    我想问,为什么想innodB这些很成熟的存储引擎都不去实现cond_push这个函数呢?

  9. 朱鹏飞
    9月 4th, 201318:07

    有一个问题,index filter的提取规则里面有提到 “若where条件为 >=、>、<、、= 2 and b =1 and d != 4 and e != ‘a’; 其中 b >= 2 and b =1已经是作为Index First Key的规则用来确定了索引的查找范围。那么这个时候如果按照文章里面写的,将c >= 1 and d != 4 置于index filter。其中C>=1的部分在Index First Key和index filter岂不是冗余了吗?求解答?

    • 朱鹏飞
      9月 4th, 201318:14

      怎么发出去的问题被截断了?重新发一下,index filter的提取规则里面有提到 “若where条件为 >=、>、<、、= 2 and b = 1 and d != 4 and e != ‘a’; 按照文章中的规则,where b >= 2 c >= 1 将作为Index First Key,而c >= 1 and d != 4 则作为index filter ,这样子其中c >= 1部分岂不是冗余了吗?求登博解答!

  10. fireflyk
    9月 5th, 201308:53

    有点疑惑,按照文中的说法,如果索引第一列的条件不是=,是>=什么的,只有第一列用来做index key。从第二列开始都是index filter key不会再利用到第二列的有序性做查找,只是一条一条的遍历索引,用index filter key的条件过滤?
    那也就是说多列索引,第一列做范围查询,后几列索引查找无法优化?

  11. rudyLi
    12月 31st, 201315:03

    你好,菜鸟想问一个问题:select * from table where((id,name) in ((1,”ni”),(2,”hao”))) explain 后没有使用索引id 和 name的组合索引,force index 也没有用,我查了下网上,说mysql 对in的操作支持不是很好,具体是什么原因呢?非常感谢

  12. jerett
    1月 1st, 201412:33

    为什么Indexkey提取到就停止了?按道理继续向下提取”可以缩小范围呀?

    • hedengcheng
      1月 1st, 201423:17

      这个问题不太看得懂?

      • jerett
        1月 7th, 201400:09

        = = 为什么我打的小于号被过滤了(所以这里比较符号我直接打中文了)。 我的意思是,比如ndexKey在提取IndexFirstKey中,遇到大于等于继续看下一个索引键值,而遇到大于号就停止了呢?我觉得碰到大于号还可以继续看索引的下一个键值啊?因为大于号也可以缩小查询范围吧。我觉得只要需要将索引移动到刚刚大于那个比较值不就可以了嘛?

        • hedengcheng
          1月 7th, 201409:58

          这个问题,你可以深入考虑下。连续的等于(包括大于等于)加上第一个不等于(大于或者是小于),可以构成一个用于定位索引范围起始位置的first key。但是不等于之后的条件,不能用于定位first key。你可以构造一个例子,然后验证一下。

          • tomwang1013
            5月 24th, 201421:40

            “连续的等于(包括大于等于)加上第一个不等于(大于或者是小于)”
            >=和>都是range condition,它们组合在一起应该不能构造出first key吧?个人理解只有第一个range condition才能作为first key的一部分,求博主解释,谢谢!

        • hedengcheng
          1月 7th, 201410:06

          同时,这么提取first key,其实是放大了范围。但是,索引范围查询,还有一个作用,为了满足隔离级别的要求。以MySQL为了,RR隔离级别,不允许幻读的存在,要锁住整个范围,此问题可以参考我的另一篇博文。因为这个原因,碰到大于后,就不能继续看索引的下一个过滤条件,否则就会导致范围没有被锁上,出现幻读。

          • jerett
            1月 7th, 201416:57

            谢了 。我也觉得是锁的问题。:)

  13. tomwang1013
    5月 19th, 201423:48

    你好,问个explain中出现using where的问题。我有一表,在其中两个字段(假设a和b)上建了索引,然后查询语句为a = 1 and b > 1,理论上这里只有index key,所以无需读取表中的记录便可以过滤查询,但是explain仍然显示了using where。看了《高性能mysql》中对using where的解释,意思是服务器需要对存储引擎中返回的记录再做一次过滤(相当于你说的table filter),原话是这样:this indicate that the mysql server is applying a where filter after the storage engine returns the rows。能帮忙解释一下using where的含义及这里的矛盾吗?

    • 。。。
      6月 30th, 201618:41

      那应该看你select的什么数据了,如果只是a和b,应该不会出现where。要是select 里还有其他列的数据,坑定要回表获取了。

      • hilo
        7月 16th, 201600:46

        我也遇到过这种情况,使用了覆盖索引且where条件出现范围查询就会用到using where,如:select b,c from t1 where b > 3 就会出现 using where,using index了,请博主答疑一下

  14. tomwang1013
    5月 24th, 201421:12

    有个疑问,在提取index key的时候如果碰到>=的key应该就停止检查吧?文中说的是碰到>才停止检查,为什么?按照对mysql索引的理解,>=也属于range condition,它右边所有的key都应该不在索引中,这里时候有问题呢?

  15. Rhett
    11月 16th, 201416:23

    参照oracle计划其实应该就是执行table access by index rowid之前,除了索引扫描的filter之外剩余的filter放在哪的问题,如果和当前扫描的index包含了filter所有列信息,则该filter 可以放在table access by index rowid之前否则放在其之后。

  16. eden
    11月 26th, 201415:48

    我有几个关于index first key的提取规则没有看懂
    1.“从索引的第一个键值开始”,索引的键值具体指的是什么?
    2.“检查其在where条件中是否存在”,是要求索引的键值正好 等于 where条件中的列和值?如果键值不是正好在where条件等于,而是大于或小于(比如b>=5),那就不能加入到index first key中?
    3.“继续读取索引的下一个键值,使用同样的提取规则”,是覆盖到Index First Key之中,还是新加呢?

    望回复

  17. eden
    11月 26th, 201415:57

    还有,“继续读取索引的下一个键值”,下一个的意思是按索引顺序从根开始从小到大的顺序?

  18. eden
    11月 26th, 201416:08

    Index Filter 是index key的结果进行顺序查找吗?
    如果某列的index first key和index last key的范围的结果集非常大,那不是不如使用btree从根开始二分查找?

  19. eden
    11月 26th, 201418:33

    希望博主能细化这遍文章

  20. 曾经的阿飞
    5月 14th, 201518:03

    发现一个奇怪问题(环境:Percona 5.6.15-56-log),大家帮看看
    CREATE TABLE `test1` (
    `id` int(11) NOT NULL AUTO_INCREMENT,
    `a` int(11) NOT NULL,
    `c` int(11) DEFAULT NULL,
    PRIMARY KEY (`id`),
    KEY `idx_a` (`a`)
    ) ENGINE=InnoDB
    插入若干数据
    admin@test04:54:26>desc select * from test1 where a>7000 limit 1\G
    *************************** 1. row ***************************
    id: 1
    select_type: SIMPLE
    table: test1
    type: range
    possible_keys: idx_a
    key: idx_a
    key_len: 4
    ref: NULL
    rows: 131104
    Extra: Using index condition
    1 row in set (0.00 sec)

    为啥会用到Using index condition呢?

  21. 宗帅
    6月 10th, 201522:43

    按照index filter里提到的提取规则:;若where条件为 >=、>、<、<= 其中的几种,则跳过索引第一列,将其余where条件中索引相关列全部加入到Index Filter之中;
    若索引只有一列,而且该条件为 explain select * from t1 where id1<2 for update;
    +——+————-+——-+——-+—————+——+———+——+——+———————–+
    | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
    +——+————-+——-+——-+—————+——+———+——+——+———————–+
    | 1 | SIMPLE | t1 | range | id1 | id1 | 5 | NULL | 1 | Using index condition |
    +——+————-+——-+——-+—————+——+———+——+——+———————–+
    index filter 提取规则是否还有其他情况?

  22. lexin
    10月 27th, 201517:16

    为了使用 Index key 来尽量缩小扫描索引的范围,我们是不是应该在建立组合索引时,尽量将where条件中等于和大于等于(还有小于等于)的字段放在组合索引的前面呢? 另外 between 如何处理呢?当成 大于等于 和 小于等于?

  23. foofish
    1月 30th, 201615:18

    (3,1,1) 并不在index key范围吧?

  24. 00姐
    2月 18th, 201617:03

    关于Index Filter的介绍有一些疑问,这个是只判定第一列索引吗?如果是判定所有列的索引,那c<1 是不是应该归到Index Key里面?

  25. sunnY
    5月 11th, 201618:16

    有一个问题,创建了一个索引idx_t1_bcd on t1(b, c, d); explain select * from t1 where c > 1; 提示不会使用到多列索引,按照您的分析,Index Filter 应该会使用到c列,为啥explain的结果是全表扫描,没有使用到c索引

  26. 。。。
    6月 30th, 201618:44

    因为不符合最左前缀原则,所以不会应用索引。