sql >> Databasteknik >  >> RDS >> Mysql

Ranking med miljontals bidrag

En enda disksökning är cirka 15 ms, kanske lite mindre med diskar av serverklass. En svarstid på mindre än 500ms begränsar dig till cirka 30 slumpmässiga diskåtkomster. Det är inte mycket.

På min lilla bärbara dator har jag en utvecklingsdatabas 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)

och en långsam bärbar disk. Jag skapade en poängtabell 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 slumpmässiga heltalspoäng och sekventiella player_id-värden. 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 upprätthåller paret (score, player_id) i score ordning i indexet score , eftersom data i ett InnoDB-index lagras i ett BTREE, och radpekaren (datapekaren) är det primära nyckelvärdet, så att definitionen KEY (score) blir KEY(score, player_id) internt. Vi kan bevisa det genom att titta på frågeplanen för en poänghämtning:

[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 är key: score används med Using index , vilket betyder att ingen dataåtkomst behövs.

Rankningsfrågan för en given konstant player_id tar exakt 500 ms på min bärbara dator:

[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 mer minne och på en snabbare låda kan det gå snabbare, men det är fortfarande en jämförelsevis dyr operation, eftersom planen suger:

[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 är den andra tabellen i planen en indexskanning, så frågan saktar ner linjärt med antalet spelare.

Om du vill ha en fullständig topplista måste du lämna where-satsen, och sedan får du två skanningar och kvadratiska körtider. Så den här planen imploderar totalt.

Dags att gå till förfarandet här:

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

Eftersom detta är en procedurplan är den instabil:

  • Du kan inte använda LIMIT, eftersom det kommer att förskjuta räknaren. Istället måste du ladda ner all denna data.
  • Du kan inte riktigt sortera. Denna ORDER BY klausul fungerar, eftersom den inte sorterar, utan använder ett index. Så snart du ser using filesort , kommer räknarvärdena att vara helt avstängda.

Det är dock den lösning som kommer närmast vad en NoSQL (läs:procedurdatabas) kommer att göra som en exekveringsplan.

Vi kan dock stabilisera NoSQL i en underfråga och sedan skära ut den del som är av intresse för oss:

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

Underfrågan kommer att materialisera den tidigare resultatuppsättningen som en ad-hoc-tabell med namnet t, som vi sedan kan komma åt i den yttre frågan. Eftersom det är en ad-hoc-tabell kommer den inte att ha något index i MySQL. Detta begränsar vad som är möjligt effektivt i den yttre frågan.

Notera dock hur båda frågorna uppfyller din tidsbegränsning. Här är 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)

Båda frågekomponenterna (den inre, DERIVED fråga och den yttre BETWEEN constraint) blir dock långsammare för dåligt rankade spelare och bryter sedan grovt mot dina tidsbegränsningar.

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

Exekveringstiden för den beskrivande metoden är stabil (beroende endast på tabellstorlek):

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

Ditt samtal.



  1. Skillnaden mellan inline och out-of-line begränsningar

  2. Ska jag använda mysql persistent connect?

  3. MySQL - SELECT ... WHERE id IN (..) - korrekt ordning

  4. Hur man delar upp en resulterande kolumn i flera kolumner