MySQL45讲之order工作原理

本文介绍 order 的三种排序方式,全字段排序、rowid 排序和索引树排序,以及每种排序方式具体是如何工作的。

当使用 explain 查看执行计划时,如果 extra 中有 Using filesort,表示经过了排序。

MySQL 会在内存中分配一块内存专门用来排序,可以通过 sort_buffer_size 设置大小。如果需要排序的数据量小于 sort_buffer_size,排序在内存中进行,否则,需要采用 外部排序方法,即借助磁盘排序。

可以通过 OPTIMIZER_TRACE 的结果来查看是否使用了临时文件,

/* 打开optimizer_trace,只对本线程有效 */
SET optimizer_trace='enabled=on';

/* 查看 OPTIMIZER_TRACE 输出 */
SELECT * FROM information_schema.OPTIMIZER_TRACE;

全字段排序

在 city 列已建立普通索引情况下,对于语句 select city,name,age from t where city='杭州' order by name limit 1000; 进行全字段排序流程是:

将要返回的字段全部放到 sort_buffer 进行排序,所以叫全字段排序。

这个算法有个缺点,如果要返回的字段很多,则一行数据的体积很大,这样很可能要用到外部排序,并且一个文件存下的行数有限,需要比较多的临时文件,临时文件一多,排序性能将十分低,所以这时 MySQL 会采用 rowid 排序算法。

rowid排序

当返回的字段很多时,MySQL 将采用 rowid 排序算法。那字段很多的标准是如何界定的呢?MySQL 有一个参数 max_length_for_sort_data,当字段类型的总字节数大于 max_length_for_sort_data 时将采用 rowid 算法。比如, select city,name,age from t where city='杭州' order by name limit 1000; 中 city 和 name 字符串长度都是 16,age 占 4 字节,即总共 36 字节。

在 city 列已建立普通索引情况下,对于语句 select city,name,age from t where city='杭州' order by name limit 1000; 进行 rowid 排序流程是:

从上面流程可见,rowid 排序算法在 sort_buffer 中只放入了排序字段和 id,尽可能避免了外部排序低效的问题,但排序之后,还需要回表重新取一遍返回值的数据。

索引树排序

你可能会问,有没有一种不需要排序的算法?

[En]

You might ask, is there an algorithm that doesn’t have to sort?

有的,就是索引树排序,因为字段值在索引树上已经有序,所以可以直接遍历索引树取到 id,然后到主键索引树拿返回值返回,不需要再排序。

您可以直接从索引树中获取返回的数据,而不是返回到表中吗?

[En]

Can you get the returned data directly from the index tree and not return to the table?

当然也是可以的,这就是索引覆盖的思想,比如 select city,name,age from t where city='杭州' order by name limit 1000; 语句,只要建立联合索引 (city, name, age),就可以避免回表操作。

假设你的表里面已经有了 city_name(city, name) 这个联合索引,然后你要查杭州和苏州两个城市中所有的市民的姓名,并且按名字排序,显示前 100 条记录。如果 SQL 查询语句是这么写的 :

CREATE TABLE t (
  id int(11) NOT NULL,
  city varchar(16) NOT NULL,
  name varchar(16) NOT NULL,
  age int(11) NOT NULL,
  addr varchar(128) DEFAULT NULL,
  PRIMARY KEY (id),
  KEY city (city)
) ENGINE=InnoDB;

select * from t where city in ('杭州',"苏州") order by name limit 100;

1、那么,这个语句执行的时候会有排序过程吗,为什么?

回答:会,因为 city_name 索引只能保证 city 相同的情况下,name 有序。而此时查询两个城市,那么显然不能保证按 name 有序。

2、如果业务端代码由你来开发,需要实现一个在数据库端不需要排序的方案,你会怎么实现呢?

回答:
对单个 city 按 name 排序是可以使用索引的,所以可以将对两个 city 的查询排序拆分成两个单独的查询,然后再合并结果。

SELECT
    *
FROM
    (
    ( SELECT * FROM t WHERE city = '杭州' ORDER BY name LIMIT 100 ) UNION ALL
    ( SELECT * FROM t WHERE city = '北京' ORDER BY name LIMIT 100 )
    ) AS tt
ORDER BY
    tt.name
    LIMIT 100;

注意:这里用 union all 方法进行连接,效率更高。如果使用 union 则会对合并结果进行去重,而这里不会重复。

如果可以修改索引结构且不影响业务,可以考虑修改联合索引为 (name, city) 来避免排序。

3、进一步地,如果有分页需求,要显示第101页,也就是说语句最后要改成 “limit 10000,100″, 你的实现方法又会是什么呢?

回答:

没有更好的优化方法。首先看看商家能不能砍掉排序要求,让用户只能一页一页地翻,让用户基本上只看前几页,不需要考虑这么大的分页。对于不太重要的功能优化,可能会得不偿失。

[En]

There is no better optimization method. First of all, let’s see whether the business can cut the sorting requirement, so that users can only turn page by page, so that users will basically only read the first few pages, so they don’t need to consider this big paging. * the loss may outweigh the gain for less significant functional optimization. *

如果实在需要,就可以先建立联合索引 (name, city),再通过下面的 SQL 查询。

SELECT * FROM t WHERE id IN ( SELECT id FROM t WHERE city IN ('杭州',"苏州") ORDER BY name LIMIT 10000,100 ) AS tmp;

内查询直接索引覆盖,遍历 10100 个节点,拿到末尾的 100 个 id,不需要回表。再在外查询中,根据 id 从表中拿到数据返回客户端。这样,可以避免回表取 10100 次数据,如果符合的数据够 10100 条的话。

Original: https://www.cnblogs.com/flowers-bloom/p/mysql45-how-order-work.html
Author: flowers-bloom
Title: MySQL45讲之order工作原理

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/508130/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球