Mon JOIN est plus rapide que ton LIMIT

J'espère que c'est une saine curiosité qui vous aura mené ici. Comment peut-on comparer LIMIT et JOIN ? Ils ne font pas la même chose… Pourtant.

LIMIT est la fameuse clause SQL, implanté dans MySQL, qui permet de limiter un résultat à un offset particulier. Comme ceci :

mysql>SELECT titre FROM bl_content LIMIT 1000, 10;

Cette requête va lire les 10 titres dans la table bl_content à partir de la position 1000. En faisant varier cette position de départ, on peut simuler les systèmes de navigations dans les résultats de grande taille : la page 1 représente le début (position 0), la page 2 représente la position 10, c'est à dire le nombre d'éléments de la page initiale plus la position de la page précédente, comme nouvelle position de départ. Je suis certain que vous avez tous utilisé cette approche pour découper un trop grand résultat en pages, comme pour une recherche dans une table.

LIMIT intervient tout à la fin du traitement de la requête SQL : après les jointures, les conditions de tris, les regroupements et les tris. En fait, elle prend le résultat et prélève uniquement les informations qui sont demandées. Pour prendre une image visuelle, cela revient à cuire un gâteau, prendre sa part, et jeter le reste.

En fait, LIMIT est un peu plus habile que cela, et il va essayer de limiter le travail à ce qui est nécessaire. Si vous demandez les 10 premières lignes d'un résultat, il va dire à la requête de s'arrêter dès que 10 lignes ont été lues. Cela évite de cuire tout le gâteau pour prendre la première part.

Toutefois, LIMIT ne peut pas économiser sur tout : si vous demandez les 10 lignes entre 1000 et 1010, il faudra bien que la requête lise 1010 lignes pour satisfaire LIMIT. Si votre table fait 1 million de lignes, cela épargne toujours 998990 lignes, mais il y a le travail est maintenant lié à la position (l'offset) demandée : LIMIT 0, 10 et LIMIT 1000,10 ne demandent pas le même travail à la requête.

De même, si vous ajoutez un tri dans la requête, il faudra que le tri soit fait dans son intégralité avant que LIMIT ne puisse intervenir. Au bout du compte, vous allez y gagner dans toutes les phases de manipulations du résultat, mais aucunement au niveau de la requête : PHP recevra bien 10 lignes, mais MySQL doit toujours manipuler un million de lignes.

Voici un atelier de performance de LIMIT sur une table de 3 millions de lignes, et fait évoluer la position de recherche. Vous pouvez voir que si la durée initiale est de quasiment null (moins de 1 ms), elle finit dans les 20 secondes autour de la position 22000000.

La table utilisée contient 3 millions de lignes, et présente cette structure :

CREATE TABLE `bl_content` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `titre` char(30) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `titre` (`titre`)
) ENGINE=MyISAM AUTO_INCREMENT=13179233 DEFAULT CHARSET=latin1

La colonne titre a été remplie aléatoirement avec des md5(), et est indexée pour assurer un meilleur tri. Dans mes tests initiaux, l'absence de l'index faisait démarrer les temps de calcul à 2 secondes.

Et la jointure ?
Tout cela est beau, mais nous sommes bien loin du problème initial : pourquoi est-ce que LIMIT est plus lent que JOIN ? Reprenons la problématique précédente : LIMIT est de plus en plus lent parce qu'il y a de plus en plus de lignes à traiter, même si on n'en voit pas plus dans le résultat. Pour accélérer cette requête, il faudrait limiter le nombre de lignes à traiter.

Si on connaissait dès le départ les positions de chaque ligne dans le résultat, on pourrait éviter la clause LIMIT, et transformer cette clause en clause WHERE :

mysql>SELECT titre FROM bl_content 
  WHERE position BETWEEN 1000 and 1000 + 10;

C'est bien beau, mais il nous manque la valeur de position, qui n'est pas connue pour le moment : à chaque fois, on le calcule au moment où le résultat a été trié. Il n'y a pas moyen de l'anticiper sans passer par les données elles-mêmes. Toutefois, une fois qu'une position a été calculée, on peut la noter dans un cache.

Il existe plusieurs possibilités pour calculer des rangs dans un résultat SQL, et je ne vais pas tous les énumérer. Comme nous voulons avoir ces valeurs en cache, je vais utiliser simplement une colonne auto_increment dans une table de navigation.

Voici la table de navigation :

CREATE TABLE `bl_content_nav` (
  `row` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `id` int(11) unsigned DEFAULT NULL,
  PRIMARY KEY (`row`),
  UNIQUE KEY `id` (`id`)
) ENGINE=MyISAM AUTO_INCREMENT=1 DEFAULT CHARSET=latin1;

C'est une table d'assistance, alors elle ne contient que le nécessaire : row, qui sera la position d'une ligne dans le résultat dans lequel nous voulons naviguer. C'est une colonne auto_increment, de manière à ce que l'insertion des lignes engendre le classement automatiquement, par les vertus de l'auto_increment.

Id est la colonne d'identification dans la table bl_content, et sa définition est identique à celle de la colonne bl_content.id, pour optimiser les jointures : car nous voilà arrivés à notre fameuse jointure.

Pour remplir cette table avec les positions et les identifiants, rien de plus simple :

mysql> INSERT INTO bl_content_nav 
  SELECT 0, id FROM bl_content ORDER BY titre;

On appliquons le tri, prélevons les identifiants dans l'ordre et la constante 0, qui tombe dans la colonne auto_increment, va nous calculer les positions. Pour mon jeu de données de 3 000 000 de lignes, cela a pris 56 secondes pour faire cette insertion.

Maintent, comment selectionner les résultats qui nous intéressent?

mysql> SET @offset := 1000;
mysql> SELECT bl_content.id FROM bl_content_nav 
  JOIN bl_content ON bl_content.id = bl_content_nav.id 
  AND bl_content_nav.row BETWEEN @offset AND @offset + 10

La jointure part de la table de navigation, limite les lignes à sélectionner aux positions qui nous intéressent, puis effectue la jointure avec la table de contenu, qui nous intéresse. Le résultat est alors impressionnant : la durée d'exécution est constantes, et tourne en permanence autour de 0,8 ms. Comparez cela aux 20 secondes que prenait LIMIT pour les positions deux millions et supérieur…

C'est comme cela que l'on peut affirmer que les jointures sont plus rapides que LIMIT.

Après les optimisations unitaires, il faut faire des tests en utilisation simultanée.

term> mysqlslap  -c 3 -i 10 -q 'SELECT id FROM test.bl_content 
     ORDER BY titre LIMIT 100000, 10' -u root -password test
Benchmark
        Average number of seconds to run all queries: 2.397 seconds
        Minimum number of seconds to run all queries: 1.589 seconds
        Maximum number of seconds to run all queries: 3.304 seconds
        Number of clients running queries: 3
        Average number of queries per client: 1
 
 
term> mysqlslap  -c 3 -i 10 -q 'SELECT bl_content.id FROM test.bl_content_nav 
      JOIN test.bl_content ON bl_content.id = bl_content_nav.id 
      AND bl_content_nav.row BETWEEN 100000 AND 100000 + 10 ' 
      -u root -password test
 
 
Benchmark
        Average number of seconds to run all queries: 0.006 seconds
        Minimum number of seconds to run all queries: 0.002 seconds
        Maximum number of seconds to run all queries: 0.031 seconds
        Number of clients running queries: 3
        Average number of queries per client: 1

Il faudrait aussi inclure le temps de rafraîchissement du cache, ou un mécanisme de mise à jour du cache. Cela sort du cadre de cet article.

Quelques limitations à ce modèle

• Le coût de mise à jour de la table de navigation peut être douloureux. Comme vous pouvez le voir, une minute de mise à jour est un temps particulièrement long. Il faut un nombre assez élevé de LIMIT > 1000 pour égaler ce temps de mise à jour.
• Si vos données évoluent peu, ou à certains moments précis, la table de navigation est idéale : elle soulage considérablement la base de données en réduisant la quantité de données manipulées, et le travail pour le faire (le tri a été mis en cache).
• Si vos données évoluent souvent, ou bien sont paramétrées, comme dans le cas d'une recherche, vous aurez un peu de mal à implémenter un cache pareil, car il faudra stocker trop de données dans la table de navigation.
• Si vous utilisez uniquement les n premières lignes de votre sélection, LIMIT est aussi rapide qu'un JOIN, et beaucoup plus facile à mettre en place

En résumé, essayez de toujours limiter le nombre de lignes manipulées par MySQL : il sera toujours plus rapide comme cela.