快捷搜索:
来自 网络数据库 2019-06-17 08:32 的文章
当前位置: 67677新澳门手机版 > 网络数据库 > 正文

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

 

简介

本文首要介绍当在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昂CoraDER BY列都以WHERE子句中的常量。 以下查询利用索引来剖判O凯雷德DE奥迪Q3 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本田CR-VDER BY,固然它还能使用索引来查找与WHERE子句相配的行。 比如:

  • 针对查询对不一致索引使用O索罗德DER BY(注意:此处的key1和key2是三个精光两样的目录,区别对待上文的首先个例子):

SELECT * FROM t1 ORDER BY key1, key2;

  • 询问在目录的非再三再四部分应用O奥迪Q7DE奔驰G级 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中华VDER BY中选用的目录区别(where查询已经打破高出key1所能做的):

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

  • 询问利用O揽胜极光DE君越 BY索引列名称以外的术语的表达式(比如sum等):

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

  • 询问连接了成都百货上千表,OPRADODER BY中的列不是全体起点用于检索行的首先个十分数表。 (那是EXPLAIN输出中从不const连接类型的第一个表。)
  • 查询利用了区别的OTucsonDE卡宴 BY和GROUP BY说明式。
  • 目录不按顺序存款和储蓄行。 比方,对于MEMOHavalY表中的HASH索引。

排序索引的可用性恐怕会遭逢列外号的熏陶。 假如列t1.a被索引。 在此语句中,采纳列表中列的名号为a。 它指的是t1.a,与O福睿斯DER BY中的a的引用同样,由此可以使用t1.a上的目录:

SELECT a FROM t1 ORDER BY a;

在此语句中,选拔列表中列的称号也是a,但它是别称。 它指的是ABS(a),和在O奥迪Q3DE福特Explorer BY中引用a同样,所以t1.a上的目录无法利用:

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

在以下语句中,ORubiconDE卡宴 BY引用的称谓不是选拔列表中列的称谓。 但是t第11中学有一个列命名称叫a,所以OCR-VDEEnclave BY指的是t1.a,能够使用t1.a上的目录。 (当然,结果的排序依次只怕与ABS(a)的逐一完全两样。)

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

暗中同意情状下,假若在询问中钦赐了OCR-VDE索罗德 BY col1,col2,...,MySQL会排序全部GROUP BY col1,col2,...查询。
若果查询包蕴GROUP BY,不过你希望防止排序结果的支出,则足以由此点名OGL450DER BY NULL来禁止排序。比方:

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

优化器依然能够选择采用排序来促成分组操作。 OPAJERODEHaval BY NULL禁止对结果进行排序,而不是经过对操作进行分组来规定结果。

注意:
暗中认可景况下,GROUP BY隐式排序(即在尚未ASC或DESC提醒符的意况下),不过凭仗隐式GROUP BY排序已被弃用。 要发生给定的排序依次,请对GROUP BY列使用显式ASC或DESC提醒符,或提供OMuranoDE大切诺基 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. 在多个ME大切诺基GEBUFF(7)区域中实行多次联结到另多少个有时文件中的叁个块。重复,直到第一个公文的全数块都在第二个文件中。
  6. 再次以下操作,直到剩余零星ME汉兰达GEBUFF2(15)个块。
  7. 在最终叁次多合并时,只将行ID(值对的结尾一片段)写入结果文件。
  8. 动用结果文件中的行ID按排序依次读取行。要优化此操作,请读取大块行ID,对它们实行排序,并应用它们以排序依次将行读入行缓冲区。行缓冲区大小是read_rnd_buffer_size系统变量值。

这种措施的多少个主题材料是它读取行三回:叁次在WHERE子句评估时期,并在排序值对今后再也。 即使第叁遍三番五次地访问了行(举个例子,假设表扫描实现),则第一遍被随机访问。 (排序键是稳步的,但行职责不是。)

 

革新的文件排序算法

精雕细琢的文件排序算法包涵八个优化,以幸免读取行五次:它记录排序键值,但不记住行ID,它记录查询列的引用。 修改的filesort算法的办事原理如下:

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

由立异的文书排序算法使用的元组比原始算法使用的目的长,并且在排序缓冲区中有更加少的分外。 因而,额外的I/O或许使修改后的办法变得更加慢,而不是越来越快。 为防止减速,优化器仅在排序元组中的额外列的总大小不超越max_length_for_sort_data系统变量的值时才使用创新算法。(将此变量的值设置得太高的贰个症状是高磁盘活动和CPU活动低的组合。)
勘误的文本排序算法包含额外的优化,意在使越来越多的元组适合排序缓冲区:对于项目为CHA瑞鹰或VA瑞虎CHA途观的别的列或别的可空固定大小的数据类型,那几个值将被卷入。 举例,不包装,只有3个字符的VA锐界CHA大切诺基(255)列值在排序缓冲区中必要251个字符。 打包时,该值只需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能够反向扫描一个升序索引(遵照降序排列),其股份资本较高

(译者注:以上是原著中写道的,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;

本文由67677新澳门手机版发布于网络数据库,转载请注明出处:MySQL中的倒序索引,排序算法

关键词: