Най-добрите подходи за групирана медиана

Още през 2012 г. написах тук публикация в блога, в която подчертавам подходите за изчисляване на медиана. В тази публикация се занимавах с много прост случай:искахме да намерим медианата на колона в цяла таблица. Оттогава ми беше споменавано няколко пъти, че по-практично изискване е да се изчисли разделена медиана . Подобно на основния случай, има множество начини за решаване на това в различни версии на SQL Server; не е изненадващо, че някои се представят много по-добре от други.

В предишния пример просто имахме общи колони id и val. Нека направим това по-реалистично и да кажем, че имаме хора по продажбите и броя на продажбите, които са направили през определен период. За да тестваме нашите заявки, нека първо създадем обикновен набор от 17 реда и се уверим, че всички те дават резултатите, които очакваме (SalesPerson 1 има медиана 7,5, а SalesPerson 2 има медиана 6,0):

СЪЗДАВАНЕ НА ТАБЛИЦА 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);

Ето заявките, които ще тестваме (с много повече данни!) спрямо купчината по-горе, както и с поддържащи индекси. Отхвърлих няколко заявки от предишния тест, които или изобщо не се мащабираха, или не се съпоставиха много добре с разделени медиани (а именно 2000_B, която използва таблица #temp, и 2005_A, която използва противоположния ред числа). Въпреки това добавих няколко интересни идеи от скорошна статия на Dwain Camps (@DwainCSQL), която се основава на предишната ми публикация.

SQL Server 2000+

Единственият метод от предишния подход, който работеше достатъчно добре на SQL Server 2000, за да го включи дори в този тест, беше подходът "мин. на едната половина, максимум на другата":

ИЗБЕРЕТЕ ДИСТАНЦИОННО с.Продавач, Медиана =( (ИЗБЕРЕТЕ МАКСИМАЛНА (сума) ОТ (ИЗБЕРЕТЕ ТОП 50 ПРОЦЕНТА СУМА ОТ dbo.Продажби КЪДЕ SalesPerson =s.Продавач ПОРЪЧКА ПО СУМА) КАТО t) + (ИЗБЕРЕТЕ МИН.(сума) ОТ (ИЗБЕРЕТЕ ТОП 50 ПРОЦЕНТА СУМА ОТ dbo.Sales WHERE SalesPerson =s.SalesPerson ПОРЪЧАЙТЕ ПО СУМА DESC) AS b)) / 2.0FROM dbo.Sales AS s;

Честно се опитах да имитирам версията на таблицата #temp, която използвах в по-простия пример, но тя изобщо не се мащабира добре. При 20 или 200 реда работеше добре; през 2000 г. това отне почти минута; на 1 000 000 се отказах след час. Включих го тук за потомство (щракнете, за да разкриете).

СЪЗДАВАНЕ НА ТАБЛИЦА #x( i INT IDENTITY(1,1), SalesPerson INT, Amount INT, i2 INT); СЪЗДАВАНЕ НА КЛУСТРИРАН ИНДЕКС v ON #x(Продавач, Сума); INSERT #x(Продавач, Сума) ИЗБЕРЕТЕ Продавач, Сума ОТ dbo.Продажби ПОРЪЧАЙТЕ ПО Продавач, ОПЦИЯ за сума (MAXDOP 1); АКТУАЛИЗАЦИЯ x SET i2 =i-( ИЗБЕРЕТЕ БРОЯ (*) ОТ #x, КЪДЕТО i <=x.i И SalesPerson  
SQL Server 2005+ 1
 

 Това използва две различни функции на прозореца за извличане на последователност и общ брой суми на търговец.
 
SELECT SalesPerson, Median =AVG(1.0*Amount)FROM( SELECT SalesPerson, Amount, rn =ROW_NUMBER() НАД (РАЗДЕЛЕНИЕ ПО ПРОДАЖБА ПОРЪЧКА ПО СУМА), c =COUNT(*) НАД (РАЗДЕЛЕНИЕ ПО ПРОДАЖБА) ОТ dbo .Продажби) КАТО xWHERE rn В ((c + 1)/2, (c + 2)/2)ГРУПА ПО ПРОДАЖБА;
 
SQL Server 2005+ 2
 

 Това идва от статията на Дуейн Кампс, която прави същото като по-горе, по малко по-сложен начин. Това основно премахва интересния ред(ове) във всяка група.
 
;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 =БРОЙ(*) ОТ dbo.ГРУПА ПРОДАЖБИ ПО ПРОДАЖБА ) a ) a КРЪСТО ПРИЛОЖИ (СТОЙНОСТИ(c1),(c2)) b(c))ИЗБЕРЕТЕ a.Продавач, Медиана=СР.(0.+b.Сума) ОТ ( ИЗБЕРЕТЕ SAlesPerson, Amount, rn =ROW_NUMBER() НАД (РАЗДЕЛЯНЕ ПО ПРОДАЖБА ПОРЪЧКА ПО СУМА) ОТ dbo.Sales a) КРЪСТНО ПРИЛАГАНЕ( ИЗБЕРЕТЕ сума ОТ Броя b КЪДЕ a.SalesPerson =b.SalesPerson И a.rn =b.c) ОТ а.Продавач;
 
SQL Server 2005+ 3
 

 Това се основава на предложение от Адам Мачаник в коментарите към предишната ми публикация и също така е подобрено от Дуейн в статията му по-горе.
 
;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. Сума, r =ROW_NUMBER() НАД (ПОРЪЧКА ПО b. Сума) ОТ dbo.Продажби b КЪДЕ a.SalesPerson =b.Продавач ПОРЪЧКА ПО b.Сума) pWHERE r МЕЖДУ ((a.c - 1) / 2) + 1 И (((a.c - 1) / 2) + (1 + (1 - a.c % 2)))ГРУПА ОТ a.SalesPerson; 
SQL Server 2005+ 4
 

 Това е подобно на "2005+ 1" по-горе, но вместо да се използва COUNT(*) OVER() за да изведе броя, той извършва самостоятелно свързване срещу изолиран агрегат в извлечена таблица.
 
SELECT SalesPerson, Median =AVG(1.0 * Amount)FROM( SELECT s.SalesPerson, s.Amount, rn =ROW_NUMBER() НАД (РАЗДЕЛЕНИЕ ПО s.SalesPerson ORDER BY s.Amount), c.c ОТ dbo.Sales AS s ВЪТРЕШНО ПРИСЪЕДИНЯВАНЕ ( ИЗБЕРЕТЕ ПРОДАЖБА, c =БРОЙ(*) ОТ dbo.Продажби ГРУПА ПО ПРОДАЖБА ) КАТО c ON s.Продавач =c.Продавач) КАТО xWHERE rn IN ((c + 1)/2, (c + 2) /2)ГРУПА ПО ПРОДАЖБА;
 
SQL Server 2012+ 1
 

 Това беше много интересен принос от колегата MVP на SQL Server Питър "Песо" Ларсон (@SwePeso) в коментарите към статията на Дуейн; той използва CROSS APPLY и новият OFFSET / FETCH функционалност по още по-интересен и изненадващ начин от решението на Ицик за по-простото изчисление на медиана.
 
SELECT d.SalesPerson, w.MedianaFROM( 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.Комплектиране на сума (d.y - 1) / 2 РЕДА ИЗВЛЕЧВАНЕ СЛЕДВАЩО 2 - d.y % САМО 2 РЕДА ) AS f) AS w(Медиана);
 
SQL Server 2012+ 2
 

 И накрая, имаме новия PERCENTILE_CONT() функция, въведена в SQL Server 2012.
 
ИЗБЕРЕТЕ продавач, медиана =MAX(медиана)FROM( SELECT Salesperson,медиана =PERCENTILE_CONT(0,5) В рамките на ГРУПА (РЕД ПО СУМА) НАД (РАЗДЕЛЕНИЕ ПО ПРОДАЖБА) ОТ dbo.Sales) КАТО xGROUP BY SalesPerson;
 
Истинските тестове
 

 За да тестваме ефективността на горните заявки, ще изградим много по-съществена таблица. Ще имаме 100 уникални търговци, с по 10 000 стойности на продажбите всеки, за общо 1 000 000 реда. Също така ще изпълним всяка заявка спрямо купчината такава, каквато е, с добавен неклъстериран индекс в (SalesPerson, Amount) , и с клъстериран индекс на същите колони. Ето настройката:
 
СЪЗДАДЕТЕ ТАБЛИЦА dbo.Sales(SalesPerson INT, Amount INT);GO --СЪЗДАЙТЕ КЛУСТРИРАН ИНДЕКС x ON dbo.Sales(SalesPerson, Amount);--СЪЗДАЙТЕ НЕКЛУСТРИРАН ИНДЕКС x ON dbo.Sales(SalesPerson, Amount);- -ИНДЕКС НА ИЗПАДАНЕ x НА dbo.sales;;С x AS ( ИЗБЕРЕТЕ ТОП (100) номер ОТ master.dbo.spt_values ​​ГРУПА ПО номер) ВЪВЕТЕ dbo.Продажби С (TABLOCKX) (Продавач, сума) ИЗБЕРЕТЕ x. номер, ABS(КОНТРОЛНА СУМА(НОВИД())) % 99 ОТ x КРЪСТО ПРИСЪЕДИНЯВАНЕ x КАТО x2 КРЪСТО ПРИСЪЕДИНЕНИЕ x КАТО x3;
 

 И ето резултатите от горните заявки, срещу хепа, неклъстерирания индекс и клъстерирания индекс:
 

 
Продължителност, в милисекунди, на различни групирани медианни подходи (срещу купчина) 
 

 
Продължителност, в милисекунди, на различни групирани медианни подходи (срещу купчина с неклъстериран индекс) 
 

 
Продължителност, в милисекунди, на различни групирани медианни подходи (срещу клъстериран индекс) 
 
Ами Хекатон?
 

 Естествено, бях любопитен дали тази нова функция в SQL Server 2014 може да помогне с някоя от тези заявки. Така че създадох база данни In-Memory, две In-Memory версии на таблицата Sales (една с хеш индекс на (SalesPerson, Amount) , а другият само на (SalesPerson) ) и изпълни отново същите тестове:
 
СЪЗДАВАНЕ НА БАЗА ДАННИ Hekaton;БАЗА ДАННИ GOALTER Hekaton ADD FILEGROUP xtp СЪДЪРЖА MEMORY_OPTIMIZED_DATA;GOALTER БАЗА ДАННИ Hekaton ДОБАВЯНЕ НА ФАЙЛ (име ='xtp', име на файл ='c:\temp\hek.mod') TOpTIZETTOSHEGOALTER_GRUPA_XtOPTIZETOSHEGOALTER_GRUPA; ON;GO ИЗПОЛЗВАЙТЕ Hekaton;GO ИЗПОЛЗВАЙТЕ ТАБЛИЦА dbo.Sales1( ID INT IDENTITY(1,1) ПЪРВИЧЕН КЛЮЧ НЕКЛУСТРИРАН, SalesPerson INT NOT NULL, Amount INT NOT NULL, INDEX x NONCLUSTERED HASH (SalesPerson, Amount) WITH =COUNT )С (MEMORY_OPTIMIZED =ON, DURABILITY =SCHEMA_AND_DATA);GO CREATE TABLE dbo.Sales2( ID INT IDENTITY(1,1) ПЪРВИЧЕН КЛЮЧ NONCLUSTERED, SalesPerson INT NOT NULL, Amount INT NOT NOT NULL, NCLUSTEles (SHNOPSales) BUCKET_COUNT =256))С (MEMORY_OPTIMIZED =ВКЛ., ИЗДЪРЖАТЕЛНОСТ =SCHEMA_AND_DATA);GO;WITH x AS (ИЗБЕРЕТЕ TOP (100) номер ОТ master.dbo.spt_values ​​GROUP BY number)INSERT dbo.Sales1 (SalesPerson) -- TABLO Amount /TABLOCKX не е позволено тук ИЗБЕРЕТЕ x.число, ABS(КОНТРОЛНА СУМА(НОВИД())) % 99 ОТ x КРЪСТО СЪЕДИНЯВАНЕ x КАТО x2 КРЪСТО ПРИСЪЕДИНЕНИЕ x КАТО x3; INSERT dbo.Sales2 (Лице за продажба, сума) ИЗБЕРЕТЕ SalesPerson, Amount FROM dbo.Sales1;
 

 Резултатите:
 

 
Продължителност, в милисекунди, за различни средни изчисления спрямо вградената памет маси 
 

 Дори и с правилния хеш индекс, всъщност не виждаме значителни подобрения в сравнение с традиционната таблица. Освен това, опитът за решаване на медианния проблем с помощта на компилирана съхранена процедура няма да е лесна задача, тъй като много от езиковите конструкции, използвани по-горе, не са валидни (и аз бях изненадан от някои от тях). Опитът за компилиране на всички горепосочени варианти на заявката доведе до този парад от грешки; някои се случиха няколко пъти в рамките на всяка процедура и дори след премахване на дубликати, това все още е малко комично:
 Msg 10794, Level 16, State 47, Procedure GroupedMedian_2000
Опцията 'DISTINCT' не се поддържа с собствено компилирани съхранени процедури.
Съобщение 12311, Ниво 16, Състояние 37, Процедура GroupedMedian
GroupedMedian
 заявки, вложени вътре в друга заявка) не се поддържат с компилирани в собствен произход съхранени процедури.
Съобщение 10794, ниво 16, състояние 48, процедура GroupedMedian_2000
Опцията 'PERCENT' не се поддържа с компилирани в собствен произход съхранени процедури.

Съобщение 12311, ниво 16, състояние 37, процедура GroupedMedian_2005_1
Подзаявки (заявки, вложени в друга заявка) не се поддържат с компилирани в собствен произход съхранени процедури.
Съобщение 10794, състояние 16, ниво 16 , Процедура GroupedMedian_2005_1
Агрегираната функция 'ROW_NUMBER' не се поддържа с компилирани в собствен произход съхранени процедури.
Съобщение 10794, ниво 16, състояние 56, процедура GroupedMedian_2005_1
Операторът не се поддържа с'IN собствено компилирани съхранени процедури.

Msg 12310, Ниво 16, състояние 36, процедура GroupedMedian_2005_2
Общите изрази за таблици (CTE) не се поддържат с компилирани в собствен произход съхранени процедури.
Съобщение 12309, ниво 16, състояние 35, процедура GroupedMedian_2005_2005, формуляра на S. INSERT…VALUES…, които вмъкват множество редове, не се поддържат с компилираните в собствената си съхранени процедури.
Съобщение 10794, ниво 16, състояние 53, процедура GroupedMedian_2005_2
Операторът 'APPLY' не се поддържа с компилирани в оригинал съхранени процедури. 
Съобщение 12311, ниво 16, състояние 37, процедура GroupedMedian_2005_2
Подзаявките (заявки, вложени в друга заявка) не се поддържат с компилирани в собствен произход съхранени процедури.
Съобщение 10794, ниво 16, състояние на процедурата GroupedMedian_2005_2
Агрегираната функция 'ROW_NUMBER' не се поддържа с компилираните в оригинал процедури.

Съобщение 12310, ниво 16, състояние 36, процедура GroupedMedian_2005_3
Общите таблици са изрази не се поддържа с нативно компилиран съхранен процедури.
Съобщение 12311, ниво 16, състояние 37, процедура GroupedMedian_2005_3
Подзаявките (заявки, вложени в друга заявка) не се поддържат с компилираните в оригинал съхранени процедури.
Съобщение 10794, ниво 916 , Процедура GroupedMedian_2005_3
Агрегираната функция 'ROW_NUMBER' не се поддържа с компилираните в оригинал процедури.
Съобщение 10794, ниво 16, състояние 53, процедура GroupedMedian_2005_3
Операторът не се поддържа с'операторът не се поддържа собствено компилирани съхранени процедури.

Съобщение 12311, ниво 16, състояние 37, процедура GroupedMedian_2005_4
Подзаявките (заявки, вложени в друга заявка) не се поддържат с естествено компилирани съхранени процедури.
Msg. 10794, ниво 16, състояние 91, процедура GroupedMedian_2005_4
Агрегираната функция 'ROW_NUMBER' не се поддържа с компилирани в собствен произход съхранени процедури.
Съобщение 10794, ниво 16, състояние 56, оператор за процедура_4_групиран
 „IN“ не се поддържа с собствено компилиран хранилище ed процедури.

Съобщение 12311, ниво 16, състояние 37, процедура GroupedMedian_2012_1
Подзаявките (заявки, вложени в друга заявка) не се поддържат с компилирани в оригинал съхранени процедури.
Съобщение 10794, Ниво 16, състояние 38, процедура GroupedMedian_2012_1
Операторът 'OFFSET' не се поддържа с компилирани в собствен произход съхранени процедури.
Съобщение 10794, ниво 16, състояние 53, процедура GroupedMedian_2012The_1'APPLY' не се поддържа с оригинално компилирани съхранени процедури.

Съобщение 12311, ниво 16, състояние 37, процедура GroupedMedian_2012_2
Подзаявките (заявки, вложени в друга заявка) не се поддържат с естествено компилирани съхранени процедури.
Съобщение 10794, ниво 16, състояние 90, процедура GroupedMedian_2012_2
Агрегираната функция 'PERCENTILE_CONT' не се поддържа с компилирани в собствен произход съхранени процедури. 

 Както е написано понастоящем, нито една от тези заявки не може да бъде пренесена в собствено компилирана съхранена процедура. Може би нещо, което да разгледате за друга последваща публикация.
 
Заключение
 

 Отхвърляне на резултатите от Hekaton и когато е налице поддържащ индекс, заявката на Питър Ларсон ("2012+ 1") с помощта на OFFSET/FETCH излезе като далечен победител в тези тестове. Макар и малко по-сложно от еквивалентната заявка в неразделените тестове, това съвпада с резултатите, които наблюдавах последния път. 
 

 В същите тези случаи 2000 MIN/MAX подход и PERCENTILE_CONT() от 2012 г излязоха като истински кучета; отново, точно както предишните ми тестове срещу по-простия случай.
 

 Ако все още не сте на SQL Server 2012, тогава следващата ви най-добра опция е "2005+ 3" (ако имате поддържащ индекс) или "2005+ 2", ако имате работа с купчина. Съжалявам, че трябваше да измисля нова схема за именуване за тях, най-вече за да избегна объркване с методите в предишната ми публикация.
 

 Разбира се, това са моите резултати спрямо много специфична схема и набор от данни – както при всички препоръки, трябва да тествате тези подходи спрямо вашата схема и данни, тъй като други фактори могат да повлияят на различни резултати.
 
Една друга бележка
 

 В допълнение към това, че е лошо представяне и не се поддържа в компилираните на собствени процедури съхранени процедури, една друга болезнена точка на PERCENTILE_CONT() е, че не може да се използва в по-стари режими на съвместимост. Ако опитате, получавате тази грешка:
 Msg 10762, ниво 15, състояние 1
Функцията PERCENTILE_CONT не е разрешена в текущия режим на съвместимост. Разрешено е само в режим 110 или по-висок.