Les jointures triangulaires

Publié le par

Nous avons tous entendu qu’écrire du code ensembliste pour gérer des données dans une base de données est la meilleure façon d’obtenir des performances correctes.

Il est vrai qu’il est difficile pour un développeur ayant une expérience du développement d’applications, en quelque langage de programmation que ce soit, de passer du code procédural, qui, en outre, traite des jeux de données extraits de bases de données « ligne par ligne », à un langage conçu pour manipuler des ensembles de données.

Nous n’aborderons pas ici l’utilisation, à proscrire, des curseurs et des boucles utilisant la commande WHILE, mais nous allons voir que, si l’on croit avoir écrit du code ensembliste, il s’agit en fait de code procédural, et qu’il peut s’avérer être contre-performant.

	-----------------------------------------
	1. Que sont les jointures triangulaires ?
	-----------------------------------------

Vous avez peut-être déjà aperçu du code dont le squelette ressemble à celui-ci :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
---------------------------------
-- Nicolas SOUQUET - 08/11/2008 -
---------------------------------
SELECT P.IDProduit,
        P.Commande,
        (
    SELECT SUM(Q.Commande)
    FROM dbo.Produits Q
    WHERE Q.IDProduit <= P.IDProduit
    ) AS Total,
        (
    SELECT COUNT(Q.Commande)
    FROM dbo.Produits Q
    WHERE Q.IDProduit <= P.IDProduit
    ) AS Nombre
 FROM dbo.Produits P

Cette requête manipule des ensembles tout en effectuant des calculs d’agrégats, quoi de plus anodin pour un traitement en base de données ?

Et pourtant cette requête est peut-être pire en termes de performance qu’un traitement avec un curseur ou avec une boucle utilisant la commande WHILE : elle spécifie ce que l’on appelle une jointure triangulaire, c’est-à-dire que les sous-requêtes qui la constituent spécifient des références en dehors d’elles-mêmes : dans l’exemple précédent, les calculs agrégés SUM et COUNT sont effectués sur l’alias Q de la table dbo.Produits, référençant la même table, mais d’alias P, en dehors de ces calculs, par une jointure.
Que se passe-t-il lors de l’exécution ? Les calculs agrégés sont effectués pour chaque ligne de P.
Attention, cette contre-performance ne provient :

– ni du calcul d’agrégats,
– ni de l’inégalité spécifiant la jointure,
– ni de l’auto-jointure.

La requête suivante :

1
2
3
4
5
6
7
8
9
10
---------------------------------
-- Nicolas SOUQUET - 08/11/2008 -
---------------------------------
SELECT A.NomAbonne + ' ' + A.PrenomAbonne,
  (
    SELECT S.NomSport
    FROM dbo.TbSport S
    WHERE A.IDSport = S.IDSport
  )
FROM dbo.TbAbonne A

produit tout à fait le même effet : à chaque ligne d’abonné lue, vous allez rechercher tous les sports pratiqués par celui-ci …

	------------------------------
	2. Un Å“il sur les performances
	------------------------------

Regardons rapidement ce que cela donne avec un jeu de données dont la cardinalité est très petite :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
---------------------------------
-- Nicolas SOUQUET - 08/11/2008 -
---------------------------------
CREATE TABLE TbSport
(
  IDSport INT IDENTITY CONSTRAINT PK_TbSport PRIMARY KEY,
  NomSport VARCHAR(16) NOT NULL CONSTRAINT UQ_TbSport_NomSport UNIQUE
)
GO
 
CREATE TABLE TbAbonne
(
  IDAbonne INT IDENTITY CONSTRAINT PK_TbAbonne PRIMARY KEY,
  NomAbonne VARCHAR(32) NOT NULL,
  PrenomAbonne VARCHAR(32) NOT NULL,
  IDSport INT NOT NULL CONSTRAINT FK_TbAbonne_IDSport FOREIGN KEY (IDSport) REFERENCES dbo.TbSport
)
GO
 
INSERT INTO dbo.TbSport VALUES ('Tennis')
INSERT INTO dbo.TbSport VALUES ('Squash')
INSERT INTO dbo.TbSport VALUES ('Tennis de table')
INSERT INTO dbo.TbSport VALUES ('Paddle')
INSERT INTO dbo.TbSport VALUES ('Pelote basque')
GO
 
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne1', 'PrenomAbonne1', 1)
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne2', 'PrenomAbonne2', 1)
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne3', 'PrenomAbonne3', 1)
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne4', 'PrenomAbonne4', 2)
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne5', 'PrenomAbonne5', 2)
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne6', 'PrenomAbonne6', 2)
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne7', 'PrenomAbonne7', 2)
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne8', 'PrenomAbonne8', 2)
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne9', 'PrenomAbonne9', 2)
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne10', 'PrenomAbonne10', 3)
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne11', 'PrenomAbonne11', 3)
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne12', 'PrenomAbonne12', 3)
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne13', 'PrenomAbonne13', 3)
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne14', 'PrenomAbonne14', 3)
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne15', 'PrenomAbonne15', 4)
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne16', 'PrenomAbonne16', 4)
INSERT INTO dbo.TbAbonne VALUES ('NomAbonne17', 'PrenomAbonne17', 5)
GO
 
-- Affiche le nombre de millisecondes requises pour analyser, compiler et exécuter chaque
-- instruction du lot
SET STATISTICS TIME ON
GO
 
PRINT '========> Jointure triangulaire'
SELECT A.NomAbonne + ' ' + A.PrenomAbonne,
    (
      SELECT S.NomSport
      FROM dbo.TbSport S
      WHERE A.IDSport = S.IDSport
    )
FROM dbo.TbAbonne A
GO
 
PRINT '========> Equi-jointure'
SELECT A.NomAbonne + ' ' + A.PrenomAbonne,
    S.NomSport
FROM dbo.TbAbonne A

JOIN dbo.TbSport S ON A.IDSport = S.IDSport

Sur un Pentium Dual Core à 2,13 GHz avec 2Go de RAM, cela donne 16ms de temps total écoulé pour la 1e requête, contre 2ms pour la seconde, avec seulement 17 lignes affectées !

	------------------------------
	3. Pourquoi est-ce plus lent ?
	------------------------------

Pour rechercher le nombre de lignes lues par ce type de requête, soient la table et la requête suivantes :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
---------------------------------
-- Nicolas SOUQUET - 08/11/2008 -
---------------------------------
SELECT 1 Nombre
INTO NombresDeUnACinq
UNION SELECT 2
UNION SELECT 3
UNION SELECT 4
UNION SELECT 5
GO
 
SELECT A.Nombre,
  (
    SELECT COUNT(*)  
    FROM NombresDeUnACinq ASUB  
    WHERE ASUB.Nombre [TypeDeDemiJointure] A.Nombre
  ) Occurences
FROM dbo.NombresDeUnACinq A
ORDER BY Occurrences
GO

Si [TypeDeDemiJointure] est :

Рune ̩qui-jointure, alors nous avons lu 5 x 5 = 25 lignes.
Рune in̩galit̩ stricte , alors nous avons lu 5(4 + 3 + 2 + 1) = 50 lignes.
Рune in̩galit̩, alors nous avons lu 5(5 + 4 + 3 + 2 + 1) = 75 lignes.
Рune diff̩rence, alors nous avons lu 5(2(4 + 3 + 2 + 1)) = 100 lignes.

On peut donc lire entre 5 et 20 fois plus de lignes qu’il n’en faut. Imaginez ce que cela donne avec un jeu de données dont la cardinalité est bien plus importante …

Voici donc l’origine de la dénomination de ce type de jointures : (les carrés noirs vérifient la clause)

	-------------
	4. Conclusion
	-------------

Comme nous l’avons vu, les jointures triangulaires s’avèrent être très mauvaises en termes de performances. Pour écrire du code ensembliste, il ne suffit donc pas de ne pas spécifier de curseur ou une boucle WHILE pour ne pas exécuter une requête sur le mode procédural : en effet cela revient au même que d’appeler une fonction SQL et de lui passer le paramètre servant de critère de recherche pour lui déléguer un traitement …

ElSuket

Laisser un commentaire