13 maja 2011

Jak obliczyć medianę przy pomocy funkcji CLR User-Defined Aggregate? - Część 2 QuickSelect po liftingu

Mediana ciąg dalszy nastąpił


W pierszym poście 'Jak obliczyć medianę przy pomocy funkcji CLR User-Defined Aggregate?' został opisany sposób implmentacji funkcji agregującej (User-Defined Aggregate function) za pomocą .NET CLR w MS SQL Server 2008, a przy okazji został wykorzystany prosty algorytm do obliczania mediany.

W poszukiwaniach lepszej wydajności algortytmu obliczania mediany, zaimplementowałem algortym QuickSelect. Implementację QuickSelect'u można znależć w poście 'Algorytm selekcji Hoare'a (QuickSelect) w C# .NET'.

Kod zródłowy projektu jest dostępny tutaj.

QuickSelect po liftingu


Do obliczenia mediany należało zmodyfikować QuickSelect w taki sposób, aby obsługiwał opcję z parzystą liczbą elementów w zbiorze. Przy parzystej liczbie elementów (n) należy wyznaczyć elementy n/2 i (n/2)+1  a następnie obliczyć średnią arytmentyczną dla tych dwóch elementów. Oczywiście można uruchomić dwukrotnie QuickSelect dla k=n/2 i k=n/2 + 1, ale to oznaczałoby utratę wydajności.

Jeżeli wynaczymy n/2 element to znaczy, że w partycji po "prawej" stronie znajduje się element n/2+1. Wystarczy zatem ponowić QuickSelect'a na tej partycji  o ideksach n/2, i lastRightBoundIndex. Algorytm zamieszczam poniżej.


using System;
using System.Collections.Generic;
using System.Data.SqlTypes;

namespace Mulawa.SqlServerStatistical.Algorithms
{
    public class MedianByQuickSelectAlgorithm
    {
        public SqlDouble Calculate(List<SqlDouble> elements)
        {
            SqlDouble medianValue = 0;
            int medianIndex = (elements.Count + 1) / 2 - 1;
            int lastRightIndex;
            int locatedMedianIndex = Select(elements, 
                0, 
                elements.Count - 1, 
                medianIndex, 
                out lastRightIndex);
            medianValue = elements[locatedMedianIndex];
            if (elements.Count % 2 == 0)
            {
                int tmpPlaceHolder;
                int previousTokthIndex = Select(elements, 
                    locatedMedianIndex, 
                    lastRightIndex, 
                    locatedMedianIndex + 1, 
                    out tmpPlaceHolder);
                medianValue = (medianValue + elements[previousTokthIndex]) / 2.0;
            }

            return medianValue;
        }

        private int Select(List<SqlDouble> list, 
            int leftBoundIndex, 
            int rightBoundIndex, 
            int kthElementIndex, 
            out int lastRightBoundIndex)
        {
            int kthElement = -1;
            int leftIndex = leftBoundIndex;
            int rightIndex = rightBoundIndex;
            lastRightBoundIndex = rightBoundIndex;

            while ((leftIndex <= rightIndex))
            {
                int randomPivotIndex = PickRandomPivotIndex(leftIndex, rightIndex);
                int newPivotIndex = PartitionListByPivotValue(list, leftIndex, 
                    rightIndex, randomPivotIndex);

                if (rightIndex != kthElementIndex)
                {
                    lastRightBoundIndex = rightIndex;
                }

                if (newPivotIndex == kthElementIndex)
                {
                    kthElement = newPivotIndex;

                    break;
                }

                if (kthElementIndex < newPivotIndex)
                {
                    rightIndex = newPivotIndex - 1;
                }
                else if (kthElementIndex > newPivotIndex)
                {
                    leftIndex = newPivotIndex + 1;
                }
            }

            return kthElement;
        }

        private int PickRandomPivotIndex(int minimum, int maximum)
        {
            return new Random().Next(minimum, maximum);
        }

        private int PartitionListByPivotValue(List<SqlDouble> list, 
            int leftBoundIndex, 
            int rightBoundIndex, 
            int pivotValueIndex)
        {
            if (leftBoundIndex == rightBoundIndex)
            {
                return leftBoundIndex;
            }

            SqlDouble pivotValue = list[pivotValueIndex];
            SwapValues(list, pivotValueIndex, rightBoundIndex);
            int currentIndex = leftBoundIndex;
            for (int i = leftBoundIndex; i < rightBoundIndex; i++)
            {
                if (list[i] < pivotValue)
                {
                    SwapValues(list, i, currentIndex);
                    currentIndex++;
                }
            }
            SwapValues(list, currentIndex, rightBoundIndex);
            return currentIndex;
        }

        private void SwapValues(List<SqlDouble> list, 
            int value1Index, 
            int value2Index)
        {
            SqlDouble temp = list[value1Index];
            list[value1Index] = list[value2Index];
            list[value2Index] = temp;
        }
    }
}

Implementację funkcji agregującej pozostawiam bez komentarza.

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

namespace Mulawa.SqlServerStatistical.Aggregates
{
    [Serializable]
    [SqlUserDefinedAggregate(
       Format.UserDefined,
      IsInvariantToDuplicates = false,
      IsInvariantToNulls = false,
      IsInvariantToOrder = true,
      IsNullIfEmpty = true,
      Name = "Median_2",
      MaxByteSize = -1
    )]
    public class MedianQuickSelectAggregate : 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(MedianQuickSelectAggregate group)
        {
            _accumulatedItems.AddRange(group.AccumulatedItems);
        }

        public  SqlDouble Terminate()
        {
            MedianByQuickSelectAlgorithm algorithm = 
                                    new MedianByQuickSelectAlgorithm();
            return algorithm.Calculate(AccumulatedItems);
        }

        /// <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);
            }
        }

    }
}

Jak zainstalować funkcję na MS SQL Server?


Do instalacji funkcji agregującej do obliczania mediany, która wykorzystuje QuickSelect wystarczy uruchomić ten skrypt (zakładając, że assembly SqlServerStatistical.dll zawiera klasę MedianQuickSelectAggregate).

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_2]') AND type = N'AF')
  DROP AGGREGATE [dbo].[Median_2]

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


Testowanie wydajności


W tym paragrafie została podjęta próba porównania wydajności funkcji obliczającej medianę za pomocą algortymu QuickSelect i funkcji opsanej w poście 'Jak obliczyć medianę przy pomocy funkcji CLR User-Defined Aggregate?'.

Najpierw wygeneruję dane, około miliona wierszy. Może zająć to kilka minut w zależności od konfiguracji sprzętowej, u mnie było to 10 minut.
USE CLRDatabase
GO
CREATE TABLE GeneratedNumbers (
  Value Float,
  Name NVarchar(30)
)

CREATE TABLE NamesDictionary
(
 Name NVarchar(30) 
)

CREATE CLUSTERED INDEX Idx_1 ON GeneratedNumbers(Name)

INSERT INTO NamesDictionary(Name)
VALUES ('IT Pro'),('.NET Developer'), ('DBA'),('SQL Developer'),
('IT Support'),('SharePoint Developer'), ('Oracle DBA'),('SQL Admin'),
('IT Specialist'),('SharePoint Admin'), ('Oracle Dev'),('SSIS Developer'),
('IT Manager'),('SharePoint IT Pro'), ('Network Admin'),('BI Developer')


DECLARE @n INT = 0 
WHILE ( @n < 1000000)
BEGIN
 DECLARE @name NVarchar(30) = 
(SELECT TOP 1 Name FROM NamesDictionary ORDER BY NEWID())
 INSERT INTO GeneratedNumbers(Name,Value)
 SELECT @name, @n 
 SET @n += 1
END


SELECT COUNT(*) NumbersCount FROM dbo.GeneratedNumbers
Porównanie wykorzystania procesora wypadło na korzysć QuickSelect'a.
SET STATISTICS IO ON
SET STATISTICS TIME ON

SELECT Name, dbo.Median_2(value) Median
  FROM GeneratedNumbers
 GROUP BY Name

SET STATISTICS TIME OFF
SET STATISTICS IO OFF

Czasy wykonania potwierdziły wyższość QuickSelect'a nad sortowaniem.

Median By QuickSelect: SQL Server Execution Times: CPU time = 6139 ms, elapsed time = 4047 ms.
Median by Sort: SQL Server Execution Times: CPU time = 8860 ms, elapsed time = 6807 ms.

Czasy wykonania były mierzone poniższym skryptem.
IF  EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'[dbo].[ExecutionSession]') AND type in (N'U'))
DROP TABLE [dbo].[ExecutionSession]

CREATE TABLE ExecutionSession(SessionId UniqueIdentifier, TimeInMiliSec Int, MetaData NVARCHAR(50))

DECLARE @execCount Int = 0
, @sessionId UNIQUEIDENTIFIER = NEWID()
WHILE @execCount < 10
BEGIN

IF OBJECT_ID('tempdb..#Test') IS NOT NULL DROP TABLE #Test
IF OBJECT_ID('tempdb..#Test2') IS NOT NULL DROP TABLE #Test2

DECLARE @datetime Datetime2 = SYSDATETIME() 

SELECT Name, dbo.Median_2(value) Median
INTO #Test
  FROM GeneratedNumbers
 GROUP BY Name

INSERT INTO ExecutionSession(SessionId, TimeInMiliSec, MetaData)
SELECT @sessionId, DATEDIFF(MILLISECOND, @datetime, SYSDATETIME()), 'Median QuickSelect'

SET @datetime = SYSDATETIME()

SELECT Name, dbo.Median(value) Median
  INTO #Test2
  FROM GeneratedNumbers
 GROUP BY Name

INSERT INTO ExecutionSession(SessionId, TimeInMiliSec, MetaData)
SELECT @sessionId, DATEDIFF(MILLISECOND, @datetime, SYSDATETIME()), 'Median'

SET @execCount += 1

END

SELECT @sessionId AS SessionId 

SELECT SessionId,MetaData
, MIN(TimeInMiliSec) MinimumExecTime
,  MAX(TimeInMiliSec) MaximumExecTime
, AVG(TimeInMiliSec) AvgExecTime
, dbo.Median_2(TimeInMiliSec) MedianExecTime
, COUNT(*) ExecCount
FROM ExecutionSession
GROUP BY SessionId, MetaData

Czasy wykonania:

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.