Il existe des problèmes courants en SQL : trouver le log le plus
récent pour chaque programme, l'article le plus populaire par
catégorie, le meilleur score pour chaque joueur ... nous allons
tenter de faire le tour de ces questions ainsi que de la possibilté
d'extraire les N premiers resultats ...
Afin d'illuster mes propos, je vais utiliser un exemple avec une
table "fruits" contenant quelques enregistrements :
+--------+------------+-------+
| type | variete | prix |
+--------+------------+-------+
| pomme | gala | 2.79 |
| pomme | fuji | 0.24 |
| pomme | Borowitsky | 2.87 |
| orange | valencia | 3.59 |
| orange | navel | 9.36 |
| poire | bradford | 6.05 |
| poire | bartlett | 2.14 |
| cerise | bing | 2.55 |
| cerise | chelan | 6.33 |
+--------+------------+-------+
Sélectionner une entrée extreme dans chaque groupe
Il est courant de vouloir selectionner dans une table le log le
plus récent pour chaque programme, ou quelque chose dans le style.
Si l'on essaie d'appliquer ce type de problème à notre table de
fruits, nous pourrions par exemple vouloir trouver, pour chaque
type la variété la moins chère.
Voici ce que nous souhaitons obtenir :
+--------+----------+-------+
| type | variete | prix |
+--------+----------+-------+
| pomme | fuji | 0.24 |
| orange | valencia | 3.59 |
| poire | bartlett | 2.14 |
| cerise | bing | 2.55 |
+--------+----------+-------+
Il existe quelques solutions à ce problème. Toutes fonctionnent en
2 temps : trouver le prix desiré, puis selectionner le reste des
données en ce basant sur ce résultat.
Une solution courante est appellé "auto-jointure". L'étape 1 est de
grouper les fruits par type, et d'en choisir le prix minimum
:
SELECT type, MIN(prix ) AS minprix
FROM fruits
GROUP BY type;
+--------+----------+
| type | minprix |
+--------+----------+
| pomme | 0.24 |
| cerise | 2.55 |
| orange | 3.59 |
| poire | 2.14 |
+--------+----------+
L'étape 2 est de selectionner le reste des lignes en faisant une
auto-jointure sur la table fruits. Comme notre premiere requete est
groupé il est nécessaire de l'intégrer dans une sous-requete afin
de faire notre jointure sur la table de base non-groupée :
SELECT f.type, f.variete, f.prix
FROM (
SELECT type, MIN(prix ) AS minprix
FROM fruits GROUP BY type
) as x INNER JOIN fruits AS f ON f.type = x.type AND f.prix = x.minprix ;
+--------+----------+-------+
| type | variete | prix |
+--------+----------+-------+
| pomme | fuji | 0.24 |
| cerise | bing | 2.55 |
| orange | valencia | 3.59 |
| poire | bartlett | 2.14 |
+--------+----------+-------+
Une autre solution, plus lisible mais potentiellement plus lente
est d'utiliser une requete imbriquée :
SELECT type, variete, prix
FROM fruits
WHERE prix = (SELECT MIN(prix ) FROM fruits AS f WHERE f.type = fruits.type);
+--------+----------+-------+
| type | variete | prix |
+--------+----------+-------+
| pomme | fuji | 0.24 |
| orange | valencia | 3.59 |
| poire | bartlett | 2.14 |
| cerise | bing | 2.55 |
+--------+----------+-------+
Selectionner les N entrées extremes de chaque groupe
Ce probléme est plus compliqué que le premier à résoudre. Sortir un
seul enregistrement est relativement simple grace aux fonctions
MIN(), MAX() ... mais il est impossible de les utiliser dans notre
cas dans le sens ou ces fonctions ne peuvent renvoyer qu'une seule
valeur.
Disons que nous souhaitons trouver les 2 variétés les moins chès de
chaque type :
SELECT type, variete, prix
FROM fruits
WHERE (
SELECT COUNT(*) FROM fruits AS f
WHERE f.type = fruits.type AND f.prix < fruits.prix
) <= 2;
+--------+----------+-------+
| type | variete | prix |
+--------+----------+-------+
| pomme | gala | 2.79 |
| pomme | fuji | 0.24 |
| orange | valencia | 3.59 |
| orange | navel | 9.36 |
| poire | bradford | 6.05 |
| poire | bartlett | 2.14 |
| cerise | bing | 2.55 |
| cerise | chelan | 6.33 |
+--------+----------+-------+
Cette requete peut être expliquée comme cela : "Selectionner la
variété de chaque type ou la variété n'est pas plus chère que la
2ème moins chème de chaque type" (ouf !).
Cette manière de faire est relativement propre dans le sens ou il
est possible de faire varier le nombre d'entrées a selectionner
facilement. En revanche au niveau performances, ce n'est pas
vraiment le top, l'utilisation d'algo quadratique devient assez
lourd lorsque le nombre d'enregistrements devient important,
surtout si les index ne sont pas ou mal définis.Existe-t-il une ou
plusieurs solutions plus optimisées ?
L'UNION fait la force
Si votre table dispose d'un index (type,prix ) et qu'il y a
beaucoup plus d'enregistrements à eliminer qu'à recuperer pour
chaque groupe, une methode plus efficace (surtout sur MySQL) est de
splitter les differentes requetes, de poser une limite sur chacunes
d'entres elles puis d'utiliser UNION pour les remettre ensemble.
Voici un exemple :
(SELECT * FROM fruits WHERE type = 'pomme' ORDER BY prix LIMIT 2)
UNION ALL
(SELECT * FROM fruits WHERE type = 'orange' ORDER BY prix LIMIT 2)
UNION ALL
(SELECT * FROM fruits WHERE type = 'poire' ORDER BY prix LIMIT 2)
UNION ALL
(SELECT * FROM fruits WHERE type = 'cerise' ORDER BY prix LIMIT 2)
Paul Zaitev a fait une description approfondie de cette
technique, je vous conseille de le lire si vous voulez en
savoir plus sur cette dernière.
Petite solution spécifique à MySQL utilisant des variables
Une autre solution, spécifique à MySQL, dans le cas ou vous
souhaitez récuperer un plus grand nombre d'enregistrements, est de
passer par des variables :
set @num := 0, @type := '';
SELECT type, variete, prix
FROM (
SELECT type, variete, prix ,
@num := if(@type = type, @num + 1, 1) AS row_number,
@type := type AS dummy
FROM fruits
ORDER BY type, prix
) AS x WHERE x.row_number <= 2;
Cette requete s'effectue au final en 2 passes, la sous-requetes
construisant implicitement une table remplie avec les données sur
lesquelles on applique tour à tour la clause WHERE.
Conclusion
Nous avons fait un tour rapide de quelques solutions au problème
qui est de pouvoir recuperer "les valeurs extremes de chaque
groupe" et également de pouvoir selectionner les N extremes
resultats de chaque groupe.
La plupart des techniques sont applicables sur divers SGBD, meme si
la derniere solution est MySQL-Specifique. Cet article est inspiré
de techniques décrites par B. Schwartz avec son autorisation
expresse.
