Query/schema SQL efficiente per una scheda leader

Question

Ho scritto un gioco stupido e voglio avere una sorta di sito web della classifica.

Solitamente le classifiche sono limitate a 10 o 20 giocatori migliori, ma ho pensato che sarebbe stato bello registrare per ogni giocatore, il loro punteggio più alto. Quindi, potrei sempre mostrare il loro rango mondiale.

Un semplice schema come ad esempio:

create table leaderboard (
    userid varchar(128) not null, 
    score real not null, 
    when datetime not null 
); 
create index on leaderboard(userid); 

sarebbe memorizzare la quantità minima di informazioni che ho bisogno - 1 ingresso per ogni utente con il loro miglior punteggio.

La mia domanda ruota attorno a come determinare in modo efficiente la posizione di qualcuno sulla classifica. L'idea generale è che vorrei la loro posizione nella lista restituita da:

select userid from leaderboard order by score desc 

Ma l'esecuzione di questa query e quindi linearmente ricerca la lista sembra un po 'ridicolo per me dal punto di vista delle prestazioni DB. Anche così, sto avendo difficoltà a immaginare una query/schema che lo renderebbe un'operazione rapida.

Qualche idea?

(io preferirei mantenere lo schema DB e interrogare generico (non legato ad un fornitore). Ma, se un fornitore rende questo facile, sono felice di utilizzare MS SQL o MySQL.

Answer 1

Che ne dite di:

select count(*)+1 as rank from leaderboard 
where score > (select score from leaderboard where userid = ?) 

Avrai anche bisogno di un indice sulla colonna del punteggio.

Facendo con score > (...) si otterrà un punteggio corretto anche quando più giocatori hanno lo stesso punteggio; facendo count() con score >= (...) no.

Answer 2

L'ovvio opzione sarebbe quella di creare un indice su "punteggio", che è perfettamente ragionevole. (Sembra che tu voglia preservare due valori - punteggio cumulativo e punteggio alto-acqua - altrimenti fraintendiamo?)

A meno che non ti aspetti decine di migliaia di utenti, anche le scansioni di tabelle non dovrebbero essere un grosso problema su una tabella con tanti record.

Answer 3

Sembra che si vuole interrogare questo:

select userid , max(score) 
from leaderboard 
group by userid 
order by max(score) desc 

Questa operazione riporta la classifica con 1 ingresso per ogni utente.

MODIFICA QUI SOTTO: Vedo nel commento che si desidera vedere il rango, non il punteggio. per questo non so la risposta SQL ANSI, ma database specifico:

In MySQL:

SELECT @rownum:=@rownum+1 rank 
, t.userid 
FROM (SELECT @rownum:=0) r, 
(select userid , score 
from leaderboard 
order by score desc 
) t; 

In Oracle è possibile utilizzare l'istruzione RANK.

Answer 4

Se questo non deve essere in tempo reale (ad esempio se l'aggiornamento una volta al giorno è accettabile), aggiungere un ulteriore campo "posizione" e aggiornarlo periodicamente utilizzando una query ordinata per punteggio.

Answer 5

In SQL Server 2005 in poi, è possibile utilizzare la funzione RANK() per restituire il rango per ogni utente, in base al loro punteggio

SELECT 
    userid, 
    RANK() OVER 
    (ORDER BY score) AS rank 
FROM leaderboard 

Se aveste più di un tipo di 'tipo di gioco', poi si potrebbe includere questo nella tabella Classifica e utilizzare la clausola PARTITION BY all'interno della funzione RANK per determinare la classifica per ciascun tipo di gioco.

Answer 6

Nel server Sql 2005, Rank() praticamente fa il lavoro per voi. Ma se disponi di milioni di dischi, li classifica in tempo reale ogni volta che il cambiamento delle statistiche sottostanti sarà performante.

Ho provato a creare una vista indicizzata sopra la query selezionata ... (la risposta votata in questo thread) ma Sql 2005 non mi consente di crearlo perché non è possibile utilizzare sottoquery, riferimento automatico in una vista indicizzata .

Quindi la nostra soluzione è di aggiornare la tabella dei ranghi ogni notte usando la funzione Riga(). Per evitare il blocco durante l'esecuzione di questo aggiornamento, conserviamo 2 copie della tabella di classifica, una che viene aggiornata e una che viene utilizzata nell'applicazione. Abbiamo una RankingView che punta alla tabella di classifica attiva in qualsiasi momento.

Mi piacerebbe sapere se esiste una soluzione per l'aggiornamento del ranking in tempo reale per tabelle veramente grandi?

Answer 7

Stavo pensando di selezione "select count (*) + 1 come rango da leaderboard
dove punteggio> (selezionare punteggio da leaderboard dove userid =?)"

Pensate alla seguente situazione: Player 1, Score 100 Player 2, Score 100 giocatore 3, Score 50

utilizzando tale SQL rango di giocatore 3 sarebbe 3, in cui la risposta corretta dovrebbe essere di 2, perché Player 1 e Player 2 sono legati a la prima posizione. La funzione di aggregazione count() in questo caso considera 2 record con colonna Punteggio> 50.

Per gestire questo caso, penso che l'opzione giusta sia quella di creare un gruppo in base a valori di punteggio così ripetibili che verranno gestiti come un'unica classifica posizione:

select score, count(*)+1 as rank from leaderboard 
group by score having (score) > (select score from leaderboard where userid = ?)