Bases de données : le problème N+1 en SQL (sous-requêtes dans le SELECT)

Qu’est-ce que le problème N+1 ?

Quand on fait des requêtes SQL complexes, on peut se retrouver à devoir récupérer des données qui ne sont pas accessibles en faisant de simples jointures. Un moyen simple mais hautement inefficace est d’ajouter des sous-requêtes dans le SELECT de la requête.

On appelle cela le “problème N+1”, car on se retrouve de fait à réaliser autant de requêtes sur la base qu’il y a de lignes dans la requête principale. Or chaque requête est très coûteuse, donc leur multiplication aboutit rapidement à des performances déplorables, tout en monopolisant les ressources du serveur, ce qui entraîne une dégradation des performances pour toutes les autres requêtes exécutées au même moment.

On va regarder ça avec des exemples basés sur MySQL.

Un exemple

Pour voir un exemple concret, imaginons un site e-commerce dont la base de données contient des produits. Les produits sont classés dans des catégories, et peuvent recevoir des avis, chaque avis contenant une note entre 1 et 5.

Voici une requête simple permettant de récupérer l’identifiant et le nom de tous les produits, avec l’identifiant et le nom de leur catégorie :

SELECT Produit.id AS id_produit,
       Produit.nom AS nom_produit,
       Categorie.id AS id_categorie,
       Categorie.nom AS nom_categorie
FROM Produit
     INNER JOIN Categorie ON (Produit.id_categorie = Categorie.id);

Rien de bien compliqué, c’est une requête toute bête avec une simple jointure entre deux tables.

Maintenant, imaginons que l’on souhaite récupérer en plus le nombre d’avis et la note moyenne de chaque produit. Ce ne sont pas des données qui sont disponibles en faisant juste une jointure supplémentaire.

Un moyen simpliste de le faire serait d’écrire :

SELECT Produit.id AS id_produit,
        Produit.nom AS nom_produit,
        Categorie.id AS id_categorie,
        Categorie.nom AS nom_categorie,
       (SELECT COUNT(*) FROM Avis
        WHERE Avis.id_produit = Produit.id) AS nbr_avis,
       (SELECT AVG(note) FROM Avis
        WHERE Avis.id_produit = Produit.id) AS note_moyenne 
FROM Produit
      INNER JOIN Categorie ON (Produit.id_categorie = Categorie.id);

Le problème

Dans cet exemple, on peut voir qu’il y a une première requête qui s’exécute pour récupérer la liste des produits (comme la première requête écrite ci-dessus), mais qu’il y a surtout deux requêtes qui s’exécutent pour chaque ligne retournée par la première requête.

Si on imagine que la base contient 5000 produits, on effectuera sans s’en rendre compte 10001 requêtes. Pas juste une seule requête, mais bien dix mille et une requêtes ! On matraque la base de données sans vergogne.

La solution

Comme bien souvent, il existe plusieurs solutions à ce problème.

L’une d’entre elles est de faire une jointure supplémentaire, et de traiter les données en dehors du SQL, de manière applicative. C’est possible, mais c’est loin d’être le plus efficace.

Il existe un moyen simple, qui est de passer par des tables temporaires. Celles-ci permettent de créer des tables contenant des données calculées, qui ne sont visibles que par la connexion qui les a créées. Les tables temporaires sont détruites automatiquement lorsque la connexion du client au serveur est coupée (ou que les tables sont explicitement détruites).

Dans notre exemple, nous commencerons par exécuter une requête qui va créer une table temporaire contenant trois champs : un identifiant de produit, le nombre d’avis de ce produit, et la note moyenne de ces avis. Tous les produits qui contiennent au moins un avis vont avoir une ligne dans cette table.

CREATE TEMPORARY TABLE tProduitAvis
SELECT id_produit,
       COUNT(*) AS nbr_avis,
       AVG(note) AS note_moyenne
FROM Avis
GROUP BY id_produit;

Notre requête peut alors faire des jointures externes sur cette table, pour en récupérer les valeurs :

SELECT Produit.id AS id_produit,
       Produit.nom AS nom_produit,
       Categorie.id AS id_categorie,
       Categorie.nom AS nom_categorie,
       IFNULL(nbr_avis, 0) AS nbr_avis,
       IFNULL(note_moyenne, 0) AS note_moyenne
FROM Produit
     INNER JOIN Categorie ON (Produit.id_categorie = Categorie.id)
     LEFT OUTER JOIN tProduitAvis ON (Produit.id = tProduitAvis.id_produit);

L’utilisation de la fonction IFNULL() dans le SELECT permet de fournir une valeur (zéro) pour les produits qui n’ont reçu aucun avis. Sinon on récupérerait la valeur NULL, car dans ce cas il n’y aurait pas d’entrées correspondant à ces produits dans la table temporaire.

On a donc remplacé nos 10001 requêtes par seulement 2 requêtes. La création de la table temporaire prend du temps, mais cela reste infiniment plus faible que le temps pris par toutes les sous-requêtes. Et plus il y aura de produits dans notre base, plus la différence de performance sera grande.

Pour économiser de la mémoire, on peut détruire la table temporaire quand on n’en a plus besoin :

DROP TEMPORARY TABLE tProduitAvis;

Optimisation

S’il y a un très grand nombre de produits, on pourra améliorer la table temporaire en ajoutant un index sur la clé étrangère vers les produits :

CREATE TEMPORARY TABLE tProduitAvis (
    id_produit     INT UNSIGNED NOT NULL,
    nbr_avis       INT UNSIGNED NOT NULL,
    note_moyenne   INT UNSIGNED NOT NULL,
    INDEX id_produit (id_produit)
) SELECT id_produit,
         COUNT(*) AS nbr_avis,
         AVG(note) AS note_moyenne
FROM Avis
GROUP BY id_produit;

Vous pouvez voir qu’on définit les champs de la table temporaire, au lieu de simplement laisser MySQL le faire automatiquement. Cela permet de faire deux optimisations :

• Ajouter un index sur la clé étrangère vers les produits. Ainsi, les jointures se feront plus vite, car MySQL n’aura pas besoin de scanner toute la table temporaire pour trouver les entrées correspondantes.
• Définir tous les champs en NOT NULL. MySQL contient des optimisations qui lui permettent de ne pas faire certaines vérifications lorsqu’il sait que les champs ne peuvent pas être nuls.

Évidemment, la création d’index prend un peu de temps. Mais ce temps est très vite récupéré au fur et à mesure que le nombre de jointures augmente.