Calcul de la médiane en MySQL

Comme vous avez pu le lire dans mon article précédent où je donne la méthode de calcul de la médiane en SQL cette formule fonctionne correctement mais peut prendre un temps extrêmement longs lorsque le nombre de lignes à étudier augmente.
Ainsi dans cette article j'obtenais le résultat au bout de 5 secondes pour une table qui contenait 4874 lignes. J'ai eu à faire le test pour une table contenant plus de 600 000 lignes et là, après 2 heures de calculs, je n'ai plus eu la patience d'attendre le résultat.
J'ai donc cherché sur le net et trouvé un projet qui fourni une fonction median en UDF. Cependant, elle ne fonctionne pas pour les versions de MySQL > 4.1.0. Je me suis donc intéressé au code et après quelques minutes j'ai pu le faire tourner sur ma version 5.0.32 !
Miracle! En utilisant cette fonction ma requête prend moins d'1 seconde !
Finalement, j'ai bien fait de me pencher vers l'utilisation d'une UDF (user-defined function)

Pour ceux qui désirent utiliser cette méthode, il suffit de suivre la procédure suivante :

cd /tmp
wget http://sites.google.com/site/filesrepository01/Home/udf_median.cc -O udf_median.cc
apt-get install libmysqlclient15-dev
gcc -Wall -I /usr/include/mysql -c udf_median.cc -o udf_median.o
ld -shared -o udf_median.so udf_median.o
cp udf_median.so /usr/lib
rm -f udf_median.*

Il ne vous reste plus qu'à vous connecter à votre serveur MySQL et à créer la fonction median :

mysql test
Reading table information for completion of table and column names
You can turn off this feature to get a quicker startup with -A

Welcome to the MySQL monitor. Commands end with ; or \g.
Your MySQL connection id is 5
Server version: 5.0.32-Debian_7etch8 Debian etch distribution

Type 'help;' or '\h' for help. Type '\c' to clear the buffer.

mysql> DROP FUNCTION median;
Query OK, 0 rows affected (0.00 sec)

mysql> CREATE AGGREGATE FUNCTION median RETURNS REAL SONAME 'udf_median.so';Query OK, 0 rows affected (0.00 sec)

mysql> SELECT semaine,MEDIAN(duree) FROM t1 GROUP BY semaine;
+---------+---------------+
| semaine | MEDIAN(duree) |
+---------+---------------+
| 1 | 11.50 |
| 2 | 22.00 |
| 3 | 13.00 |
+---------+---------------+
3 rows in set (0.84 sec)

C'est donc plus rapide que nos 5 secondes de mon dernier article et sur une table qui est 125 fois plus volumineuse. Autres chiffres, sur une table de 10000 enregistrements composée de 4 colonnes (int, varchar(255),int,varchar(20)), la 1ère méthode (pur SQL) obtient le résultat en 2 min 55.24 sec, tandis que cette méthode prend 10ms.

Blogged with the Flock Browser

Calcul de la médiane en SQL

Depuis Oracle 10g il est possible d'effectuer le calcul de la médiane très facilement en utilisant la nouvelle fonction MEDIAN disponible.
Je suppose que vous disposez d'une table data constituée de 2 colonnes semaine et duree. Pour calculer la médiane sous Oracle vous n'avez plus qu'à utiliser la requête suivante :

SELECT semaine,MEDIAN(duree) FROM data GROUP BY semaine;

Pour MySQL c'est beaucoup plus compliqué puisqu'on ne dispose pas de cette magnifique fonction. J'ai donc fait quelques recherches et je suis tombé sur les travaux de frédéric Brouard. J'ai pu trouver la procédure adéquate basée sur la solution de Chris Date.

En supposant que vous disposez toujours de la table data qui chez moi utilise le moteur CSV, la méthode est la suivante :

CREATE TABLE d AS SELECT * FROM data;
ALTER TABLE d ADD COLUMN id INT AUTO_INCREMENT PRIMARY KEY FIRST, ADD INDEX (semaine,duree) ;

SELECT semaine,round(AVG(duree),2) AS MEDIANE
FROM (
   SELECT semaine,MIN(duree) AS duree
   -- valeurs au dessus
   FROM
   (
       SELECT ST1.semaine,ST1.id, ST1.duree
       FROM    d AS ST1
       INNER JOIN d AS ST2
       ON ST1.duree <= ST2.duree AND ST1.semaine=ST2.semaine
       GROUP BY ST1.id, ST1.duree
       HAVING COUNT(*) <= (SELECT CEILING(COUNT(*) / 2.0)
       FROM d d2 where d2.semaine=ST1.semaine)
   ) SUR
   GROUP BY semaine
   UNION
   SELECT semaine,MAX(duree) AS duree
   -- valeurs en dessous
   FROM
   (
       SELECT ST1.semaine, ST1.duree
       FROM    d AS ST1
       INNER JOIN d AS ST2
       ON ST1.duree >= ST2.duree AND ST1.semaine=ST2.semaine
       GROUP BY ST1.id, ST1.duree
       HAVING COUNT(*) <= (SELECT CEILING(COUNT(*) / 2.0)
       FROM d d2 where d2.semaine=ST1.semaine)
   ) SOU
   GROUP BY semaine
   ) T
GROUP BY semaine;

DROP TABLE d;

Sous Oracle, la requête est très rapide et il n'est pas nécessaire de créer un index particulier. Par contre sous MySQL, si vous vous amusez à supprimer l'index vous le ressentirez très vite si vous disposez de beaucoup de données. Dans mon cas, ma table contient 4874 lignes. Sans l'index, la requête dure près de 5 minutes contre moins de 5 secondes une fois indexée.