Nejlepší přístupy pro seskupený medián

V roce 2012 jsem zde napsal blogový příspěvek, který zdůrazňoval přístupy pro výpočet mediánu. V tomto příspěvku jsem se zabýval velmi jednoduchým případem:chtěli jsme najít medián sloupce v celé tabulce. Od té doby mi bylo několikrát zmíněno, že praktičtějším požadavkem je vypočítat rozdělený medián . Stejně jako u základního případu existuje několik způsobů, jak to vyřešit v různých verzích SQL Server; není divu, že některé fungují mnohem lépe než jiné.

V předchozím příkladu jsme měli pouze obecné sloupce id a val. Udělejme to realističtěji a řekněme, že máme obchodníky a počet prodejů, které provedli za určité období. Abychom otestovali naše dotazy, nejprve vytvořte jednoduchou haldu se 17 řádky a ověřte, že všechny poskytují výsledky, které očekáváme (Prodejce 1 má medián 7,5 a Prodejce 2 medián 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);

Zde jsou dotazy, které se chystáme otestovat (s mnohem větším množstvím dat!) proti hromadě výše, stejně jako s podpůrnými indexy. Zahodil jsem několik dotazů z předchozího testu, které se buď vůbec neškálovaly, nebo se příliš dobře nemapovaly na rozdělené mediány (jmenovitě 2000_B, která používala #temp tabulku, a 2005_A, která používala opačný řádek čísla). Přidal jsem však několik zajímavých nápadů z nedávného článku od Dwain Camps (@DwainCSQL), který vycházel z mého předchozího příspěvku.

SQL Server 2000+

Jedinou metodou z předchozího přístupu, která na SQL Server 2000 fungovala dostatečně dobře na to, aby byla zahrnuta do tohoto testu, byl přístup „min jedné poloviny, max. druhé“:

SELECT DISTINCT s.SalesPerson, Medián =( (VYBRAT MAX.(Částku) OD (VYBRAT NEJLEPŠÍCH 50 PROCENT Částka OD dbo.Sales WHERE SalesPerson =s.SalesPerson ORDER BY Amount) AS t) + (SELECT MIN (Částka) OD (VYBERTE NEJLEPŠÍCH 50 PROCENT Částku OD dbo.Sales WHERE SalesPerson =s.SalesPerson OBJEDNAT PODLE Částky DESC) AS b)) / 2.0FROM dbo.Sales AS s;

Upřímně jsem se snažil napodobit verzi tabulky #temp, kterou jsem použil v jednodušším příkladu, ale vůbec se to neškálovalo dobře. Na 20 nebo 200 řádcích to fungovalo dobře; v roce 2000 to trvalo skoro minutu; na 1 000 000 jsem to po hodině vzdal. Zahrnul jsem to sem pro potomky (kliknutím zobrazíte).

CREATE TABLE #x( i INT IDENTITY(1,1), Prodejce INT, Částka 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
 

 To využívá dvě různé funkce okna k odvození sekvence a celkového počtu částek na prodejce.
 
SELECT SalesPerson, Medián =AVG(1,0*Částka)FROM( SELECT SalesPerson, Amount, rn =ROW_NUMBER() OVER (PARTITION BY SalesPerson ORDER BY Amount), c =COUNT(*) OVER (PARTITION BY SalesPerson) OD dbo .Sales)AS xWHERE rn IN ((c + 1)/2, (c + 2)/2)GROUP BY SalesPerson;
 
SQL Server 2005+ 2
 

 Vyšlo to z článku Dwaina Campse, který dělá totéž jako výše, trochu propracovanějším způsobem. Tím se v zásadě odkloní zajímavé řádky v každé skupině.
 
;WITH Counts AS( SELECT SalesPerson, c FROM ( SELECT SalesPerson, c1 =(c+1)/2, c2 =CASE c%2 WHEN 0 THEN 1+c/2 ELSE 0 END FROM ( SELECT SalesPerson, c =POČET(*) OD dbo.Sales GROUP PODLE Prodejce ) a ) a KŘÍŽOVÉ POUŽITÍ (HODNOTY(c1),(c2)) b(c))VYBRAT a.Prodejce, Medián=AVG(0.+b.Částka)OD ( SELECT SalesPerson, Amount, rn =ROW_NUMBER() OVER (PARTITION BY SalesPerson ORDER BY Amount) OD dbo.Sales a) ACROSS APPLY( SELECT Amount FROM Counts b WHERE a.SalesPerson =b.SalesPerson AND a.rn =b.c)GROUP BY a.SalesPerson;
 
SQL Server 2005+ 3
 

 Toto bylo založeno na návrhu od Adama Machanice v komentářích k mému předchozímu příspěvku a také vylepšeno Dwainem ve svém článku výše.
 
;WITH POČTY JAKO( SELECT Prodejce, c =POČET(*) FROM dbo.Sales GROUP BY Prodejce)SELECT a.Prodejce, Medián =AVG(0.+Částka)FROM Počty napříč APLIKOVAT( SELECT TOP ((a.c - 1) / 2) + (1 + (1 - a.c % 2))) b.Částka, r =ŘÁDEK_ČÍSLO() NAD (OBJEDNAT PODLE B.Částky) OD dbo.Prodej b KDE a.Osoba prodeje =b.Osoba prodeje OBJEDNÁVKA BY b.Částka) pWHERE r MEZI ((a.c - 1) / 2) + 1 AND (((a.c - 1) / 2) + (1 + (1 - a.c % 2)))SKUPINA PODLE a. Prodejce; 
SQL Server 2005+ 4
 

 Je to podobné jako „2005+ 1“ výše, ale místo použití COUNT(*) OVER() k odvození počtů provede vlastní spojení proti izolovanému agregátu v odvozené tabulce.
 
SELECT SalesPerson, Medián =AVG(1,0 * Částka)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(*) OD dbo.Sales GROUP BY SalesPerson ) AS c ON s.SalesPerson =c.SalesPerson) AS xWHERE rn IN ((c + 1)/2, (c + 2) /2)GROUP BY SalesPerson;
 
SQL Server 2012+ 1
 

 Toto byl velmi zajímavý příspěvek od kolegy MVP pro SQL Server Petera "Peso" Larssona (@SwePeso) v komentářích k Dwainovu článku; používá CROSS APPLY a nový OFFSET / FETCH funkčnost ještě zajímavějším a překvapivějším způsobem než Itzikovo řešení jednoduššího výpočtu mediánu.
 
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. OFFSET částky (d.y - 1) / 2 ŘÁDKY NAČÍTÁNÍ DALŠÍ 2 - d.y % 2 ŘÁDKY POUZE ) AS f) AS w(Median);
 
SQL Server 2012+ 2
 

 Nakonec máme nový PERCENTILE_CONT() funkce představená v SQL Server 2012.
 
SELECT SalesPerson, Medián =MAX(Median)FROM( SELECT SalesPerson,Median =PERCENTILE_CONT(0.5) WITHIN GROUP (ORDER PODLE ČÁSTKY) NAD (ODDĚLENÍ PODLE Prodejce) OD dbo.Sales) JAKO xGROUP BY SalesPerson;
 
Skutečné testy
 

 Abychom otestovali výkon výše uvedených dotazů, vytvoříme mnohem podstatnější tabulku. Budeme mít 100 jedinečných prodejců, každý s 10 000 údaji o objemu prodeje, celkem 1 000 000 řádků. Také spustíme každý dotaz na hromadě tak, jak je, s přidaným indexem bez klastrů na (SalesPerson, Amount) a se seskupeným indexem ve stejných sloupcích. Zde je nastavení:
 
CREATE TABLE dbo.Sales(SalesPerson INT, Amount INT);GO --CREATE CLUSTERED INDEX x ON dbo.Sales(SalesPerson, Amount);--CREATE NENCLUSTERED INDEX x ON dbo.Sales(SalesPerson, Amount); -DROP INDEX x ON dbo.prodej;;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;
 

 A zde jsou výsledky výše uvedených dotazů v porovnání s haldou, neseskupeným indexem a seskupeným indexem:
 

 
Trvání v milisekundách různých seskupených mediánových přístupů (proti hromada) 
 

 
Trvání v milisekundách různých seskupených mediánových přístupů (proti halda s indexem bez klastrů) 
 

 
Trvání v milisekundách různých seskupených mediánových přístupů (proti seskupený index) 
 
A co Hekaton?
 

 Přirozeně jsem byl zvědavý, zda tato nová funkce v SQL Server 2014 může pomoci s některým z těchto dotazů. Vytvořil jsem tedy databázi In-Memory, dvě verze In-Memory tabulky Prodeje (jedna s hash indexem na (SalesPerson, Amount) , a druhý pouze na (SalesPerson) ) a znovu spusťte stejné testy:
 
VYTVOŘIT DATABÁZI Hekaton;DATABÁZE BRANKŮ Hekaton PŘIDAT SKUPINU SOUBORŮ xtp OBSAHUJE MEMORY_OPTIMIZED_DATA;DATABÁZE BRANKA ON;GO USE Hekaton;GO CREATE TABLE dbo.Sales1( ID INT IDENTITY(1,1) PRIMÁRNÍ KLÍČ NEZAHRNUTÝ, INT prodejce NENÍ NULL, Částka INT NENÍ NULL, INDEX x NEZAHRNUTÝ HASH (Osoba prodeje, Částka) S (BUCKET_COUNT) S (BUCKET_COUNT) )WITH (MEMORY_OPTIMIZED =ON, DURABILITY =SCHEMA_AND_DATA);GO CREATE TABLE dbo.Sales2( ID INT IDENTITY(1,1) PRIMÁRNÍ KLÍČ NEZAHRNUTÝ, Prodejce INT NENÍ NULL, Částka INT NENÍ NULL, INDEXTHaSHLes PNCLUSTERson BUCKET_COUNT =256))WITH (MEMORY_OPTIMIZED =ZAPNUTO, ŽIVOTNOST =SCHEMA_AND_DATA);GO;WITH x AS ( SELECT TOP (100) number FROM master.dbo.spt_values ​​GROUP BY number)INSERT dbo.Sales1 (AmountSalesPerson) -- TAB /TABLOCKX zde není povoleno SELECT x.number, ABS(CHECKSUM(NEWID())) % 99 OD x PŘÍČNÉ SPOJENÍ x JAKO x2 PŘÍČNÉ SPOJENÍ x JAKO x3; INSERT dbo.Sales2 (SalesPerson, Částka) SELECT Prodejce, Částka FROM dbo.Sales1;
 

 Výsledky:
 

 
Trvání v milisekundách pro různé výpočty mediánu oproti paměti tabulky 
 

 I se správným hash indexem ve skutečnosti nevidíme výrazná zlepšení oproti tradiční tabulce. Kromě toho pokus o vyřešení problému mediánu pomocí nativně zkompilované uložené procedury nebude snadným úkolem, protože mnoho z výše použitých jazykových konstrukcí není platných (také mě několik z nich překvapilo). Pokus o kompilaci všech výše uvedených variant dotazů přinesl tuto přehlídku chyb; některé se vyskytly několikrát během každého postupu a i po odstranění duplikátů je to stále trochu komické:
 Msg 10794, Level 16, State 47, Procedure GroupedMedian_2000
Volba 'DISTINCT' není podporována u nativně zkompilovaných uložených procedur.
Msg 12311, Level 16, State 37, Procedure GroupedMedian_2000
Subqueries dotazy vnořené do jiného dotazu) nejsou podporovány nativně zkompilovanými uloženými procedurami.
Zpráva 10794, úroveň 16, stav 48, procedura GroupedMedian_2000
Volba 'PERCENT' není podporována u nativně kompilovaných uložených procedur.

Zpráva 12311, úroveň 16, stav 37, procedura GroupedMedian_2005_1
Poddotazy (dotazy vnořené do jiného dotazu) nejsou podporovány nativně kompilovanými uloženými procedurami.
Zpráva 10794, úroveň 16, stav 91 , Procedure GroupedMedian_2005_1
Agregační funkce 'ROW_NUMBER' není podporována u nativně zkompilovaných uložených procedur.
Msg 10794, Level 16, State 56, Procedure GroupedMedian_2005_1
Operátor 'IN' není podporován s nativně zkompilované uložené procedury.

Msg 12310, Úroveň 16, stav 36, procedura GroupedMedian_2005_2
Common Table Expressions (CTE) nejsou podporovány s nativně zkompilovanými uloženými procedurami.
Msg 12309, Level 16, State 35, Procedure GroupedMedian_2005_2
Příkazy formuláře INSERT…VALUES…, které vkládají více řádků, nejsou podporovány u nativně kompilovaných uložených procedur.
Zpráva 10794, úroveň 16, stav 53, procedura GroupedMedian_2005_2
Operátor 'APPLY' není podporován u nativně kompilovaných uložených procedur. 
Zpráva 12311, úroveň 16, stav 37, procedura GroupedMedian_2005_2
Poddotazy (dotazy vnořené do jiného dotazu) nejsou podporovány nativně kompilovanými uloženými procedurami.
Zpráva 10794, úroveň 16, stav 91, procedura GroupedMedian_2005_2
Agregační funkce 'ROW_NUMBER' není podporována nativně zkompilovanými uloženými procedurami.

Msg 12310, Level 16, State 36, Procedure GroupedMedian_2005_3
Common Table Expressions (CTE) jsou není podporováno s nativně zkompilovaným uloženým procedury.
Zpráva 12311, úroveň 16, stav 37, procedura GroupedMedian_2005_3
Poddotazy (dotazy vnořené do jiného dotazu) nejsou podporovány nativně kompilovanými uloženými procedurami.
Zpráva 10794, úroveň 16, stav 91 , Procedure GroupedMedian_2005_3
Agregační funkce 'ROW_NUMBER' není podporována nativně zkompilovanými uloženými procedurami.
Msg 10794, Level 16, State 53, Procedure GroupedMedian_2005_3
Operátor 'APPLY' není podporován s nativně zkompilované uložené procedury.

Msg 12311, Level 16, State 37, Procedure GroupedMedian_2005_4
Poddotazy (dotazy vnořené do jiného dotazu) nejsou podporovány u nativně kompilovaných uložených procedur.
Msg 10794, úroveň 16, stav 91, procedura GroupedMedian_2005_4
Agregační funkce 'ROW_NUMBER' není podporována nativně zkompilovanými uloženými procedurami.
Zpráva 10794, úroveň 16, stav 56, Procedure GroupedMedian_2005_4
Operátor 'IN' není podporováno s nativně zkompilovaným stor ed procedury.

Msg 12311, Level 16, State 37, Procedure GroupedMedian_2012_1
Poddotazy (dotazy vnořené do jiného dotazu) nejsou podporovány nativně kompilovanými uloženými procedurami.
Msg 10794, Úroveň 16, stav 38, procedura GroupedMedian_2012_1
Operátor 'OFFSET' není podporován nativně zkompilovanými uloženými procedurami.
Zpráva 10794, úroveň 16, stav 53, procedura GroupedMedian_2012_1
Operátor 'APPLY' není podporováno s nativně kompilovanými uloženými procedurami.

Zpráva 12311, úroveň 16, stav 37, procedura GroupedMedian_2012_2
Poddotazy (dotazy vnořené do jiného dotazu) nejsou podporovány u nativně kompilovaných uložených procedur.
Msg 10794, Level 16, State 90, Procedure GroupedMedian_2012_2
Agregační funkce 'PERCENTILE_CONT' není podporována nativně kompilovanými uloženými procedurami. 

 Jak je aktuálně napsáno, ani jeden z těchto dotazů nelze přenést do nativně zkompilované uložené procedury. Možná něco, na co byste se měli podívat v dalším následném příspěvku.
 
Závěr
 

 Zahození výsledků Hekaton a pokud je přítomen podpůrný index, dotaz Petera Larssona ("2012+ 1") pomocí OFFSET/FETCH vyšel v těchto testech jako absolutní vítěz. I když je to trochu složitější než ekvivalentní dotaz v testech bez oddílů, odpovídalo to výsledkům, které jsem pozoroval minule. 
 

 Ve stejných případech 2000 MIN/MAX a PERCENTILE_CONT() z roku 2012 vyšli jako skuteční psi; znovu, stejně jako mé předchozí testy proti jednoduššímu případu.
 

 Pokud ještě nepoužíváte SQL Server 2012, pak je vaší další nejlepší možností „2005+ 3“ (pokud máte podpůrný index) nebo „2005+ 2“, pokud máte co do činění s haldou. Promiňte, musel jsem pro ně vymyslet nové schéma pojmenování, většinou proto, abych se vyhnul záměně s metodami v mém předchozím příspěvku.
 

 Samozřejmě, toto jsou mé výsledky na základě velmi specifického schématu a souboru dat – stejně jako všechna doporučení byste měli tyto přístupy otestovat proti vašemu schématu a datům, protože jiné faktory mohou ovlivnit různé výsledky.
 
Ještě jedna poznámka
 

 Kromě toho, že je to špatný výkon a není podporováno v nativně kompilovaných uložených procedurách, jeden další bolestivý bod PERCENTILE_CONT() je, že jej nelze použít ve starších režimech kompatibility. Pokud to zkusíte, zobrazí se tato chyba:
 Msg 10762, Level 15, State 1
Funkce PERCENTILE_CONT není v aktuálním režimu kompatibility povolena. Je povoleno pouze v režimu 110 nebo vyšším.