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);Langage du code : SQL (Structured Query Language) (sql)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);Langage du code : SQL (Structured Query Language) (sql)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;Langage du code : SQL (Structured Query Language) (sql)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);Langage du code : SQL (Structured Query Language) (sql)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;Langage du code : SQL (Structured Query Language) (sql)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.
Merci pour cet article.
Cependant, je ne vois pas 10001 requêtes mais bien une seule requête SQL.
SQL est un langage en partie fonctionnel de mon pont de vue. Le vrai problème, c’est que votre moteur de BdD ne fait pas les optimisations nécessaires pour aller chercher l’information de manière efficace alors que vous lui donnez tout ce dont il a besoin (la condition de jointure entre Avis et Produit).
Selon moi, une solution à votre problème est d’écrire la requête de cette manière :
SELECT Produit.id AS id_produit,
Produit.nom AS nom_produit,
Categorie.id AS id_categorie,
Categorie.nom AS nom_categorie,
COUNT(Avid.id) AS nbr_avis,
AVG(Avis.note) AS note_moyenne
FROM Produit
INNER JOIN Categorie ON (Produit.id_categorie = Categorie.id)
LEFT OUTER JOIN Avis ON (Avis.id_produit = Produit.id)
GROUP BY Produit.id, Produit.nom, Categorie.id, Categorie.nom;
N’est pas plus simple et tout aussi efficace ?
Je ne sais pas si un moteur de BdD le fait, mais c’est la manière dont j’espère qu’il interprète ce type de requêtes.
Un livre existe sur ce problème, appliqué à PHP : https://leanpub.com/sn1php
@Michel : Merci, je ne connaissais pas ce libre. Je connais « Modernizing Legacy Applications in PHP », du même auteur, donc j’ai tendance à penser qu’il doit être de bonne qualité.
Après, il y a déjà pas mal de littérature sur le sujet.
@Julien L. : Non, il y a bien 10001 requêtes, car les sous-requêtes dans le select génèrent des requêtes séparées, qui assassinent la base de données.
Sinon je suis d’accord, sur l’exemple que je donne on pourrait tout à faire faire une seule requête avec un group by. C’était à fin d’illustration, et si on imagine que les deux sous-requêtes opèrent sur des tables différentes (au lieu de taper deux fois sur la table Avis), l’utilisation de tables temporaire devient assez indispensable.
Bonjour,
Un moyen simple d’éviter de passer par la case table temporaire (et donc de réaliser 2 instructions séparées qui peuvent être contraignantes selon le contexte) est de construire une vue à la volée dans le FROM :
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 (
SELECT id_produit,
COUNT(*) AS nbr_avis,
AVG(note) AS note_moyenne
FROM Avis
GROUP BY id_produit) tProduitAvis on (Produit.id = tProduitAvis.id_produit);
tProduitAvis existera uniquement pendant l’exécution de la requête principale. Pratique.
Traditionnellement, le sens de résolution des requêtes par les moteurs est : FROM->WHERE->SELECT
Et donc effectivement, les SELECT dans les SELECT sont à proscrire.
Cette technique de remonter le maximum de requêtes dans le FROM principal quand on le peut est me semble t’il une bonne pratique en général, et pas seulement pour le problème N+1 (par exemple permet d’exécuter des restrictions pertinentes avant les jointures, prendre la main sur le sens de résolution et le plan d’exécution), puisque tout commence dans le FROM…et ce qui est fait n’est plus à faire.
@Kir : Oui, tout à fait, cela revient au même dans ce cas. MySQL va automatiquement créer une table temporaire dans laquelle il stockera le résultat de la première requête.
Le fait de passer par de « vraies » tables temporaires offre d’autres avantages, comme celui de pouvoir effectuer plusieurs requêtes utilisant le contenu des tables temporaires. Cela évite à MySQL de retourner chercher les données à chaque fois.