Schätzen der Anzahl diskreter Werte

Snowflake verwendet HyperLogLog, um die ungefähre Anzahl diskreter Werte in einem Dataset zu schätzen. HyperLogLog ist ein hochmoderner Algorithmus zur Kardinalitätsschätzung, der in der Lage ist, unterschiedliche Kardinalitäten von Billionen von Zeilen mit einem durchschnittlichen relativen Fehler von wenigen Prozent zu schätzen.

HyperLogLog kann anstelle von COUNT(DISTINCT …) in Situationen verwendet werden, in denen die Schätzung der Kardinalität akzeptabel ist.

Unter diesem Thema:

Ü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 Aggregatfunktionen 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.

„Dense“-Format

version

Versionsnummer der HyperLogLog-Implementierung.

precision

Anzahl der Bits für Hash-Werte, die zur Auswahl von Substreams verwendet werden. Derzeit feste Anzahl von 12.

dense

Ein Array von ganzen Zahlen, jede mit der maximale Anzahl an führenden Nullen + 1 für den entsprechenden Substream enthalten. 0 bedeutet, dass der entsprechende Substream noch nicht belegt wurde. Die gültigen Werte liegen im Bereich von 0 bis 53. Der entsprechende Substream-Index wird durch die Elementposition im Array gegeben.

Beispiel:

{
  "version" : 3,
  "precision" : 12,
  "dense" : [3,3,3,3,5,3,4,3,5,6,2,4,4,7,5,6,6,3,2,2,3,2,4,5,5,5,2,5,5,3,6,1,4,2,2,4,4,5,2,5,...,4,6,3]
}
Copy

„Sparse“-Format

version

Versionsnummer der HyperLogLog-Implementierung.

precision

Anzahl der Bits für Hash-Werte, die zur Auswahl von Substreams verwendet werden. Derzeit feste Anzahl von 12.

sparse

indices: Ein Array von ganzen Zahlen, jede mit jeweils einem Substream-Index (Basis 0). Die gültigen Werte liegen im Bereich von 0 bis 4.095.

maxLzCounts: Ein Array von ganzen Zahlen, jede mit der maximale Anzahl an führenden Nullen + 1 für den entsprechenden Substream. 0 bedeutet, dass der entsprechende Substream noch nicht belegt wurde.

Die gültigen Werte liegen im Bereich von 0 bis 53. Der Substream für eine gegebene Anzahl von führenden Nullen ist durch das entsprechende Element im indices-Array gegeben.

Die Arrays indices und maxLzCounts müssen die gleiche Länge haben. Die Funktion HLL_IMPORT prüft auch, ob sich die Substream-Indizes im gültigen Bereich befinden und ob es keine doppelten Substream-Indizes gibt. Das indices-Array muss nicht sortiert werden. Die Zählungen der führenden Null werden nicht validiert. Ungültige Werte verursachen keine Abfragefehler, sondern führen zu undefinierten Ergebnissen für HLL_ESTIMATE.

Beispiel:

{
  "version" : 3,
  "precision" : 12,
  "sparse" : {
    "indices": [1131,1241,1256,1864,2579,2699,3730],
    "maxLzCounts":[2,4,2,1,3,2,1]
  }
}
Copy

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.