索引查询

页内查询

对于主键索引查询，根据槽使用二分法快速定位主键所在小组位置，然后在小组内顺序查找。

多页查询

如果数据较多，对于多页的数据查询，首先要定位数据所在的页，然后再根据页内查询的方式进行查找。

非索引查询

如果不使用索引，必须从首页的首条记录开始遍历比较查找数据

索引树查询

索引树的组成为叶子节点和非叶子节点。
非叶子节点存储页的最小记录值，对应主键值以及对应页号。
在查找时根据记录值来定位到对应的页号，一般B+树的高度不超过4，所以最多经过三次页号的查询后即可定位到记录所在的页号。特别的，如果对于非唯一列，假定两个页的最小记录值都一样，此时就比较索引和待插入数据的主键值来决定去哪个页。
叶子节点记录着对应的值，对于主键索引，就是记录本身。对于非主键索引，叶子节点记录的是索引列值和主键值。根据非主键索引查询时，每次命中索引都会回表，如果索引列不是唯一的，会一直扫描直到不匹配为止。

根页面

新建索引时，根页面无记录，当记录超过一页时，所有记录复制到新页中并进行分裂，根页面升级为目录页。因此，根页面页号永不改变，对于某个索引建立后，根页面页页号页随之固定并被存储，mysql能够固定的从该页进行索引的查找。

MyISAM索引结构

MyISAM将数据和索引分开存放，数据在一个文件中且没有按照主键顺序存放，索引单独存储，记录主键值和行号来快速定位。

索引的有序性

对于联合索引多列一致的升/降序查询可以使用索引的有序性来进行排序，但如果查询方式是 order by c1 desc， c2 asc这种升降混合的，则无法应用索引排序。因为此时先根据C1索引定位到C1最大的位置后，对应的C2也是最大的，要找C2最小的必须往左一条一条的遍历查询才能找到。
mysql8.0的Descending Index可以支持混排

索引不一定快

根据二级索引查询时，由于二级索引的顺序性并不代表主键的顺序性，所以在根据二级索引查找时，需要频繁回表非顺序的主键查询，从而带来大量随机IO，有时候可能还不如顺序性的全表扫描来的快。

索引合并查询

intersection

对于查询select * from table where c1 = 1 and c2 = 1
其中c1和c2都是普通的二级索引，此时mysql可以分别使用c1索引和c2索引，拿到两个结果集中id相同的交集去回表，减少回表次数。

union

对于查询select * from table where c1 = 1 or c2 = 1
其中c1和c2都是普通的二级索引，此时mysql可以分别使用c1索引和c2索引，拿到两个结果集中id并集去回表，减少回表次数。

对于索引合并，必须要求扫描到的索引记录是按照主键顺序排列的，原因为为了更快速方便的去重，且回表也可以顺序。因此对于多列索引无法使用该查询，因为多列索引不能保证索引记录是按照主键顺序排序的.

index不命中

  1. 对索引字段做函数操作无法使用索引
  2. 隐形的类型转换会导致无法使用索引（默认会进行函数转换，字符串转数字）
  3. 隐形的字符集转换会导致无法使用索引（默认函数转换） ```sql

    无法使用索引

    select * from table where cast(name as signed int) = 123

可以使用索引

select * from table where numId = cast(‘123’ as signed int)

  1. <a name="5sgrE"></a>
  2. # order by
  3. ```sql
  4. ## city存在索引
  5. select city,name,age from t where city='杭州' order by name limit 1000

这句语句的执行过程为：

  1. 初始化 sort_buffer，确定放入 name、city、age 这三个字段;
  2. 从索引 city 找到第一个满足 city=’杭州’条件的主键 id;
  3. 到主键 id 索引取出整行，取 name、city、age 三个字段的值，存入 sort_buffer 中
  4. 从索引 city 取下一个记录的主键 id;
  5. 重复步骤 3、4 直到 city 的值不满足查询条件为止，注意这里第一个不满足条件的记录会被扫描到;
  6. 对 sort_buffer 中的数据按照字段 name 做快速排序;
  7. 按照排序结果取前 1000 行返回给客户端。

对于步骤6的排序，如果sort_buffer_size足够大，则在内存中排序，否则会使用临时文件辅助排序（归并）。
如果要查询的字段太多，单行数据大小超过了max_length_for_sort_data，则会使用新的算法，此时放入sort_buffer中的字段只有主键id和排序字段，其过程会在上述步骤后额外的再去主表根据主键id查询出具体的字段内容再返回给客户端（查一条返回一条，不需要额外存储，返回时一个持续的过程）。

发生额外排序的原因是在city索引上，name是无序的，如果修改索引为（city，name），即在索引中name即时有序的，就不需要再进行这种额外排序了。

join

使用straight_join可以强制使用前表驱动后表

对于查询 select * from t1 (inner join) t2 where t1.c1 =1 and t1.c2=t2.c2 and t2.c1 = 1
有单表条件：t1.c1 =1 ， t2.c1 = 1
有多表条件： t1.c2=t2.c2
假定判断t1代价最小作为驱动表，则先根据t1.c1 =1查找符合的记录，假设是2条。
根据这两条记录查两次t2表时会将 t1.c2=t2.c2 转换为t2的条件，结合 t2.c1 = 1 去查t2表。

内外链接
  • 内连接：驱动表中的记录在被驱动表中找不到匹配的记录，则该记录不加入结果集。

  • 外连接：驱动表中的记录在被驱动表中找不到匹配的记录，则该记录仍然要加入结果集。

    where和on

  • where：不符合的记录不会加入结果集

  • on：在被驱动表中找不到匹配的记录，则该记录对应字段置NULL，仍然要加入结果集

即on专为外连接使用，对于内连接，on等价where

Index Nested-Loop Join

驱动表只会访问一次，被驱动表可能会访问多次。
被驱动表上存在join条件的索引，其过程如下：

  1. 全表扫描从驱动表取出一行数据；
  2. 扫描被驱动表（走索引扫描），取出符合条件的数据；
  3. 将1，2的数据组合成一行作为结果集的一部分；
  4. 重复执行上述步骤；

其过程是嵌套遍历形式的。对于驱动表行数N，被驱动表行数M，有以下效率计算（log记为以2为底）：
对于驱动表，全表扫描复杂度为：N
对于被驱动表，先走普通索引，再走主表索引，共N此，因此复杂度为：N2logM
因此总复杂度为：N+2NlogM
N与M相比N对复杂度的影响更大，因此N越小，复杂度越小，所以得到结论—>小表驱动大表效率更高。
什么是小表？经过对应条件筛选过后，行数最小的表为小表。

Simple Nested-Loop Join

被驱动表上没有join条件的索引，针对驱动表的每条数据，都要在被驱动表上进行全表扫描，其复杂度为N+NM，这种算法效率太低，Mysql并没有使用这种方法。

Block Nested-Loop Join

被驱动表上没有join条件的索引，有以下步骤：

  1. 全表遍历驱动表，取出所有满足条件的数据放在join_buffer中
  2. 全表遍历被驱动表，每取出一条数据，将其与join_buffer中的所有数据进行比对，如果满足条件则作为结果集返回。

复杂度为：N+NM（这里假设不设置条件，驱动表所有数据全部放入join_buffer）
其复杂度与simple算法一样，但这里的比较是在内存中比较的，要更快。

如果驱动表数据太多无法全部放入join_buffer中，则进行分段，其过程如下：

  1. 全表遍历驱动表，取出部分满足条件的数据放在join_buffer中
  2. 全表遍历被驱动表，每取出一条数据，将其与join_buffer中的所有数据进行比对，如果满足条件则作为结果集返回。
  3. 清空join_buffer
  4. 全表遍历驱动表，取出剩余满足条件的数据放在join_buffer中
  5. 如步骤2

可以看出这时会多次遍历t2，但比较次数不会变，仍然是NM=0.5NM+0.5NM
由于驱动表会遍历一遍，而被驱动表可能会遍历多次，所以小表驱动大表效率更高。

这种算法可能多次扫描大表，可能带来以下问题：

  1. IO和CPU压力增大
  2. 多次扫描会影响Buffer_Pool的热数据，影响命中（长期影响）

可以在被驱动表上加索引，变为BKA算法（见下文）

Multi-Rang Read优化

其思想就是将回表的随机读变为顺序读，提高性能。
根据普通索引查询再回表的过程，是一条一条的回表的，即在普通索引上得到一个id，就回一次表。
按照普通索引的顺序读到的id是随机的，每次回表都是随机读，性能差。
MRR优化将普通索引读到的id暂时存储在read_rnd_buffer中，当buffer满了或普通索引查完了，就对buffer中的数据根据主键进行排序，然后按顺序去回表查，因此其结果集也是按照id排序的。
使用MRR需要set optimizer_switch=”mrr_cost_based=off” 来进行开启。

Batched Key Access

5.6支持，开启指令：set optimizer_switch=’mrr=on,mrr_cost_based=off,batched_key_access=on’;
对于 index Nested-Loop Join，每次取出小表的一行去大表匹配并回表，无法应用MRR优化，因此可以利用join_buffer，其过程如下：

  1. 从驱动表中取出满足条件的数据放入join_buffer
  2. 遍历被驱动表的索引树与join_buffer中的数据比对，满足条件的放入read_rnd_buffer
  3. 排序read_rnd_buffer按照id顺序，并按照主键顺序回表顺序查大表组成结果集返回

同样，如果步骤1中的数据不足以全部放入join_buffer，则分段进行。

Temple-Table

如果BNL转BKA不方便加索引的，可以使用临时表，在临时表上加索引进行join操作提升效率。

in vs exist

in走的是内表驱动外表，exist相反。
因此，当内表小时，使用in，外表小时，使用exist。

in子查询优化

select from t where col in ( select from t)
如果子查询结果集太大，可能造成

  1. 内存放不下
  2. in中参数太多，匹配很耗时，且外层查询可能无法有效使用索引

因此会将该子查询结果放入临时表，并进行去重（通过唯一或主键索引形式），建立哈希索引，来进行匹配是否在表中。
然后会将外查询和内查询看作一个内连接，判定使用哪个作为驱动表

count

对于没有where条件的count()，MyAsIM使用一个字段存储着行数，可以直接返回，而innodb则需要扫描所有行数进行统计，因为innodb存在多版本并发控制mvcc，因此在多会话的环境中，innodb的count()所返回的行数跟当前的事务有关系，其只能返回当前事务可见的行数。
由于普通索引同样存着主键，对于行数，普通索引与主键索引是保持一致的，而普通索引更小，因此Mysql会尽量扫描更小的普通索引树来进行统计。

count()是一个聚合函数，参数不为NULL时累计值+1，否则就不变。在innodb中，有以下区别（按效率排序）

count(*) 遍历表，不取值，一直累加
count(1) 遍历表，不取值，传1给count，1不可能为NULL，所以一直累加
count(id) 遍历表，取出id传给count，由于id不可能为NULL，所以一直累加
count(字段) 遍历表，如果字段为not null则累加；如果可以null，则取出值传给count，不为NULL累加

代码中常常会使用count来判断一下是否存在符合条件的数据，可以用以下语句代替，如果存在会返回1，否则0

select 1 from table where condition

union

## a like b
select * from b union select * from a

union会使用到内部临时表，对于以上语句，其流程如下：

  1. 从b中取出数据放入临时表中
  2. 从a中取数据并插入到临时表中，如果有重复的行将会被过滤
  3. 将结果集返回

如果是union all则不会进行去重。

group by

select id%10 as m, count(*) as c from t1 group by m;

group by 也会使用到临时表，对于以上语句，其流程如下：

  1. 创建临时表，字段有m（主键）和c。
  2. 如果有索引会走索引，没有走主键索引，取出id并计算%10作为m放入临时表中。
  3. 如果计算出的id%10在临时表中已经存在，则c+1。
  4. 全部取出后对临时表做根据m值的排序并返回

如果不需要最后的排序可以加 order by null跳过排序
如果在使用内存临时表tmp_table_size时发现空间不足，会从内存临时表专为磁盘临时表（innodb类型）。

优化

  1. group by 需要临时表和排序是因为扫出来的分组数据（id%10 as m）是无序的，如果是有序的，则只需要顺序扫描顺序累加即可，因此可以在字段上添加索引来避免临时表和排序。
  2. 使用SQL_BIG_RESULT来直接启用磁盘临时表

having

必须跟随group by一起使用，用于对group by后的分组数据进行过滤。
where必写在group by前面，即是分组前过滤数据，having是分组后过滤数据。