Schätzen der Anzahl diskreter Werte¶

Übersicht¶

Snowflake bietet eine verzerrungskorrigierte Implementierung des HyperLogLog-Algorithmus, der in HyperLogLog: Analyse eines nahezu optimalen Kardinalitätsschätzalgorithmus von Flajolet et al. vorgestellt wurde.

Wir empfehlen die Verwendung von HyperLogLog, wenn die Eingabemenge potenziell groß ist und ein ungefähres Ergebnis akzeptabel ist. Der durchschnittliche relative Fehler unserer HyperLogLog-Implementierung (d. h. die durchschnittliche relative Differenz zum entsprechenden COUNT(DISTINCT …)-Ergebnis) beträgt 1,62338 %.

SQL-Funktionen¶

Die folgenden Aggregationsfunktionen sind für die Schätzung der Kardinalität mit HyperLogLog vorgesehen:

• HLL: Gibt eine Approximation der Kardinalität distinkter Werte der Eingabe zurück.

• HLL_ACCUMULATE: Überspringt den letzten Schätzschritt und gibt den HyperLogLog-Status am Ende einer Aggregation zurück.

• HLL_COMBINE: Kombiniert mehrere Eingabestatus zu einem einzigen Ausgabestatus (d. h. sie werden zusammengeführt).

• HLL_ESTIMATE: Berechnet die Kardinalitätsschätzung eines HyperLogLog-Status, der von HLL_ACCUMULATE und HLL_COMBINE generiert wird.

• HLL_EXPORT: Konvertiert HyperLogLog-Status vom BINARY-Format in ein OBJECT-Format (das dann gedruckt und als JSON-Format exportiert werden kann).

• HLL_IMPORT: Konvertiert HyperLogLog-Status vom OBJECT-Format in das BINARY-Format.

Implementierungsdetails¶

Unsere Implementierung wandelt die Eingabezeilen per Hashfunktion in 64-Bit-Werte um, von denen die oberen 12 Bit oder „Genauigkeit“ (wie im HyperLogLog-Algorithmusdokument erwähnt; Details siehe Dokumentenlink oben) verwendet werden, um Eingabewerte in sogenannte Substreams zu partitionieren. Dies ergibt einen durchschnittlichen relativen Fehler von:

sqrt(3*ln(2)-1)/sqrt(2^precision) = 0.0162338 = 1.62338%

Mit anderen Worten, für eine Abfrage, bei der COUNT(DISTINCT …) ein Ergebnis von 1,000,000 zurückgibt, wird HyperLogLog typischerweise einen Bereich von 983,767 bis 1,016,234 zurückgeben.

Für jeden Substream behält HyperLogLog die maximale Anzahl an führenden Nullen bei (zwischen 0 und 52 für 64-Bit-Werte bei Genauigkeit = 12). Die einfachste Repräsentation dieses Status ist ein einfaches Byte-Array mit einem Byte für jeden der 2^12 = 4096 Substreams. Unsere Implementierung benötigt in der Tat maximal 4.096 Byte (2^precision = 2^12 = 4096) Arbeitsspeicher pro Aggregationsgruppe. Technisch gesehen werden pro Substream nur 6 Bit (statt 8 Bit) benötigt, aber wir tauschen etwas Speicherplatzeffizienz gegen mehr Recheneffizienz ein.

Bei kleinen Eingabe-Kardinalitäten werden die meisten Substreams nie belegt. Anstatt also im Voraus einen ganzen Block von 4.096 Byte pro Aggregationsgruppe zu verteilen, verwendet unsere Implementierung eine Speicherplatz-optimierte Darstellung dieses Status, wann immer dies sinnvoll ist. Folglich können die Speicherkosten von HyperLogLog wesentlich niedriger sein als 4.096 Byte pro Aggregationsgruppe (bis zu etwa 32 Byte pro Aggregationsgruppe). Dies ermöglicht eine Kardinalitätsschätzung für viele Aggregationsgruppen (Millionen oder sogar Milliarden, wie durch die GROUP BY- oder OVER-Klausel der Abfrage bestimmt), wobei die Größenordnungen weniger Speicher und CPU-Zeit verbrauchen als entsprechende COUNT(DISTINCT …)-Abfragen.

In dem (seltenen) Fall, dass eine extrem große Eingabetabelle und viele Aggregationsgruppen HyperLogLog dazu veranlassen, das Gesamtspeicherbudget zu überschreiten, ist Snowflake immer noch in der Lage, temporären Speicher per Überlauf zu verwenden und rekursive Aggregationen auszuführen, wie bei jeder anderen Aggregationsfunktion.

Exportiertes Statusformat¶

Der Status des HyperLogLog-Algorithmus kann mit den Funktionen HLL_EXPORT und HLL_IMPORT exportiert und importiert (oder erneut importiert) werden. Der exportierte Status ist vom Typ OBJECT und enthält die folgenden Felder.

Beispiele¶

Einrichtung der Umgebung:*

USE WAREHOUSE dontdrop;
USE DATABASE stressdb;
USE SCHEMA bdb_5nodes;

SELECT COUNT(*) FROM uservisits;

-----------+
 COUNT(*)  |
-----------+
 751754869 |
-----------+

Copy

Schritt 1:

Erstellen einer Tabelle, die das Kalenderdatum (Jahr/Monat/Tag) und die HLL-Struktur enthält. Wir verwenden HLL_EXPORT, um die binäre Struktur als Textobjekt zu speichern:

CREATE OR REPLACE TABLE daily_uniques
AS
SELECT
 visitdate,
 hll_export(hll_accumulate(sourceip)) AS hll_sourceip
FROM uservisits
GROUP BY visitdate;

Copy

Schritt 2:

Wir können die einzigartige IPs nach Monat berechnen, indem wir die HLL-Struktur jedes Tages aus Schritt 1 aggregieren. Wir verwenden HLL_IMPORT, um den Text in die binäre Struktur umzuwandeln, dann HLL_COMBINE, um mehrere HLL-Strukturen zu einer einzigen Struktur zu kombinieren, und dann HLL_ESTIMATE, um die Anzahl der verschiedenen Werte zu berechnen:

SELECT
  EXTRACT(year FROM visitdate) AS visit_year,
  EXTRACT(month FROM visitdate) AS visit_month,
  hll_estimate(hll_combine(hll_import(hll_sourceip))) AS distinct_ips
FROM daily_uniques
WHERE visitdate BETWEEN '2000-01-01' AND '2000-12-31'
GROUP BY 1,2
ORDER BY 1,2;

------------+-------------+--------------+
 VISIT_YEAR | VISIT_MONTH | DISTINCT_IPS |
------------+-------------+--------------+
       2000 |           1 |      1515168 |
       2000 |           2 |      1410289 |
       2000 |           3 |      1491997 |
       2000 |           4 |      1460837 |
       2000 |           5 |      1546647 |
       2000 |           6 |      1485599 |
       2000 |           7 |      1522643 |
       2000 |           8 |      1492831 |
       2000 |           9 |      1488507 |
       2000 |          10 |      1553201 |
       2000 |          11 |      1461140 |
       2000 |          12 |      1515772 |
------------+-------------+--------------+

Elapsed 1.3s

Copy

Vergleichen:

Wir vergleichen die Verwendung der Aggregation mit HLL-Funktionen und mit HLL auf Daten der Detailebene. In diesem Fall entspricht HLL() dem HLL_ESTIMATE(HLL_COMBINE(HLL_IMPORT())) aus Schritt 2:

SELECT
  EXTRACT(year FROM visitdate) AS visit_year,
  EXTRACT(month FROM visitdate) AS visit_month,
  hll(sourceip) AS distinct_ips
FROM uservisits
WHERE visitdate BETWEEN '2000-01-01' AND '2000-12-31'
GROUP BY 1,2
ORDER BY 1,2;

------------+-------------+--------------+
 VISIT_YEAR | VISIT_MONTH | DISTINCT_IPS |
------------+-------------+--------------+
       2000 |           1 |      1515168 |
       2000 |           2 |      1410289 |
       2000 |           3 |      1491997 |
       2000 |           4 |      1460837 |
       2000 |           5 |      1546647 |
       2000 |           6 |      1485599 |
       2000 |           7 |      1522643 |
       2000 |           8 |      1492831 |
       2000 |           9 |      1488507 |
       2000 |          10 |      1553201 |
       2000 |          11 |      1461140 |
       2000 |          12 |      1515772 |
------------+-------------+--------------+

Elapsed 2m 29s

Copy

Es wird deutlich, dass die Aggregation der HLL-Strukturen deutlich schneller ist als die Aggregation über die Basisdaten: in diesem kleinen Beispiel 1,3 Sekunden vs. 149 Sekunden, was einer 100-fachen Beschleunigung der Abfragezeit entspricht.