11 Okt

Spieler-Ranglisten in MySQL

Wer sich schon einmal an einem Browserspiel probiert hat, der möchte seinen Spielern auch eine Rangliste anzeigen, das wichtigste ist schließlich der Wettbewerb mit den Mitspielern. Als Entwickler steht man dann vor dem Problem die Ranglisten-Plätze der Spieler berechnen zu müssen, und das möglichst effizient.

Aus Performance-Gründen speichern wir den Rang eines Spielers neben seinem Namen und seiner Punktzahl in der Tabelle. Ungefähr so:

CREATE TABLE player (
  name varchar(50) NOT NULL,
  score int NOT NULL DEFAULT 0,
  rank int NOT NULL DEFAULT 0
)

Als nächstes müssen die Testdaten eingefügt werden:

INSERT INTO player (name, score)
VALUES ('Adam', 32), ('Bert', 65), ('Carla', 32), ('Detlev', 28), ('Emil', 123)

Nun soll die Spalte rank mit einem UPDATE-Statement entsprechend der Rangfolge aktualisiert werden. Dabei bedienen wir uns MySQL-Uservariablen. Zusätzlich wird ausgenutzt, dass im Update ein Order By enthalten sein darf.

SET @rank = 0;
UPDATE player SET rank = (@rank := @rank + 1) ORDER BY score DESC;

Mit folgendem Ergebnis:

name score rank
Emil 123 1
Bert 65 2
Adam 32 3
Carla 32 4
Detlev 28 5

Wie zu sehen, haben Adam und Carla einen unterschiedlichen Rang bekommen, obwohl die beiden die gleiche Punktzahl haben. Das kann umgangen werden, indem zusätzlich die Punktzahl des zuletzt betrachteten Spielers berücksichtigt wird.

SET @rank = 0, @lastscore = 0;
UPDATE player SET rank = (@rank := @rank + IF(score = @lastscore, 0, 1)), score = (@lastscore := score) ORDER BY score DESC;

In der Variable @lastscore steht immer die Punktezahl des vorherigen Spielers. Mit der IF-Funktion wird dann geprüft, ob sich die Punktezahl verändert hat, entsprechend wird der Rang um 1 inkrementiert oder nicht.

name score rank
Emil 123 1
Bert 65 2
Adam 32 3
Carla 32 3
Detlev 28 4

Adam und Carla teilen sich nun den 3. Platz und Detlev ist auf den 4. vorgerückt. Oft gibt es zusätzlich die Regelung, dass Ranglistenplätze übersprungen werden sollen, wenn vorherige mehrfach belegt wurden:

SET @rank = 0, @lastscore = 0, @skips = 0;
UPDATE player SET rank = (@rank := @rank + IF(score = @lastscore, 0 * (@skips := @skips + 1), 1 + @skips + (@skips := 0))),
score = (@lastscore := score) ORDER BY score DESC;

Wenn die Punktzahl zum vorherigen Spieler gleichgeblieben ist, wird @rank nicht erhöht, stattdessen wird die @skips-Variable inkrementiert. Wenn die Punktzahl nicht gleichgeblieben ist, wird der Rang um @skips + 1 inkrementiert und die @skips-Variable auf 0 zurückgesetzt.

name score rank
Emil 123 1
Bert 65 2
Adam 32 3
Carla 32 3
Detlev 28 5

Detlev hat nun wie erwartet den 5. Platz, da der 3. doppelt belegt ist.

Vorteile der vorgestellten Verfahren mit Uservariablen, UPDATE-Statement und speichern des Ranges in der Spieler-Tabelle:

  • benötigt nur einen Table-Scan (keine Joins oder ähnliches)
  • hat keine zusätzlichen Roundtrips zum Client
  • schnelles und direktes Abfragen des Ranglistenplatzes

Nachteile:

  • rank ändert sich nicht automatisch bei einer Änderung von score, die Folge sind inkonsistente Daten
  • muss immer auf der gesamten Tabelle ausgeführt werden; auch Bereichsupdates sind nicht möglich

Weitere Optimierungen:

  • Ein Index auf der Spalte score kann das Rang-Update beschleunigen:
CREATE INDEX player_score_index ON player (score DESC)
  • Ein Primärschlüssel auf der Spalte name kann das Abfragen eines Ranglistenplatzes für einen konkreten Spieler beschleunigen:
ALTER TABLE player ADD PRIMARY KEY (name)
  • Ein Index auf der Spalte rank beschleunigt das Abfragen der Rangliste:
CREATE INDEX player_rank_index ON player (rank ASC)
  • Mit Cron-Jobs kann der Rang-UPDATE-Befehl regelmäßig (z.B. täglich) ausgeführt werden.

… oder ganz anders …

Ein ganz anderer Ansatz setzt auf verschachtelte SELECTs und benötigt auch keine rank-Spalte.

SELECT name, score, 1 + (SELECT count(1) FROM player a WHERE a.score > b.score) AS rank FROM player b ORDER BY rank ASC

Vorteil hierbei ist nun, dass die Ranglisten-Daten immer aktuell sind und bereichsweise oder einzeln berechnet werden können. Das Ergebnis ist das selbe wie beim dritten UPDATE-Statement. Dafür dauert allerdings auch die Berechnung länger, da für jeden Spieler die Anzahl der Spieler berechnet wird, die besser sind als dieser. Auch hier bringt ein Index auf die score-Spalte verbesserte Performance.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.