La búsqueda de un solo disco es de aproximadamente 15 ms, tal vez un poco menos con discos de servidor. Un tiempo de respuesta de menos de 500 ms lo limita a unos 30 accesos aleatorios al disco. Eso no es mucho.
En mi diminuta computadora portátil, tengo una base de datos de desarrollo con
[email protected] [kris]> select @@innodb_buffer_pool_size/1024/1024 as pool_mb;
+--------------+
| pool_mb |
+--------------+
| 128.00000000 |
+--------------+
1 row in set (0.00 sec)
y un disco portátil lento. Creé una tabla de puntuación con
[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)
con puntajes enteros aleatorios y valores secuenciales de player_id. Tenemos
[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 datos mantiene el par (score, player_id) en score orden en el índice score , ya que los datos en un índice InnoDB se almacenan en un BTREE, y el puntero de fila (puntero de datos) es el valor de la clave principal, por lo que la definición KEY (score) termina siendo KEY(score, player_id) internamente. Podemos probar eso mirando el plan de consulta para una recuperación de puntuación:
[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)
Como puede ver, la key: score se está utilizando con Using index , lo que significa que no es necesario acceder a los datos.
La consulta de clasificación para una constante determinada player_id toma exactamente 500 ms en mi computadora portátil:
[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)
Con más memoria y en una caja más rápida, puede ser más rápido, pero sigue siendo una operación comparativamente costosa, porque el plan apesta:
[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)
Como puede ver, la segunda tabla del plan es un escaneo de índice, por lo que la consulta se ralentiza linealmente con la cantidad de jugadores.
Si desea una tabla de clasificación completa, debe omitir la cláusula where y luego obtiene dos escaneos y tiempos de ejecución cuadráticos. Así que este plan implosiona por completo.
Es hora de pasar al procedimiento aquí:
[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 |
...
Debido a que este es un plan de procedimiento, es inestable:
- No puede usar LIMIT, porque eso compensará el contador. En su lugar, debe descargar todos estos datos.
- Realmente no puedes ordenar. Este
ORDER BYfunciona, porque no ordena, sino que usa un índice. Tan pronto como veausing filesort, los valores del contador estarán muy fuera de lugar.
Sin embargo, es la solución que más se acerca a lo que hará una base de datos NoSQL (léase:procedimental) como plan de ejecución.
Sin embargo, podemos estabilizar el NoSQL dentro de una subconsulta y luego dividir la parte que nos interesa:
[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 subconsulta materializará el conjunto de resultados anterior como una tabla ad-hoc llamada t, a la que luego podemos acceder en la consulta externa. Debido a que es una tabla ad-hoc, en MySQL no tendrá índice. Esto limita lo que es posible de manera eficiente en la consulta externa.
Sin embargo, tenga en cuenta cómo ambas consultas satisfacen su restricción de tiempo. Este es el plan:
[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)
Ambos componentes de consulta (el interior, DERIVED consulta y el exterior BETWEEN Sin embargo, se volverá más lento para los jugadores mal clasificados y luego violará gravemente sus restricciones de tiempo.
[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)
El tiempo de ejecución del enfoque descriptivo es estable (depende únicamente del tamaño de la tabla):
[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)
Tu llamada.
