Home Posts Tags

Contents

MySQL Query Optimization

frankma included in mysql
   13054 words   27 minutes 
/images/mysql-query-optimization.png

最全面的资料都在: MySQL Optimization Documentation

基于成本的查询优化

https://raw.githubusercontent.com/Fedomn/misc-blog-assets/master/mysql-optimizer-overview.png

MySQL优化器将SQL作为输入，产生一个执行计划，最终在执行查询。

执行计划如：按照什么顺序连接表、应该使用那些索引，是全表扫描还是走索引查询等。

MySQL优化器从众多执行计划中选择成本最低的计划，优化器选择的依据是：数据字典中表/索引的信息、存储引擎中数据的统计信息。

执行计划的成本单位是：从磁盘读取随机数据页的成本。所以，优化最终目的都是为了减少磁盘读取随机数据页。

https://raw.githubusercontent.com/Fedomn/misc-blog-assets/master/mysql-optimizer-cost-model.png

上图是MySQL中成本模型。它的输入是SQL，成本模型则组成：

  • 执行该SQL的基本成本(需要临时表、需求子查询、需要表连接等)
  • 执行该SQL估计的行数(估算数据来源于元数据和统计信息，如表中的行数、索引基数)
  • 成本常量(如DISK_TEMPTABLE_CREATE_COST/IO_BLOCK_READ_COST，在opt_costconstants.cc里)
  • 元数据与统计信息(行和列的长度，数据量大需要全表扫描文件排序等)。

下面通过示例直观展示优化器计算的成本与执行计划的选择。

先构造表与数据：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

CREATE TABLE `test` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `weight` int(11) DEFAULT 0,
  `price` int(11) DEFAULT 0,
  `name` varchar(255) DEFAULT '',
  `desc` varchar(255) DEFAULT '',
  PRIMARY KEY (`id`),
  KEY `idx_weight` (`weight`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

-- prepare data
drop procedure if exists idata;
delimiter ;;
create procedure idata()
begin
  declare i int;
  set i=1;
  while i<500000 do
	INSERT INTO `test` (`weight`, `price`, `name`, `desc`) VALUES (i, i, concat(i, '-name'), concat(i, '-desc'));
    set i=i+1;
  end while;
end;;
delimiter ;

call idata();

我们构造了50万的数据，通过正常SQL与force index SQL来观察优化器的执行成本与最终选择。 https://raw.githubusercontent.com/Fedomn/misc-blog-assets/master/mysql-optimizer-cost-demo.png

Performance Schema

performance schema里表有大量性能相关的数据。

总览信息：

  • events_statements_history、events_statements_history_long：最近执行查询的统计信息
  • events_statements_summary_by_digest：汇总了类似查询的数据
  • file_summary_by_event_name：包含获取文件IO的统计信息(关注事件:wait/io/file/innodb/innodb_data_file)
  • table_io_waits_summary_by_table、table_io_waits_summary_by_index_usage：表和索引的存储引擎访问统计数据

语句事件：

  • events_statements_current：每个线程的当前语句
  • events_statements_history：每个线程10个最新的语句
  • events_statements_history_long：10000条最近的语句

其中关键的列：

  • TIME_WAIT：执行查询需要多长时间，单位是皮秒(picosecond)，1,000,000,000 ps = 1 ms
  • ROWS_SEND：结果的行数
  • ROWS_EXAMINED：执行查询时必须访问的行数
  • CREATED_TMP_DISK_TABLES：是否在磁盘上创建了临时表

语句摘要：

单独提出events_statements_summary_by_digest表，它将相同语句只是查询参数不同的SQL汇总统计，

常用列：

  • DIGEST_TEXT：规范后的查询文本
  • COUNT_STAR：执行此查询的次数
  • SUM_TIMER_WAIT：执行此查询所用的时间
  • AVG_TIMER_WAIT：每次执行的平均时间
  • FIRST_SEEN：这类查询第一次执行的时间，它可以快速定位最近新增的SQL

Sys Schema

Performance Schema有很多数据细节，所以MySQL提供了sys_schema，这个一个视图、存储过程、函数的集合，为了让查询Performance Schema数据更容易。

注意视图中有很多以 x$ 开头的视图，它的用于给工具处理，如时间是原始数据，没有精确到ms之类的。

下面介绍视图的类别：

  • host_summary：以host分组展示文件I/O、语句统计信息
  • user_summary：以user分组展示文件I/O、语句统计信息
  • innodb：innodb层面的，如innodb缓存信息按照schema和table分组，如innodb的锁定信息
  • io：I/O层的统计
  • memory：内存使用情况
  • schema：schema级别的统计信息。如重复或冗余的索引，如未使用的索引。
  • session：会话级别。如当前的connection
  • statement：SQL语句级别执行次数，是否全表扫描，延迟时间等。通过它可以进行一些性能分析。
  • wait：关于等待信息的统计

常用查询：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

-- 1、查看process：show processlist包含的信息较少可以通过下面语句

select * from sys.session;
select * from sys.processlist;

-- 2、查看数据库中热SQL

select db,exec_count,query from sys.statement_analysis order by exec_count desc limit 10;

-- 3、查看SQL用了临时表与磁盘临时表

select db, query, tmp_tables, tmp_disk_tables 
from sys.statement_analysis where tmp_tables>0 or tmp_disk_tables >0 
order by (tmp_tables+tmp_disk_tables) desc limit 20;

-- 4、查看冗余索引与unused索引

select * from sys.schema_redundant_indexes;
select * from sys.schema_unused_indexes;

-- 5、没有正确关闭数据库连接的用户

SELECT ess.user, ess.host, 
(a.total_connections - a.current_connections) - ess.count_star as not_closed, 
(a.total_connections - a.current_connections) as total_closed, 
((a.total_connections - a.current_connections) - ess.count_star) * 100 / (a.total_connections - a.current_connections) as pct_not_closed
FROM performance_schema.events_statements_summary_by_account_by_event_name ess
JOIN performance_schema.accounts a on (ess.user = a.user and ess.host = a.host)
WHERE ess.event_name = 'statement/com/quit' AND (a.total_connections - a.current_connections) > ess.count_star;

-- 6、查看最大延迟的SQL

select query, db, full_scan, exec_count, err_count, warn_count, sys.format_time(total_latency) as total_latency, sys.format_time(max_latency) as max_latency, sys.format_time(avg_latency) as avg_latency, sys.format_time(lock_latency) as lock_latency, first_seen, last_seen
from sys.x$statement_analysis where order by max_latency desc limit 10\G

-- 7、查看全表扫描的SQL

select * from sys.statements_with_full_table_scans order by exec_count desc limit 10\G

-- 8、用到临时表的SQL

select * from sys.statements_with_temp_tables

-- 9、查看MySQL event对应的次数和延迟

select * from sys.waits_global_by_latency
-- 其中events参考 https://dev.mysql.com/doc/refman/8.0/en/performance-schema-instrument-naming.html

Optimizer Trace

调试执行计划通过optimizer trace输出优化器选择该执行计划的原因。

1
2
3
4
5
6
7
8

set optimizer_trace='enabled=on';
select sum(price) from go_dev.test where weight between 1 and 100000;
select trace from information_schema.optimizer_trace;
set optimizer_trace='enabled=off';

-- 排序时MySQL可以最大分配的内存大小，如果数据量大于这个值就会使用磁盘临时表(默认256KB)
show variables like 'sort_buffer_size';

Query execution plan

解释基本的explain使用，例子还是上面的test表，需求是统计distinct weight个数， SQL如下：

1
2
3
4
5
6
7
8
9

-- SQL1
explain format=json
select SQL_NO_CACHE count(weight)
from ( select weight from test group by weight ) as g;

-- SQL2
explain format=json
select SQL_NO_CACHE count(distinct(weight))
from test;

第一个是先group by后count，直观感觉会产生derived table效率低。第二个是直接count distinct索引。下面通过explain数据支撑假设：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

// SQL1 - explain format=json
{
  "query_block": { //整个查询块
    "select_id": 1, //等同于explain结果的第一列id
    "cost_info": {
      "query_cost": "118083.00" //针对select_id=1的查询成本
    },
    "table": {
      "table_name": "g",
      "access_type": "ALL",
      "rows_examined_per_scan": 472292, //每次扫描的行数
      "rows_produced_per_join": 472292, //每次join的行数
      "filtered": "100.00",
      "cost_info": {
        "read_cost": "23624.60", //IO/MEM读取的成本
        "eval_cost": "94458.40", //评估出的成本
        "prefix_cost": "118083.00", //加入下一次join-table的成本(没有join就是这次查询的成本)
        "data_read_per_join": "7M" //每次join需要读的数据大小
      },
      "used_columns": [
        "weight"
      ],
      "materialized_from_subquery": { //物化子查询
        "using_temporary_table": true, //使用了临时表
        "dependent": false,
        "cacheable": true,
        "query_block": {
          "select_id": 2,
          "cost_info": {
            "query_cost": "96222.40" //针对select_id=2的查询成本
          },
          "grouping_operation": {
            "using_filesort": false,
            "table": {
              "table_name": "test",
              "access_type": "index",
              "possible_keys": [
                "idx_weight"
              ],
              "key": "idx_weight",
              "used_key_parts": [
                "weight"
              ],
              "key_length": "5",
              "rows_examined_per_scan": 472292,
              "rows_produced_per_join": 472292,
              "filtered": "100.00",
              "using_index": true,
              "cost_info": {
                "read_cost": "1764.00",
                "eval_cost": "94458.40",
                "prefix_cost": "96222.40",
                "data_read_per_join": "929M"
              },
              "used_columns": [
                "id",
                "weight"
              ]
            }
          }
        }
      }
    }
  }
}

// SQL1 - explain

+----+-------------+------------+------------+-------+---------------+------------+---------+------+--------+----------+-------------+
| id | select_type | table      | partitions | type  | possible_keys | key        | key_len | ref  | rows   | filtered | Extra       |
+----+-------------+------------+------------+-------+---------------+------------+---------+------+--------+----------+-------------+
|  1 | PRIMARY     | <derived2> | NULL       | ALL   | NULL          | NULL       | NULL    | NULL | 472292 |   100.00 | NULL        |
|  2 | DERIVED     | test       | NULL       | index | idx_weight    | idx_weight | 5       | NULL | 472292 |   100.00 | Using index |
+----+-------------+------------+------------+-------+---------------+------------+---------+------+--------+----------+-------------+

explain output详细字段参考MySQL Explain Output Format，只记录几个易忘的点

  1. rows：MySQL估算的，需要执行查询要扫描的行数
  2. filtered：MySQL估算的，查询条件过滤出的行数 百分比。100%表示没有filter出行。
  3. rows x filtered = rows_produced_per_join 也就是下次将要连接表的行数
  4. Extra：MySQL查询如何执行查询的额外信息。很重要。如出现Using filesort、Using temporary就需要优化，其他的查看文档 MySQL Explain Extra Information
  5. select_type：select的类型。介绍常用的几个
    • SIMPLE：简单的select没有union和subqueries子查询
    • PRIMARY：最外面的select，一般有子查询时包在最外面的select
    • DERIVED：派生表
    • MATERIALIZED：物化子查询
  6. table：这行explain对应的表名
    • <derivedN>：这行explain对应的派生表，其中N就是select id可以从explain中找到对应的行
    • <subqueryN>：这行explain对应的物化子查询，N是select id。
  7. ref：表示索引用到的是表中的哪个字段或常量
  8. type：表的连接方式。可以理解成通过什么方式去找表中的数据，并与其它表join。best -> worst:
    • system：表里只用一行数据，它是一种特殊的const
    • const：表里最多只有一行匹配。针对PK和UK的等值查询。查询很快因为在查询时候，就只读出整行并只读一次。通过explain后，show warnings可以看出rewrite的SQL
    • eq_ref：连接时，只有一行读出来和前表的行匹配。针对join时候，index是Pk或UK NOT NULL的等值查询
    • ref：连接时，读出多行和前表匹配。针对不是PK/UK，也就是说基于index无法只查出一行。场景index列的 = or <>操作
    • fulltext：使用FULLTEXT索引执行连接。
    • ref_or_null：和ref一样，只不过有个额外条件or index列是null。
    • index_merge：表示使用了索引合并优化：检索具有多个扫描范围的行，并将结果合并为一个。
    • unique_subquery：对于value in(select pk from table where xxx)这样的子查询情况，此类型替换eq_ref。unique_subquery只是一个index查找的function，完全替换子查询以提高效率
    • index_subquery：对于value in(select idx from table where xxx)这样的非唯一索引子查询，index_subquery用来取代in子查询。
    • range：索引范围扫描，仅检索给定范围内的行，使用索引来选择行。=, <>, >, >=, <, <=, IS NULL, <=>, BETWEEN, LIKE, or IN()这些操作中将key与常量比较时会使用range
    • index：全索引扫描，类似ALL不过它是全索引扫描。如果是覆盖索引，则Extra会显示Using index。否则会先索引后回表查询，Extra没有Using index。仅当MySQL查询 使用一个索引列时，才会选这个type。
    • ALL：全表扫描，尽量避免。

到这里有个疑问，MySQL derived-table和materialized-subquery是什么？有关系吗？

先看Derived-Tables，派生表是一个查询在 from 语句内生成的table。而materialization是对派生表的一种优化方式，但物化是有成本的应该尽量避免，所以优化器还提供一种Merge派生表到外查询块的方式。Optimizing Derived Tables with Merging or Materialization。

同时Optimizer也会给materialization的表加index。

继续看SQL2，对比query_cost就可以基本知道查询快慢。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// SQL2 - explain format=json

{
  "query_block": {
    "select_id": 1,
    "cost_info": {
      "query_cost": "94458.60"
    },
    "table": {
      "table_name": "test",
      "access_type": "range",
      "possible_keys": [
        "idx_weight"
      ],
      "key": "idx_weight",
      "used_key_parts": [
        "weight"
      ],
      "key_length": "5",
      "rows_examined_per_scan": 472293,
      "rows_produced_per_join": 472293,
      "filtered": "100.00",
      "using_index_for_group_by": "scanning",
      "cost_info": {
        "read_cost": "0.00",
        "eval_cost": "94458.60",
        "prefix_cost": "94458.60",
        "data_read_per_join": "929M"
      },
      "used_columns": [
        "weight"
      ]
    }
  }
}

// SQL2 - explain
+----+-------------+-------+------------+-------+---------------+------------+---------+------+--------+----------+-------------------------------------+
|  1 | SIMPLE      | test  | NULL       | range | idx_weight    | idx_weight | 5       | NULL | 472293 |   100.00 | Using index for group-by (scanning) |
+----+-------------+-------+------------+-------+---------------+------------+---------+------+--------+----------+-------------------------------------+

Optimizer选择访问方法

上面有了优化器和执行计划的感受。下面介绍一些具体的方法，也就是MySQL Optimizing SQL Statements 与 Optimizing Subqueries, Derived Tables, View References, and Common Table Expressions。

选择访问方法：寻找从存储引擎中读取数据的最佳方法，方法的选择也是基于成本的，通过估算选择成本最低的方法。

查询有很多种，select、create table … as select、insert into … select、update/delete where，它们都要有性能考量当需要一些查询数据时。

Optimization思路：

  • 看where条件是否可以加index，同时避免过多index(磁盘空间浪费，插入效率降低)
  • 注意function call，它会在every row上执行，同时走不了索引扩大了效率问题
  • 尽量避免对大表的full table scan
  • 保持表的统计信息准确，给优化器选择合理的执行计划 提供判断基准。通过alalyze table更新
  • 优化InnoDB查询：给每个表设PK、PK不要太长、考虑联合索引而不是多列索引(每次查询仅用到一个index不包含索引合并优化)、避免索引列default null加快查询消除没必要的check-null
  • 优化InnoDB单查询事务：InnoDB可以避免设置TRX_ID的开销通过Read-Only-Transaction，不能write和select for update，写操作会得到ERROR。当然，这里仍有考虑点，如果只是读MVCC也是没有必要开Transaction的。
  • explain和pt-query-digest
  • 注意locking issues

下面是具体场景下的Optimization策略

where clause optimization

MySQL在prepare阶段会对SQL中的一些计算rewrite，如减少没必要的()和5=5条件，也会detect无效的where直接返回空数据。

having会直接merge到where中，如果没有使用聚合函数或groupby。

orderby/groupby在join时的策略，orderby/groupby包含其它表的列时会创建temporary table处理。

索引查询和全表扫描不仅仅基于最佳索引字段是否超过全表的30%，优化器很复杂还会依赖于很多其他成本，最终选择。

走覆盖索引就不会去读数据文件。

having语句在最后阶段执行(有聚合函数或groupby)，即server给client数据的时候过滤，没有进行优化。也就是说引擎仍然扫描出1W条只是在server层数据筛选，同时limit在having之后执行。

range optimization

索引范围扫描：通过一个索引检索出一些行。下面是optimizer使用range的几种情况：

单一索引

首先要有range condition概念，针对单一索引，MySQL会构造范围条件来快速扫描。而range condition的定义是=, <>, >, >=, <, <=, IS NULL, <=>, BETWEEN, LIKE(most-left-match), or IN()这些操作中将key与常量比较时会使用range。

MySQL会将where中不满足range condition的条件先用TRUE替换掉，将overlapping的条件合并，去除无效的condition。所以range scan的条件会小于where条件。至于没有range scan的条件，最终会通过using where再过滤。

复合索引

multiple-part indexes是single-part indexes的扩展。这里只说BTree。假设有复合索引key1(key_part1, key_part2, key_part3)。

当key_part1 = 'foo' AND key_part2 >= 10 AND key_part3 > 10时，它定义出的range是('foo',10,-inf) < (key_part1,key_part2,key_part3) < ('foo',+inf,+inf)。注意这里没有使用到key_part3的原因，复合索引相当于三个需要按照顺序一起比较，如key_part1.1 > key_part1.2时，不论key_part2.1和key_part2.2的大小了。

进一步，我们的range scan需要定义一个确定的single interval才好去走索引filter，所以上面的key_part3 > 10为什么没法走索引查询的原因是，key_part2 >= 10是个范围条件，我们没法保证按照索引顺序找到key_part2>=10的记录之后key_part3一定都是>10的。

所以，就有了and条件下复合索引会怎么使用的讲究：

当第一个key的比较符是： =, <=>, or IS NULL

optimizer就会接着尝试下一个key去判断

如果第二个key的operator是： >, <, >=, <=, !=, <>, BETWEEN, or LIKE

optimizer会使用第二个key，但是不会继续使用第三个key了，原因如上。

接着，or条件下复合索引使用的讲究：

1

(key_part1 = 1 AND key_part2 < 2) OR (key_part1 > 5)

通过or连接起来的条件，最终将每个小块的intervals union起来。如一个or就对应两个intervals。对单独的interval继续索引filter。上面的or对应的intervals:

1
2

(1,-inf) < (key_part1,key_part2) < (1,2)
(5,-inf) < (key_part1,key_part2)

Equality Range Optimization of Many-Valued Comparisons

多值比较中的 相等 range 优化。如下两行里的val1~valN都是Equality Range，示例：

1
2

col_name IN(val1, ..., valN)
col_name = val1 OR ... OR col_name = valN

这里的range是一个single value，也就说上面的查询包含了很多个range。优化器如何去估算满足条件的行数呢。(MySQL是基于成本的查询优化，在优化器阶段需要估算出行数)

  • 如果col_name是uk：估算的行数 = 1，唯一键很好理解
  • 如果col_name不是uk其他idx：优化器使用index statistics 或 index dives

index statistics使用MySQL维护的index的抽样结果，index dives(索引下潜)是一种精确的统计行方式，同时它的成本也会比较高。 MySQL通过eq_range_index_dive_limit来控制是否index dives。8.0之后除了这个变量还有其他方式控制。

Skip Scan Range Access Method

这一点也是MySQL内部自己优化的手段，看起来不能走index的查询，通过其他方式优化。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

CREATE TABLE t1 (f1 INT NOT NULL, f2 INT NOT NULL, PRIMARY KEY(f1, f2));
INSERT INTO t1 VALUES
  (1,1), (1,2), (1,3), (1,4), (1,5),
  (2,1), (2,2), (2,3), (2,4), (2,5);
INSERT INTO t1 SELECT f1, f2 + 5 FROM t1;
INSERT INTO t1 SELECT f1, f2 + 10 FROM t1;
INSERT INTO t1 SELECT f1, f2 + 20 FROM t1;
INSERT INTO t1 SELECT f1, f2 + 40 FROM t1;
ANALYZE TABLE t1;

EXPLAIN SELECT f1, f2 FROM t1 WHERE f2 > 40;

上面SQL keypoints是PK(f1, f2)，查询时只用了f2 > 40，没有f1。

前置知识：range scan is more efficient than full index scan，想象Tree里查询，就理解range scan为什么会更快点。

回到上面的SQL，由于没有f1即第一个索引列，所以没法使用range scan。但是，在MySQL8.0中，optimizer可以通过multiple range scan，操作起来是，扫描f1的每一个值(f1=1 and f2 >40、f1=2 and f2 > 40、……)。这种方式称作skip scan 很类似于 Loose Index Scan。

具体的algorithm：取到distinct f1的所有值 -> 遍历 distinct f1 同时append f2的条件如上。-> 一直到distinct f1走完

优势：减少了扫描的行。由原先的full index scan(理解需要scan tree的最下一层 所有叶子节点)，到现在skip scan(通过tree查询，快速定位到f1=1 and f2>40的行，理论上比full index scan会少)。

当然真实情况会更复杂，所以也会优先限制详见文档。

Limiting Memory Use for Range Optimization

这一条是说如果控制 range scan的内存限制，如果exceed limitation，就会废弃range scan采用full table scan。这显然会cause Performance(optimizer估算成本到一半又换方案，肯定有消耗的)。所以，可以适当increase range_optimizer_max_mem_size，它的默认值：8388608 bytes = 8M

Index Merge Optimization

接着上面的range scan，当处理多个range scan时，我们知道会有多个intervals，此时MySQL可以通过index merge来优化。

限制条件：single table only 、not across multiple tables

may be used index merge:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

SELECT * FROM tbl_name WHERE key1 = 10 OR key2 = 20;

SELECT * FROM tbl_name
  WHERE (key1 = 10 OR key2 = 20) AND non_key = 30;

SELECT * FROM t1, t2
  WHERE (t1.key1 IN (1,2) OR t1.key2 LIKE 'value%')
  AND t2.key1 = t1.some_col;

SELECT * FROM t1, t2
  WHERE t1.key1 = 1
  AND (t2.key1 = t1.some_col OR t2.key2 = t1.some_col2);

index merge有几种algorithm: using intersect / using union / using sort_union 对应explain的Extra

Index Merge Intersection Access Algorithm

索引合并交集：where条件可以转成多个range conditions。不同的index key通过and连接起来。如：

1
2
3
4
5

SELECT * FROM innodb_table
 WHERE primary_key < 10 AND key_col1 = 20;

SELECT * FROM tbl_name
 WHERE key1_part1 = 1 AND key1_part2 = 2 AND key2 = 2;

index merge intersection是同时scan index，然后产出一个交集结果，有两个知识点：

  • 如果走覆盖索引，则不需要去取整行数据
  • 如果where条件中有PK，则它不会去scan index。它会用来filter其他secondary index条件(二级索引叶子是clustered index)

Index Merge Union Access Algorithm

它和intersection相似，不同的index key通过or连接起来，同时scan index，最终union起来结果，如：

1
2
3
4
5
6

SELECT * FROM t1
  WHERE key1 = 1 OR key2 = 2 OR key3 = 3;

SELECT * FROM innodb_table
  WHERE (key1 = 1 AND key2 = 2)
     OR (key3 = 'foo' AND key4 = 'bar') AND key5 = 5;

用我们上面的test表模拟一个using union: explain select * from test where id > 5 or weight = 10;

Index Merge Sort-Union Access Algorithm

1
2
3
4
5

SELECT * FROM tbl_name
  WHERE key_col1 < 10 OR key_col2 < 20;

SELECT * FROM tbl_name
  WHERE (key_col1 > 10 OR key_col2 = 20) AND nonkey_col = 30;

用我们上面的test表模拟一个using sort_union: explain select * from test where id > 5 or weight < 10;

它的特点，union之前先sort 行的ID。猜测一下，先sort之后再union，是优化器成本衡量后的结果，毕竟sort也是有成本的。

但是，当我们union两个list，如果它们是有序的，那union效率就会高很多。

同时，也要注意如果condition过滤后本身已经有序了，直接union就可以。类似test的using union例子。

也就是说，没必要sort_union的 直接union就可以了。说到底，都是动态成本估算后，选择的问题。

Influencing Index Merge Optimization

MySQL提供optimizer_switch system variable 和 Optimizer Hits来控制Index Merge

问题来了，你会发现index merge并不太高效，and情况下，复合索引会高效点。

or情况下，使用不了combined index，仍然需要index merge，至少比full table scan快。

所以，看起来针对or，single index仍然有存在价值。

更多示例参见Percona multi-column-indexes-vs-index-merge

Hash Join Optimization

这是MySQL8.0.18开始提供的。相比之前版本的 block nested loop，hash join提供更快速的join。注意它的前提：

  • equi-join condition
  • on condition uses no indexes
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

CREATE TABLE t1 (c1 INT, c2 INT);
CREATE TABLE t2 (c1 INT, c2 INT);
CREATE TABLE t3 (c1 INT, c2 INT);

mysql> EXPLAIN FORMAT=TREE
    -> SELECT * 
    ->     FROM t1 
    ->     JOIN t2 
    ->         ON t1.c1=t2.c1\G
*************************** 1. row ***************************
EXPLAIN: -> Inner hash join (t2.c1 = t1.c1)  (cost=0.70 rows=1)
    -> Table scan on t2  (cost=0.35 rows=1)
    -> Hash
        -> Table scan on t1  (cost=0.35 rows=1)

如果给t1.c1加了index，那走的就是Nested loop

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

explain format=tree
SELECT * 
    FROM t1 
    JOIN t2 
        ON t1.c1=t2.c1;

-> Nested loop inner join  (cost=0.70 rows=1)
    -> Filter: (t2.c1 is not null)  (cost=0.35 rows=1)
         -> Table scan on t2  (cost=0.35 rows=1)
    -> Index lookup on t1 using idx_t1_c1 (c1=t2.c1)  (cost=0.35 rows=1)

关于hash join并不是新东西，但是MySQL8.0.18才引入。简单来说，通过hash table去find匹配的行，在两个输入的表中。而不是通过以前的内嵌循环连接。

Hash join可以分为 build阶段 和 probe阶段。

  • build phase：选取smaller的表(size smaller not number of rows)，构建内存hash table，hash key是equi-join的条件
  • probe phase：从bigger的表read row by line，到hash table里去match，match上的send to client

关键点：join_buffer_size

对nested loop join增大它的值，可以减少对被驱动表的扫描次数。而对hash join来说，由于需要build出一个完整的hash table，如果join_buffer_size太小，就会采用spill to disk。没有放到join_buffer里的key，通过chunk files on disk。

目前版本的hash join limitation：

  • only inner hash join，其他的anti, semi, outer joins仍然BNL
  • 如果condition column use index，optimizer仍然会计划BNL，但此时hash join应该是更快的选择

更详细的参加MySQL Blog: Hash join in MySQL 8

Index Condition Pushdown Optimization

ICP：索引条件下推。我们知道MySQL architecture，MySQL server下还有storage engine层来操作文件。而我们优化的终极目的：减少I/O操作，即减少不必要的 retrieve rows。

简单来说，就是把where中的索引条件放到 storage engine层去filter。还是不懂，没关系。粗暴的说法，where中的所有条件，都是可以通过索引去过滤。例子：

1
2
3
4
5
6

-- INDEX (zipcode, lastname, firstname)

SELECT * FROM people
  WHERE zipcode='95054'
  AND lastname LIKE '%etrunia%'
  AND address LIKE '%Main Street%';

直观来看，这个查询只能用到前缀zipcode，而lastname和address没法继续使用索引。当没有index condition pushdown时，MySQL会将zipcode='95054’的行从storage engine读出来，传递给server层继续filter lastname和address。这个过程就产生了 对多余行读的I/O操作，是可以避免的。

我们再来看有了index condition pushdown，where里的其他filter都可以在secondary index上找到，所以，storage engine找到zipcode='95054’的行后，会继续check lastname和address，如果不满足条件 就不去read full table row，从而避免了多余行的读 和 传输。

最后，列出一些ICP的试用场景

  • ICP is used for the range, ref, eq_ref, and ref_or_null access methods when there is a need to access full table rows.
  • ICP can be used for InnoDB and MyISAM tables, including partitioned InnoDB and MyISAM tables.
  • For InnoDB tables, ICP is used only for secondary indexes. The goal of ICP is to reduce the number of full-row reads and thereby reduce I/O operations. For InnoDB clustered indexes, the complete record is already read into the InnoDB buffer. Using ICP in this case does not reduce I/O.
  • ICP is not supported with secondary indexes created on virtual generated columns. InnoDB supports secondary indexes on virtual generated columns.
  • Conditions that refer to subqueries cannot be pushed down.
  • Conditions that refer to stored functions cannot be pushed down. Storage engines cannot invoke stored functions.
  • Triggered conditions cannot be pushed down.

Nested-Loop Join Algorithms

我们知道MySQL处理join tables的算法是：Nested-Loop Join Algorithm 或 NL 的变种 BNL

Nested-Loop Join

简单来说就是，从第一个表中读一行，就去join表里loop一遍匹配，如果有第三个表那就继续嵌套下去。所以，它需要nested-loop很多次，可以理解成N*M*X次遍历。如下：

1
2
3
4
5
6
7

for each row in t1 matching range {
  for each row in t2 matching reference key {
    for each row in t3 {
      if row satisfies join conditions, send to client
    }
  }
}

Block Nested-Loop Join

BNL是优化的结果，它的优化点在于NL的痛点，NL需要多次nested-loop，而我们必须使用loop才能找到匹配的行。结果很自然的想到缓存来减少loop，它就是join buffer。

还是拿t1 t2 t3三个表join做例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

for each row in t1 matching range {
  for each row in t2 matching reference key {
    store used columns from t1, t2 in join buffer
    if buffer is full {
      for each row in t3 {
        for each t1, t2 combination in join buffer {
          if row satisfies join conditions, send to client
        }
      }
      empty join buffer
    }
  }
}

记得我们NL的循环次数是N*M*X，通过join buffer对t3的扫描次数极大的减少了，因为对t3的一次扫描，就可以去匹配join buffer里的很多行，并且这是内存匹配操作。

注意误区，即使2个表 t1 和 t2仍然可以使用join buffer。一次query可能会有多个join buffer

Block Nested Loop的关键点是block，通过一次性读取多行放到内存里，再遍历join表依次内存匹配。所以，match次数并没有减少，只是match操作从文件到内存，自然快了很多。

细心的会发现，loop遍历还是会很慢呀。MySQL会针对join还会有其他的优化点。

Outer Join Optimization

outer joins include right join and left join

假设有 A left join B join_specification，则会有以下关键点：

If there is a row in A that matches the WHERE clause, but there is no row in B that matches the ON condition, an extra B row is generated with all columns set to NULL.

基于left join没有匹配上，new row(null)来替代，这点进阶一下就是：left join => inner join。如下:

1

SELECT * FROM t1 LEFT JOIN t2 ON (column1) WHERE t2.column2=5;

设想一下，t1没有匹配到的t2，我们用null来填上，但是where条件又是在filter t2，所以这个where肯定一直都是false。optimizer就会转换成inner join，目的为了更有效的估算查询成本。如下：

1

SELECT * FROM t1, t2 WHERE t2.column2=5 AND t1.column1=t2.column1;

问题来了，平时explain left join的现象中，你也会发现，第一步有时候会先过滤表，第二步再去join。我们知道这是optimizer的结果，结合上面的left join 到 inner join转换，深入的outer join 的 simplification 操作：

outer join simplification: Table expressions in the FROM clause of a query are simplified in many cases.

首先明确几点：

  • right join 和 left join 是可以互相转换的 (t1 right join t2 on xxx => t2 left join t1 on xxx)
  • inner join 可以转换成 from list (T1 INNER JOIN T2 ON P(T1,T2) => T1,T2, P(T1,T2))
  • 优化器在评估outer join时，并不很智能。它估算的是这个SQL本身，如果不rewrite SQL，即使从逻辑上我们先filter后在join成本会低很多，它仍然会先join后where。

举例：

1

SELECT * T1 LEFT JOIN T2 ON P1(T1,T2) WHERE P(T1,T2) AND R(T2)

只针对上面这个SQL，优化器会先执行T1 join T2，注意：又回到rewrite的点，我们left join T2，然后filter T2。此时，没有匹配到的T2为null，所以R(T2)也就一直是false。

这也就相当于 R(T2) 只对 join到的行 起效，所以 这个left join 是可以转换为 inner join

提炼：

t1 left join t2 => t1 inner join t2 的前提：关于t2的where 是 null-rejected

白话来说，这个where拒绝null的行。关键点在于，考虑这个condition是否对null都是false。如果不是(t2.b is null) 或 判断不了(t1.b < 3 or t2.b > 3)，都是无法转换的。

最后：

通过simplification这个机制，也就可以理解最开始的explain会先filter再join的问题。

MMR Optimization

继续上面的range scan优化，MRR是storage engine层的优化。

当range scan二级索引后，用PK回表拿整行数据时，就会产生大量random disk access。

MRR(Multi Range Read)做法是：将二级索引对应的PK先排序，再进行磁盘扫描 Disk-Sweep，以减少磁盘随机访问。

MRR提供了batch操作：

  • 对于range scan：

    通过index读一点到read_rnd_buffer，排序后在回表拿数据。(因为大多数的数据都是按照主键递增顺序插入得到的，所以我们可以认为，如果按照主键的递增顺序查询的话，对磁盘的读比较接近顺序读，能够提升读性能。)

  • 对于join：

    以往的BNL问题在于，对被驱动表多次scan占用I/O资源，大量join条件判断(M*N)占用CPU，导致buffer pool热数据被淘汰影响命中率。

    BNL转向BKA(Batched Key Access)，当出现BNL应该优化，通过被驱动表join字段加索引。它和BNL的区别就是通过index在被驱动表里搜索行。

BNL and BKA

Block Nested-Loop and Batched Key Access Joins

BKA简单说是使用index去访问join table和join buffer，它极大的提高的join的效率扩展了BNL。

下面是怎么更有效的使用join buffer：

  • MySQL可以使用join buffer即使没有index，同时对inner join / outer join / semi join 都可以有效的使用到
  • join buffer会尽力减小内存使用，如row的column值为null就不分配空间；对varchar可变字符长度进行有多长分配多大字节空间
  • join buffer有两种类型：regular 和 incremental. incremental join buffer是基于前一次的join buffer形成的，也就是说多次join中，第一次join是regular join buffer，后面的是incremental join buffer。
    • regular join buffer包含了join双方的所需的columns，
    • incremental join buffer包含这次需要join的新表column，和一个指向regular的link。这样做可以最大限度降低空间使用。
  • join buffer里的行都会附加一个match flag，用来标记该行是否匹配到join表，join完后将flag没有enabled的行append上null，表示没有匹配上行。
  • join buffer里会先放入驱动表的行R1，如果匹配到被驱动表的的行R2，就会在join buffer中R1行extend上R2的列。
  • BKA通过提取join buffer里row的keys，然后提交给engine 通过MMR接口。存储引擎通过MMR去查询索引快速找到match行，然后返回match行+关联的join buffer对应的行reference
  • join_buffer_size决定了BKA发送的key，也决定了MMR效率。
  • 当前BKA是off的，它基于MMR所以需要同时enable。mysql> SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

至于为什么，BKA默认disable，官方有句话：Currently, the cost estimation for MRR is too pessimistic. Hence, it is also necessary for mrr_cost_based to be off for BKA to be used. 你需要使用的话，也可以通过Optimizer Hits告诉优化器。

未完待续…

Reference

Updated on 2020-03-13
 mysql
Back | Home