Peringkat dengan jutaan entri

Pencarian disk tunggal adalah sekitar 15 ms, mungkin sedikit kurang dengan disk tingkat server. Waktu respons kurang dari 500 ms membatasi Anda hingga sekitar 30 akses disk acak. Itu tidak banyak.

Di laptop kecil saya, saya memiliki database pengembangan dengan

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

dan disk laptop yang lambat. Saya membuat tabel skor dengan

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

dengan skor integer acak dan nilai player_id berurutan. Kami memiliki

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

Basis data mempertahankan pasangan (score, player_id) dalam score urutan dalam indeks score , karena data dalam indeks InnoDB disimpan dalam BTREE, dan penunjuk baris (penunjuk data) adalah nilai kunci utama, sehingga definisi KEY (score) akhirnya menjadi KEY(score, player_id) secara internal. Kami dapat membuktikannya dengan melihat rencana kueri untuk pengambilan skor:

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

Seperti yang Anda lihat, key: score sedang digunakan dengan Using index , artinya tidak diperlukan akses data.

Kueri peringkat untuk konstanta player_id dibutuhkan tepat 500 ms di laptop saya:

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

Dengan lebih banyak memori dan pada kotak yang lebih cepat, ini bisa lebih cepat, tetapi ini masih merupakan operasi yang relatif mahal, karena paketnya payah:

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

Seperti yang Anda lihat, tabel kedua dalam rencana adalah pemindaian indeks, sehingga kueri melambat secara linier dengan jumlah pemain.

Jika Anda menginginkan papan peringkat penuh, Anda harus meninggalkan klausa where, dan kemudian Anda mendapatkan dua pemindaian dan waktu eksekusi kuadrat. Jadi rencana ini meledak sepenuhnya.

Saatnya untuk pergi prosedural di sini:

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

Karena ini adalah rencana prosedural, tidak stabil:

• Anda tidak dapat menggunakan LIMIT, karena itu akan mengimbangi penghitung. Sebagai gantinya, Anda harus mengunduh semua data ini.
• Anda tidak bisa benar-benar menyortir. Ini ORDER BY klausa berfungsi, karena tidak mengurutkan, tetapi menggunakan indeks. Segera setelah Anda melihat using filesort , nilai penghitung akan sangat mati.

Ini adalah solusi yang paling mendekati apa yang akan dilakukan database NoSQL (baca:prosedural) sebagai rencana eksekusi.

Kami dapat menstabilkan NoSQL di dalam subquery dan kemudian memotong bagian yang menarik bagi kami, meskipun:

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

Subquery akan mewujudkan set hasil sebelumnya sebagai tabel ad-hoc bernama t, yang kemudian dapat kita akses di kueri luar. Karena ini adalah tabel ad-hoc, di MySQL tidak akan ada index. Ini membatasi apa yang mungkin secara efisien di kueri luar.

Perhatikan bagaimana kedua kueri memenuhi batasan waktu Anda. Ini rencananya:

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

Kedua komponen kueri (bagian dalam, DERIVED kueri dan bagian luar BETWEEN kendala) akan menjadi lebih lambat untuk pemain dengan peringkat buruk, dan kemudian sangat melanggar batasan waktu Anda.

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

Waktu eksekusi untuk pendekatan deskriptif stabil (hanya bergantung pada ukuran tabel):

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

Panggilan Anda.