Classement en MySQL, comment obtenir les meilleures performances avec des mises à jour fréquentes et un grand ensemble de données?

Question

Je veux un classement groupé sur une très grande table, j'ai trouvé quelques solutions pour ce problème, par exemple. en this post et d'autres endroits sur le web. Je suis cependant incapable de comprendre la complexité la plus défavorable de ces solutions. Le problème spécifique consiste en une table où chaque ligne a un nombre de points et un nom associé. Je veux être en mesure de demander des intervalles de rang tels que 1-4. Voici quelques exemples de données:

name | points 
Ab  14 
Ac  14 
B  16 
C  16 
Da  15 
De  13 

Avec ces valeurs suivantes « classement » est créé:

Query id | Rank | Name 
1   1  B 
2   1  C 
3   3  Da 
4   4  Ab 
5   4  Ac 
6   6  De 

Et il devrait être possible de créer l'intervalle suivant sur de ID_requête: 2-5 dons rang: 1,3,4 et 4.

La base de données contient environ 3 millions d'enregistrements, donc si possible, je veux éviter une solution avec une complexité supérieure à log (n). Il y a constamment des mises à jour et des insertions sur la base de données, de sorte que ces actions devraient de préférence être effectuées aussi dans la complexité log (n). Je ne suis pas sûr que ce soit possible et j'ai essayé d'envelopper ma tête pendant un certain temps. Je suis arrivé à la conclusion qu'une recherche binaire devrait être possible mais je n'ai pas été capable de créer une requête qui fait cela. J'utilise un serveur MySQL.

Je vais élaborer sur la façon dont le pseudo-code pour le filtrage pourrait fonctionner. Tout d'abord, un index sur (points, nom) est nécessaire. En entrée, vous donnez un fromrank et un tillrank. Le nombre total d'enregistrements dans la base de données est n. Le pseudocode doit ressembler à ceci:

Trouver la valeur du point médian, compter les lignes inférieures à cette valeur (le nombre donne une estimation grossière du rang, sans tenir compte de celles ayant le même nombre de points). Si le nombre renvoyé est supérieur au délimiteur fromrank, nous subdivisons la première moitié et trouvons la médiane de celle-ci. Nous continuons à faire cela jusqu'à ce que nous soyons ciblés sur le nombre de points où fromrank devrait commencer. alors nous faisons la même chose dans la quantité de points avec l'index de nom, et trouvons la médiane jusqu'à ce que nous ayons atteint la rangée correcte. Nous faisons exactement la même chose pour tillrank.

Le résultat devrait être log (n) nombre de subdivisions. Donc, étant donné que la médiane et le compte peuvent être faits en temps de log (n), il devrait être possible de résoudre le problème dans le cas le plus défavorable du log de complexité (n). Corrigez-moi si je me trompe.

Answer 1

Vous avez besoin d'une procédure stockée pour être en mesure d'appeler cela avec les paramètres:

CREATE TABLE rank (name VARCHAR(20) NOT NULL, points INTEGER NOT NULL); 

CREATE INDEX ix_rank_points ON rank(points, name); 

CREATE PROCEDURE prc_ranks(fromrank INT, tillrank INT) 
BEGIN 
    SET @fromrank = fromrank; 
    SET @tillrank = tillrank; 
    PREPARE STMT FROM 
    ' 
    SELECT rn, rank, name, points 
    FROM (
    SELECT CASE WHEN @cp = points THEN @rank ELSE @rank := @rn + 1 END AS rank, 
      @rn := @rn + 1 AS rn, 
      @cp := points, 
      r.* 
    FROM (
     SELECT @cp := -1, @rn := 0, @rank = 1 
     ) var, 
     (
     SELECT * 
     FROM rank 
     FORCE INDEX (ix_rank_points) 
     ORDER BY 
      points DESC, name DESC 
     LIMIT ? 
     ) r 
    ) o 
    WHERE rn >= ? 
    '; 
    EXECUTE STMT USING @tillrank, @fromrank; 
END; 

CALL prc_ranks (2, 5); 

Si vous créez l'index et la force MySQL à utiliser (comme dans ma requête), la complexité de la requête ne dépend pas du nombre de lignes du tout, cela dépendra seulement de tillrank.

En réalité, les valeurs tillrank seront prises à partir de l'index, effectueront des calculs simples et filtreront les premières valeurs fromrank.

Le temps de cette opération, comme vous pouvez le voir, ne dépend que de tillrank, cela ne dépend pas du nombre d'enregistrements disponibles.

Je viens de vérifier sur 400,000 lignes, il sélectionne les rangs de 5 à 100 en 0,004 secondes (c'est instantanément)

Important: cela ne fonctionne que si vous triez sur les noms dans l'ordre DESCENDING.MySQL ne prend pas en charge la clause DESC dans les index, cela signifie que les points et name doivent être triés dans un ordre pour que INDEX SORT soit utilisable (à la fois ASCENDING ou les deux DESCENDING). Si vous voulez rapidement ASC tri par name, vous devrez garder à la base de données négatifs points et changer le signe dans la clause SELECT.

Vous pouvez également supprimer name de l'index du tout, et d'effectuer une ORDER « ing finale sans utiliser un indice:

CREATE INDEX ix_rank_points ON rank(points); 

CREATE PROCEDURE prc_ranks(fromrank INT, tillrank INT) 
BEGIN 
    SET @fromrank = fromrank; 
    SET @tillrank = tillrank; 
    PREPARE STMT FROM 
    ' 
    SELECT rn, rank, name, points 
    FROM (
    SELECT CASE WHEN @cp = points THEN @rank ELSE @rank := @rn + 1 END AS rank, 
      @rn := @rn + 1 AS rn, 
      @cp := points, 
      r.* 
    FROM (
     SELECT @cp := -1, @rn := 0, @rank = 1 
     ) var, 
     (
     SELECT * 
     FROM rank 
     FORCE INDEX (ix_rank_points) 
     ORDER BY 
      points DESC 
     LIMIT ? 
     ) r 
    ) o 
    WHERE rn >= ? 
    ORDER BY rank, name 
    '; 
    EXECUTE STMT USING @tillrank, @fromrank; 
END; 

Ce sera la performance des répercussions sur les grandes gammes, mais vous remarquerez à peine sur petit gammes.