Discussion :

[fsmrel]

Bonjour,


Xo a évoqué il y a déjà un moment l’alternative : Faire les jointures dans la clause WHERE ou avec des JOIN ?

Je dirais pour ma part que la question est à formuler autrement, car on n’effectue pas de jointure dans une clause WHERE, mais seulement une restriction appliquée à un produit cartésien, lui même formulé dans la clause FROM.

Quelques remarques :

1. Il est parfaitement légitime de considérer la jointure comme une primitive, et de suivre la norme en utilisant JOIN. Comme à une clause SELECT ne peut être associée qu’une clause FROM unique, cette dernière peut comporter une liste de jointures (JOIN donc) de tous types (naturelle, thêta, externe, croisée, semi, etc.) : rien à redire. La clause WHERE sert alors seulement pour une salade composée de RESTRICT et de constructions telles que IN et EXISTS, relevant plus ou moins de l’algèbre relationnelle ou du calcul relationnel. JOIN n’entrant pas dans la composition de cette salade, il a le mérite de ne pas contribuer à la rendre indigeste.
   
   
2. Maintenant, si à l’instar de Ted Codd, l’inventeur du Modèle Relationnel de Données, vous considérez la jointure comme n’étant pas une opération primitive (Cf. "Relational completeness of data base sublanguages", March 6, 1972, page 9), mais plutôt comme un RESTRICT appliqué au résultat d’un PRODUIT cartésien, alors dans le contexte de SQL, il est logique de nommer les opérandes du PRODUIT dans la clause FROM et de fournir dans la clause WHERE le prédicat du RESTRICT associé. Les parents de SQL, à savoir Don Chamberlin et al., ont manifestement utilisé la définition de Codd. Je ne cherche pas à justifier leur choix, mais simplement à remettre en perspective les choses dans le contexte de l'époque (plus de trente ans déjà...)
   
   
3. Si IBM avait demandé à Codd de superviser le projet SQL (Codd faisait alors partie du centre de recherche d’IBM à San Jose), SQL ressemblerait aujourd’hui plus à Phoebus qu’à Quasimodo (dont je ne mets pas en cause le bon cœur), mais ceci est une autre histoire, on ne refait pas le passé...

Toujours à l’attention de Xo :

Vous écrivez "Les jointures faites dans la clause WHERE (ancienne syntaxe de 1986 !)..."

Vous pouvez remonter encore au moins de 10 ans dans le temps, pour trouver l’utilisation de WHERE en conjugaison avec la jointure, quand SQL s’appelait encore SEQUEL (nom qu’il a fallu changer pour des problèmes de copyright). L’opérateur JOIN a pour sa part été déjà décrit par Ted Codd en 1969, du temps où celui-ci était chercheur chez IBM ("Derivability, Redundancy, and Consistency of Relations Stored in Large Data Banks").


Étant un vieux de la vieille, j'utilise plutôt l'ancienne syntaxe, me contentant d'énumérer les tables à joindre, sagement rangées dans la clause FROM, accompagnées de leur noms de corrélation et je laisse le soin à l'optimiseur de s'accommoder des prédicats de jointure, très facilement repérables dans la clause WHERE, tous bien regroupés dans un coin du saladier. Je suis confus de ne pas être un très bon exemple, mais que voulez vous, après plus de 20 ans de SQL...

[Alain Defrance]

Très intéressant.
J'ai par ailleurs remarqué que ça pose pas mal de problème dans le travail collaboratif où chaqu'un fait à sa manière si le chef de projet n'impose rien.
Les jointures sont souvent sujettes à de longues discussions concernant le rôle d'optimisation et de pertinence de la sémantique des JOIN.

Etant jeune et possédant une expérience réduite dans le développement, et particulièrement dans le SQL, je me suis imposé de suivre les normes les plus récentes a savoir l'utilisation de JOIN. Mais je comprend qu'on puisse garder de mauvaise habitudes. Par ailleurs c'est ce qui est enseigné et les JOIN sont souvent mal connu et mal appliqué des professeurs.

[oadin]

le problème vient de l'optimisation de la requète par le sgbd.

Pour ma part je travaille en sql server, je ne m'avancerai pas sur un autre sgbd, mais la clause on d'un join est largement prioritaire dans l'ordre d'exécution d'une requète sql sur la clause where.

La clause on (du join donc) est numéro 2 alors que le where reste en 3ème position (4ème je sais plus de mémoire après les join).

Donc pour faire un peu de math, si A = 25 enregistrement, B = 10 enregistrement

select * from a join b on A = b(on va faire simple)
va traiter une table de 25 -> table de 10 -> résultat.

select * from a, b where a = 10 and a=b
va traiter table 25 -> table 250 -> table de 10 -> résultat
qqch du genre

[fsmrel]

Bonjour kazou,

je comprend qu'on puisse garder de mauvaise habitudes

Le qualificatif de "mauvaise" n’est pas approprié et la formulation peut être remplacée par celle-ci : " je comprends qu'on puisse garder ses habitudes". En effet, dans ce que j’ai écrit, il s’agit bien d’exprimer une jointure sous la forme d’une restriction appliquée à un produit cartésien, ce qui mathématiquement est tout à fait respectable. Les opérations de restriction et de produit sont ici considérées comme des primitives, tandis que l’on peut désormais préférer l'alternative moderne, consistant à voir la jointure comme devenant à son tour une opération primitive, à la place du produit (considéré alors comme le cas dégénéré de la jointure).

[fsmrel]

Bonjour oadin,

Pour ma part je travaille en sql server... Donc pour faire un peu de math, si A = 25 enregistrement, B = 10 enregistrement

select * from a join b on A = b(on va faire simple)
va traiter une table de 25 -> table de 10 -> résultat.

select * from a, b where a = 10 and a=b
va traiter table 25 -> table 250 -> table de 10 -> résultat

Conceptuellement, ce que vous dites est recevable. Au plan de la réalisation, les choses ne se passent pas ainsi et c’est heureux ! SQL Server a un optimiseur et il traite les deux requêtes très exactement de la même façon.

Puisque vous mentionnez SQL Server, considérons un cas concret. Si j’exécute une 1ere jointure de la façon suivante, entre la table des 37500 communes françaises (Commune) et celle des liens représentant les communes limitrophes (Commune_Commune, 215000 liens) :

Code :

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

1
2
3
Select  Distinct a.CommuneNom
From    Commune a Join Commune_Commune b 
        ON   a.CommuneId = b.CommuneId ;

Le temps d’exécution est d’environ une seconde et le plan d’exécution est le suivant :




Maintenant, si j’effectue la jointure avec la requête suivante :

Code :

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

1
2
3
4
 Select  Distinct a.CommuneNom
From    Commune a   
      , Commune_Commune b
where   a.CommuneId = b.CommuneId ;

Alors le plan d’exécution est le même (ainsi donc que le temps d’exécution) :




Si jamais quelqu’un utilise un SGBDR qui favoriserait une des deux requêtes au détriment de l’autre, je l’engage vivement à se débarrasser de ce "SGBDR" à l'optimiseur pas très performant...

[pacmann]

[*]Maintenant, si à l’instar de Ted Codd, l’inventeur du Modèle Relationnel de Données, vous considérez la jointure comme n’étant pas une opération primitive (Cf. "Relational completeness of data base sublanguages", March 6, 1972, page 9), mais plutôt comme un RESTRICT appliqué au résultat d’un PRODUIT cartésien, alors dans le contexte de SQL,...

Tiens, c'est amusant :
Pour moi, j'aurai dit que la clause JOIN, c'est la définition de la relation.
Alors que la clause WHERE est une définition de sous-ensemble

Soient A et B deux ensembles.
On définit R relation sur A, B.
Soient (x,y) € A x B
x R y <=> (Condition JOIN)

Et à partir de R (abus de langage entre la relation et le sous-ensemble du produit qu'elle définit), on définit
R2 cette fois comme sous ensemble (et non comme une relation) par la clause WHERE...
X € R2 <=> X € R et (Condition WHERE)

Bon, mais j'imagine que Codd connaissait mieux le sujet que moi

[Alain Defrance]

Bonjour kazou,




Le qualificatif de "mauvaise" n’est pas approprié et la formulation peut être remplacée par celle-ci : " je comprends qu'on puisse garder ses habitudes". En effet, dans ce que j’ai écrit, il s’agit bien d’exprimer une jointure sous la forme d’une restriction appliquée à un produit cartésien, ce qui mathématiquement est tout à fait respectable. Les opérations de restriction et de produit sont ici considérées comme des primitives, tandis que l’on peut désormais préférer l'alternative moderne, consistant à voir la jointure comme devenant à son tour une opération primitive, à la place du produit (considéré alors comme le cas dégénéré de la jointure).

Autant pour moi, ne je voulais pas donner une qualification péjorative.
De plus je suis d'accord avec toi.

En revanche j'ai souvent entendu dire que les clauses JOIN permettent au SGBD de s'y retrouver, et de pratique de multiples optimisations lors de l'exécution de la requête. Qu'en est-il réellement ?
La réponse sera différente en fonction des SGBD, de plus certain ne supporte pas la clause JOIN (ce qui fait l'utilisation du FROM + WHERE plus sûr, mais pour les autres qu'en est-il ?

[fsmrel]

Bonsoir,

Pour moi, j'aurai dit que la clause JOIN, c'est la définition de la relation.
Alors que la clause WHERE est une définition de sous-ensemble.

Tout d’abord, pour Codd, une relation est un sous-ensemble (Cf. "A Relational Model of Data for Large Shared Data Banks”). Je traduis ce qu’il a écrit à ce sujet :

"Le terme de relation est utilisé ici dans son acception mathématique. Étant donnés les ensembles S1, S2, ..., Sn (non nécessairement distincts), R est une relation sur ces n ensembles si c’est un ensemble de n-uplets, le 1er élément de chacun d’eux tirant sa valeur de S1, le 2e de S2, et ainsi de suite (de manière plus concise, R est un sous-ensemble du produit cartésien S1 X S2 X ... X Sn). On fera référence à Sj comme étant le jième domaine de R... De manière plus concise, R est un sous-ensemble du produit cartésien S1 X S2 X ... X Sn".

Concernant la clause WHERE et pour changer un peu de référence, je cite Georges Gardarin ("Bases de données. Les systèmes et leurs langages". (Eyrolles, 1988)) :

La restriction de la relation R par une qualification Q est une relation R’ de même schéma, dont les tuples sont ceux de R satisfaisant la qualification Q.

Ainsi, quand vous dites que la clause WHERE est une définition de sous-ensemble, je suppose que cette clause représente pour vous la qualification Q au sens de Gardarin, c'est-à-dire une conjonction de qualifications (ou conditions) élémentaires : Q1 ET Q2 ET ... ET Qn.

Conceptuellement parlant, je pense ne pas trahir la pensée de Don Chamberlin (un des pères de SQL), en disant que le résultat d’un FROM est une valeur de table qui devient un opérande pour WHERE, qui pond à son tour une valeur de table qui servira pour la projection finale (SELECT col1, col2, ...). WHERE est en fait le pendant de l’opérateur RESTRICT (ou θ-RESTRICT, ou θ-SELECT, etc.) de la théorie relationnelle, laquelle adhère totalement au principe de fermeture, selon lequel le résultat d’une opération relationnelle est toujours une relation. Le résultat d’un FROM, d’un WHERE, d’un SELECT n’est pas forcément toujours une relation et c’est bien malheureux car alors la fermeture chancelle, mais ceci est une autre histoire...

[fsmrel]

j'ai souvent entendu dire que les clauses JOIN permettent au SGBD de s'y retrouver, et de pratique de multiples optimisations lors de l'exécution de la requête. Qu'en est-il réellement ?

Comme je le disais à oadin, le résultat de l’optimisation doit être strictement le même, que la jointure soit formulée à l’aide de JOIN ou non. C’est le cas avec DB2 et SQL Server. Pour les autres SGBD je ne me prononce pas, car je n’ai pas testé, mais je répète :

Si jamais quelqu’un utilise un SGBDR qui favoriserait un style de jointure au détriment de l’autre, je l’engage vivement à se débarrasser de ce "SGBDR" à l'optimiseur un peu trop fruste....

[Emmanuel Lecoester]

idem pour Oracle. Même plan d'accès entre clause join et clause where .

Il y a deux an, un client est passé de Oracle à DB2 nous sommes donc passé de requete avec des jointures ouvertes à la Oracle "(+)" vers DB2 "left outer join". Même si j'ai trouvé çà affreux en terme d'écriture au début, je trouve qu'une requete est plus facilement appréhendable avec une écrite en join : On a la selection, les jointures, les restrictions. Là ou çà compliquer c'est ceux qui ajoutent des clauses where dans leur join.

Conclusion : +1 pour les join.

[fsmrel]

je trouve qu'une requete est plus facilement appréhendable avec une écrite en join

Si l'optimiseur n'a pas d'état d'âme à ce sujet, il est vrai que concernant le développeur, je suis d'accord, c'est plus structurant, les requêtes sont moins difficiles à maintenir.

[pacmann]

Bonsoir,
Tout d’abord, pour Codd, une relation est un sous-ensemble (Cf. "A Relational Model of Data for Large Shared Data Banks”). Je traduis ce qu’il a écrit à ce sujet :

"Le terme de relation est utilisé ici dans son acception mathématique. Étant donnés les ensembles S1, S2, ..., Sn (non nécessairement distincts), R est une relation sur ces n ensembles si c’est un ensemble de n-uplets, le 1er élément de chacun d’eux tirant sa valeur de S1, le 2e de S2, et ainsi de suite (de manière plus concise, R est un sous-ensemble du produit cartésien S1 X S2 X ... X Sn). On fera référence à Sj comme étant le jième domaine de R... De manière plus concise, R est un sous-ensemble du produit cartésien S1 X S2 X ... X Sn".

Ce n'est qu'un point de vue, et je me ferai surement démolir quand un vrai matheux lira ça :

Les notions "relation" et "sous-ensemble du produit cartésien" sont clairements "en bijection", puisqu'il s'agit même d'une définition.

Pourtant, quand on dit "sous-ensemble du produit cartésient", on se concentre sur la notion ensembliste d'inclusion.
Avec la définition d'une nouvelle notion "relation", on répond à un nouveau besoin.
Et même si toutes les nouvelles notions inhérentes sont totalement traduisibles en opérations de base sur des ensembles,
le fait d'utiliser l'un ou l'autre des vocabulaires n'est pas anodine.

Ainsi, on a développé des notions sur les relations comme par exemple la composition.
Soient A, B et C des ensembles.
Soient P1 = AxB et P2 = BxC
Soient R1 une relation sur entre A et B, et R2 une relation de B et C.

On définit R3 = R1 rond R2, relation entre A et C, telle que :
pour tout (x,z) € A x C, xR3z <=> Il existe y € B tel que xR1y et yR2z

Et effectivement, ça peut aussi être écrit entièrement avec des sous-ensembles de produits cartésiens, mais le fera-t-on ?

Je dirais donc qu'on parle de "sous-ensemble de produit cartésien" lorsqu'on est plus intéressé la vision ensembliste d'inclusion,
que par le lien logique entre les éléments des ensembles composant le produit cartésien...
Si par exemple, tu ressens la nécessité de citer des opérateurs définis particulièrement sur les relations,
il ne faut pas les retraduire en termes de base...

Dira-t-on que la fonction f(x) = 2x est :
"le sous-ensemble P du produit cartésien de R x R définit par
(x, y) € P <=> x = 2y " ?
(car une fonction est une relation, qui elle même est un sous-ensemble du produit cartésien...)


Alors dans le cas présent, que représente une jointure ?
La jointure est-elle plus un sous-ensemble quelconque du grand produit cartésien des deux ensembles,
ou correspond elle plus à un lien logique défini entre les deux ensembles de base (et qui certes résulte en un sous-ensemble du produit cartésient...)

Alors que pour le reste de la condition where, n'a ton pas le sentiment qu'il s'agit de tronquer un premier ensemble de résultats ?

En fait, j'identifie exactement la différence entre "sous-ensemble du produit cartésien" et "relation" à celle entre "JOIN" et "WHERE"

[oadin]

Conceptuellement, ce que vous dites est recevable. Au plan de la réalisation, les choses ne se passent pas ainsi et c’est heureux ! SQL Server a un optimiseur et il traite les deux requêtes très exactement de la même façon.

Sur une requète aussi simpliste heureusement oui sql server a le même plan de travail. Mais je ne suis pas totalement sur que ce soit le même cas lorsque nous avons des requètes qui se compliquent légèrement et qui finissent par dépasser les 150 lignes.

Avec des clauses select imbriquée de ce style-ci

Code :

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

select * from (select champs1 from (select ch1 from table1) as t) as ta

J'ai déjà vu au travail des requètes avec des select imbriqués dans les from que sql server 2000 ne savait pas traiter pour cause de trop d'imbrication (je n'ai plus le terme exact d'erreur qu'il renvoyait)

Dans des cas ou la requète va fournir des milliers de plan d'exécution, autant également aider l'optimiseur.
Même si l'optimiseur peut faire une partie du travail a notre place, il reste un cout en calcul et compilation de la requête.


Maintenant pour des requètes simples, effectivement c'est principalement un outil de lecture que d'utiliser les join plutot que de les inclure dans des clauses where

[fsmrel]

J'ai déjà vu au travail des requètes avec des select imbriqués dans les from que sql server 2000 ne savait pas traiter pour cause de trop d'imbrication (je n'ai plus le terme exact d'erreur qu'il renvoyait)

Dans des cas ou la requète va fournir des milliers de plan d'exécution, autant également aider l'optimiseur.
Même si l'optimiseur peut faire une partie du travail a notre place, il reste un cout en calcul et compilation de la requête.

L’avantage d’un SGBDR, qu’il s’agisse de SQL Server ou autre, c’est qu’au fil des versions, son optimiseur (entre autres) s’améliore, de façon transparente pour les applications (indépendance logique respectée). Ainsi, dans les années 80, j’ai vu des requêtes faire tousser DB2, tandis qu’aujourd’hui il arrive à m’épater quant à ses stratégies. Certes, il y a toujours quelques cas où le SGBD est pris en défaut, et il y en aura sans doute toujours, mais ça reste un champion de la programmation qui me bat à plates coutures.
Quant au coût en calcul et compilation, ça devient de plus en plus peanut, surtout si l’on précompile, cas normal dans le contexte de la production informatique.

[fsmrel]

Bonsoir,

Ce n'est qu'un point de vue, et je me ferai surement démolir quand un vrai matheux lira ça

N’étant aucunement mathématicien, je resterai sur une prudente réserve, tout en étant d’accord avec le distinguo relation vs sous-ensemble. Je pense que nous sommes tous marqués par l’utilisation systématique du concept de table, cette dernière n’étant qu’une image à deux dimensions d’une réalité bien différente.

En échange, je vous invite à méditer quelques réflexions de Ronald Fagin (Ph.D. in Mathematics, University of California at Berkeley. Thesis: Contributions to the Model Theory of Finite Structures), connu pour avoir découvert et théorisé les 4e et 5e formes normales, et dont j'extrais quelques lignes de l'hommage qu'il rendit à Codd (mort en 2003) :

... Ted did everything necessary to make the relational model succeed. First, he laid such a solid mathematical foundation for it that theorists like me could have a field day deriving results about it, practitioners could obtain clean and efficient implementations of it, and users could understand it intuitively and use it effectively...

Que dire d’autre ?

Il ne faut pas oublier qu’à l’époque à laquelle Ted Codd a inventé le modèle relationnel, les systèmes de bases de données fonctionnaient comme des systèmes de gestion de fichiers certes très sophistiqués, mais nous ne manipulions que des enregistrements, les uns après les autres, laborieusement. Il n’y avait aucun modèle théorique, pas d’algèbre, rien (et je sais de quoi je parle, j’ai chahuté bien des SGBD pré-relationnels pendant une quinzaine d’années, j’en ai même réécrit un à la demande d’un de mes clients, il y a plus de 30 ans...ouille !) Il a fallu que ce soit Codd lui-même qui théorise le modèle réseau de Bachman, pour en démontrer au passage les faiblesses inhérentes et rédhibitoires.

Les notions "relation" et "sous-ensemble du produit cartésien" sont clairements "en bijection", puisqu'il s'agit même d'une définition.

Pourtant, quand on dit "sous-ensemble du produit cartésient", on se concentre sur la notion ensembliste d'inclusion.
Avec la définition d'une nouvelle notion "relation", on répond à un nouveau besoin.
Et même si toutes les nouvelles notions inhérentes sont totalement traduisibles en opérations de base sur des ensembles,
le fait d'utiliser l'un ou l'autre des vocabulaires n'est pas anodine.

Je peux me tromper, mais je ne pense pas que Jeffrey Ullman ait été plus troublé que Fagin par cette dualité, pas plus que les professeurs Delobel, Adiba, Gardarin, Miranda, Bouzeghoub et cie (pour citer des Français). Cela dit, dans son ouvrage "The Relational Model for Database Management: Version 2" (Reading, Mass.: Addison-Wesley, 1990), écrit 20 ans après son article fondateur, Ted Codd écrit à la 2e page :

A relation in the relational model is very similar to its counterpart in mathematics.

Et de la même façon, les opérateurs relationnels ne sont pas exactement ceux qu’on utilise en mathématiques. Ainsi, concernant le produit cartésien U = S X T, je cite Codd :

In textbooks on mathematics the usual explanation is that U is the set of all tuples of the form

< < a1,a2, ..., am >, < b1, b2, ..., bn > >,

where < a1,a2, ..., am > is a tuple of S and < b1, b2, ..., bn > is a tuple of T... For purposes of database management, it is more useful to adopt a slightly different definition, and to say that U is the set of all tuples of the form

< a1,a2, ..., am, b1, b2, ..., bn >.

Etc. Comme en plus, l’ordre des éléments n’intervient plus du fait de l’utilisation d’attributs nommés, le produit cartésien relationnel est commutatif et associatif (ce qui est intéressant pour un optimiseur).
Vous remarquerez que l’opérateur relationnel UNION est lui aussi différent de l’UNION au sens traditionnel, il en est une extension du fait de sa contrainte d’union-compatibilité.

En fait, j'identifie exactement la différence entre "sous-ensemble du produit cartésien" et "relation" à celle entre "JOIN" et "WHERE"

Pourquoi pas ? Mais autant "sous-ensemble du produit cartésien", "relation", "JOIN" sont rigoureusement définis, il est difficile d'en dire autant, mathématiquement parlant, de la clause "WHERE" de SQL. C’est un mot-clé du langage, bien défini au plan de la syntaxe par la norme SQL, mais que l’on peut finalement interpréter plus ou moins chacun à sa façon. Au fond, avec SQL qui s’est voulu non procédural (par opposition aux systèmes pré-relationnels), on propose de manière déclarative sa requête à l’aide du célèbre triplet SELECT/FROM/WHERE, au système de se débrouiller.

Cela dit, WHERE est aussi un autre nom pour l’opérateur de restriction du modèle relationnel. Je cite Chris Date, le complice de Ted Codd :

Soit a une relation d’attributs X, Y, ..., Z et soit p une fonction vérifonctionnelle dont les paramètres sont, précisément, un certain sous-ensemble de X, Y, ..., Z. Alors la restriction de a selon p

a WHERE p

est une relation dont l’en-tête est identique à celui de a et dont le corps est constitué de tous les tuples de a tels que p est évaluée à VRAI pour les tuples considérés.

Ainsi, on a développé des notions sur les relations comme par exemple la composition.

En 1969, Codd avait défini un opérateur de composition :

Given relations A(Y,Y) and B(Y,Z), the composition of A with B is the projection on X et Z of a join of A with B...

Mais en 1972, cet opérateur a disparu.

Je crois qu’on pourrait discuter encore bien longtemps de tout cela...

Un dernier mot concernant l’algèbre relationnelle. Selon Chris Date, Codd préférait le calcul relationnel à l’algèbre relationnelle. QUEL, le langage du SGBDR Ingres (ancêtre de Postgres) est bâti sur ce calcul. Malheureusement, on peut considérer que SQL a eu sa peau...

Amicalement et relationnellement,

fsmrel

[GrandFather]

Bonjour,

Si jamais quelqu’un utilise un SGBDR qui favoriserait une des deux requêtes au détriment de l’autre, je l’engage vivement à se débarrasser de ce "SGBDR" à l'optimiseur pas très performant...

Argh... Me demander de me débarasser de PostgreSQL relève de la cruauté.

Voici l'extrait de la documentation de Postgres traitant de l'optimisation et des clauses JOIN explicites :

Il est possible de contrôler le planificateur de requêtes à un certain point en utilisant une syntaxe JOIN explicite. Pour voir en quoi ceci est important, nous avons besoin de quelques connaissances.
Dans une simple requête de jointure, telle que :
SELECT * FROM a, b, c WHERE a.id = b.id AND b.ref = c.id;
le planificateur est libre de joindre les tables données dans n'importe quel ordre. Par exemple, il pourrait générer un plan de requête qui joint A à B en utilisant la condition WHERE a.id = b.id, puis joint C à cette nouvelle table jointe en utilisant l'autre condition WHERE. Ou il pourrait joindre B à C, puis A au résultat de cette jointure précédente. Ou il pourrait joindre A à C puis les joindre avec B mais cela pourrait ne pas être efficace car le produit cartésien complet de A et C devra être formé alors qu'il n'y a pas de condition applicable dans la clause WHERE pour permettre une optimisation de la jointure (toutes les jointures dans l'exécuteur PostgreSQL™ arrivent entre deux tables en entrées donc il est nécessaire de construire le résultat de l'une ou de l'autre de ces façons). Le point important est que ces différentes possibilités de jointures donnent des résultats sémantiquement équivalents mais pourraient avoir des coûts d'exécution grandement différents. Du coup, le planificateur va toutes les explorer pour trouver le plan de requête le plus efficace.
Quand une requête implique seulement deux ou trois tables, il y a peu d'ordres de jointures à préparer. Mais le nombre d'ordres de jointures possibles grandit de façon exponentielle au fur et à mesure que le nombre de tables augmente. Au-delà de dix tables en entrée, il n'est plus possible de faire une recherche exhaustive de toutes les possibilités et même la planification de six ou sept tables pourrait prendre beaucoup de temps. Quand il y a trop de tables en entrée, le planificateur PostgreSQL™ basculera d'une recherche exhaustive à une recherche génétique probabiliste via un nombre limité de possibilités (la limite de bascule est initialisée par le paramètre en exécution geqo_threshold). La recherche génétique prend moins de temps mais elle ne trouvera pas nécessairement le meilleur plan possible.[...]

Pour des requêtes n'impliquant que peu de tables, comme dans votre exemple, le planificateur est à même de trouver l'ordre de jointure optimal ; pour des requêtes plus complexes, il sera nécessaire "d'aider" le planificateur en lui spécifiant l'ordre des jointures à l'aide de JOIN. La question que je me pose est : est-ce une "limitation" inhérente à Postgres, où retrouve-t-on le même comportement sous Oracle et SQL Server ?

[vmolines]

Je peux dire que sous MySQL on peut aussi influencer le plan d'execution en spécifiant des ordres de jointures ou des index spécifiques à utiliser pour ceux là.

[fsmrel]

Je peux dire que sous MySQL on peut aussi influencer le plan d'execution en spécifiant des ordres de jointures ou des index spécifiques à utiliser pour ceux là.

Ceci ne doit être fait qu’en dernier ressort, quand on a la preuve que le SGBD se vautre dans la détermination de sa stratégie. Par exemple, je me souviens d’une séance de prototypage des performances, au cours de laquelle j’avais tempêté contre DB2 parce qu’il n’utilisait pas ce que je considérais être la seule et bonne stratégie : après quelques tentatives vaines de contournement de ma part, je me suis rendu compte à la réflexion que mon MLD était à revoir (en fait mon MCD)...

[fsmrel]

Argh... Me demander de me débarrasser de PostgreSQL relève de la cruauté

Le motif que j’ai invoqué est peut-être finalement un peu trop brutal, et puis si vous aimez, ne comptez pas...

Pour des requêtes n'impliquant que peu de tables, comme dans votre exemple, le planificateur est à même de trouver l'ordre de jointure optimal ; pour des requêtes plus complexes, il sera nécessaire "d'aider" le planificateur en lui spécifiant l'ordre des jointures à l'aide de JOIN. La question que je me pose est : est-ce une "limitation" inhérente à Postgres, où retrouve-t-on le même comportement sous Oracle et SQL Server ?

Dans ce qui suit, je parlerai d’optimiseur plutôt que de planificateur, car c’est le terme utilisé depuis les origines, dans la littérature traitant des bases de données relationnelles.

Concernant Oracle, je zappe car, si par exemple j’ai été favorablement impressionné par sa performance dans le cas de recherches récursives (nomenclatures), je ne l’ai pas secoué dans le contexte d’une dizaine de tables en jointure.

Concernant DB2 que je connais beaucoup mieux : j’ai observé la façon dont son optimiseur réagit. Au début des années 80, je me souviens que DB2 avait des heuristiques pas toujours fameuses au vu de ce qu’il racontait au résultat de l’exécution d’une instruction EXPLAIN PLAN. Et puis, au fil des ans, les statistiques qu’il tient au sein du catalogue relationnel se sont terriblement enrichies et ses choix en matière d’optimisation sont devenus de plus en plus pertinents. Il est certain que plus les facteurs de filtrage sont juteux, plus la tâche du SGBD est simplifiée dans ses choix heuristiques. Certes, il reste des cas de figure tordus où on le piège si l’on est mal intentionné, mais sur la base de 1000 requêtes, je dirais qu’il faudrait que je donne un sérieux coup de main au SGBD pour peut-être 20 d’entre elles. C’est subjectif, car chacun a son style de programmation et surtout une architecture de bases de données qui ressemble rarement à celle du voisin. Et puis, il y a toujours des gens qui n’ont pas compris l’importance du maintien des données statistiques du catalogue relationnel, et donc toujours prêts à fustiger le SGBD quant à ses performances, alors qu'ils ne doivent s’en prendre qu’à eux-mêmes.

En gros je dirais :

Les heuristiques de DB2 se sont très sensiblement affinées depuis 30 ans (c'est-à-dire depuis l’utilisation en vraie grandeur de l’ancêtre, SYSTEM R).

La mise à niveau du catalogue relationnel est déterminante (facteur de filtrage, volumétrie des tables et index, top n des valeurs les plus fréquentes, bref, toutes ces choses qui aident bien le SGBD dans ses choix quand le nombre de jointures est élevé).

Une mise en œuvre pertinente et raisonnée des index facilite aussi le travail de l’optimiseur. La clusterisation au sens de DB2 (et de SQL Server) facilite aussi grandement le travail du SGBD dans ses choix.

Quand pour une requête donnée, DB2 est en présence d’une diarrhée de jointures et qu’il se rend compte que certaines tables impliquées ne sont que des nœuds intermédiaires pour aller de A à Z, s’il le peut il les shunte c'est-à-dire tant que la clé primaire de A est propagée. Ceci est fort utile pour la performance des grosses applications batch et simplifie au passage la tâche de l’optimiseur qui n’a plus qu’à se concentrer sur un nombre plus réduit de tables pour déterminer sa stratégie. (J’ai constaté que SQL Server 2005 ne savait pas en faire autant).

DB2 pratique la fermeture transitive, c'est-à-dire que pour une requête du genre :

Code :

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

1
2
3
4
Select   B.coly 
from     A JOIN B
          ON A.colx = B.colx
where    A.colx = 'xxx'

DB2 enrichit la requête :

Code :

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

1
2
3
4
5
Select   B.coly 
from     A JOIN B
          ON A.colx = B.colx
where    A.colx = 'xxx'
and      B.colx = 'xxx'

ce qui est intéressant quand la table B possède un index connecté sur colx et que la table A n’en dispose pas. A noter que SQL Server procède de façon analogue.

Quand il y a une diarrhée de tables dans une jointure, certaines d’entre elles sont terminales, ce sont des petites tables où l’on va simplement chercher des libellés associés à des codes : DB2 cherchera à terminer ses jointures par ce genre de tables qui restent en mémoire et dont le coût d’accès est négligeable.

Concernant les jointures naturelles, DB2 n’ignore pas qu’elles sont associatives et commutatives. Je ne sais pas si cela peut l’aider, il faudrait poser la question à IBM.

J’oublie plein de choses, mais je conclurai en disant que ce n’est qu’en dernier ressort qu’il faut forcer la main au SGBD dans le choix de sa stratégie.

[fsmrel]

quand on dit "sous-ensemble du produit cartésien", on se concentre sur la notion ensembliste d'inclusion

Juste en passant et si vous avez une minute. Soit R1 et R2, deux variables relationnelles (au sens du Modèle Relationnel de Données, informellement tables). Considérons leur produit cartésien :

R1 X R2

Si j’écris :

R1 X R2 = R1,

à quoi ressemble R2 ? (intension et extension, degré, cardinal).