之前做过一次论坛宠物的ORDER BY RAND()的优化,这篇文章只是深入的去读解优化的原理和具体步骤。觉得讲的不错分享一下。
原文地址:http://jan.kneschke.de/projects/mysql/order-by-rand
翻译:ShiningRay
译者序
之前有位朋友提到从MySQL随机取1条记录其实只要SELECT * FROM table ORDER BY RAND() LIMIT 1即可。其实这个语句有很大的性能问题,对于大表的效率是非常低下的。我们可以看一下MySQL对其的解释:
EXPLAIN SELECT *
FROM `money_logs`
ORDER BY RAND( )
LIMIT 1
id select_type table type possible_keys key key_len ref rows Extra
1 SIMPLE table ALL NULL NULL NULL NULL 173784 Using temporary; Using filesort
这个SQL语句无法使用任何索引,还必须使用临时表和文件排序,在一个15万条记录的MyISAM表需要花大约0.3秒。已经是相当慢的了。如何优化,请往下看:
第一个例子我们先假设ID是从1开始并且1和ID的最大值之间没有任何空档。
将工作移入应用程序
第一个想法:如果我们可以事先在应用程序中计算出ID,那么就可以简化整个工作。
SELECT MAX(id) FROM random;
## 在应用程序中生成随机id
SELECT name FROM random WHERE id = 由于MAX(id) == COUNT(id) 我们只要生成从1到MAX(id)之间一个随机数,并将其传给数据库并取回随机行。
上面第一个SELECT基本上是一个可以被优化掉的空操作。第二个是一个针对常量的eq_ref查询,同样也很快。
将任务放入数据库
不过有必要将其放入应用程序吗?难道我们不能在数据库里完成?
# 生成一个随机 ID
> SELECT RAND() * MAX(id) FROM random;
+——————+
| RAND() * MAX(id) |
+——————+
| 689.37582507297 |
+——————+
# 喔,这是一个浮点数,不过我们需要整数
> SELECT CEIL(RAND() * MAX(id)) FROM random;
+————————-+
| CEIL(RAND() * MAX(id)) |
+————————-+
| 1000000 |
+————————-+
# 好多了。不过性能如何?
> EXPLAIN
SELECT CEIL(RAND() * MAX(id)) FROM random;
+—-+————-+——-+——-+——+————-+
| id | select_type | table | type | rows | Extra |
+—-+————-+——-+——-+——+————-+
| 1 | SIMPLE | random | index | 1000000 | Using index |
+—-+————-+——-+——-+——+————-+
## 一个索引扫描?我们没有对MAX()进行优化
> EXPLAIN
SELECT CEIL(RAND() * (SELECT MAX(id) FROM random));
+—-+————-+——-+——+——+——————————+
| id | select_type | table | type | rows | Extra |
+—-+————-+——-+——+——+——————————+
| 1 | PRIMARY | NULL | NULL | NULL | No tables used |
| 2 | SUBQUERY | NULL | NULL | NULL | Select tables optimized away |
+—-+————-+——-+——+——+——————————+
## 一个简单的子查询给我们将性能找了回来。OK,现在我们知道如何生成随机ID了,不过如何获取记录行?
> EXPLAIN
SELECT name
FROM random
WHERE id = (SELECT CEIL(RAND() *
(SELECT MAX(id)
FROM random));
+—-+————-+——–+——+—————+——+———+——+———+——————————+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+—-+————-+——–+——+—————+——+———+——+———+——————————+
| 1 | PRIMARY | random | ALL | NULL | NULL | NULL | NULL | 1000000 | Using where |
| 3 | SUBQUERY | NULL | NULL | NULL | NULL | NULL | NULL | NULL | Select tables optimized away |
+—-+————-+——–+——+—————+——+———+——+———+——————————+
> show warnings;
+——-+——+——————————————+
| Level | Code | Message |
+——-+——+——————————————+
| Note | 1249 | Select 2 was reduced during optimization |
+——-+——+——————————————+哦,不!不要走这条路。虽然它很直观,但是也是最容易犯的错。理由是:在WHERE子句中的SELECT会针对外部SELECT取出的每一行执行一次。这可能会是0到4091行,看你的运气了。
我们必须用一种方法确保随机ID只被生成一次:
SELECT name
FROM random JOIN
(SELECT CEIL(RAND() *
(SELECT MAX(id)
FROM random)) AS id
) AS r2
USING (id);
+—-+————-+————+——–+——+——————————+
| id | select_type | table | type | rows | Extra |
+—-+————-+————+——–+——+——————————+
| 1 | PRIMARY | | system | 1 | |
| 1 | PRIMARY | random | const | 1 | |
| 2 | DERIVED | NULL | NULL | NULL | No tables used |
| 3 | SUBQUERY | NULL | NULL | NULL | Select tables optimized away |
+—-+————-+————+——–+——+——————————+内部的 SELECT 生成了一个常数临时(TEMPORARY)表并且联接(JOIN)只选择了一行。完美。
没有排序、没有应用程序介入,查询的大部分都被优化了。
在数字中加入空档
为了使最终的解决方案通用化,我们必须考虑空档的可能性,如当你删除(DELETE)了记录行。
SELECT name
FROM random AS r1 JOIN
(SELECT (RAND() *
(SELECT MAX(id)
FROM random)) AS id)
AS r2
WHERE r1.id >= r2.id
ORDER BY r1.id ASC
LIMIT 1;
+—-+————-+————+——–+——+——————————+
| id | select_type | table | type | rows | Extra |
+—-+————-+————+——–+——+——————————+
| 1 | PRIMARY | | system | 1 | |
| 1 | PRIMARY | r1 | range | 689 | Using where |
| 2 | DERIVED | NULL | NULL | NULL | No tables used |
| 3 | SUBQUERY | NULL | NULL | NULL | Select tables optimized away |
+—-+————-+————+——–+——+——————————+JOIN现在加入了所有大于等于我们随机数的ID,并且当直接匹配不存在的时候,只选择最临近的记录。不过一旦找到了某一行,我们就立刻停止(LIMIT 1)。同时我们根据索引(ORDER BY id ASC)读取记录。由于我们使用了>=而非=,所以我们可以削去CEIL同时还能获取同样的结果,节省了一点点开销。
平均分布
一旦ID的分布不再是平均的了,那么我们对行的选择也不是完全随机的了。
> select * from holes;
+—-+———————————-+———-+
| id | name | accesses |
+—-+———————————-+———-+
| 1 | d12b2551c6cb7d7a64e40221569a8571 | 107 |
| 2 | f82ad6f29c9a680d7873d1bef822e3e9 | 50 |
| 4 | 9da1ed7dbbdcc6ec90d6cb139521f14a | 132 |
| 8 | 677a196206d93cdf18c3744905b94f73 | 230 |
| 16 | b7556d8ed40587a33dc5c449ae0345aa | 481 |
+—-+———————————-+———-+RAND函数生成诸如9到15之间的ID都会让id 16被选择。
目前还没有针对这个问题的真正的解决方案,不过你的数据是大部分不变的话可以添加一个将行号映射到ID的映射表:
> create table holes_map ( row_id int not NULL primary key, random_id int not null);
> SET @id = 0;
> INSERT INTO holes_map SELECT @id := @id + 1, id FROM holes;
> select * from holes_map;
+——–+———–+
| row_id | random_id |
+——–+———–+
| 1 | 1 |
| 2 | 2 |
| 3 | 4 |
| 4 | 8 |
| 5 | 16 |
+——–+———–+row_id现在则是没有空档的,我们就可以再次运行我们的随机查询了:
SELECT name FROM holes
JOIN (SELECT r1.random_id
FROM holes_map AS r1
JOIN (SELECT (RAND() *
(SELECT MAX(row_id)
FROM holes_map)) AS row_id)
AS r2
WHERE r1.row_id >= r2.row_id
ORDER BY r1.row_id ASC
LIMIT 1) as rows ON (id = random_id);1000次查找之后,我们可以看到一个平均分布:
> select * from holes;
+—-+———————————-+———-+
| id | name | accesses |
+—-+———————————-+———-+
| 1 | d12b2551c6cb7d7a64e40221569a8571 | 222 |
| 2 | f82ad6f29c9a680d7873d1bef822e3e9 | 187 |
| 4 | 9da1ed7dbbdcc6ec90d6cb139521f14a | 195 |
| 8 | 677a196206d93cdf18c3744905b94f73 | 207 |
| 16 | b7556d8ed40587a33dc5c449ae0345aa | 189 |
+—-+———————————-+———-+使用触发器维护有空档的表
让我们就用前面的几个表:
DROP TABLE IF EXISTS r2;
CREATE TABLE r2 (
id SERIAL,
name VARCHAR(32) NOT NULL UNIQUE
);
DROP TABLE IF EXISTS r2_equi_dist;
CREATE TABLE r2_equi_dist (
id SERIAL,
r2_id bigint unsigned NOT NULL UNIQUE
);
一旦我们在r2中改动了某些东西,我们希望r2_equi_dist也被更新。
DELIMITER $$
DROP TRIGGER IF EXISTS tai_r2$$
CREATE TRIGGER tai_r2
AFTER INSERT ON r2 FOR EACH ROW
BEGIN
DECLARE m BIGINT UNSIGNED DEFAULT 1;
SELECT MAX(id) + 1 FROM r2_equi_dist INTO m;
SELECT IFNULL(m, 1) INTO m;
INSERT INTO r2_equi_dist (id, r2_id) VALUES (m, NEW.id);
END$$
DELIMITER ;
DELETE FROM r2;
INSERT INTO r2 VALUES ( NULL, MD5(RAND()) );
INSERT INTO r2 VALUES ( NULL, MD5(RAND()) );
INSERT INTO r2 VALUES ( NULL, MD5(RAND()) );
INSERT INTO r2 VALUES ( NULL, MD5(RAND()) );
SELECT * FROM r2;
+—-+———————————-+
| id | name |
+—-+———————————-+
| 1 | 8b4cf277a3343cdefbe19aa4dabc40e1 |
| 2 | a09a3959d68187ce48f4fe7e388926a9 |
| 3 | 4e1897cd6d326f8079108292376fa7d5 |
| 4 | 29a5e3ed838db497aa330878920ec01b |
+—-+———————————-+
SELECT * FROM r2_equi_dist;
+—-+——-+
| id | r2_id |
+—-+——-+
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
+—-+——-+
INSERT很简单,但在DELETE时我们需要更新equi-dist-id来维持id的连续。
DELIMITER $$
DROP TRIGGER IF EXISTS tad_r2$$
CREATE TRIGGER tad_r2
AFTER DELETE ON r2 FOR EACH ROW
BEGIN
DELETE FROM r2_equi_dist WHERE r2_id = OLD.id;
UPDATE r2_equi_dist SET id = id – 1 WHERE r2_id > OLD.id;
END$$
DELIMITER ;
DELETE FROM r2 WHERE id = 2;
SELECT * FROM r2;
+—-+———————————-+
| id | name |
+—-+———————————-+
| 1 | 8b4cf277a3343cdefbe19aa4dabc40e1 |
| 3 | 4e1897cd6d326f8079108292376fa7d5 |
| 4 | 29a5e3ed838db497aa330878920ec01b |
+—-+———————————-+
SELECT * FROM r2_equi_dist;
+—-+——-+
| id | r2_id |
+—-+——-+
| 1 | 1 |
| 2 | 3 |
| 3 | 4 |
+—-+——-+
UPDATE就非常直观了。我们只要维护一下外键约束:
DELIMITER $$
DROP TRIGGER IF EXISTS tau_r2$$
CREATE TRIGGER tau_r2
AFTER UPDATE ON r2 FOR EACH ROW
BEGIN
UPDATE r2_equi_dist SET r2_id = NEW.id WHERE r2_id = OLD.id;
END$$
DELIMITER ;
UPDATE r2 SET id = 25 WHERE id = 4;
SELECT * FROM r2;
+—-+———————————-+
| id | name |
+—-+———————————-+
| 1 | 8b4cf277a3343cdefbe19aa4dabc40e1 |
| 3 | 4e1897cd6d326f8079108292376fa7d5 |
| 25 | 29a5e3ed838db497aa330878920ec01b |
+—-+———————————-+
SELECT * FROM r2_equi_dist;
+—-+——-+
| id | r2_id |
+—-+——-+
| 1 | 1 |
| 2 | 3 |
| 3 | 25 |
+—-+——-+
一次多行
如果你想一次取回多行,你可以:
执行多次查询
写一个存储过程执行查询并将结果存入一个临时表
进行一个UNION
存储过程
存储过程为你提供了通用语言中很有用的一些结构:
循环
控制结构
过程
…
这个任务中我们只需要一个LOOP:
DELIMITER $$
DROP PROCEDURE IF EXISTS get_rands$$
CREATE PROCEDURE get_rands(IN cnt INT)
BEGIN
DROP TEMPORARY TABLE IF EXISTS rands;
CREATE TEMPORARY TABLE rands ( rand_id INT );
loop_me: LOOP
IF cnt < 1 THEN
LEAVE loop_me;
END IF;
INSERT INTO rands
SELECT r1.id
FROM random AS r1 JOIN
(SELECT (RAND() *
(SELECT MAX(id)
FROM random)) AS id)
AS r2
WHERE r1.id >= r2.id
ORDER BY r1.id ASC
LIMIT 1;
SET cnt = cnt – 1;
END LOOP loop_me;
END$$
DELIMITER ;
CALL get_rands(4);
SELECT * FROM rands;
+———+
| rand_id |
+———+
| 133716 |
| 702643 |
| 112066 |
| 452400 |
+———+
下面的问题留给读者解决:
使用动态SQL并传入临时表的名字
在表上使用一个UNIQUE索引并捕获UNIQUE键冲突来消除结果集中可能的重复记录。
性能
现在让我们看看性能方面发生了什么变化。我们有三个不同的查询来解决这个问题。
Q1. ORDER BY RAND()
Q2. RAND() * MAX(ID)
Q3. RAND() * MAX(ID) + ORDER BY ID
Q1预期消耗N * log2(N),Q2和Q3接近常数。
下标是评测的结果,针对N行的表(从一千行到一百万行),每个查询执行1000次。
100 1.000 10.000 100.000 1.000.000
Q1 0:00.718s 0:02.092s 0:18.684s 2:59.081s 58:20.000s
Q2 0:00.519s 0:00.607s 0:00.614s 0:00.628s 0:00.637s
Q3 0:00.570s 0:00.607s 0:00.614s 0:00.628s 0:00.637s如你所见,普通的ORDER BY RAND()从仅100行的表开始便落后于优化过的查询了。
关于这些查询更详细的分析可以在analyzing-complex-queries查阅.