Класиране с милиони записи

Търсенето на един диск е около 15 мс, може би малко по-малко при дискове от сървърен клас. Време за реакция по-малко от 500 ms ви ограничава до около 30 произволни достъпа до диска. Това не е много.

На моя малък лаптоп имам база данни за разработка с

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

и бавен диск на лаптоп. Създадох таблица с резултати с

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

със случайни цели числа и последователни стойности на player_id. Имаме

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

Базата данни поддържа двойката (score, player_id) в score ред в индекса score , тъй като данните в индекс на InnoDB се съхраняват в BTREE, а указателят на ред (указател на данни) е стойността на първичния ключ, така че дефиницията KEY (score) в крайна сметка е KEY(score, player_id) вътрешно. Можем да докажем това, като разгледаме плана на заявката за извличане на резултат:

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

Както можете да видите, key: score се използва с Using index , което означава, че не е необходим достъп до данни.

Заявката за класиране за дадена константа player_id отнема точно 500 мс на моя лаптоп:

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

С повече памет и по-бърза кутия може да е по-бързо, но все пак е сравнително скъпа операция, защото планът е гадно:

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

Както можете да видите, втората таблица в плана е индексно сканиране, така че заявката се забавя линейно с броя на играчите.

Ако искате пълно класиране, трябва да изключите клаузата where и след това получавате две сканирания и квадратично време за изпълнение. Така че този план се разпада напълно.

Време е да преминете към процедура тук:

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

Тъй като това е процедурен план, той е нестабилен:

• Не можете да използвате LIMIT, защото това ще компенсира брояча. Вместо това трябва да изтеглите всички тези данни.
• Не можете наистина да сортирате. Това ORDER BY клаузата работи, защото не сортира, а използва индекс. Веднага щом видите using filesort , стойностите на брояча ще бъдат силно изключени.

Това е решението, което се доближава най-много до това, което NoSQL (четете:процедурна) база данни ще направи като план за изпълнение.

Можем обаче да стабилизираме NoSQL в подзаявка и след това да изрежем частта, която ни интересува:

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

Подзаявката ще материализира предишния набор от резултати като ad-hoc таблица с име t, до която след това имаме достъп във външната заявка. Тъй като това е ad-hoc таблица, в MySQL тя няма да има индекс. Това ограничава ефективно възможното във външната заявка.

Обърнете внимание обаче как и двете заявки удовлетворяват вашето времево ограничение. Ето плана:

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

И двата компонента на заявката (вътрешният, DERIVED заявка и външният BETWEEN ограничение) обаче ще стане по-бавно за лошо класирани играчи и след това грубо ще наруши вашите времеви ограничения.

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

Времето за изпълнение на описателния подход е стабилно (зависи само от размера на таблицата):

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

Вашето обаждане.