07 maja 2011

Jak obliczyć medianę przy pomocy funkcji CLR User-Defined Aggregate?

1.Dwa słowa o medianie


Jednym z podstawowych terminów w statystyce jest mediana (median). Jej definicja jest intuicyjna i prosta do zrozumienia. Z tego powodu została wybrana do zaprezentowania koncepcji implementacji przy użyciu .NET CLR funkcji agregującej (User-Defined Aggregate function) w MS SQL Server. Mediana jest wartością środkową posortowanego szeregu danych. Jeżeli liczba n-elementów jest nieparzysta to miediana jest równa elementowi o indeksie (n+1)/2. Natomiast, jeżeli liczba elementów szeregu jest parzysta, to średnia arytmentyczna dwóch środkowych elemetów jest wartością mediany.

Przykładowe obliczenia mediany dla zbiorów Y z liczbą elementów parzystą i nieparzystą.

 Y = [1, 2, 3, 4, 8, 9, 11]
 Mediana (Y) =  4

Y =   [1, 2, 3, 4, 8, 9, 11, 12]
Mediana (Y) = (4 + 8)/2 = 6


Bardziej formalną definicję mediany można znaleść na wikipedii (polecam wersję angielską jako że autor bardziej wyczerpująco podszedł do tematu).    

Kod źrodłowy jest do ściągnięcia tutaj.

Implementacja algorytmu QuickSelect przy obliczeniu mediany została opisana w poście 'Jak obliczyć medianę przy pomocy funkcji CLR User-Defined Aggregate? - Część 2 QuickSelect po liftingu'.

2. Jak można policzyć medianę w MS SQL Server?


Medianę w SQL Server można liczyć przy użyciu skryptu w T-SQL'u , można też zaimplmenetować funkcję agregującą  (User-Defined Aggregate) przy użyciu .NET Framework. W tym arktykule skupimy się na implementacji funkcji agregującej w języku C#.

Funkcja agregująca musi być zaimplementowana jako klasa lub struktura. Klasa funkcji powinna być opatrzona atrybutem SqlUserDefinedAggregateAttribute. Atrybut ten posiada kilka istotnych właściwości, których konfiguracja jest bardzo ważna dla implementacji funkcji. 

Właściwości SqlUserDefinedAggregateAttribute

  • Format - klasa funkcji agregującej może być serializowana w czasie obliczania wartości funkcji. Programista może użyć standardowej serializacji poprzez wybranie Format.Native lub zdecydować się na Format.UserDefined Type co wymusi implemetację interfejsu IBinarySerialize.
  • IsInvariantToDuplicates - określa czy pojawienie się duplikatów wartości (tych samych wierszy) wpłynie na wynik agregacji. W przypadku mediany duplikaty mają wpływ na wynik, natomiast w przypadku funkcji liczącej minimum duplikaty nie zmieniłyby wyniku obliczeń. 
  • IsInvariantToNulls - atrybut wpływa na to, czy funkcja przyjmuje wartości NULL
  • IsInvariantToOrder - atrybut określa czy kolejność danych wpływa na wyniki obliczeń, w przypaku mediany nie ma to znaczenia
  • IsNullIfEmpty  - określa czy jeżeli nie ma wierszy do procesowania to można zwrócić od razu wartość NULL 
  • MaxByteSize - określa maksymalną wielkość instancji klasy Agregacyjnej , w SQL Server 2005 było to 8000 bajtów, w SQL Server 2008 zwiększono to do 2GB. MaxByteSize ustawiony na -1 ustala maksymalny rozmiar instancji klasy funkcji agregującej na 2GB. 
  • Name - nazwa funkcji agregującej nadana przy automatycznej instalacji

Każda funkcja agregująca musi zaimplementować następujące metody


public void Init() - metoda ta jest wywoływana przy pierwszym użyciu funkcji agregującej w danym wywołaniu agregacji. Może zdarzyć się tak, że instancja klasy funkcji agregującej będzie użyta wielokrotnie i zadaniem metody Init jest przygotowanie instancji do ponownego użycia.

public void Accumulate(value,...) - metoda jest wywoływana dla każdego wiersza, od MS SQL Server 2008 może posiadać więcej niż jeden argument.

public void Merge(MedianAggregate group) - optymalizator może zrównoleglić oblicznia i zdecydować się na scalenie wyników obliczeń.

public SqlDouble Terminate() - metoda jest wywoływana raz w celu zwrócenia wyniku agregacji.

Serializacja


Instancja funckji agregującej może być wielokrotnie serializowana, programista będzie miał pełną kontrolę nad tym jak instancja funkcji jest deserializowana jeżeli zaimplementuje interfejs IBinarySerialize. Interfejs udostępnia dwie metody:

public void Read(BinaryReader reader) - deserializacja instancji funkcji agregującej.
public void Write(BinaryWriter writer) - serializacja instancji funkcji agregującej.


3. MedianAggregate w całej okazałości



Do implementacji funkcji agregującej dla Mediany wybrałem najprostszy algorytm, który sortuje kolekcję elementów agregowanych przed wyliczeniem. Następnie wylicza wartość mediany w zależności od liczby elementów zbioru.


using System;
using System.Collections.Generic;
using System.Data.SqlTypes;
using System.IO;
using Microsoft.SqlServer.Server;

namespace Mulawa.SqlServerStatistical.Aggregates
{
    [Serializable]
    [SqlUserDefinedAggregate(
       Format.UserDefined, 
      IsInvariantToDuplicates = false, 
      IsInvariantToNulls = false, 
      IsInvariantToOrder = true, 
      IsNullIfEmpty = true, 
      Name = "Median",
      MaxByteSize = -1 
    )]
    public struct MedianAggregate : IBinarySerialize
    {
        private List<SqlDouble> _accumulatedItems;

        public List<SqlDouble> AccumulatedItems
        {
            get { return _accumulatedItems; }
        }

        public void Init()
        {
            _accumulatedItems = new List<SqlDouble>();
        }

        public void Accumulate(SqlDouble value)
        {
            if (!value.IsNull)
            {
                _accumulatedItems.Add(value);
            }
        }

        public void Merge(MedianAggregate group)
        {
            _accumulatedItems.AddRange(group.AccumulatedItems);
        }

        public SqlDouble Terminate()
        {
            return CalculateMedian();
        }

        private SqlDouble CalculateMedian()
        {
            SqlDouble medianValue;
            _accumulatedItems.Sort();
            if (_accumulatedItems.Count % 2 == 1)
            {
                int medianIndex = (_accumulatedItems.Count + 1) / 2 - 1;
                medianValue = _accumulatedItems[medianIndex];
            }
            else
            {
                int medianIndexElem1 = _accumulatedItems.Count / 2;
                int medianIndexElem2 = _accumulatedItems.Count / 2 - 1;
                medianValue = (_accumulatedItems[medianIndexElem1] + 
                    _accumulatedItems[medianIndexElem2]) / 2.0;
            }

            return medianValue;
        }


        /// <summary>
        /// Format
        /// Bytes 1 - 4: list items count
        /// Byter 5 - 5+8xlist.Count : 8 byte floating point numbers
        /// </summary>
        /// <param name="reader"></param>
        public void Read(BinaryReader reader)
        {
            _accumulatedItems = new List<SqlDouble>();
            int itemsCount = reader.ReadInt32();
            for (int i = 0; i < itemsCount; i++)
            {
                _accumulatedItems.Add(
                    new SqlDouble(reader.ReadDouble()));
            }
        }

        public void Write(BinaryWriter writer)
        {
            writer.Write(_accumulatedItems.Count);
            foreach (var value in _accumulatedItems)
            {
                writer.Write(value.Value);
            }
        }
    }
}

4. Instalacja i testowanie


Dokładny opis aktywowania .NET CLR w MS SQL Server można znaleźć w poście Implementacja DML Triggerów w CLR .NET.  

CREATE DATABASE CLRDatabase
GO
USE CLRDatabase
GO
EXEC sp_configure 'show advanced option',1
GO
RECONFIGURE
GO
EXEC sp_configure 'clr enabled',1
GO
RECONFIGURE
GO
IF  EXISTS (SELECT * FROM sys.assemblies asms WHERE asms.name = N'SqlServerStatistical')
  DROP ASSEMBLY [SqlServerStatistical]

CREATE ASSEMBLY [SqlServerStatistical]
AUTHORIZATION [dbo]
FROM 'C:\MaxWorkspace\Blog\SqlServerStatistical\SqlServerStatistical\SqlServerStatistical\bin\Debug\SqlServerStatistical.dll'
WITH PERMISSION_SET = SAFE

IF  EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'[dbo].[Median]') AND type = N'AF')
  DROP AGGREGATE [dbo].[Median]

CREATE AGGREGATE [dbo].[Median]
 (@value [float])
RETURNS[float]
EXTERNAL NAME 
[SqlServerStatistical].[Mulawa.SqlServerStatistical.Aggregates.MedianAggregate] 

Otwierając Management Studio powiniśmy zlokalizować funkcję agregującą w miejscu przedstawionym na obrazku poniżej




Jak to działa?


Skrypt testowy oblicza medianę płac dla trzech przypadków

  1. Mediana dla 3-elementowego zbioru
  2. Mediana dla 4 - elementowego zbioru
  3. Mediana jest liczona dla trzech miast przy użyciu klauzuli GROUP BY

USE CLRDatabase
GO
IF OBJECT_ID('PolishDevelopersSalaries','U') IS NOT NULL DROP TABLE dbo.PolishDevelopersSalaries

CREATE TABLE dbo.PolishDevelopersSalaries
(
 City NVARCHAR(20) NOT NULL,
 Salary FLOAT NOT NULL
) 

TRUNCATE TABLE dbo.PolishDevelopersSalaries

INSERT INTO dbo.PolishDevelopersSalaries(City, Salary)
VALUES ('Warszawa', '4000'),('Poznan', '5000'),('Wroclaw', '6000')

SELECT dbo.Median(pds.Salary)
  FROM dbo.PolishDevelopersSalaries pds

TRUNCATE TABLE dbo.PolishDevelopersSalaries

INSERT INTO dbo.PolishDevelopersSalaries(City, Salary)
VALUES ('Warszawa', '4000'),('Poznan', '5000'),('Wroclaw', '6000'),('Krakow', '7000')

SELECT dbo.Median(pds.Salary)
  FROM dbo.PolishDevelopersSalaries pds

TRUNCATE TABLE dbo.PolishDevelopersSalaries

INSERT INTO dbo.PolishDevelopersSalaries(City, Salary)
VALUES ('Poznan',5021),('Poznan', 5888), ('Poznan',10233), ('Poznan',10742), ('Poznan', 11079)
     , ('Poznan',11502), ('Poznan',11512), ('Poznan',12388), ('Poznan',13362), ('Poznan',14304)
     , ('Warszawa',5738), ('Warszawa',6305),('Warszawa',11010), ('Warszawa', 11292) , ('Warszawa',11830)
     ,('Warszawa', 12055),('Warszawa', 12195), ('Warszawa',12307), ('Warszawa',12447),('Warszawa', 13015)
     , ('Wroclaw',6116) , ('Wroclaw',6905), ('Wroclaw',9747), ('Wroclaw',9951), ('Wroclaw',11298)

SELECT pds.City, dbo.Median(pds.Salary)
  FROM dbo.PolishDevelopersSalaries pds
 GROUP BY pds.City
ORDER BY pds.City 

Wyniki testu:


Skrypty były testowane na następujących konfiguracjach:
  • SQL Server 2008 R2, Developer Edition, 32bit.

Brak komentarzy:

Prześlij komentarz

Uwaga: tylko uczestnik tego bloga może przesyłać komentarze.