MySQL实践篇-order by

数据库 评论

order by是怎么工作的？

按照名字排序返回前1000个人的姓名、年龄。

假设这个表的是这样的

1
2
3
4
5
6
7
8
9
10

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;

SQL语句

1
2

select city,name,age from t where city='杭州' order by name limit 1000  ;

全字段排序

在city字段上创建索引之后，用explain命令来看看这个语句的执行情况。

Extra 这个字段中“Using filesort”表示的就是需要排序，MySQL会给每个线程分配一块内存用于排序，称为sort_buffer。

满足city=“杭州”条件的行，是从ID_X到ID_(X+N)的这些记录。

通常情况下，语句的执行流程如下：

  1. 初始化sort_buffer,确定放入name，city，age这三个字段；
  2. 从索引city找到第一个满足city=“杭州”条件的主键id，也就是图中的ID_X;
  3. 到主键id索引取出整行，取name、city、age三个字段的值，存入sort_buffer中；
  4. 从索引city取下一个记录的主键id；
  5. 重复步骤3、4知道city的值不满足查询条件为止，对应的主键id也就是图中的ID_Y;
  6. 对sort_buffer中的数据按照字段name做快速排序；
  7. 按照排序结果取前1000行返回给客户端。

这个排序过程，称为全字段排序。

图中按name排序这个动作，可能在内存中完成，也可能需要使用外部排序，这取决于排序所需的内存和参数sort_buffer_size。

sort_buffer_size,就是MySQL为排序开辟的内存(sort_buffer)的大小。如果要排序的数据量小于sort_buffer_size，排序就在内存中完成。但是如果排序数据量太大，内存放不下，则不得不利用磁盘临时文件辅助排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

/* @a保存Innodb_rows_read的初始值 */
select VARIABLE_VALUE into @a from  performance_schema.session_status where variable_name = 'Innodb_rows_read';

/* 执行语句 */
select city, name,age from t where city='杭州' order by name limit 1000; 

/* 查看 OPTIMIZER_TRACE 输出 */
SELECT * FROM `information_schema`.`OPTIMIZER_TRACE`\G

/* @b保存Innodb_rows_read的当前值 */
select VARIABLE_VALUE into @b from performance_schema.session_status where variable_name = 'Innodb_rows_read';

/* 计算Innodb_rows_read差值 */
select @b-@a;

这个方法是通过OPTIMIZER_TRACE
的结果来确认的，可以从number_of_tmp_files中看到是否使用了临时文件。

number_of_tmp_files表示的是，排序过程中使用的临时文件数。外部排序一般使用归并排序算法。

MySQL将需要排序的数据分成12份，每一份单独排序后存在这些临时文件中，然后把这12个有序文件再合并成一个有序的大文件。

如果sort_buffer_size超过了需要排序的数据量的大小，number_of_tmp_files就是0，表示排序可以直接在内存中完成。

否则就需要放在临时文件中排序。sort_buffer_size越小，需要分成份数越多，number_of_tmp_files的值就越大。

上图的内容：

示例表中有4000条满足city=‘杭州’的记录，所以你可以看到examined_rows=4000.表示参与排序的行数是4000行。

sort_model里面的packed_additional_fields的意思是，排序过程中对字符串做了“紧凑”处理。即使name字段的定义是varchar(16),在排序过程中还是按照实际长度来分配空间的。

对原表的数据读了以便，剩下的操作都是在sort_buffer和临时文件中执行。如果查询要返回的字段很多的话，那么sort_buffer里面要放的字段数太多，这样内存里能同时放下的行数很少，要分成很多个临时文件，排序的性能会很差。

rowid排序

如果MySQL认为排序的单行长度太大会怎么做呢？

1
2

SET max_length_for_sort_data = 16;

max_length_for_sort_data，是Mysql中专门控制用于排序的行数据的长度的一个参数。如果单行的长度超过这个值，MySQL就认为单行太大，要换一个算法。

city、name、age这三个字段的定义长度是36，把max_length_for_sort_data设置为16。

新的算法放入sort_buffer的字段，只有要排序的列(即name字段)和主键id。

但这时，排序的结果积极因为少了city和age字段的值，不能直接返回了，整个执行流程就变成了如下这样：

  1. 初始化sort_buffer，确定放如两个字段，即name和id；
  2. 从索引city找到第一个满足city=‘杭州’条件的主键id，也就是图中的ID_X;
  3. 到主键id索引取出整行，取name、id这两个字段，存入sort_buffer中；
  4. 从索引city取下一个记录的主键id；
  5. 重复步骤3、4直到不满足city=‘杭州’条件为止，也就是图中的ID_Y;
  6. 对sort_buffer中的数据按照字段name排序；
  7. 遍历排序结果、取前1000行，并按照id的值回到原表中取出city、name和age三个字返回给客户端。

从OPYIMIZER_TRACE的结果：

  • sort_mode变成了<sort_key,rowid>，表示参与排序的只有name和id这两个字段。
  • number_of_tmp_files变成10了，是因为这个时候参与排序的行数虽然仍然是4000行，但是每一行都变小了，因此需要排序的总数据量就变小了，需要的临时文件也相应地变少了。

全字段排序VSrowid排序

如果MySQL实在是担心排序内存大小，会影响排序效率，才会采用rowid排序算法，这样排序过程中一次可以排序更多行，但是需要再回到原表去取数据。

如果MySQL认为内存足够大，会优先选择全字段排序，把需要的字段都放到sort_buffer中，这样排序后就会直接从内存里面返回查询结果了，不用再回到原表去取数据。

体现了MySQL的一个设计思想L如果内存够，就要多利用内存，尽量少磁盘访问。

对于InnoDB表来说，rowid排序会要求回表多造成磁盘度，因此不会优先选择。

如果能够保证city这个索引上取出来的行，天然就是按照name递增排序的话，就可以不用再排序了。

1
2

alter table t add index city_user(city, name);

可以创建一个city和name的联合索引

这样查询流程就变成了：

  1. 从索引(city，name)找到第一个满足的city=‘杭州’条件的主键id；
  2. 到主键id索引取出整行，取name，city、age三个字段的值，作为结果集的一部分直接返回。
  3. 从索引(city,name)取下一个记录主键id；
  4. 重读步骤2、3直到查到第1000条记录，或者是不满足city=‘杭州’条件时循环结束。

可以看到Extra字段中没有Using filesort了，也就是不需要排序了。由于联合索引(city,name)本身有序，所以查询也不用把4000行全部读一遍。

可以用覆盖索引进一步优化

1
2

alter table t add index city_user_age(city, name, age);

这时，对于city字段的值相同的行来说，还是按照name字段的值递增排序的，此时的查询语句也就不需要排序了。

这时查询语句的执行流程就变成了：

  1. 从索引(city,name,age)找到第一个满足city=‘杭州’条件的记录，取出其中的city、name、age这三个字段的值，作为结果集的一部分直接返回；
  2. 从索引(city,name,age)取下一个记录，同样取出这三个字段的值，作为结果集的一部分直接返回；
  3. 重复执行步骤2，直接到查到第1000条记录，或者是不满足city=‘杭州’条件时循环结束。

Extra字段多了Using index，表示的就是使用了覆盖索引，性能上会快很多。

另外一种需求，当需要随机滚动查询时，如何来设计SQL语句。

直接从单词表中随机选出三个单词

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

mysql> CREATE TABLE `words` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `word` varchar(64) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

delimiter ;;
create procedure idata()
begin
  declare i int;
  set i=0;
  while i<10000 do
    insert into words(word) values(concat(char(97+(i div 1000)), char(97+(i % 1000 div 100)), char(97+(i % 100 div 10)), char(97+(i % 10))));
    set i=i+1;
  end while;
end;;
delimiter ;

call idata();

内存临时表

使用order by rand()来实现这个逻辑。

1
2

mysql> select word from words order by rand() limit 3;

随机排序取前3个。

explain命令来查看语句的执行情况。

Extra字段显示Using temporary，表示的是需要使用临时表；Using filesort，表示是需要执行排序操作。

对于InnoDB表来说，临时内存表，执行全字段排序会减少磁盘访问，因此会被优先选择。

对于内存表，回表过程只是简单地根据数据行的为止，直接访问内存得到数据，根本不会导致多访磁盘。优化器没有了这一层顾虑，那么它会优先考虑，就是用于排序的行越小越好。所以MySQL这时就会选择rowid排序。

这条语句的执行流程：

  1. 创建一个临时表。这个临时表使用的是memory引擎，表里有两个字段，第一个字段是double类型，为了后面描述方便，记为字段R，第二个字段是varchar(64)类型，记为字段W。并且，这个表没有建索引。
  2. 从words表，按主键顺序取出所有的word值，对于每一个word值，调用rand()函数生成一个大于0小于1的随机小数，并把这个随机小数和word分别存入临时表的R和W字段中，到此，扫描行数是10000。
  3. 现在临时表有10000行数据了，接下来你要是在这个没有索引的内存临时表上，按照字段R排序。
  4. 初始化sort_buffer。sort_buffer中有两个字段，一个是double类型，另一个是整型。
  5. 在内存临时表中一行一行地取出R值和位置信息(位置信息？)，分别存入sort_buffer中的两个字段里。这个过程要对内存临时表做全表扫描，此时扫描行数增加10000，变为20000。
  6. 在sort_buffer中根据R的值进行排序。这个过程没有涉及到表操作，所以不会增加扫描行数。
  7. 排序完成后，取出前三个结果的位置信息，依次在内存临时表取出word值，返回给客户端。这个过程中，访问了表的三行数据，总扫描行数变成了20003。

通过满查询日志(show log)来验证一下我们分析得到的扫描行数是否正确。

1
2
3
4

# Query_time: 0.900376  Lock_time: 0.000347 Rows_sent: 3 Rows_examined: 20003
SET timestamp=1541402277;
select word from words order by rand() limit 3;

MySQL的表是用什么方法来定位”一行数据”的

如果把InnoDB表的主键删掉，就没有主键了，就没办法回表了。

如果你创建的表有主键，或者把这个表的主键删掉了，那么InnoDB会自己生成一个长度为6字节的rowid来作主键。

这也就是排序模式里面，rowid名字的来历。实际上它表示的是：每个引擎用来唯一标识数据行的信息。

  • 对于有主键的InnoDB表来说，这个rowid就是主键ID；
  • 对于没有主键的InnoDB表来说，这个rowid就是由系统生成的；
  • MEMORY引擎不是索引组织表，这个例子里面，你可以认为他就是一个数组，因此，这个rowid其实就是数组的下标。

order by rand()使用了内存临时表，内存临时表排序的时候使用了rowid排序方法啊。

磁盘临时表

tmp_table_size这个配置限制了内存临时表的大小，默认值是16M。如果临时表大小超过了tmp_table_size,那么内存临时表就会转换成磁盘临时表。

磁盘临时表使用的引擎默认是InnoDB，是由参数internal_tmp_disk_storage_engine控制的。

当使用磁盘临时表的时候，对应的就是一个没有显示索引的InnoDB表的排序过程。

为了复现这个过程，我把tmp_table_size设置成1024，把sort_buffer_size设置成32768，把max_length_for_sort_data设置成16。

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

set tmp_table_size=1024;
set sort_buffer_size=32768;
set max_length_for_sort_data=16;
/* 打开 optimizer_trace，只对本线程有效 */
SET optimizer_trace='enabled=on'; 

/* 执行语句 */
select word from words order by rand() limit 3;

/* 查看 OPTIMIZER_TRACE 输出 */
SELECT * FROM `information_schema`.`OPTIMIZER_TRACE`\G

因为将max_length_for_sort_data设置成16，小于word字段的长度定义，所以看到sort_mode里面显示的rowid排序，这个是符合预期的，参与排序的是随机值R字段和rowid字段组成的行。

filesort_priority_queue_optimization这个部分的chosen=true，表示使用了优先队列算法。这个过程中不需要临时文件，因此对应number_of_tmp_files是0。

R字段存放的随机值就是8个字节，rowid是6个字节(为什么是6个呢？),数据总行数是10000，这样算出来就有140000字节，超过了sort_buffer_size定义的32768字节了。但是，number_of_tmp_files的值居然是0。难道是需要用临时文件吗？

这个语句采用了新的排序算法，优先队列排序算法。为什么没有使用临时文件的算法—–归并排序算法，而是采用了优先队列排序算法。

其实，SQL语句只需要取R值最小的3个rowid。但是如果使用归并排序算法的话，虽然最终也能得到前3个值，但是这个算法结束后，已经将10000行数据都排好序了。

优先队列算法，就可以精确地只得到三个最小值

  1. 对10000个准备排序的(R,rowid),先取前三行，构造一个堆；
  2. 取下一行(R’,rowid’),跟当前堆里面最大的R 比较，如果R‘小于R，把这个(R,rowid)从堆中去掉换成(R’,rowid’);
  3. 重复第2步，直到第10000个(R’,rowid’)完成比较。

随机排序方法

如果只所以1个word值。

  1. 取得这个表的主键的最大值M和最小值N；
  2. 用随机函数生成一个最大值到最小值之间的数X=(M-N)*rand+N;
  3. 取小于X的第一个ID的行。

这个算法，暂时称作随机算法1.

1
2
3
4

mysql> select max(id),min(id) into @M,@N from t ;
set @X= floor((@M-@N+1)*rand() + @N);
select * from t where id >= @X limit 1;

这个方法效率很高，因为取max(id)和min(id)都不需要扫描索引，而第三步的select也可以用索引快速定位，可以认为就只扫描了3行。

这个算法不够严谨，因为ID中间可能有空洞，因此选择不同行的概率不一样，不是真正的随机。

为了得到严格随机的结果，需要下面的流程：

  1. 取得整个表的行数，并记为C；
  2. 取得Y=floor(C*rand())。floor函数在这里的作用，就是取整数部分。
  3. 再用limitY，1取一行。

这个算法称为随机算法2

1
2
3
4
5
6
7

mysql> select count(*) into @C from t;
set @Y = floor(@C * rand());
set @sql = concat("select * from t limit ", @Y, ",1");
prepare stmt from @sql;
execute stmt;
DEALLOCATE prepare stmt;

由于limit后面的参数不能直接跟变量，所以在代码中使用了prepare+execute的方法。

MySQL处理limit Y，1的做法是按照顺序一个一个地读出来，丢掉前Y个，然后把下一个记录作为返回结果。因此这一步需要扫描Y+1行。再加上，第一步扫描的C行，总共需要扫描C+Y+1行，执行代价比随机算法1的代价要高。

按照随机算法2的思路，要随机取3个word值

  1. 取得整行表的行数，记为C；
  2. 根据相同的随机算法得到Y1，Y2，Y3;
  3. 再执行三个limitY，1语句得到三行数据。
1
2
3
4
5
6
7
8

mysql> select count(*) into @C from t;
set @Y1 = floor(@C * rand());
set @Y2 = floor(@C * rand());
set @Y3 = floor(@C * rand());
select * from t limit @Y1，1； //在应用代码里面取Y1、Y2、Y3值，拼出SQL后执行
select * from t limit @Y2，1；
select * from t limit @Y3，1；

Vincent Xin从零开始的程序猿之路

努力变瘦的胖子。