Das Median-Problem, Teil 1

Der SQL Server 2005 bietet erstmals die Möglichkeit benutzerdefinierte Aggregatfunktionen zu entwickeln. Als ich über das Thema zum ersten Mal las, fand ich es ganz spannend und begann sogleich meine eigene Aggregatfunktion, namens „Median“ zu implementieren.

Bei Median geht es darum - ähnlich wie bei AVG() - den Mittelwert einer Ergebnismenge zu berechnen. Doch anders als AVG() berechnet Median nicht den Durchschnittswert, sondern ermittelt stattdessen den Wert, der in der Mitte einer sortierten Liste steht. Dieses Verfahren wird gerne im statistischen Bereich verwendet, da das Ergebnis hierbei nicht durch einzelne extrem kleine oder große Werte verfälscht wird.

Soweit der Plan. Doch schauen wir uns das mal aus der Nähe an:

[Serializable]
[SqlUserDefinedAggregate(
    Format.UserDefined,
    IsInvariantToDuplicates=true,
    MaxByteSize=8000)]
public struct Median : IBinarySerialize
{
    private ArrayList m_values;

    public void Init()
    {
        m_values = new ArrayList();
    }

    public void Accumulate(SqlMoney Value)
    {
        if (Value.IsNull)
            return;

        m_values.Add(Value.ToDecimal());
    }

    public void Merge(Median Group)
    {
        m_values.AddRange(Group.m_values);
    }

    public SqlMoney Terminate()
    {
        return new SqlMoney(
            (Decimal)m_values[m_values.Count / 2]);
    }
        ...
}

Zunächst lege ich die Membervariable m_values an, in die ich alle Werte speichere, die über die Accumulate() bzw. Merge()-Methode herein kommen. Zuletzt wird die Terminate()-Methode aufgerufen, in der ich den mittleren Wert der Liste ermittle.

Diese Aggregatfunktion könnte ich nun in T-SQL wie folgt verwenden:

SELECT Median(LineTotal) AS TheMedian
FROM Sales.SalesOrderDetail
ORDER BY LineTotal

Das sieht ja zunächst ganz brauchbar aus. Doch bei näherer Betrachtung stellt man fest, dass diese Lösung auf Sand gebaut ist. Der Grund hierfür ist, dass die Größe einer Aggregatinstanz 8K nicht übersteigen darf. Da das Aggregat die Werte zwischenspeichert, wächst die Größe jedoch stetig an, was dazu führt, das nach 500 Zeilen ein Fehler ausgelöst wird (16 Bytes * 500 = 8K).

Letztendlich macht die Limitation Sinn, da die Verfügbarkeit bei sehr großen Ergebnismengen in Mitleidenschaft gezogen werden kann. Doch wie ermittle ich nun meinen Median? Im zweiten Teil versuche ich einen anderen Weg.