Discussion :

[sevyc64]

Salut à tous,

Je rencontre un phénomène étrange que je ne sais pas expliquer. Je suis sous Firebird 2.5, et mon logiciel est développé avec Delphi6 (mais j'ai le même phénomène si j'utilise DataBase Workbench, EMS)

J'ai la requête suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
SELECT ....
FROM A
LEFT JOIN B ON A.FKB=B.PK
LEFT JOIN C ON A.FKC=C.PK
LEFT JOIN D ON C.FKD=D.PK

Cette requête met un certain temps à s’exécuter (A environ 30000 lignes, B 5 lignes, C environ 200 lignes, D 10 lignes)

Si je transforme les LEFT JOIN en INNER JOIN sur C et D, je n'ai quasiment pas de variation de temps d’exécution (idem si je supprime carrément la jointure sur D)

Par contre si je transforme la jointure sur B en INNER JOIN, non seulement j'ai le temps d’exécution qui est divisé par, mais aussi et surtout le temps de parcours des résultats diviser quasiment par 10

Je ne comprend pas pourquoi la modification de la jointure sur B a une telle incidence alors que le modification de la jointure sur C n'a aucune incidence.
B et C ont des structures similaires, clé primaire, index asc et desc sur la clé primaire, jointure sur la clé primaire.

[Artemus24]

Salut sevyc64.

Un left, ce n'est pas inner !! Je sais, c'est une vérité de La Palice.

Faisons le raisonnement que sur deux tables.
Voici la jointure :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
SELECT ....
FROM A
LEFT JOIN B ON B.PK = A.FKB;

La table A fait 30.000 lignes et B fait 5 lignes.

Que se passe-t-il ?

La balayage va se faire en partant de la table A.
A chaque jointure, il va vérifier la présence de la clef dans la table B.
Si trouvé, il met les valeurs des colonnes de la table B.
Si pas trouvé, il met des nulls pour les coonnes de la table B.

Nombre d'accès sur table A : 30.000
Nombre d'accès sur table B : 30.000

Et c'est normal, car tu commences par dire que la table maitre est la table A.
Si maintenant, tu fais :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
SELECT ....
FROM B
LEFT JOIN A ON A.FKB = B.PK;

Tu auras cimme résultat :

Nombre d'accès sur table B : 5
Nombre d'accès sur table A : 5

Et si on fait un inner ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
SELECT ....
FROM A
INNER JOIN B ON B.PK = A.FKB;

Ici, le SGBD va commencer par la table la plus petite. Donc ici, il parcourt en premier la table B.
Et ensuite, il va chercher la jointure dans la table A.

Nombre d'accès sur table B : 5
Nombre d'accès sur table A : 5

En gros, un left, c'est très coûteux en terme de performance, surtout si tu désignes comme table maître, la plus grosse table en terme de lignes.

@+

[TryExceptEnd]

Salut sevyc64.

Un left, ce n'est pas inner !! Je sais, c'est une vérité de La Palice.

Faisons le raisonnement que sur deux tables.
Voici la jointure :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
SELECT ....
FROM A
LEFT JOIN B ON B.PK = A.FKB;

La table A fait 30.000 lignes et B fait 5 lignes.

Que se passe-t-il ?

La balayage va se faire en partant de la table A.
A chaque jointure, il va vérifier la présence de la clef dans la table B.
Si trouvé, il met les valeurs des colonnes de la table B.
Si pas trouvé, il met des nulls pour les coonnes de la table B.

Nombre d'accès sur table A : 30.000
Nombre d'accès sur table B : 30.000

hola! c'est quoi ce chiffre de 30.000 pour la table B ?
si on suis ton raisonnement ce serait plutôt : 30.000 x 5 = 150.000 accès ! ce qui est faux bien-sur.
comme la jointure se fait avec des colonnes avec des clés primaires, l’accès sur la table B se feras seulement 5 fois.

Le problème vient surement des index utilisé, qui ne seraient pas assez sélectifs.

[sevyc64]

Ok, Artemus24 mais tu ne réponds pas à la problématique.

La problématique n'est pas de savoir comment fonctionne un LEFT JOIN. Oui un LEFT join est plus long qu'un INNER en règle générale, oui la table B sera interrogée 30000 fois, une fois par ligne de la table A. Mais normalement, ce n'est pas la table B qui est parcourue mais plutôt l'index de sa clé primaire. La table sera, elle, interrogée directement à l'enregistrement qui va bien.

Maintenant, la problématique. Elle porte sur 3 points :

1. le rapport sur le temps d’exécution entre un LEFT et INNER JOIN. Il est ici de 10. Personnellement j'étais plus habitué à des rapports de 2 à 3.
   Encore, soit, que suivant les SGBD, ce rapport soit différent, c'est pas inconcevable.
2. Pourquoi de ce rapport de 1 à 10 concernant la jointure sur B, alors que le même rapport est de l'ordre de 1 concernant la jointure sur C. B et C étant de structure similaire, c'est illogique.
   Ou alors quelque chose m'échappe. Et quelque chose m'échappe, oui, mais quoi ?
3. Le point qui m'a le plus surpris est encore en réalité celui-ci. Pourquoi de passer d'un LEFT à un INNER influence-t-il à ce point le parcours du recordset? Pour moi, une fois la requête exécutée, les données finales sont dans le recordset, il ne devrait y avoir de différence. Ici, on dirait au contraire que les jointures ne se font pas à l’exécution de la requête mais bien à la lecture du recordset.
   Je n'avais jamais constater ça jusqu'à maintenant. Bon il est vrai aussi que je n'avais jamais réellement investigué sur ce point car je n’avais jamais constater de variation importante au parcours d'un recordset mais plutôt toujours à l’exécution de la requête.

Il n'y a qu'un seul point que je n'ai pas pensé à vérifier (et aujourd'hui, j'ai fait autre chose) c'est la définition des colonnes servant de clé étrangères sur la table A, notamment si elles ont, elles-aussi, des index ou pas. Je suis à peu prés sur que la colonne servant de FK sur la table C a au moins un index asc. Pour l'autre, je n'en sais rien.

[Artemus24]

Salut à tous.

hola! c'est quoi ce chiffre de 30.000 pour la table B ?

Quand tu fais un "left join", la requête commence nécessairement par lire en premier la table A.
Donc pour chaque ligne de la table A, il y a un accès vers la table B.
S'il y a 30.000 lignes dans la table A, il y a nécessairement 30.000 accès à la table B.
Si tu utilises un index, alors chaque accès à la table B se ferra en un seule lecture.

si on suis ton raisonnement ce serait plutôt : 30.000 x 5 = 150.000 accès ! ce qui est faux bien-sur.

Mais ce n'est pas mon raisonnement ! Ton résultat suppose que tu fais un seul accès à la table B, ce qui est faux.
L'algorithme utilisé ici est un Nested loop join !

La problématique n'est pas de savoir comment fonctionne un LEFT JOIN.

Bien sûr que oui, car cela va influencer les performances de la requête.

Oui un LEFT join est plus long qu'un INNER en règle générale, oui la table B sera interrogée 30000 fois, une fois par ligne de la table A.

Nous sommes d'accord sur ce point.

Mais normalement, ce n'est pas la table B qui est parcourue mais plutôt l'index de sa clé primaire. La table sera, elle, interrogée directement à l'enregistrement qui va bien.

Ta remarque est tout à fait juste. Pour un accès donné à la table B, il va interroger l'index et faire une seule lecture, s'il trouve la ligne correspondante, et soit renseigner les colonnes ou bien mettre null !

1.le rapport sur le temps d’exécution entre un LEFT et INNER JOIN.

Tout dépend du résultat que tu recherches à obtenir. C'est le point le plus important.
Si tu as fait le choix du "left join", c'est pour obtenir toutes les lignes de la table A et remplacer les lignes absentes de la table B par des null.
Ce n'est pas exactement la même chose que de récupérer toutes les lignes de B et remplacer les lignes absentes de la table A par des null.
Ni la même chose que de récupérer toutes les lignes de A qui sont en jointures avec celle de B car ce cas-ci est l'intersection.

Entrons dans le vif du sujet. Nous voulons comparer quatre cas de figures :
1) A left join B
2) B left join A

3) A inner join B
4) B inner join A

Le cas 3) et 4) sont totalement similaires car le "inner join" est symétrique en terme de résultat à l'affichage. Pourquoi ?
Partir de la table A et rechercher les jointures présentent dans la table B, c'est exactement pareil que faire l'inverse.
En mathématique, cela se nomme l'intersection de deux ensembles. Voici une image résumant cela :


Par contre le cas 1) n'est pas du tout équivalent au cas 2).

Pour la cas 1) on part de la table A, et on affiche toutes les lignes de la table A.
Mais pour la table B, on affiche soit les lignes en jointures avec la table A ou soit des null.
Donc on affiche toutes les lignes de la table A.

Pour la cas 2) ici, on part de la table B, et on affiche toutes les lignes de la table B.
Mais pour la table A, on affiche soit les lignes en jointures de la table B, soit des null.
Donc on affiche toutes les lignes de la table B.

Et comme la table A n'est pas identique à la table B, en nombre de lignes, de ce fait, le "A left join B" n'est pas symétrique au "B left join A".

Reste à savoir si le cas 1) et/ou le cas 2) sont équivalents aux cas 3) et 4) qui eux sont identiques ?

a) toutes les lignes de la table B sont en relation avec les lignes de la table A. C'est le cas de l'inclusion.
De cela, le cas 2), 3) et 4) produisent le même résultat puisque la table B est incluse dans la table A.

Par contre, nous n'obtenons pas les mêmes résultat sur le cas 1) qui est l'ensemble le plus grand.

b) toutes les lignes de la table B ne sont pas nécessairement en relation avec les lignes de la table A.
Autrement dit, il y a des lignes B qui ne sont pas en jointure avec les lignes de la table A.

Le plus petit ensemble de lignes seront les cas 3) et 4). C'est le cas de l'intersection.

Le cas 1) reste le plus grand ensemble de lignes à l'affichage car c'est la table qui contient le plus de lignes.

le cas 2) est un ensemble intermédiaire car il va afficher toutes les lignes de la table B, même celles qui sont absentes de la table A.

Pourquoi de ce rapport de 1 à 10 concernant la jointure sur B, alors que le même rapport est de l'ordre de 1 concernant la jointure sur C. B et C étant de structure similaire, c'est illogique.

Selon l'usage que l'on fait soit du "left join" ou soit du inner join" dans une requête, nous n'obtenons pas nécessairement les mêmes résultats.

Dans le cas du "left join", le SGBD ne fait aucune optimisation et traite les tables selon l'ordre indiqué dans la requête.
Dans le cas du "inner join", le SGBD fait une optimisation en traitant en premier la table la plus petite.

Et c'est pourquoi, si la table A contient plus de lignes que la table B, en terme de performance, "A left join B" ne produira pas les mêmes résultats que "A inner join B", mais mettra plus de temps à l'exécution.

Et la différence de performance peut aussi s'expliquer par le nombre de lignes à traiter.

Donc en résumé :

--> vérifier que les résultats sont bien ceux que vous désirez obtenir à l'affichage. Autrement dit, avez-vous toutes vos lignes et toutes vos valeurs dans vos colonnes ?

--> ne confondez pas un "left join" avec un "inner join". Cela ne produit pas les mêmes résultats au final.

--> dans un "left join", si vous le pouvez, commencez par la table ayant le plus petit nombre de lignes.

--> si c'est une intersection que vous recherchez, utilisez le "inner join" ! Ici, l'ordre n'a plus aucune importance.

--> utilisez des index sur les colonnes servant aux jointures.

--> si vous utilisez un where sur plusieurs colonnes, utilisez aussi un index.

@+

[SergioMaster]

Bonjour,

je ne m'étendrais pas sur la "polémique" JOIN/LEFT JOIN/INNER JOIN et l'ordre d'interrogation des tables.

En première lecture de ton Post, ma première idée non postée était : "et en mettant la jointure sur B en fin"

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
SELECT ....
FROM A
LEFT JOIN C ON A.FKC=C.PK LEFT JOIN D ON C.FKD=D.PK
LEFT JOIN B ON A.FKB=B.PK

puis, à ce propos, j'ai toujours eu du mal à savoir s'il était mieux de mettre la jointure ainsi FROM A LEFT JOIN B ON A.FKB=B.PKou ainsi FROM A LEFT JOIN B ON B.PK=A.FBKComme il y a égalité cela n'a certainement aucune importance mais j'ai toujours un doute

Il n'y a qu'un seul point que je n'ai pas pensé à vérifier (et aujourd'hui, j'ai fait autre chose) c'est la définition des colonnes servant de clé étrangères sur la table A, notamment si elles ont, elles-aussi, des index ou pas. Je suis à peu prés sur que la colonne servant de FK sur la table C a au moins un index asc. Pour l'autre, je n'en sais rien.

Que dit le PLAN ? si tu as accès à ce dernier bien sûr

est-il possible d'avoir le jeu d'essais (tout du moins la structure des Index) pour tenter de trouver le problème, voire vérifier que la version 3 fait la même chose ?

[sevyc64]

merci pour le cours mais je connais déjà bien le principe des jointures. Et ça ne répond toujours pas à mes questions :

- Pourquoi de modifier une jointure LEFT vers INNER a un telle influence alors que de modifier la seconde jointure LEFT vers INNER n'a aucune influence. Ce n'est pas l'explication du LEFT vers JOIN que je demande, mais bien la différence de comportement sur les 2 modifications.

- Pourquoi de modifier une jointure LEFT vers INNER a une incidence sur la lecture même du recordset. Il est censé contenir uniquement les résultats finaux qui sont ici dans les 2 cas strictement identiques, donc son parcours devrait être de même durée. Hors j'ai bien l'a aussi un rapport de 1 à 10. Et c'est bien la lecture de chaque enregistrement qui est plus longue et non pas uniquement celle qui correspond au chargement de la page suivante, tous les 264 enregistrements dans le cas présent.



Juste pour info, oui, les requêtes, ici, étaient mal conçue, elles auraient dû être avec des inner dès le départ. La base elle-même est mal conçue, il manque la moitié des clé primaires, il n'y a aucune clé étrangère en tant que tel (et donc aussi les contraintes qui vont avec), il manque aussi un bon nombre d'index, mais c'est un combat quotidien pour faire accepter les modifications sur cette base.

[sevyc64]

Que dit le PLAN ? si tu as accès à ce dernier bien sûr

Le plan est évidemment nettement plus concis dans le cas du INNER. Par contre je ne l'ai pas sous les yeux, là, ni un jeu d'essai, et je n'ai jamais été trop fort pour interpréter les plans dans le détails.

De toute façon, maintenant l'applicatif est corrigé avec des INNER dans cette requête là.
Et peut-être qu'il sera encore plus corrigé prochainement pour carrément virer les jointures et charger les tables B et C dans des listes dans l'applicatif avant d’exécuter la requête sur la table A. C'est en cours de discussion.
Les tables B et C, dans le cas présent, ne servent pas de "filtre" aux enregistrements venant de A mais juste à récupérer des infos complémentaires. Elles pourraient donc être chargées séparément sans influencer le résultat sur la table A

[Artemus24]

Salut sevyc64.

Je pensais pourtant avoir été clair sur la différence de comportement entre le "left join" et le "inner join".

- Pourquoi de modifier une jointure LEFT vers INNER a un telle influence alors que de modifier la seconde jointure LEFT vers INNER n'a aucune influence. Ce n'est pas l'explication du LEFT vers JOIN que je demande, mais bien la différence de comportement sur les 2 modifications.

La différence essentielle tient au nombre de lignes lues en premier !

Avec un "left join", tu lis en premier toute la table A, sans passer par l'index et donc tu lis 30.000 lignes. pourquoi ? Car lire l'index en plus, prend plus de temps que de faire un balayage de la totalité de la table A.
Avec un "inner join", tu lis en premier la plus petite des deux tables A ou B, et tu traites d'abord la jointure, c'est-à-dire que tu passes par l'index. Ici, c'est B, donc tu lis 5 lignes.
Le rapport de performance est de l'ordre de 30.000 / 5 = 6.000

Modifier la seconde jointure n'a aucun influence, car cette seconde jointure dépend essentiellement de la première jointure, et donc du nombre de lignes lues en premier.

- Pourquoi de modifier une jointure LEFT vers INNER a une incidence sur la lecture même du recordset.

Je l'ai dit précédemment. Avec un "left join", il n'y a pas d'optimisation. Le SGBD lit les tables selon l'ordre indiqué dans la requête.
Avec un "inner join", le SGBD optimise les accès, et va sélectionner en premier la plus petite table à lire.

Il est censé contenir uniquement les résultats finaux qui sont ici dans les 2 cas strictement identiques, donc son parcours devrait être de même durée.

Non, car dans le "left join", il balaye la totalité de la table A.
Dans le cas du "inner join", il traite en premier la plus petite table, soit la B, et passe par l'index de la jointure.

Hors j'ai bien l'a aussi un rapport de 1 à 10. Et c'est bien la lecture de chaque enregistrement qui est plus longue et non pas uniquement celle qui correspond au chargement de la page suivante, tous les 264 enregistrements dans le cas présent.

Ce n'est pas le temps de lecture de chaque ligne qui a changé.
C'est que tu ne lis pas le même nombre de lignes pour ta requête !

Il vaut mieux nous donner intégralement ta requête, car on final, on ne sait pas s'il n'y a pas aussi des regroupements ("group by"), ou des exclusions ("where") dans ta requête. Car ceux-ci se font après l'extraction des tables, donc n'ont aucune influence sur le nombre de lectures.

@+