Approximative Aggregation für große Datenmengen: HyperLogLog und Co

1. Warum exakte Aggregation bei großen Datenmengen an Grenzen stößt

Approximative Aggregation löst ein Problem, das bei wachsenden Datenmengen unvermeidlich auftritt: COUNT(DISTINCT spalte) muss intern jeden einzelnen bereits gesehenen Wert vorhalten, um Duplikate zuverlässig zu erkennen, meist in einer Hash-Tabelle oder einer sortierten Zwischenstruktur. Bei einer Tabelle mit einigen Tausend Zeilen ist das trivial, bei mehreren Milliarden eindeutigen Werten wird der Speicherbedarf und die Laufzeit für ein exaktes Ergebnis jedoch schnell unpraktikabel, besonders wenn die Kennzahl in einem interaktiven Dashboard live berechnet werden soll.

Approximative Aggregation begegnet diesem Problem mit probabilistischen Algorithmen, die nicht jeden einzelnen Wert exakt vorhalten, sondern eine kompakte statistische Zusammenfassung, einen sogenannten Sketch, aus dem Schätzwerte mit einer bekannten, kontrollierbaren Fehlerspanne abgeleitet werden. Der zentrale Kompromiss lautet: ein kleiner, vorab festgelegter relativer Fehler von meist unter zwei Prozent wird akzeptiert, im Gegenzug sinken Speicherbedarf und Laufzeit um Größenordnungen, oft von mehreren Gigabyte Zwischenspeicher auf wenige Kilobyte pro Sketch.

Dieser Artikel erklärt das Funktionsprinzip von HyperLogLog für Distinct-Zählungen und von t-digest für Perzentil-Schätzungen, zeigt konkrete SQL-Syntax verschiedener Datenbankplattformen für approximative Aggregation, und grenzt klar ab, in welchen Reporting-Szenarien exakte Werte weiterhin unverzichtbar bleiben.

2. HyperLogLog: das Prinzip hinter der Distinct-Schätzung

HyperLogLog ist der bekannteste Algorithmus für approximative Aggregation von Distinct-Zählungen und basiert auf einer eleganten statistischen Beobachtung: Wird jeder Eingabewert gehasht, verteilen sich die resultierenden Bitmuster gleichmäßig zufällig. Die Wahrscheinlichkeit, unter n zufälligen Bitmustern eines mit vielen führenden Nullen zu finden, hängt direkt von n ab. Aus der längsten beobachteten Folge führender Nullen im Hash lässt sich dadurch die ungefähre Anzahl unterschiedlicher Eingabewerte zurückrechnen, ohne jeden einzelnen Wert gespeichert zu haben.

HyperLogLog verbessert die Genauigkeit dieser Schätzung, indem der Hash-Raum in viele Register aufgeteilt wird, typischerweise mehrere Tausend, wobei jedes Register unabhängig die längste Nullfolge innerhalb seines Teilbereichs speichert. Der Mittelwert über alle Register glättet statistisches Rauschen und liefert bei modernen Implementierungen einen Standardfehler von ungefähr ein bis zwei Prozent, bei einem Speicherbedarf von nur wenigen Kilobyte pro Sketch, unabhängig davon, ob die zugrunde liegende Datenmenge tausend oder zehn Milliarden Zeilen umfasst.

-- Exact COUNT DISTINCT vs. approximate aggregation with HyperLogLog (BigQuery syntax)
SELECT
    DATE_TRUNC(event_date, MONTH) AS month,
    COUNT(DISTINCT user_id)            AS exact_unique_users,     -- slow, scans full data
    APPROX_COUNT_DISTINCT(user_id)     AS approx_unique_users     -- fast, ~1-2% error
FROM events
GROUP BY month
ORDER BY month;

3. APPROX_COUNT_DISTINCT in der Praxis einsetzen

Die meisten großen Analytics-Datenbanken bieten approximative Aggregation über eine direkte, einfach zu nutzende Funktion an, ohne dass Entwickler den zugrunde liegenden HyperLogLog-Algorithmus selbst implementieren müssten. BigQuery kennt APPROX_COUNT_DISTINCT als direkten Ersatz für COUNT(DISTINCT spalte), Redshift bietet dieselbe Funktion unter identischem Namen, PostgreSQL benötigt für native HyperLogLog-Unterstützung die Extension hll, und ClickHouse liefert mit uniqHLL12 eine eigene, performanceoptimierte Variante direkt im Kern der Datenbank.

Der praktische Einsatz von APPROX_COUNT_DISTINCT unterscheidet sich syntaktisch kaum von COUNT(DISTINCT spalte), was den Umstieg auf approximative Aggregation in bestehenden Reports meist auf eine einfache Funktionsersetzung reduziert. Wichtig ist, vor der Umstellung zu prüfen, ob die konkrete Kennzahl eine exakte Zahl fachlich zwingend benötigt, etwa bei finanzieller Berichterstattung, oder ob eine Schätzung mit ein bis zwei Prozent Fehler für den Anwendungsfall, etwa ein Analytics-Dashboard mit Nutzerzahlen, völlig ausreichend ist.

-- Approximate aggregation across different database platforms
-- PostgreSQL with the hll extension
SELECT hll_cardinality(hll_add_agg(hll_hash_text(user_id))) AS approx_unique_users
FROM events;

-- ClickHouse native approximate distinct count
SELECT uniqHLL12(user_id) AS approx_unique_users
FROM events;

-- Redshift, syntax identical to BigQuery
SELECT APPROX_COUNT_DISTINCT(user_id) AS approx_unique_users
FROM events;

4. Sketches kombinieren: Union über mehrere Partitionen

Ein entscheidender Vorteil von approximativer Aggregation gegenüber exakter Distinct-Zählung zeigt sich beim Kombinieren von Teilergebnissen aus verschiedenen Partitionen oder vorab berechneten Zeiträumen. Ein HyperLogLog-Sketch für Januar und ein separater Sketch für Februar lassen sich mathematisch korrekt zu einem gemeinsamen Sketch für Januar bis Februar zusammenführen, ohne die zugrunde liegenden Rohdaten erneut lesen zu müssen, weil die Union zweier HyperLogLog-Register bitweise durch Maximumbildung erfolgt.

Diese Eigenschaft macht approximative Aggregation besonders wertvoll für inkrementelle Reporting-Pipelines: Statt jeden Monat die komplette Historie neu zu scannen, um eine kumulative Distinct-Zählung zu aktualisieren, wird lediglich ein neuer Sketch für den aktuellen Monat berechnet und mit den bereits gespeicherten Sketches der Vormonate vereinigt. Eine exakte COUNT(DISTINCT)-Berechnung böte diese Eigenschaft nicht, weil sich zwei exakte Distinct-Mengen nicht ohne Zugriff auf die vollständigen Ursprungsdaten korrekt vereinigen lassen.

-- Merging pre-computed HyperLogLog sketches across months (BigQuery)
WITH monthly_sketches AS (
    SELECT
        DATE_TRUNC(event_date, MONTH) AS month,
        HLL_COUNT.INIT(user_id) AS sketch
    FROM events
    GROUP BY month
)
SELECT
    HLL_COUNT.MERGE(sketch) AS approx_unique_users_year_to_date
FROM monthly_sketches
WHERE month BETWEEN '2026-01-01' AND '2026-06-30';
-- No need to re-scan raw events, sketches are merged directly

5. t-digest und Perzentil-Schätzung bei großen Datenmengen

Neben Distinct-Zählungen betrifft approximative Aggregation auch Perzentil-Berechnungen, die bei sehr großen Datenmengen ebenfalls teuer werden, weil eine exakte Perzentil-Berechnung eine vollständige Sortierung aller Werte voraussetzt. Der t-digest-Algorithmus löst dieses Problem, indem er die Wertverteilung in eine variable Anzahl von Clustern zusammenfasst, wobei Cluster an den Rändern der Verteilung, dort wo Perzentile wie P95 oder P99 typischerweise interessieren, feiner aufgelöst werden als Cluster in der Mitte der Verteilung.

Diese ungleichmäßige Auflösung ist der entscheidende Designtrick von t-digest bei approximativer Aggregation: Für den Median, also P50, reicht eine grobe Schätzung meist aus, während extreme Perzentile wie P99 oder P99.9 in Monitoring- und Latenz-Reports besonders wichtig sind und deshalb mit höherer Präzision abgebildet werden. Datenbanken wie ClickHouse und Analytics-Plattformen wie Druid bieten t-digest-basierte Perzentilfunktionen nativ an, wodurch sich P95-Latenzen über Milliarden von Log-Zeilen in Millisekunden statt Minuten berechnen lassen.

-- Approximate percentile estimation with t-digest style functions (ClickHouse)
SELECT
    endpoint,
    quantile(0.50)(response_time_ms) AS p50_approx,
    quantile(0.95)(response_time_ms) AS p95_approx,
    quantile(0.99)(response_time_ms) AS p99_approx
FROM request_logs
GROUP BY endpoint;

6. Fehlergrenzen verstehen und kontrollieren

Der Fehler bei approximativer Aggregation ist kein zufälliges Rauschen, sondern eine bekannte, mathematisch herleitbare Größe, die sich über die Anzahl der verwendeten Register oder Cluster gezielt steuern lässt. Bei HyperLogLog sinkt der relative Standardfehler ungefähr proportional zu eins geteilt durch die Wurzel aus der Registeranzahl, sodass eine Verdopplung der Register den Fehler um etwa 30 Prozent reduziert, allerdings auch den Speicherbedarf pro Sketch verdoppelt.

Diese Beziehung zwischen Genauigkeit und Ressourcenverbrauch ist bei approximativer Aggregation bewusst konfigurierbar, nicht fest vorgegeben. Für ein internes Analytics-Dashboard, bei dem ein Fehler von zwei Prozent bei Nutzerzahlen niemand bemerkt, reicht die Standardkonfiguration meist völlig aus. Für eine Kennzahl, die in einer regulatorischen Meldung oder einer Abrechnung mit Kunden auftaucht, sollte approximative Aggregation dagegen entweder mit deutlich mehr Registern konfiguriert oder komplett durch exakte Berechnung ersetzt werden.

-- BigQuery: trading precision for cost via the optional precision parameter
SELECT
    -- Default precision, ~1-2% relative error, smallest sketch
    APPROX_COUNT_DISTINCT(user_id) AS approx_default,
    -- HLL_COUNT.INIT allows explicit precision control (10-24, higher = more accurate)
    HLL_COUNT.EXTRACT(HLL_COUNT.INIT(user_id, 20)) AS approx_higher_precision
FROM events;

7. Typische Anwendungsfälle: Analytics, Monitoring, Reichweite

Approximative Aggregation hat sich in drei Bereichen als Standardwerkzeug etabliert. Im Web- und Produkt-Analytics werden tägliche, wöchentliche und monatliche aktive Nutzerzahlen fast ausschließlich approximativ berechnet, weil die absolute Präzision einer einzelnen Nutzerzahl geschäftlich irrelevant ist, solange der Trend über die Zeit korrekt sichtbar bleibt. Im Infrastruktur-Monitoring werden Latenz-Perzentile wie P95 und P99 über riesige Mengen an Log-Zeilen fast durchgängig mit t-digest-artigen Algorithmen geschätzt, weil eine exakte Sortierung von Milliarden Log-Einträgen pro Minute die Monitoring-Pipeline selbst überlasten würde.

Der dritte klassische Anwendungsfall ist die Reichweitenmessung in Werbe- und Marketing-Systemen, bei der die Anzahl eindeutig erreichter Nutzer über mehrere Kampagnen und Kanäle hinweg geschätzt werden muss. Da sich HyperLogLog-Sketches wie in Abschnitt vier beschrieben mengentheoretisch korrekt vereinigen lassen, kann approximative Aggregation hier sogar Überschneidungen zwischen Kampagnen abschätzen, eine Berechnung, die mit exakten Zählungen bei der schieren Datenmenge kommerzieller Werbeplattformen praktisch nicht mehr durchführbar wäre.

8. Wann approximative Aggregation die falsche Wahl ist

So nützlich approximative Aggregation auch ist, es gibt klare Grenzen, an denen exakte Berechnung zwingend bleibt. Finanzielle Kennzahlen wie Umsatzsummen, Kontostände oder Steuerbeträge dürfen niemals approximiert werden, weil bereits ein Bruchteil eines Prozents Abweichung rechtliche und buchhalterische Konsequenzen haben kann. Ebenso ungeeignet ist approximative Aggregation für kleine Datenmengen, bei denen exakte Berechnung ohnehin schnell genug ist und die eingesparte Zeit die zusätzliche Komplexität eines Sketch-basierten Ansatzes nicht rechtfertigt.

Ein weiterer Fall, in dem approximative Aggregation vermieden werden sollte, betrifft Kennzahlen mit sehr kleinen absoluten Werten, etwa eine Distinct-Zählung von unter hundert eindeutigen Werten. HyperLogLog liefert bei solchen kleinen Kardinalitäten proportional größere relative Fehler als bei Millionen von Werten, weil der Algorithmus für große Zahlenbereiche optimiert ist. Für kleine, präzisionskritische Zählungen bleibt eine exakte COUNT(DISTINCT)-Abfrage die richtige und ohnehin performante Wahl.

9. Exakte vs. approximative Aggregation im Vergleich

Die folgende Übersicht fasst zusammen, wann exakte und wann approximative Aggregation die passende Wahl ist.

Die Wahl zwischen exakter und approximativer Aggregation ist keine reine Performance-Frage, sondern eine bewusste fachliche Entscheidung, die abwägt, ob die Kennzahl absolute Präzision erfordert oder ob ein kleiner, kontrollierter Fehler für den jeweiligen Anwendungsfall wirtschaftlich vertretbar ist.

Wer approximative Aggregation gezielt für die richtigen Kennzahlen einsetzt und exakte Berechnung dort belässt, wo sie fachlich unverzichtbar ist, gewinnt bei großen Datenmengen erhebliche Performance, ohne die Verlässlichkeit kritischer Zahlen zu gefährden.

10. Zusammenfassung

Approximative Aggregation ersetzt exakte Berechnungen wie COUNT(DISTINCT) oder Perzentile durch probabilistische Algorithmen wie HyperLogLog und t-digest, die bei sehr großen Datenmengen einen kontrollierten, meist ein bis zwei Prozent betragenden Fehler gegen erhebliche Performance- und Speichervorteile eintauschen. HyperLogLog schätzt Distinct-Zählungen über Hash-basierte Register, t-digest schätzt Perzentile über eine ungleichmäßig aufgelöste Cluster-Struktur.

Der besondere Vorteil approximativer Aggregation liegt in der Kombinierbarkeit von Sketches über Partitionsgrenzen hinweg, was inkrementelle Reporting-Pipelines erst praktikabel macht. Finanzielle Kennzahlen und kleine Datenmengen bleiben dagegen weiterhin eine Domäne exakter Berechnung, weil dort entweder Präzision zwingend erforderlich ist oder der Performance-Vorteil approximativer Aggregation den zusätzlichen Aufwand nicht rechtfertigt.

11. FAQ: Approximative Aggregation