Žebříček s miliony záznamů

Vyhledání jednoho disku je asi 15 ms, možná o něco méně u disků serverové třídy. Doba odezvy menší než 500 ms vás omezuje na přibližně 30 náhodných přístupů na disk. To není mnoho.

Na svém malém notebooku mám vývojovou databázi s

[email protected] [kris]> select @@innodb_buffer_pool_size/1024/1024 as pool_mb;
+--------------+
| pool_mb      |
+--------------+
| 128.00000000 |
+--------------+
1 row in set (0.00 sec)

a pomalý notebookový disk. Vytvořil jsem tabulku skóre pomocí

[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)

s náhodnými celočíselnými skóre a sekvenčními hodnotami player_id. Máme

[email protected] [kris]> select count(*)/1000/1000 as mrows from score\G
*************************** 1. row ***************************
mrows: 2.09715200
1 row in set (0.39 sec)

Databáze udržuje pár (score, player_id) v score pořadí v indexu score , protože data v indexu InnoDB jsou uložena v BTREE a ukazatel řádku (datový ukazatel) je hodnota primárního klíče, takže definice KEY (score) skončí jako KEY(score, player_id) vnitřně. Můžeme to dokázat pohledem na plán dotazů pro načítání skóre:

[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)

Jak vidíte, key: score se používá s Using index , což znamená, že není nutný žádný přístup k datům.

Dotaz na hodnocení pro danou konstantu player_id trvá přesně 500 ms na mém notebooku:

[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)

S větší pamětí a na rychlejší krabici to může být rychlejší, ale pořád je to poměrně drahá operace, protože plán je na hovno:

[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)

Jak vidíte, druhá tabulka v plánu je indexové skenování, takže dotaz se lineárně zpomaluje s počtem hráčů.

Pokud chcete úplný žebříček, musíte vynechat klauzuli where a pak získáte dva skeny a kvadratické časy provedení. Takže tento plán zcela imploduje.

Čas přejít na procedurální postup zde:

[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 |
...

Protože se jedná o procedurální plán, je nestabilní:

Nemůžete použít LIMIT, protože to vyrovná počítadlo. Místo toho musíte všechna tato data stáhnout.
Neumíte skutečně třídit. Tento ORDER BY klauzule funguje, protože netřídí, ale používá index. Jakmile uvidíte using filesort , hodnoty počítadla budou divoce vypnuté.

Je to řešení, které se nejvíce blíží tomu, co NoSQL (čti:procedurální) databáze udělá jako plán provádění.

Můžeme však stabilizovat NoSQL uvnitř poddotazu a poté oddělit část, která nás zajímá:

[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)

Poddotaz zhmotní dřívější sadu výsledků jako ad-hoc tabulku s názvem t, ke které pak můžeme přistupovat ve vnějším dotazu. Protože se jedná o ad-hoc tabulku, v MySQL nebude mít žádný index. To omezuje to, co je efektivně možné ve vnějším dotazu.

Všimněte si však, jak oba dotazy splňují vaše časové omezení. Zde je plán:

[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)

Obě komponenty dotazu (vnitřní, DERIVED dotaz a vnější BETWEEN omezení) se však pro hráče se špatným hodnocením zpomalí a pak hrubě poruší vaše časová omezení.

[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)

Doba provádění pro popisný přístup je stabilní (závisí pouze na velikosti tabulky):

[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)

Váš hovor.