排序算法,MySQL中的倒序索引

2019-12-31 06:17 来源:未知

 

简介

本文首要介绍当在MySQL中实践order by时,MySQL使用的排序算法。当在select语句中运用order by语句时,MySQL首先会利用索引来制止实施排序算法;在不可能接纳索引的状态下,或许利用 高速排序归拢列排在一条线序堆排序拓展排序。
本文中大多地点都以翻译的MySQL官网,克罗地亚语好的校友可径直翻看原作

译者注:
MySQL 8.0事情发生前,不管是或不是钦定索引建的排序格局,都会忽略创设索引时候钦命的排序方式(语法上不会报错),最后都会创制为ASC情势的目录,
在试行查询的时候,只设有forwarded(正向)情势对索引举行围观。
至高满堂向索引和反向索引,逻辑上比较轻巧掌握,这里有八个相关的概念:
正向索引可能反向(倒序)索引,两者都以在营造B树索引时候的相干字段排序情势,是B索引树的逻辑存款和储蓄方式
正向扫描(forward)和反向扫描( Backward index scan;)是实施查询的经过中对B树索引的扫描情势,是多少实行陈设时候的生机勃勃种索引围观方式
有关正向扫描也许反向扫描不是专擅的,受sql语句中(正/反向)排序方式以至(正/反向)索引的影响
前边在sqlserver中简单写过一些肖似的事物,

目录排序

在一些意况下,MySQL能够行使索引来满意O福睿斯DER BY子句,进而无需实行额外的排序。
尽管O兰德逍客DER BY与索引不完全协作,索引也能够选取,只要索引的享有未利用部分和兼具额外的O奥迪Q3DER BY列都以WHERE子句中的常量。 以下查询利用索引来解析OCRUISERDE凯雷德 BY部分:

SELECT * FROM t1
  ORDER BY key_part1, key_part2;

SELECT * FROM t1
  WHERE key_part1 = constant
  ORDER BY key_part2;

SELECT * FROM t1
  ORDER BY key_part1 DESC, key_part2 DESC;

SELECT * FROM t1
  WHERE key_part1 = 1
  ORDER BY key_part1 DESC, key_part2 DESC;

SELECT * FROM t1
  WHERE key_part1 > constant
  ORDER BY key_part1 ASC;

SELECT * FROM t1
  WHERE key_part1 < constant
  ORDER BY key_part1 DESC;

SELECT * FROM t1
  WHERE key_part1 = constant1 AND key_part2 > constant2
  ORDER BY key_part2;

在好几意况下,MySQL不可能运用索引来深入解析O纳瓦拉DER BY,就算它还是可以够使用索引来查找与WHERE子句相称的行。 举个例子:

  • 针对查询对差别索引使用OSportageDER BY(注意:此处的key1和key2是四个精光两样的目录,差距对待上文的首先个例子):

SELECT * FROM t1 ORDER BY key1, key2;

  • 询问在目录的非一而再三番五次部分选拔OLacrosseDE昂Cora BY:

SELECT * FROM t1 WHERE key2=constant ORDER BY key_part1, key_part3;

  • 查询混合使用ASC和DESC:

SELECT * FROM t1 ORDER BY key_part1 DESC, key_part2 ASC;

  • 用来获取行的目录与O奥德赛DER BY中运用的目录差异(where查询已经打破超过key1所能做的):

SELECT * FROM t1 WHERE key2=constant ORDER BY key1;

  • 查询利用OSportageDE凯雷德 BY索引列名称以外的术语的表明式(比方sum等卡塔尔(قطر‎:

SELECT * FROM t1 ORDER BY ABS(key);
SELECT * FROM t1 ORDER BY -key;

  • 询问连接了广大表,O猎豹CS6DER BY中的列不是整个来源于用于检索行的第八个可怜数表。 (那是EXPLAIN输出中一直不const连接类型的首先个表。)
  • 询问利用了不相同的OMuranoDEHaval BY和GROUP BY表明式。
  • 目录不按顺序存款和储蓄行。 比如,对于MEMOXC90Y表中的HASH索引。

排序索引的可用性可能会惨被列别称的影响。 假使列t1.a被索引。 在这里语句中,选取列表中列的称谓为a。 它指的是t1.a,与OHavalDER BY中的a的援用一样,由此能够使用t1.a上的目录:

SELECT a FROM t1 ORDER BY a;

在此语句中,选拔列表中列的名称也是a,但它是小名。 它指的是ABS(a),和在OEnclaveDE宝马X3 BY中引用a相仿,所以t1.a上的目录不可能使用:

SELECT ABS(a) AS a FROM t1 ORDER BY a;

在偏下语句中,OLacrosseDETiggo BY援引的名号不是挑选列表中列的称号。 可是t1中有一个列命名称叫a,所以OPAJERODEPAJERO BY指的是t1.a,能够使用t1.a上的目录。 (当然,结果的排序依次大概与ABS(a)的逐个完全区别。)

SELECT ABS(a) AS b FROM t1 ORDER BY a;

私下认可意况下,若是在查询中钦定了O中华VDE科雷傲 BY col1,col2,...,MySQL会排序全部GROUP BY col1,col2,...查询。
假诺查询包涵GROUP BY,不过你希望幸免排序结果的花销,则足以由此点名O凯雷德DER BY NULL来制止排序。举个例子:

INSERT INTO foo
SELECT a, COUNT(*) FROM bar GROUP BY a ORDER BY NULL;

优化器照旧能够筛选接收排序来促元素组操作。 O冠道DE福睿斯 BY NULL防止对结果举行排序,并非经过对操作举办分组来规定结果。

注意:
私下认可情况下,GROUP BY隐式排序(即在还未有ASC或DESC提醒符的情形下),然而依赖隐式GROUP BY排序已被弃用。 要发出给定的排序依次,请对GROUP BY列使用显式ASC或DESC提示符,或提供O君越DEQashqai BY子句。 GROUP BY排序是一个MySQL扩大,或许会在以后的版本中纠正; 举例,为了使优化器以其感觉最可行的不二等秘书籍对分组实行排序并制止排序开支。

一言以蔽之,抛开正向索引和倒序索引,在围观扫描的长河中,正向索引围观的在质量上,稍稍优于反向索引围观。
可是,即正是反向索引围观,也是优化器依照实际查询进行优化的结果,并不是两个倒霉的选料。

排序算法

当order by不可能利用索引实行排序时,将采纳排序算法进行排序:

  1. 若排序内容能全体放入内部存款和储蓄器,则仅在内部存款和储蓄器中央银行使迅猛排序
  2. 若排序内容不可能一切归入内部存款和储蓄器,则分批次将排好序的剧情放入文件,然后将四个公文实行合併列排在一条线序
    3.若排序中包括limit语句,则运用堆排序优化排序进程

注意:
MySQL是在5.6后引进堆排序来优化limit子句,但堆排序是非稳固的(对于同生机勃勃的key值,不能够保险排序后与排序前的职位大器晚成致卡塔尔(قطر‎,所以产生分页重复的现象。为了防止这几个难点,大家可以在排序中增添唯风姿罗曼蒂克值,举例主键id,那样由于id是唯风华正茂的,确认保证参预排序的key值不等同。
例:SELECT * FROM ratings ORDER BY category, id LIMIT 5;

 

土生土养文件排序算法

  1. 依据键或表扫描读取全体行。跳过不切合WHERE子句的行。
  2. 对于每大器晚成行,在排序缓冲区中蕴藏由大器晚成对值(排序键值和行ID)组成的元组。
  3. 若果持有对都相符排序缓冲区,则不会创立不常文件。否则,当排序缓冲区变满时,在内部存储器中运作迅猛排序并将其写入不经常文件。保存指向排序块的指针。
  4. 双重上述手续,直到读取全部行。
  5. 在多少个MERAV4GEBUFF(7)区域中进行多次联合到另多少个不经常文件中的二个块。重复,直到第一个文本的兼具块都在其次个公文中。
  6. 重新以下操作,直到剩余零星MECR-VGEBUFF2(15)个块。
  7. 在最终二次多合併时,只将行ID(值没有错尾声一片段)写入结果文件。
  8. 使用结果文件中的行ID按排序依次读取行。要优化此操作,请读取大块行ID,对它们进行排序,并利用它们以排序依次将行读入行缓冲区。行缓冲区大小是read_rnd_buffer_size系统变量值。

这种艺术的叁个难题是它读取行五回:一回在WHERE子句评估时期,并在排序值对现在再次。 就算第一回三回九转地拜望了行(例如,倘诺表扫描实现),则第4回被轻巧访谈。 (排序键是一动不动的,但行任务不是。)

 

精耕细作的公文排序算法

校订的公文排序算法包括叁个优化,以制止读取行四遍:它记录排序键值,但不记住行ID,它记录查询列的援用。 改革的filesort算法的行事规律如下:

  1. 读取与WHERE子句相配的行。
  2. 对于每生龙活虎行,在排序缓冲区中积存由排序键值和询问引用的列组成的元组。
  3. 当排序缓冲区变满时,通过内部存款和储蓄器中的排序键值对元组进行排序,并将其写入临时文件。
  4. 在联合排序有的时候文件之后,以排序依次检索行,可是从排序的元组中平昔读取查询所需的列,并非重新做客该表。

由改善的文书排序算法使用的元组比原始算法使用的靶子长,而且在排序缓冲区中有更加少的相称。 由此,额外的I/O恐怕使校勘后的艺术变得更加慢,实际不是更加快。 为幸免减速,优化器仅在排序元组中的额外列的总大小不当先max_length_for_sort_data系统变量的值时才使用修改算法。(将此变量的值设置得太高的二个病症是高磁盘活动和CPU活动低的组合。)
精雕细琢的文件排序算法饱含额外的优化,意在使更加多的元组切合排序缓冲区:对于项目为CHATucson或VARCHAHaval的此外列或别的可空固定大小的数据类型,这几个值将棉被服装进。 比如,不包装,唯有3个字符的VARCHAWrangler(255)列值在排序缓冲区中须求255个字符。 打包时,该值只需3个字符,加上三个字节的长短提示符。 NULL值只需求三个位掩码。


参考文献

  1. ORDER BY Optimization
  2. LIMIT Query Optimization

原来的文章链接:http://mysqlserverteam.com/mysql-8-0-labs-descending-indexes-in-mysql/ 

 

以下为译文:

从8.0优化器实验室公布开端,MySQL先河辅助倒序索引。
正如小编就要本文中详尽介绍的,那些新个性可以用来消灭对结果排序的急需,并在重重询问中带给品质修正。

 

简介

在那版本以前,全数索引都以按升序成立的。当语法自个儿被分析时,元数据不会被保留。举个例子在MySQL 5.7中:

mysql 5.7> CREATE TABLE t1 (a INT, b INT, INDEX a_desc_b_asc (a DESC, b ASC));
Query OK, 0 rows affected (0.47 sec)

mysql 5.7> SHOW CREATE TABLE t1G
*************************** 1. row ***************************
       Table: t1
Create Table: CREATE TABLE `t1` (
  `a` int(11) DEFAULT NULL,
  `b` int(11) DEFAULT NULL,
  KEY `a_desc_b_asc` (`a`,`b`) <-- 创建索引时候的元数据没有被保留
) ENGINE=InnoDB DEFAULT CHARSET=latin1
1 row in set (0.00 sec)

应当注意的是,MySQL 5.7 optimizer能够反向扫描三个升序索引(遵照降序排列State of Qatar,其资金财产较高

(译者注:以上是原来的作品中写道的,MySQL 5.7中不掌握怎么去看清在对索引围观的时候,究竟是正向扫描依然反向扫描)。
正如能够更进一层测验,大家能够见见正向索引围观比反向索引围观好~15%。
不能帮衬倒叙索引的入眼限定是,优化器必得对混合顺序(如DESC、b ASC的逐个卡塔尔使用文件排序。

MySQL 8.0中的订正

引进反向索引后,InnoDB现在得以据守降序顺序存款和储蓄数据行,优化器将在查询中倡议降序时使用它。
双重上边包车型大巴例子,大家能够看出在开立表时目录顺序消息被科学地保存了:

mysql 8.0> CREATE TABLE t1 (a INT, b INT, INDEX a_desc_b_asc (a DESC, b ASC));
Query OK, 0 rows affected (0.47 sec)

mysql 8.0> show create table t1;
+-------+--------------------------------------------------------------------------------------------------------------------------------------------------------+
| Table | Create Table |
+-------+--------------------------------------------------------------------------------------------------------------------------------------------------------+
| t1 | CREATE TABLE `t1` (
`a` int(11) DEFAULT NULL,
`b` int(11) DEFAULT NULL,
KEY `a_desc_b_asc` (`a` DESC,`b`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1 |
+-------+--------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.00 sec)

为了分化向后和前进索引围观,还改进了EXPLAIN的输出。
对此MySQL-5.7,除了查询2和查询6之外,大家对负有查询都利用反向索引围观或文件排序,因为这多个查询只须要升序。

 

Query 1: SELECT * FROM t1 ORDER BY a DESC;

mysql 8.0> explain SELECT * FROM t1 ORDER BY a DESC;
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-------------+
| 1  | SIMPLE    | t1    | NULL    | index  | NULL | a_desc_b_asc | 10 | NULL | 10 | 100.00 | Using index |
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

Query 2: SELECT * FROM t1 ORDER BY a ASC;

mysql 8.0> explain SELECT * FROM t1 ORDER BY a ASC;
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+----------------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+----------------------------------+
| 1 | SIMPLE | t1 | NULL | index | NULL | a_desc_b_asc | 10 | NULL | 10 | 100.00 | Backward index scan; Using index |
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+----------------------------------+
1 row in set, 1 warning (0.00 sec)

Query 3: SELECT * FROM t1 ORDER BY a DESC, b ASC;

mysql 8.0> EXPLAIN SELECT * FROM t1 ORDER BY a DESC, b ASC;
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-------------+
| 1 | SIMPLE | t1 | NULL | index | NULL | a_desc_b_asc | 10 | NULL | 10 | 100.00 | Using index |
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)

Query 4: SELECT * FROM t1 ORDER BY a ASC, b DESC;

mysql 8.0> EXPLAIN SELECT * FROM t1 ORDER BY a ASC, b DESC;
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+----------------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+----------------------------------+
| 1 | SIMPLE | t1 | NULL | index | NULL | a_desc_b_asc | 10 | NULL | 10 | 100.00 | Backward index scan; Using index |
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+----------------------------------+
1 row in set, 1 warning (0.00 sec)

Query 5: SELECT * FROM t1 ORDER BY a DESC, b DESC;

mysql 8.0> EXPLAIN SELECT * FROM t1 ORDER BY a DESC, b DESC;
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------------+
| 1 | SIMPLE | t1 | NULL | index | NULL | a_desc_b_asc | 10 | NULL | 10 | 100.00 | Using index; Using filesort |
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------------+
1 row in set, 1 warning (0.01 sec)

Query 5: SELECT * FROM t1 ORDER BY a ASC, b ASC;

mysql 8.0> EXPLAIN SELECT * FROM t1 ORDER BY a ASC, b ASC;
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------------+
| 1 | SIMPLE | t1 | NULL | index | NULL | a_desc_b_asc | 10 | NULL | 10 | 100.00 | Using index; Using filesort |
+----+-------------+-------+------------+-------+---------------+--------------+---------+------+------+----------+-----------------------------+
1 row in set, 1 warning (0.00 sec)

当表中有二个索引a_desc_b_asc (a DESC, b ASCState of Qatar时,以下是上述6个查询的品质指标。

多少大小为1000万行。在MySQL-5.7中,它是a_asc_b_asc(a ASC, b ASC卡塔尔(قطر‎,因为不协理倒叙索引。

图片 1

质量目的的表达:

1, 对于查询1,也即OTucsonDEPRADO BY a DESC;:
我们看看查询1中性能的晋升,因为要求的语句排序是“a”列的DESC
翻译注:因为MySQL8.0中能够建构倒叙索引,查询1依照a字段desc排序,直接走正向(forwarded)索引围观就能够达成查询,
制止了在MySQL5.7中询问出来数据未来再实行排序操作的步骤

2,对于查询2:
鉴于查询2的排序为正序(译者注:与索引的顺序相反,由此要求反向扫描),由于反向索引围观,
在MySQL-8.0中(相对于查询1)实行向反向索引围观必要更加多的小运
(注意,从图中能够见到,MySQL-8.0总体上显示更加好。MySQL 5.7纯正向索引围观,与MySQL 8.0中反向索引围观费用的日子(大致)相似)

3,对于查询3 也即O哈弗DEPRADO BY a DESC, b ASC;:
查询3的排序格局与查询1像样,但是在MySQL-5.7中,对于其他央求混合顺序的询问,会对查询结果再度排序,由此质量差异是品格高尚的人的。

4,对于查询4 也即 ORubiconDE福睿斯 BY a ASC, b DESC;
能够见到,在MySQL 8.0中,查询4推行的是反向索引围观,由此比查询3耗费了越来越多的时间,
虽说,在查询5和询问6中,排序的秘技是(a DESC, b DESC卡塔尔/(a ASC, b ASC卡塔尔国,不管是正向扫描依旧反向扫描,都不可能满足排序须要,因而会用到filesort
只是,在此种场合下,由于在MySQL-5.7中ASC/DESC索引标识被忽略(译者注:MySQL 5.7中并未有正向和反向索引的概念),由此MySQL-5.7能够使用(正向/反向)索引围观来交给央浼的次第。

5,要是顾客想要幸免查询5和查询6的filesorts,能够改良表以增添三个键(a ASC, b ASC卡塔尔国。
除此以外,假诺顾客也想制止反向索引围观,能够并且丰裕(a ASC, b DESC卡塔尔国和(a DESC, b DESCState of Qatar。

下边是加多了第5点下的额外索引后的MySQL-5.7.14和MySQL-8.0-labs的末段比较:

图片 2

介意,在MySQL-5.7中,大家不能够增添额外的目录来提升上述查询的本性。
还要,有了那一个特点,在少数景况下得以幸免物化,比如在连接中的第一个表上倡议混合顺序。
在有个别用例中,反向索引提升了质量。区间扫描采访方法也利用反向索引。
即便并非具备的限量扫描访谈方法都应用反向索引,但大家将在未来尝试废除那个节制。

改进

乘胜倒序索引(反向索引)的引进,大家已经去除了对隐式排序的支撑,结果是作为GROUP BY的一片段涉及的列的升序。
除去上述改善外,大家还看见在有个别情景下质量拿到了改革,那么些意况下的依次是富含的,但大概不是非常重要的。

 

总结

大家很快乐可以消除MySQL社区短期存在的效率央浼之少年老成。请垂询倒叙索引的性子,让大家知道您的主张!

 

 

TAG标签:
版权声明:本文由金沙澳门唯一官网发布于数据库管理,转载请注明出处:排序算法,MySQL中的倒序索引