Mysql
 sql >> Datenbank >  >> RDS >> Mysql

Ranking mit Millionen Einträgen

Eine einzelne Festplattensuche dauert etwa 15 ms, bei Server-Festplatten vielleicht etwas weniger. Eine Antwortzeit von weniger als 500 ms beschränkt Sie auf etwa 30 zufällige Festplattenzugriffe. Das ist nicht viel.

Auf meinem winzigen Laptop habe ich eine Entwicklungsdatenbank mit

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

und eine langsame Laptop-Festplatte. Ich habe eine Score-Tabelle mit

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

mit zufälligen ganzzahligen Punktzahlen und sequentiellen player_id-Werten. Wir haben

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

Die Datenbank verwaltet das Paar (score, player_id) in score Reihenfolge im Index score , da Daten in einem InnoDB-Index in einem BTREE gespeichert werden und der Zeilenzeiger (Datenzeiger) der Primärschlüsselwert ist, sodass die Definition KEY (score) endet als KEY(score, player_id) im Inneren. Wir können das beweisen, indem wir uns den Abfrageplan für einen Score-Abruf ansehen:

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

Wie Sie sehen können, ist der key: score wird mit Using index verwendet , was bedeutet, dass kein Datenzugriff erforderlich ist.

Die Ranking-Abfrage für eine gegebene Konstante player_id dauert auf meinem Laptop genau 500ms:

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

Mit mehr Speicher und auf einer schnelleren Box kann es schneller gehen, aber es ist immer noch eine vergleichsweise teure Operation, weil der Plan scheiße ist:

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

Wie Sie sehen können, ist die zweite Tabelle im Plan ein Index-Scan, daher verlangsamt sich die Abfrage linear mit der Anzahl der Spieler.

Wenn Sie eine vollständige Rangliste wünschen, müssen Sie die Where-Klausel weglassen, und Sie erhalten zwei Scans und quadratische Ausführungszeiten. Dieser Plan implodiert also vollständig.

Zeit, hier zum Verfahren zu gehen:

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

Da dies ein prozeduraler Plan ist, ist er instabil:

  • Sie können LIMIT nicht verwenden, da dies den Zähler versetzen würde. Stattdessen müssen Sie all diese Daten herunterladen.
  • Sie können nicht wirklich sortieren. Dieses ORDER BY -Klausel funktioniert, weil sie nicht sortiert, sondern einen Index verwendet. Sobald Sie using filesort sehen , werden die Zählerwerte wild ausfallen.

Es ist jedoch die Lösung, die dem am nächsten kommt, was eine NoSQL-Datenbank (sprich:prozedural) als Ausführungsplan tun wird.

Wir können das NoSQL jedoch innerhalb einer Unterabfrage stabilisieren und dann den für uns interessanten Teil herausschneiden:

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

Die Unterabfrage materialisiert die frühere Ergebnismenge als Ad-hoc-Tabelle namens t, auf die wir dann in der äußeren Abfrage zugreifen können. Da es sich um eine Ad-hoc-Tabelle handelt, hat sie in MySQL keinen Index. Dies schränkt ein, was in der äußeren Abfrage effizient möglich ist.

Beachten Sie jedoch, wie beide Abfragen Ihre zeitliche Einschränkung erfüllen. Hier ist der Plan:

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

Beide Abfragekomponenten (die innere, DERIVED Abfrage und das äußere BETWEEN Einschränkung) wird jedoch für schlecht platzierte Spieler langsamer und verstößt dann grob gegen Ihre Zeitbeschränkungen.

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

Die Ausführungszeit für den deskriptiven Ansatz ist stabil (abhängig nur von der Tabellengröße):

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

Ihr Anruf.