Ответ 1
Одиночный поиск диска составляет около 15 мс, а может быть, немного меньше, чем на серверных дисках. Время отклика менее 500 мс ограничивает вас до 30 случайных дисков. Это не так много.
На моем крошечном ноутбуке у меня есть база данных разработки с
[email protected] [kris]> select @@innodb_buffer_pool_size/1024/1024 as pool_mb;
+--------------+
| pool_mb |
+--------------+
| 128.00000000 |
+--------------+
1 row in set (0.00 sec)
и медленный ноутбук. Я создал таблицу баллов с помощью
[email protected] [kris]> show create table score\G
*************************** 1. row ***************************
Table: score
Create Table: CREATE TABLE `score` (
`player_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
`score` int(11) NOT NULL,
PRIMARY KEY (`player_id`),
KEY `score` (`score`)
) ENGINE=InnoDB AUTO_INCREMENT=2490316 DEFAULT CHARSET=latin1
1 row in set (0.00 sec)
со случайными целыми числами и последовательными значениями player_id. Мы имеем
[email protected] [kris]> select count(*)/1000/1000 as mrows from score\G
*************************** 1. row ***************************
mrows: 2.09715200
1 row in set (0.39 sec)
База данных поддерживает пар (score, player_id) в score порядке в индексе score, так как данные в индексе InnoDB хранятся в BTREE, а указатель строки (указатель данных) является значением первичного ключа, поэтому что определение KEY (score) заканчивается KEY(score, player_id) внутренне. Мы можем доказать, что, посмотрев план запроса для поиска баллов:
[email protected] [kris]> explain select * from score where score = 17\G
*************************** 1. row ***************************
id: 1
select_type: SIMPLE
table: score
type: ref
possible_keys: score
key: score
key_len: 4
ref: const
rows: 29
Extra: Using index
1 row in set (0.00 sec)
Как вы можете видеть, key: score используется с Using index, что означает, что доступ к данным не требуется.
Запрос на ранжирование для данной константы player_id занимает ровно 500 мс на моем ноутбуке:
[email protected] [kris]> select p.*, count(*) as rank
from score as p join score as s on p.score < s.score
where p.player_id = 479269\G
*************************** 1. row ***************************
player_id: 479269
score: 99901
rank: 2074
1 row in set (0.50 sec)
С большим объемом памяти и более быстрой коробкой это может быть быстрее, но это все еще сравнительно дорогостоящая операция, потому что план отстой:
[email protected] [kris]> explain select p.*, count(*) as rank from score as p join score as s on p.score < s.score where p.player_id = 479269;
+----+-------------+-------+-------+---------------+---------+---------+-------+---------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+-------+---------------+---------+---------+-------+---------+--------------------------+
| 1 | SIMPLE | p | const | PRIMARY,score | PRIMARY | 4 | const | 1 | |
| 1 | SIMPLE | s | index | score | score | 4 | NULL | 2097979 | Using where; Using index |
+----+-------------+-------+-------+---------------+---------+---------+-------+---------+--------------------------+
2 rows in set (0.00 sec)
Как вы можете видеть, вторая таблица в плане - это сканирование индекса, поэтому запрос замедляется линейно с количеством игроков.
Если вам нужна полная таблица лидеров, вам нужно оставить условие where, а затем вы получите два сканирования и квадратичное время выполнения. Таким образом, этот план полностью разрушается.
Время для прохождения процедуры:
[email protected] [kris]> set @count = 0;
select *, @count := @count + 1 as rank from score where score >= 99901 order by score desc ;
...
| 2353218 | 99901 | 2075 |
| 2279992 | 99901 | 2076 |
| 2264334 | 99901 | 2077 |
| 2239927 | 99901 | 2078 |
| 2158161 | 99901 | 2079 |
| 2076159 | 99901 | 2080 |
| 2027538 | 99901 | 2081 |
| 1908971 | 99901 | 2082 |
| 1887127 | 99901 | 2083 |
| 1848119 | 99901 | 2084 |
| 1692727 | 99901 | 2085 |
| 1658223 | 99901 | 2086 |
| 1581427 | 99901 | 2087 |
| 1469315 | 99901 | 2088 |
| 1466122 | 99901 | 2089 |
| 1387171 | 99901 | 2090 |
| 1286378 | 99901 | 2091 |
| 666050 | 99901 | 2092 |
| 633419 | 99901 | 2093 |
| 479269 | 99901 | 2094 |
| 329168 | 99901 | 2095 |
| 299189 | 99901 | 2096 |
| 290436 | 99901 | 2097 |
...
Поскольку это процедурный план, он нестабилен:
- Вы не можете использовать LIMIT, потому что это компенсирует счетчик. Вместо этого вам нужно загрузить все эти данные.
- Вы действительно не можете сортировать. Это предложение
ORDER BYработает, потому что оно не сортируется, а использует индекс. Как только вы увидитеusing filesort, значения счетчика будут отключены.
Это решение, которое ближе всего подходит к тому, что база данных NoSQL (read: процедурная) будет выполнять как план выполнения.
Мы можем стабилизировать NoSQL внутри подзапроса, а затем разрезать интересующую нас часть:
[email protected] [kris]> set @count = 0;
select * from (
select *, @count := @count + 1 as rank
from score
where score >= 99901
order by score desc
) as t
where player_id = 479269;
Query OK, 0 rows affected (0.00 sec)
+-----------+-------+------+
| player_id | score | rank |
+-----------+-------+------+
| 479269 | 99901 | 2094 |
+-----------+-------+------+
1 row in set (0.00 sec)
[email protected] [kris]> set @count = 0;
select * from (
select *, @count := @count + 1 as rank
from score
where score >= 99901
order by score desc
) as t
where rank between 2090 and 2100;
Query OK, 0 rows affected (0.00 sec)
+-----------+-------+------+
| player_id | score | rank |
+-----------+-------+------+
| 1387171 | 99901 | 2090 |
| 1286378 | 99901 | 2091 |
| 666050 | 99901 | 2092 |
| 633419 | 99901 | 2093 |
| 479269 | 99901 | 2094 |
| 329168 | 99901 | 2095 |
| 299189 | 99901 | 2096 |
| 290436 | 99901 | 2097 |
+-----------+-------+------+
8 rows in set (0.01 sec)
Подзапрос будет реализовывать прежний результирующий набор как ad-hoc-таблицу с именем t, которую мы тогда можем получить во внешнем запросе. Поскольку это специальная таблица, в MySQL он не будет иметь индекса. Это ограничивает возможности эффективного внешнего запроса.
Обратите внимание, что оба запроса удовлетворяют вашему ограничению по времени. Вот план:
[email protected] [kris]> set @count = 0; explain select * from ( select *, @count := @count + 1 as rank from score where score >= 99901 order by score desc ) as t where rank between 2090 and 2100\G
Query OK, 0 rows affected (0.00 sec)
*************************** 1. row ***************************
id: 1
select_type: PRIMARY
table: <derived2>
type: ALL
possible_keys: NULL
key: NULL
key_len: NULL
ref: NULL
rows: 2097
Extra: Using where
*************************** 2. row ***************************
id: 2
select_type: DERIVED
table: score
type: range
possible_keys: score
key: score
key_len: 4
ref: NULL
rows: 3750
Extra: Using where; Using index
2 rows in set (0.00 sec)
Оба компонента запроса (внутренний, DERIVED запрос и внешнее ограничение BETWEEN) будут замедляться для игроков с плохой оценкой, но затем грубо нарушают ваши ограничения времени.
[email protected] [kris]> set @count = 0; select * from ( select *, @count := @count + 1 as rank from score where score >= 0 order by score desc ) as t;
...
2097152 rows in set (3.56 sec)
Время выполнения дескриптивного подхода стабильно (зависит только от размера таблицы):
[email protected] [kris]> select p.*, count(*) as rank
from score as p join score as s on p.score < s.score
where p.player_id = 1134026;
+-----------+-------+---------+
| player_id | score | rank |
+-----------+-------+---------+
| 1134026 | 0 | 2097135 |
+-----------+-------+---------+
1 row in set (0.53 sec)
Ваш вызов.