Mysql
 sql >> Base de données >  >> RDS >> Mysql

Classement avec des millions d'entrées

Une seule recherche de disque dure environ 15 ms, peut-être un peu moins avec des disques de qualité serveur. Un temps de réponse inférieur à 500 ms vous limite à environ 30 accès disque aléatoires. Ce n'est pas beaucoup.

Sur mon petit ordinateur portable, j'ai une base de données de développement avec

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

et un disque d'ordinateur portable lent. J'ai créé un tableau des scores avec

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

avec des scores entiers aléatoires et des valeurs séquentielles player_id. Nous avons

[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 données maintient la paire (score, player_id) en score ordre dans l'index score , car les données d'un index InnoDB sont stockées dans un BTREE, et le pointeur de ligne (pointeur de données) est la valeur de la clé primaire, de sorte que la définition KEY (score) finit par être KEY(score, player_id) intérieurement. Nous pouvons le prouver en regardant le plan de requête pour une récupération de score :

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

Comme vous pouvez le voir, la key: score est utilisé avec Using index , ce qui signifie qu'aucun accès aux données n'est nécessaire.

La requête de classement pour une constante player_id donnée prend exactement 500 ms sur mon ordinateur portable :

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

Avec plus de mémoire et sur une machine plus rapide, cela peut être plus rapide, mais cela reste une opération relativement coûteuse, car le plan est nul :

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

Comme vous pouvez le voir, la deuxième table du plan est une analyse d'index, de sorte que la requête ralentit linéairement avec le nombre de joueurs.

Si vous voulez un classement complet, vous devez omettre la clause where, puis vous obtenez deux scans et des temps d'exécution quadratiques. Alors ce plan implose complètement.

Il est temps de procéder ici :

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

Comme il s'agit d'un plan procédural, il est instable :

  • Vous ne pouvez pas utiliser LIMIT, car cela décalera le compteur. Au lieu de cela, vous devez télécharger toutes ces données.
  • Vous ne pouvez pas vraiment trier. Ce ORDER BY La clause fonctionne, car elle ne trie pas, mais utilise un index. Dès que vous voyez using filesort , les valeurs des compteurs seront complètement faussées.

Cependant, c'est la solution qui se rapproche le plus de ce qu'une base de données NoSQL (lire :procédurale) fera en tant que plan d'exécution.

Nous pouvons cependant stabiliser le NoSQL dans une sous-requête, puis découper la partie qui nous intéresse :

[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 sous-requête matérialisera l'ancien jeu de résultats sous la forme d'une table ad hoc nommée t, à laquelle nous pourrons ensuite accéder dans la requête externe. Comme il s'agit d'une table ad hoc, dans MySQL, elle n'aura pas d'index. Cela limite ce qui est possible efficacement dans la requête externe.

Notez comment les deux requêtes satisfont votre contrainte de temps, cependant. Voici le planning :

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

Les deux composants de requête (le composant interne, DERIVED requête et le BETWEEN externe contrainte) deviendra plus lent pour les joueurs mal classés, cependant, et violera alors grossièrement vos contraintes de timing.

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

Le temps d'exécution de l'approche descriptive est stable (dépendant uniquement de la taille de la table) :

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

Votre appel.