Quel est le problème de requête SELECT N + 1?

Supposons que vous ayez une collection d’objects Car (lignes de firebase database) et que chaque Car possède une collection d’objects Wheel (également des lignes). Autrement dit, Car -> Wheel est une relation un à plusieurs.

Maintenant, supposons que vous ayez à parcourir toutes les voitures et à imprimer une liste des roues. L’implémentation naïve O / R ferait ce qui suit:

 SELECT * FROM Cars; 

Et puis pour chaque Car :

 SELECT * FROM Wheel WHERE CarId = ? 

En d’autres termes, vous avez un choix pour les voitures, puis N sélections supplémentaires, où N est le nombre total de voitures.

Alternativement, on pourrait obtenir toutes les roues et effectuer les recherches en mémoire:

 SELECT * FROM Wheel 

Cela réduit le nombre d’allers-retours à la firebase database de N + 1 à 2. La plupart des outils ORM vous permettent d’éviter plusieurs sélections N + 1.

Référence: Java Persistence with Hibernate , chapitre 13.

 SELECT table1.* , table2.* INNER JOIN table2 ON table2.SomeFkId = table1.SomeId 

Cela vous permet d’obtenir un jeu de résultats où les lignes enfants de la table 2 entraînent une duplication en renvoyant les résultats de la table1 pour chaque ligne enfant de la table2. Les mappeurs O / R doivent différencier les instances table1 en fonction d’un champ clé unique, puis utiliser toutes les colonnes table2 pour remplir les instances enfant.

 SELECT table1.* SELECT table2.* WHERE SomeFkId = # 

N + 1 est l’endroit où la première requête remplit l’object primaire et la seconde requête remplit tous les objects enfants pour chacun des objects primaires uniques renvoyés.

Considérer:

 class House { int Id { get; set; } ssortingng Address { get; set; } Person[] Inhabitants { get; set; } } class Person { ssortingng Name { get; set; } int HouseId { get; set; } } 

et des tableaux avec une structure similaire. Une seule requête pour l’adresse “22 Valley St” peut retourner:

 Id Address Name HouseId 1 22 Valley St Dave 1 1 22 Valley St John 1 1 22 Valley St Mike 1 

L’O / RM doit remplir une instance de Home avec ID = 1, Address = “22 Valley St”, puis remplir le tableau Inhabitants avec des instances People pour Dave, John et Mike avec une seule requête.

Une requête N + 1 pour la même adresse utilisée ci-dessus entraînerait:

 Id Address 1 22 Valley St 

avec une requête séparée comme

 SELECT * FROM Person WHERE HouseId = 1 

et résultant dans un dataset distinct comme

 Name HouseId Dave 1 John 1 Mike 1 

et le résultat final étant le même que ci-dessus avec la requête unique.

Les avantages de la sélection simple sont que vous obtenez toutes les données à l’avance, ce qui peut être ce que vous désirez en fin de compte. Les avantages de N + 1 sont que la complexité des requêtes est réduite et vous pouvez utiliser le chargement différé où les jeux de résultats enfants ne sont chargés qu’à la première demande.

Fournisseur avec une relation un à plusieurs avec Product. Un fournisseur a (fournit) de nombreux produits.

 ***** Table: Supplier ***** +-----+-------------------+ | ID | NAME | +-----+-------------------+ | 1 | Supplier Name 1 | | 2 | Supplier Name 2 | | 3 | Supplier Name 3 | | 4 | Supplier Name 4 | +-----+-------------------+ ***** Table: Product ***** +-----+-----------+--------------------+-------+------------+ | ID | NAME | DESCRIPTION | PRICE | SUPPLIERID | +-----+-----------+--------------------+-------+------------+ |1 | Product 1 | Name for Product 1 | 2.0 | 1 | |2 | Product 2 | Name for Product 2 | 22.0 | 1 | |3 | Product 3 | Name for Product 3 | 30.0 | 2 | |4 | Product 4 | Name for Product 4 | 7.0 | 3 | +-----+-----------+--------------------+-------+------------+ 

Facteurs:

• Mode paresseux pour le fournisseur défini sur «true» (par défaut)

• Le mode de récupération utilisé pour interroger le produit est Sélectionner

• Mode de récupération (par défaut): les informations du fournisseur sont accessibles

• Caching ne joue pas un rôle pour la première fois

• Le fournisseur est accédé

Le mode de récupération est Select Fetch (par défaut)

 // It takes Select fetch mode as a default Query query = session.createQuery( "from Product p"); List list = query.list(); // Supplier is being accessed displayProductsListWithSupplierName(results); select ... various field names ... from PRODUCT select ... various field names ... from SUPPLIER where SUPPLIER.id=? select ... various field names ... from SUPPLIER where SUPPLIER.id=? select ... various field names ... from SUPPLIER where SUPPLIER.id=? 

Résultat:

• 1 relevé de sélection pour le produit
• N déclarations sélectionnées pour le fournisseur

Ceci est N + 1 sélectionner le problème!

Je ne peux pas commenter directement d’autres réponses, car je n’ai pas assez de réputation. Mais il convient de noter que le problème ne se pose essentiellement que parce que, historiquement, beaucoup de dbms ont été assez pauvres en termes de gestion des jointures (MySQL étant un exemple particulièrement remarquable). Ainsi, n + 1 a souvent été nettement plus rapide qu’une jointure. Et puis, il y a des moyens d’améliorer n + 1 mais toujours sans avoir besoin d’une jointure, ce à quoi le problème initial se rapporte.

Cependant, MySQL est désormais bien meilleur qu’avant en matière de jointure. Lorsque j’ai appris MySQL pour la première fois, j’ai beaucoup utilisé. Ensuite, j’ai découvert à quel point ils étaient lents et je suis passé à n + 1 dans le code. Mais, récemment, je suis revenu aux jointures, car MySQL les gère beaucoup mieux qu’au début de son utilisation.

De nos jours, une simple jointure sur un ensemble de tables correctement indexées pose rarement problème, en termes de performances. Et si les performances sont atteintes, l’utilisation d’indices d’index les résout souvent.

Ceci est discuté ici par l’une des équipes de développement MySQL:

http://jorgenloland.blogspot.co.uk/2013/02/dbt-3-q3-6-x-performance-in-mysql-5610.html

Le résumé est donc le suivant: si vous avez évité des jointures par le passé à cause des performances désastreuses de MySQL, essayez à nouveau avec les dernières versions. Vous serez probablement agréablement surpris.

Nous nous sums éloignés de l’ORM de Django à cause de ce problème. Fondamentalement, si vous essayez de faire

 for p in person: print p.car.colour 

L’ORM renverra avec plaisir toutes les personnes (généralement en tant qu’instances d’un object Person), mais devra ensuite interroger la table de la voiture pour chaque personne.

Une approche simple et très efficace à cet égard est quelque chose que j’appelle ” fanfolding “, qui évite l’idée absurde que les résultats de requête provenant d’une firebase database relationnelle doivent être redirigés vers les tables d’origine à partir desquelles la requête est composée.

Étape 1: Sélection large

  select * from people_car_colour; # this is a view or sql function 

Cela retournera quelque chose comme

  p.id | p.name | p.telno | car.id | car.type | car.colour -----+--------+---------+--------+----------+----------- 2 | jones | 2145 | 77 | ford | red 2 | jones | 2145 | 1012 | toyota | blue 16 | ashby | 124 | 99 | bmw | yellow 

Etape 2: Objectiver

Sucer les résultats dans un créateur d’object générique avec un argument à diviser après le troisième élément. Cela signifie que l’object “jones” ne sera pas fabriqué plus d’une fois.

Étape 3: Rendu

 for p in people: print p.car.colour # no more car queries 

Voir cette page web pour une implémentation de fanfolding pour python.

Supposons que vous avez SOCIETE et EMPLOYÉ. L’ENTREPRISE compte de nombreux EMPLOYÉS (ie EMPLOYEE a un champ COMPANY_ID).

Dans certaines configurations O / R, lorsque vous avez un object Société mappé et que vous accédez à ses objects Employee, l’outil O / R en sélectionne un pour chaque employé. Si vous ne faites que des opérations SQL, vous pouvez select * from employees where company_id = XX . Ainsi N (# d’employés) plus 1 (entreprise)

C’est ainsi que fonctionnaient les versions initiales d’EJB Entity Beans. Je crois que des choses comme Hibernate ont fait disparaître cela, mais je ne suis pas trop sûr. La plupart des outils incluent généralement des informations sur leur stratégie de cartographie.

Voici une bonne description du problème – http://www.realsolve.co.uk/site/tech/hib-tip-pitfall.php?name=why-lazy

Maintenant que vous comprenez le problème, vous pouvez généralement l’éviter en effectuant une extraction de jointure dans votre requête. Cela force fondamentalement la récupération de l’object chargé paresseux afin que les données soient extraites dans une requête au lieu de n + 1 requêtes. J’espère que cela t’aides.

Vérifiez Ayende post sur le sujet: Combattre le problème Select N + 1 dans NHibernate

Fondamentalement, lorsque vous utilisez un ORM tel que NHibernate ou EntityFramework, si vous avez une relation un-à-plusieurs (maître-détail) et que vous souhaitez répertorier tous les détails pour chaque fiche, vous devez appeler N + 1 firebase database, “N” étant le nombre de fiches: 1 requête pour obtenir toutes les fiches, et N requêtes, une par fiche, pour obtenir tous les détails par fiche.

Davantage d’appels de firebase database -> plus de temps de latence -> diminution des performances de l’application / de la firebase database.

Cependant, les ORM ont des options pour éviter ce problème, en utilisant principalement des “jointures”.

À mon avis, l’article écrit dans Hibernate Pitfall: Pourquoi les relations devraient être paresseuses est exactement opposé à la question réelle de N + 1.

Si vous avez besoin d’une explication correcte, référez-vous à Hibernate – Chapitre 19: Amélioration des performances – Récupération de stratégies

Sélectionner la récupération (valeur par défaut) est extrêmement vulnérable aux problèmes de sélection de N + 1, nous pouvons donc vouloir activer la récupération de jointure

Le lien fourni présente un exemple très simple du problème n + 1. Si vous l’appliquez à Hibernate, vous parlez essentiellement de la même chose. Lorsque vous interrogez un object, l’entité est chargée, mais toutes les associations (sauf si elles sont configurées autrement) seront chargées par défaut. D’où une requête pour les objects racine et une autre requête pour charger les associations pour chacun d’eux. 100 objects retournés signifient une requête initiale et 100 requêtes supplémentaires pour obtenir l’association pour chacun, n + 1.

http://pramatr.com/2009/02/05/sql-n-1-selects-explained/

Il est beaucoup plus rapide d’émettre 1 requête qui renvoie 100 résultats que d’émettre 100 requêtes renvoyant chacune 1 résultat.

Le problème de requête N + 1 se produit lorsque vous oubliez de récupérer une association et que vous devez y accéder:

 List comments = entityManager.createQuery( "select pc " + "from PostComment pc " + "where pc.review = :review", PostComment.class) .setParameter("review", review) .getResultList(); LOGGER.info("Loaded {} comments", comments.size()); for(PostComment comment : comments) { LOGGER.info("The post title is '{}'", comment.getPost().getTitle()); } 

Qui génère les instructions SQL suivantes:

 SELECT pc.id AS id1_1_, pc.post_id AS post_id3_1_, pc.review AS review2_1_ FROM post_comment pc WHERE pc.review = 'Excellent!' INFO - Loaded 3 comments SELECT pc.id AS id1_0_0_, pc.title AS title2_0_0_ FROM post pc WHERE pc.id = 1 INFO - The post title is 'Post nr. 1' SELECT pc.id AS id1_0_0_, pc.title AS title2_0_0_ FROM post pc WHERE pc.id = 2 INFO - The post title is 'Post nr. 2' SELECT pc.id AS id1_0_0_, pc.title AS title2_0_0_ FROM post pc WHERE pc.id = 3 INFO - The post title is 'Post nr. 3' 

Tout d’abord, Hibernate exécute la requête JPQL et une liste d’entités PostComment est extraite.

Ensuite, pour chaque PostComment , la propriété post associée est utilisée pour générer un message de journal contenant le titre de la Post .

Comme la post association n’est pas initialisée, Hibernate doit récupérer l’entité Post avec une requête secondaire et pour N entités PostComment , N nouvelles requêtes vont être exécutées (d’où le problème de requête N + 1).

Tout d’abord, vous devez disposer d’ une journalisation et d’une surveillance SQL appropriées afin de détecter ce problème.

Deuxièmement, ce type de problème est préférable aux tests d’intégration. Vous pouvez utiliser une assertion automatique JUnit pour valider le nombre attendu d’instructions SQL générées . Le projet db-unit fournit déjà cette fonctionnalité et est open source.

Lorsque vous avez identifié le problème de requête N + 1, vous devez utiliser un JOIN FETCH pour que les associations enfants soient récupérées dans une requête au lieu de N. Si vous devez récupérer plusieurs associations enfants, il est préférable de récupérer une collection dans la requête initiale et la seconde avec une requête SQL secondaire.

Un millionnaire a N voitures. Vous voulez obtenir toutes les 4 roues.

Une (1) requête charge toutes les voitures, mais pour chaque (N) voiture, une requête distincte est envoyée pour le chargement des roues.

Frais:

Supposons que les index s’intègrent dans ram.

Analyse et planification de la requête 1 + N + recherche d’index ET access à la plaque 1 + N + (N * 4) pour le chargement de la charge utile.

Supposons que les index ne rentrent pas dans ram.

Coûts supplémentaires dans le pire des cas 1 + N access à la plaque pour indice de chargement.

Résumé

Le goulot de la bouteille est un access à la plaque (environ 70 fois par seconde, access aléatoire sur disque dur). Donc, si les index s’intègrent dans ram – pas de problème, c’est assez rapide car seules les opérations de RAM sont impliquées.

Le problème, comme d’autres l’ont dit avec plus d’élégance, est que vous avez soit un produit cartésien des colonnes OneToMany, soit des sélections N + 1. Soit un ensemble de résultats gigantesque ou bavard avec la firebase database, respectivement.

Je suis surpris que cela ne soit pas mentionné, mais c’est comme ça que j’ai contourné ce problème … Je crée un tableau des identifiants semi-temporaires . Je le fais aussi lorsque vous avez la limitation de la clause IN () .

Cela ne fonctionne pas dans tous les cas (probablement pas même une majorité), mais cela fonctionne particulièrement bien si vous avez beaucoup d’objects enfants tels que le produit cartésien deviendra OneToMany (c.-à-d. Beaucoup de colonnes OneToMany le nombre de résultats sera une multiplication des colonnes) et son plus d’un travail comme un lot.

D’abord, vous insérez vos identifiants d’object parent en tant que batch dans une table d’identifiants. Ce batch_id est quelque chose que nous générons dans notre application et que nous conservons.

 INSERT INTO temp_ids (product_id, batch_id) (SELECT p.product_id, ? FROM product p ORDER BY p.product_id LIMIT ? OFFSET ?); 

Maintenant, pour chaque colonne OneToMany , il suffit de faire un SELECT sur la table des identifiants INNER JOIN la table enfant avec un WHERE batch_id= (ou vice versa). Vous voulez simplement vous assurer que vous commandez par la colonne id car cela facilitera la fusion des colonnes de résultats (sinon vous aurez besoin d’un HashMap / Table pour l’ensemble des résultats qui peut ne pas être si mauvais).

Ensuite, vous nettoyez périodiquement la table des identifiants.

Cela fonctionne particulièrement bien si l’utilisateur sélectionne une centaine d’éléments distincts pour un traitement en bloc. Mettez les 100 identifiants distincts dans la table temporaire.

Maintenant, le nombre de requêtes que vous effectuez se fait par le nombre de colonnes OneToMany.

Le problème de sélection N + 1 est douloureux et il est logique de détecter de tels cas dans les tests unitaires. J’ai développé une petite bibliothèque pour vérifier le nombre de requêtes exécutées par une méthode de test donnée ou simplement un bloc de code arbitraire – JDBC Sniffer

Ajoutez simplement une règle JUnit spéciale à votre classe de test et placez une annotation avec le nombre de requêtes attendu sur vos méthodes de test:

 @Rule public final QueryCounter queryCounter = new QueryCounter(); @Expectation(atMost = 3) @Test public void testInvokingDatabase() { // your JDBC or JPA code } 

Prenons l’exemple de Matt Solnit, imaginez que vous définissiez une association entre Car and Wheels et LAZY et que vous ayez besoin de champs de roues. Cela signifie qu’après la première sélection, hibernate va faire “Select * from Wheels where car_id =: id” POUR CHAQUE voiture.

Cela fait que le premier choix et plus 1 sélectionnent par chaque voiture N, c’est pourquoi il est appelé problème n + 1.

Pour éviter cela, faites en sorte que l’association soit récupérée avec impatience, afin que l’hibernation charge les données avec une jointure.

Mais attention, si vous n’accédez pas souvent à des roues associées, il est préférable de le garder LAZY ou de modifier le type de recherche avec les critères.