Une seule recherche de disque dure environ 15 ms, peut-être un peu moins avec des disques de qualité serveur. Un temps de réponse inférieur à 500 ms vous limite à environ 30 accès disque aléatoires. Ce n'est pas beaucoup.
Sur mon petit ordinateur portable, j'ai une base de données de développement avec
[email protected] [kris]> select @@innodb_buffer_pool_size/1024/1024 as pool_mb;
+--------------+
| pool_mb |
+--------------+
| 128.00000000 |
+--------------+
1 row in set (0.00 sec)
et un disque d'ordinateur portable lent. J'ai créé un tableau des scores avec
[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)
avec des scores entiers aléatoires et des valeurs séquentielles player_id. Nous avons
[email protected] [kris]> select count(*)/1000/1000 as mrows from score\G
*************************** 1. row ***************************
mrows: 2.09715200
1 row in set (0.39 sec)
La base de données maintient la paire (score, player_id)
en score
ordre dans l'index score
, car les données d'un index InnoDB sont stockées dans un BTREE, et le pointeur de ligne (pointeur de données) est la valeur de la clé primaire, de sorte que la définition KEY (score)
finit par être KEY(score, player_id)
intérieurement. Nous pouvons le prouver en regardant le plan de requête pour une récupération de score :
[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)
Comme vous pouvez le voir, la key: score
est utilisé avec Using index
, ce qui signifie qu'aucun accès aux données n'est nécessaire.
La requête de classement pour une constante player_id
donnée prend exactement 500 ms sur mon ordinateur portable :
[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)
Avec plus de mémoire et sur une machine plus rapide, cela peut être plus rapide, mais cela reste une opération relativement coûteuse, car le plan est nul :
[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)
Comme vous pouvez le voir, la deuxième table du plan est une analyse d'index, de sorte que la requête ralentit linéairement avec le nombre de joueurs.
Si vous voulez un classement complet, vous devez omettre la clause where, puis vous obtenez deux scans et des temps d'exécution quadratiques. Alors ce plan implose complètement.
Il est temps de procéder ici :
[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 |
...
Comme il s'agit d'un plan procédural, il est instable :
- Vous ne pouvez pas utiliser LIMIT, car cela décalera le compteur. Au lieu de cela, vous devez télécharger toutes ces données.
- Vous ne pouvez pas vraiment trier. Ce
ORDER BY
La clause fonctionne, car elle ne trie pas, mais utilise un index. Dès que vous voyezusing filesort
, les valeurs des compteurs seront complètement faussées.
Cependant, c'est la solution qui se rapproche le plus de ce qu'une base de données NoSQL (lire :procédurale) fera en tant que plan d'exécution.
Nous pouvons cependant stabiliser le NoSQL dans une sous-requête, puis découper la partie qui nous intéresse :
[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)
La sous-requête matérialisera l'ancien jeu de résultats sous la forme d'une table ad hoc nommée t, à laquelle nous pourrons ensuite accéder dans la requête externe. Comme il s'agit d'une table ad hoc, dans MySQL, elle n'aura pas d'index. Cela limite ce qui est possible efficacement dans la requête externe.
Notez comment les deux requêtes satisfont votre contrainte de temps, cependant. Voici le planning :
[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)
Les deux composants de requête (le composant interne, DERIVED
requête et le BETWEEN
externe contrainte) deviendra plus lent pour les joueurs mal classés, cependant, et violera alors grossièrement vos contraintes de timing.
[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)
Le temps d'exécution de l'approche descriptive est stable (dépendant uniquement de la taille de la table) :
[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)
Votre appel.