Meilleures approches pour la médiane groupée

En 2012, j'ai écrit un article de blog ici mettant en évidence les approches pour calculer une médiane. Dans cet article, j'ai traité le cas très simple :nous voulions trouver la médiane d'une colonne sur l'ensemble d'un tableau. Il m'a été mentionné à plusieurs reprises depuis lors qu'une exigence plus pratique consiste à calculer une médiane partitionnée . Comme dans le cas de base, il existe plusieurs façons de résoudre ce problème dans différentes versions de SQL Server ; sans surprise, certains fonctionnent bien mieux que d'autres.

Dans l'exemple précédent, nous avions juste les colonnes génériques id et val. Rendons cela plus réaliste et disons que nous avons des vendeurs et le nombre de ventes qu'ils ont réalisées au cours d'une certaine période. Pour tester nos requêtes, créons d'abord un simple tas de 17 lignes et vérifions qu'elles produisent toutes les résultats attendus (SalesPerson 1 a une médiane de 7,5 et SalesPerson 2 a une médiane de 6,0) :

CREATE TABLE dbo.Sales(SalesPerson INT, Amount INT);GO INSERT dbo.Sales WITH (TABLOCKX)(SalesPerson, Amount) VALUES(1, 6 ),(1, 11),(1, 4 ),( 1, 4 ),(1, 15),(1, 14),(1, 4 ),(1, 9 ),(2, 6 ),(2, 11),(2, 4 ),(2, 4 ),(2, 15),(2, 14),(2, 4 );

Voici les requêtes que nous allons tester (avec beaucoup plus de données !) par rapport au tas ci-dessus, ainsi qu'avec les index de support. J'ai ignoré quelques requêtes du test précédent, qui ne s'évoluaient pas du tout ou ne correspondaient pas très bien aux médianes partitionnées (à savoir, 2000_B, qui utilisait une table #temp, et 2005_A, qui utilisait la ligne opposée Nombres). J'ai cependant ajouté quelques idées intéressantes tirées d'un article récent de Dwain Camps (@DwainCSQL), qui s'appuyait sur mon précédent article.

SQL Server 2000+

La seule méthode de l'approche précédente qui fonctionnait assez bien sur SQL Server 2000 pour même l'inclure dans ce test était l'approche "min d'une moitié, max de l'autre" :

SELECT DISTINCT s.SalesPerson, Median =( (SELECT MAX(Amount) FROM (SELECT TOP 50 PERCENT Amount FROM dbo.Sales WHERE SalesPerson =s.SalesPerson ORDER BY Amount) AS t) + (SELECT MIN(Amount) FROM (SÉLECTIONNEZ LES 50 POURCENTAGES SUPÉRIEURS DU MONTANT DE dbo.Sales WHERE SalesPerson =s.SalesPerson ORDER BY Amount DESC) AS b)) / 2.0FROM dbo.Sales AS s ;

Honnêtement, j'ai essayé d'imiter la version de la table #temp que j'ai utilisée dans l'exemple le plus simple, mais elle n'a pas bien évolué du tout. À 20 ou 200 rangées, cela a bien fonctionné ; à 2000, cela a pris près d'une minute; à 1 000 000 j'ai abandonné au bout d'une heure. Je l'ai inclus ici pour la postérité (cliquez pour révéler).

CREATE TABLE #x( i INT IDENTITY(1,1), SalesPerson INT, Amount INT, i2 INT); CREATE CLUSTERED INDEX v ON #x(SalesPerson, Amount); INSERT #x(SalesPerson, Amount) SELECT SalesPerson, Amount FROM dbo.Sales ORDER BY SalesPerson,Amount OPTION (MAXDOP 1); UPDATE x SET i2 =i-( SELECT COUNT(*) FROM #x WHERE i <=x.i AND SalesPerson  
SQL Server 2005+ 1
 

 Cela utilise deux fonctions de fenêtrage différentes pour dériver une séquence et un décompte global des montants par vendeur.
 
SELECT SalesPerson, Median =AVG(1.0*Amount)FROM( SELECT SalesPerson, Amount, rn =ROW_NUMBER() OVER (PARTITION BY SalesPerson ORDER BY Amount), c =COUNT(*) OVER (PARTITION BY SalesPerson) FROM dbo .Sales)AS xWHERE rn IN ((c + 1)/2, (c + 2)/2)GROUP BY SalesPerson ;
 
SQL Server 2005+ 2
 

 Cela vient de l'article de Dwain Camps, qui fait la même chose que ci-dessus, d'une manière légèrement plus élaborée. Cela annule essentiellement le pivot de la ou des lignes intéressantes dans chaque groupe.
 
;WITH Compte AS( SELECT Vendeur, c FROM ( SELECT Vendeur, c1 =(c+1)/2, c2 =CASE c%2 WHEN 0 THEN 1+c/2 ELSE 0 END FROM ( SELECT Vendeur, c =COUNT(*) FROM dbo.Sales GROUP BY SalesPerson ) a ) a CROSS APPLY (VALUES(c1),(c2)) b(c))SELECT a.SalesPerson, Median=AVG(0.+b.Amount)FROM ( SELECT SalesPerson, Amount, rn =ROW_NUMBER() OVER (PARTITION BY SalesPerson ORDER BY Amount) FROM dbo.Sales a) aCROSS APPLY( SELECT Amount FROM Counts b WHERE a.SalesPerson =b.SalesPerson AND a.rn =b.c) bGROUP PAR un.Vendeur ;
 
SQL Server 2005+ 3
 

 Ceci était basé sur une suggestion d'Adam Machanic dans les commentaires de mon post précédent, et également amélioré par Dwain dans son article ci-dessus.
 
;WITH Counts AS( SELECT SalesPerson, c =COUNT(*) FROM dbo.Sales GROUP BY SalesPerson)SELECT a.SalesPerson, Median =AVG(0.+Amount)FROM Counts aCROSS APPLY( SELECT TOP (((a.c - 1) / 2) + (1 + (1 - a.c % 2))) b.Amount, r =ROW_NUMBER() OVER (ORDER BY b.Amount) FROM dbo.Sales b WHERE a.SalesPerson =b.SalesPerson ORDER BY b.Amount) pWHERE r BETWEEN ((a.c - 1) / 2) + 1 AND (((a.c - 1) / 2) + (1 + (1 - a.c % 2)))GROUP BY a.SalesPerson; 
SQL Server 2005+ 4
 

 Ceci est similaire à "2005+ 1" ci-dessus, mais au lieu d'utiliser COUNT(*) OVER() pour dériver les décomptes, il effectue une auto-jointure sur un agrégat isolé dans une table dérivée.
 
SELECT SalesPerson, Median =AVG(1.0 * Amount)FROM( SELECT s.SalesPerson, s.Amount, rn =ROW_NUMBER() OVER (PARTITION BY s.SalesPerson ORDER BY s.Amount), c.c FROM dbo.Sales AS s INNER JOIN ( SELECT SalesPerson, c =COUNT(*) FROM dbo.Sales GROUP BY SalesPerson ) AS c ON s.SalesPerson =c.SalesPerson) AS xWHERE rn IN ((c + 1)/2, (c + 2) /2) GROUPER PAR Vendeur ;
 
SQL Server 2012+ 1
 

 Il s'agit d'une contribution très intéressante de Peter "Peso" Larsson (@SwePeso), MVP de SQL Server, dans les commentaires sur l'article de Dwain ; il utilise CROSS APPLY et le nouveau OFFSET / FETCH fonctionnalité d'une manière encore plus intéressante et surprenante que la solution d'Itzik au calcul médian plus simple.
 
SELECT d.SalesPerson, w.MedianFROM( SELECT SalesPerson, COUNT(*) AS y FROM dbo.Sales GROUP BY SalesPerson) AS dCROSS APPLY( SELECT AVG(0E + Amount) FROM ( SELECT z.Amount FROM dbo.Sales AS z WHERE z.SalesPerson =d.SalesPerson ORDER BY z.Amount OFFSET (d.y - 1) / 2 ROWS FETCH NEXT 2 - d.y % 2 ROWS ONLY ) AS f) AS w(Median);
 
SQL Server 2012+ 2
 

 Enfin, nous avons le nouveau PERCENTILE_CONT() fonction introduite dans SQL Server 2012.
 
SELECT SalesPerson, Median =MAX(Median)FROM( SELECT SalesPerson,Median =PERCENTILE_CONT(0.5) WITHIN GROUP (ORDER BY Amount) OVER (PARTITION BY SalesPerson) FROM dbo.Sales) AS xGROUP BY SalesPerson;
 
Les vrais tests
 

 Pour tester les performances des requêtes ci-dessus, nous allons construire une table beaucoup plus conséquente. Nous allons avoir 100 vendeurs uniques, avec 10 000 montants de ventes chacun, pour un total de 1 000 000 de lignes. Nous allons également exécuter chaque requête sur le tas tel quel, avec un index non cluster ajouté sur (SalesPerson, Amount) , et avec un index clusterisé sur les mêmes colonnes. Voici la configuration :
 
CREATE TABLE dbo.Sales(SalesPerson INT, Amount INT);GO --CREATE CLUSTERED INDEX x ON dbo.Sales(SalesPerson, Amount);--CREATE NONCLUSTERED INDEX x ON dbo.Sales(SalesPerson, Amount);- -DROP INDEX x ON dbo.sales ;;WITH x AS ( SELECT TOP (100) number FROM master.dbo.spt_values ​​GROUP BY number)INSERT dbo.Sales WITH (TABLOCKX) (SalesPerson, Amount) SELECT x.number, ABS(CHECKSUM(NEWID())) % 99 FROM x CROSS JOIN x AS x2 CROSS JOIN x AS x3;
 

 Et voici les résultats des requêtes ci-dessus, sur le tas, l'index non clusterisé et l'index clusterisé :
 

 
Durée, en millisecondes, de diverses approches médianes groupées (contre un tas) 
 

 
Durée, en millisecondes, de diverses approches médianes groupées (contre un tas avec un index non clusterisé) 
 

 
Durée, en millisecondes, de diverses approches médianes groupées (contre un index clusterisé) 
 
Qu'en est-il d'Hékaton ?
 

 Naturellement, j'étais curieux de savoir si cette nouvelle fonctionnalité de SQL Server 2014 pouvait aider avec l'une de ces requêtes. J'ai donc créé une base de données In-Memory, deux versions In-Memory de la table Sales (une avec un index de hachage sur (SalesPerson, Amount) , et l'autre uniquement sur (SalesPerson) ), et refait les mêmes tests :
 
CREATE DATABASE Hekaton;GOALTER DATABASE Hekaton ADD FILEGROUP xtp CONTAINS MEMORY_OPTIMIZED_DATA;GOALTER DATABASE Hekaton ADD FILE (name ='xtp', filename ='c:\temp\hek.mod') TO FILEGROUP xtp;GOALTER DATABASE Hekaton SET MEMORY_OPTIMIZED_ELEVATE_TO_SNAPSHOT ON;GO USE Hekaton;GO CREATE TABLE dbo.Sales1( ID INT IDENTITY(1,1) PRIMARY KEY NONCLUSTERED, SalesPerson INT NOT NULL, Amount INT NOT NULL, INDEX x NONCLUSTERED HASH (SalesPerson, Amount) WITH (BUCKET_COUNT =256) )WITH (MEMORY_OPTIMIZED =ON, DURABILITY =SCHEMA_AND_DATA);GO CREATE TABLE dbo.Sales2( ID INT IDENTITY(1,1) PRIMARY KEY NONCLUSTERED, SalesPerson INT NOT NULL, Amount INT NOT NULL, INDEX x NONCLUSTERED HASH (SalesPerson) WITH ( BUCKET_COUNT =256))WITH (MEMORY_OPTIMIZED =ON, DURABILITY =SCHEMA_AND_DATA);GO ;WITH x AS ( SELECT TOP (100) number FROM master.dbo.spt_values ​​GROUP BY number)INSERT dbo.Sales1 (SalesPerson, Amount) -- TABLOCK /TABLOCKX non autorisé ici SELECT x.number, ABS(CHECKSUM(NEWID())) % 99 DE x JOINT CROISÉ x AS x2 JOINT CROISÉ x AS x3 ; INSERT dbo.Sales2 (SalesPerson, Montant) SELECT SalesPerson, Montant FROM dbo.Sales1 ;
 

 Les résultats :
 

 
Durée, en millisecondes, pour divers calculs médians par rapport à In-Memory tableaux 
 

 Même avec le bon index de hachage, nous ne voyons pas vraiment d'améliorations significatives par rapport à une table traditionnelle. De plus, essayer de résoudre le problème médian à l'aide d'une procédure stockée compilée en mode natif ne sera pas une tâche facile, car de nombreuses constructions de langage utilisées ci-dessus ne sont pas valides (j'ai également été surpris par quelques-unes d'entre elles). Essayer de compiler toutes les variations de requête ci-dessus a généré ce défilé d'erreurs ; certains se sont produits plusieurs fois dans chaque procédure, et même après avoir supprimé les doublons, cela reste assez comique :
 Msg 10794, niveau 16, état 47, procédure GroupedMedian_2000
L'option "DISTINCT" n'est pas prise en charge avec les procédures stockées compilées en mode natif.
Msg 12311, niveau 16, état 37, procédure GroupedMedian_2000
Sous-requêtes ( les requêtes imbriquées dans une autre requête) ne sont pas prises en charge avec les procédures stockées compilées en mode natif.
Msg 10794, niveau 16, état 48, procédure GroupedMedian_2000
L'option 'PERCENT' n'est pas prise en charge avec les procédures stockées compilées en mode natif.

Msg 12311, Niveau 16, État 37, Procédure GroupedMedian_2005_1
Les sous-requêtes (requêtes imbriquées dans une autre requête) ne sont pas prises en charge avec les procédures stockées compilées en mode natif.
Msg 10794, Niveau 16, État 91 , Procedure GroupedMedian_2005_1
La fonction d'agrégation 'ROW_NUMBER' n'est pas prise en charge avec les procédures stockées compilées en mode natif.
Msg 10794, Level 16, State 56, Procedure GroupedMedian_2005_1
L'opérateur 'IN' n'est pas pris en charge avec procédures stockées compilées nativement.

Msg 12310, Niveau 16, État 36, Procédure GroupedMedian_2005_2
Les expressions de table communes (CTE) ne sont pas prises en charge avec les procédures stockées compilées en mode natif.
Msg 12309, Niveau 16, État 35, Procédure GroupedMedian_2005_2
Instructions du formulaire INSERT…VALUES… qui insèrent plusieurs lignes ne sont pas pris en charge avec les procédures stockées compilées en mode natif.
Msg 10794, Level 16, State 53, Procedure GroupedMedian_2005_2
L'opérateur 'APPLY' n'est pas pris en charge avec les procédures stockées compilées en mode natif. 
Msg 12311, Niveau 16, État 37, Procédure GroupedMedian_2005_2
Les sous-requêtes (requêtes imbriquées dans une autre requête) ne sont pas prises en charge avec les procédures stockées compilées en mode natif.
Msg 10794, Niveau 16, État 91, Procédure GroupedMedian_2005_2
La fonction d'agrégation "ROW_NUMBER" n'est pas prise en charge avec les procédures stockées compilées en mode natif.

Msg 12310, niveau 16, état 36, procédure GroupedMedian_2005_3
Common Table Expressions (CTE) are non pris en charge avec le stockage compilé en mode natif procédures.
Msg 12311, Niveau 16, État 37, Procédure GroupedMedian_2005_3
Les sous-requêtes (requêtes imbriquées dans une autre requête) ne sont pas prises en charge avec les procédures stockées compilées en mode natif.
Msg 10794, Niveau 16, État 91 , Procedure GroupedMedian_2005_3
La fonction d'agrégation 'ROW_NUMBER' n'est pas prise en charge avec les procédures stockées compilées en mode natif.
Msg 10794, Level 16, State 53, Procedure GroupedMedian_2005_3
L'opérateur 'APPLY' n'est pas pris en charge avec procédures stockées compilées en mode natif.

Msg 12311, niveau 16, état 37, procédure GroupedMedian_2005_4
Les sous-requêtes (requêtes imbriquées dans une autre requête) ne sont pas prises en charge avec les procédures stockées compilées en mode natif.
Msg 10794, niveau 16, état 91, procédure GroupedMedian_2005_4
La fonction d'agrégation "ROW_NUMBER" n'est pas prise en charge avec les procédures stockées compilées en mode natif.
Msg 10794, niveau 16, état 56, procédure GroupedMedian_2005_4
L'opérateur 'IN' n'est pas pris en charge avec le stockage compilé en mode natif ed procédures.

Msg 12311, Level 16, State 37, Procedure GroupedMedian_2012_1
Les sous-requêtes (requêtes imbriquées dans une autre requête) ne sont pas prises en charge avec les procédures stockées compilées en mode natif.
Msg 10794, Niveau 16, état 38, procédure GroupedMedian_2012_1
L'opérateur 'OFFSET' n'est pas pris en charge avec les procédures stockées compilées en mode natif.
Msg 10794, niveau 16, état 53, procédure GroupedMedian_2012_1
L'opérateur 'APPLY' n'est pas pris en charge avec les procédures stockées compilées en mode natif.

Msg 12311, Niveau 16, État 37, Procédure GroupedMedian_2012_2
Les sous-requêtes (requêtes imbriquées dans une autre requête) ne sont pas prises en charge avec les procédures stockées compilées en mode natif.
Msg 10794, Niveau 16, État 90, Procédure GroupedMedian_2012_2
La fonction d'agrégation 'PERCENTILE_CONT' n'est pas prise en charge avec les procédures stockées compilées en mode natif. 

 Dans l'état actuel des choses, aucune de ces requêtes ne peut être portée vers une procédure stockée compilée en mode natif. Peut-être quelque chose à examiner pour un autre post de suivi.
 
Conclusion
 

 En rejetant les résultats Hekaton, et lorsqu'un index de support est présent, la requête de Peter Larsson ("2012+ 1") en utilisant OFFSET/FETCH est sorti vainqueur de loin de ces tests. Bien qu'un peu plus complexe que la requête équivalente dans les tests non partitionnés, cela correspondait aux résultats que j'ai observés la dernière fois. 
 

 Dans ces mêmes cas, les 2000 MIN/MAX approche et PERCENTILE_CONT() de 2012 sont sortis comme de vrais chiens; encore une fois, tout comme mes tests précédents contre le cas le plus simple.
 

 Si vous n'êtes pas encore sur SQL Server 2012, votre meilleure option suivante est "2005+ 3" (si vous avez un index de support) ou "2005+ 2" si vous avez affaire à un tas. Désolé, j'ai dû trouver un nouveau schéma de nommage pour ceux-ci, principalement pour éviter toute confusion avec les méthodes de mon message précédent.
 

 Bien sûr, ce sont mes résultats par rapport à un schéma et un ensemble de données très spécifiques - comme pour toutes les recommandations, vous devez tester ces approches par rapport à votre schéma et à vos données, car d'autres facteurs peuvent influencer différents résultats.
 
Une autre remarque
 

 En plus d'être peu performant et de ne pas être pris en charge dans les procédures stockées compilées en mode natif, un autre problème de PERCENTILE_CONT() est qu'il ne peut pas être utilisé dans les anciens modes de compatibilité. Si vous essayez, vous obtenez cette erreur :
 Msg 10762, Niveau 15, État 1
La fonction PERCENTILE_CONT n'est pas autorisée dans le mode de compatibilité actuel. Il n'est autorisé qu'en mode 110 ou supérieur.