En enkelt disksøgning er omkring 15 ms, måske lidt mindre med diske af serverkvalitet. En responstid på mindre end 500ms begrænser dig til omkring 30 tilfældige diskadgange. Det er ikke meget.
På min lille bærbare computer har jeg en udviklingsdatabase med
[email protected] [kris]> select @@innodb_buffer_pool_size/1024/1024 as pool_mb;
+--------------+
| pool_mb |
+--------------+
| 128.00000000 |
+--------------+
1 row in set (0.00 sec)
og en langsom bærbar disk. Jeg oprettede en scoretabel med
[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)
med tilfældige heltalsscore og sekventielle player_id-værdier. Vi har
[email protected] [kris]> select count(*)/1000/1000 as mrows from score\G
*************************** 1. row ***************************
mrows: 2.09715200
1 row in set (0.39 sec)
Databasen vedligeholder parret (score, player_id) i score rækkefølge i indekset score , da data i et InnoDB-indeks lagres i et BTREE, og rækkemarkøren (datamarkøren) er den primære nøgleværdi, således at definitionen KEY (score) ender med at blive KEY(score, player_id) internt. Det kan vi bevise ved at se på forespørgselsplanen for en scorehentning:
[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)
Som du kan se, er key: score bliver brugt med Using index , hvilket betyder, at ingen dataadgang er nødvendig.
Rangeringsforespørgslen for en given konstant player_id tager præcis 500ms på min bærbare computer:
[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)
Med mere hukommelse og på en hurtigere boks kan det være hurtigere, men det er stadig en forholdsvis dyr operation, fordi planen stinker:
[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)
Som du kan se, er den anden tabel i planen en indeksscanning, så forespørgslen bremses lineært med antallet af spillere.
Hvis du vil have en fuld leaderboard, skal du udelade where-klausulen, og så får du to scanninger og kvadratiske eksekveringstider. Så denne plan imploderer fuldstændigt.
Tid til at gå procedure her:
[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 |
...
Fordi dette er en procedureplan, er den ustabil:
- Du kan ikke bruge LIMIT, fordi det vil udligne tælleren. I stedet skal du downloade alle disse data.
- Du kan ikke rigtig sortere. Denne
ORDER BYklausul virker, fordi den ikke sorterer, men bruger et indeks. Så snart du serusing filesort, vil tællerværdierne være vildt slukket.
Det er dog den løsning, der kommer tættest på, hvad en NoSQL (læs:proceduremæssig) database vil gøre som en eksekveringsplan.
Vi kan dog stabilisere NoSQL inde i en underforespørgsel og derefter udskære den del, der er af interesse for os:
[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)
Underforespørgslen vil materialisere det tidligere resultatsæt som en ad-hoc-tabel ved navn t, som vi så kan få adgang til i den ydre forespørgsel. Fordi det er en ad-hoc tabel, vil den i MySQL ikke have noget indeks. Dette begrænser, hvad der er muligt effektivt i den ydre forespørgsel.
Bemærk dog, hvordan begge forespørgsler opfylder din tidsbegrænsning. Her er planen:
[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)
Begge forespørgselskomponenter (den indre, DERIVED forespørgsel og den ydre BETWEEN constraint) vil dog blive langsommere for dårligt rangerede spillere og derefter groft overtræde dine timing-begrænsninger.
[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)
Udførelsestiden for den beskrivende tilgang er stabil (kun afhængig af tabelstørrelsen):
[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)
Dit opkald.