Schätzen häufiger Werte¶
Snowflake verwendet den Space-Saving-Algorithmus, eine speicherplatz- und zeitsparende Methode zum Schätzen von ungefähr häufigen Werten in Datasets.
Unter diesem Thema:
Übersicht¶
Snowflake stellt eine Implementierung des Space-Saving-Algorithmus bereit, der in Effiziente Berechnung von häufigen und Top-k-Elementen in Datenströmen von Metwally, Agrawal und Abbadi vorgestellt wird. Er wird über die APPROX_TOP_K-Funktionsfamilie implementiert.
Zusätzlich verwendet die APPROX_TOP_K_COMBINE-Funktion den parallelen Space-Saving-Algorithmus, der von Cafaro, Pulimeno und Tempesta beschrieben wurde.
Die Fehlerquote des Algorithmus hängt stark davon ab, wie verzerrt die Daten sind und wie viele Zähler im Algorithmus verwendet werden. Wenn die Daten stärker verzerrt sind oder mehr Zähler verwendet werden, ist das Ergebnis genauer.
SQL-Funktionen¶
Die folgenden Aggregatfunktionen sind für die Verwendung von Space-Saving zum Schätzen häufiger Werte vorgesehen:
APPROX_TOP_K: Gibt eine Approximation für häufige Werte in der Eingabe zurück.
APPROX_TOP_K_ACCUMULATE: Überspringt den letzten Schätzschritt und gibt am Ende einer Aggregation den Space-Saving-Status zurück.
APPROX_TOP_K_COMBINE: Kombiniert mehrere Eingabestatus zu einem einzigen Ausgabestatus (d. h. sie werden zusammengeführt).
APPROX_TOP_K_ESTIMATE: Berechnet eine Kardinalitätsschätzung eines Space-Saving-Status, der von APPROX_TOP_K_ACCUMULATE und APPROX_TOP_K_COMBINE erstellt wird.
Implementierungsdetails¶
Jeder Zähler in unserer Implementierung verfolgt ein Element und dessen Häufigkeit. Insbesondere verfolgt unsere Implementierung nicht die Epsilon-Werte von Zählern, da diese nur nützlich sind, um das Ergebnis des Algorithmus zu garantieren, sie werden nicht für den Algorithmus selbst verwendet.
Die maximale Anzahl der Zähler ist auf 100.000 eingestellt. In diesem Fall sind 100.000 Zähler im Speicher gespeichert, aber nur ein Bruchteil davon wird in einem exportierten Status gespeichert.
Die maximale Anzahl von k ist 100.000. Dieser Wert wird automatisch reduziert, wenn nicht alle Werte in die Ausgabe passen.
In den meisten Fällen ist die Laufzeit unserer Implementierung nicht von der Anzahl der Zähler abhängig. Unsere Implementierung stellt sicher, dass die Anzahl der Zähler keinen spürbaren Einfluss auf die Laufzeit des Algorithmus hat.
Jeder Zähler in jedem Aggregationszustand verwendet eine konstante Menge an Speichermehraufwand von etwa 100 Byte. Wenn also eine Aggregation c Zähler verwendet und es g Aggregationsgruppen gibt, verwendet die Aggregation c * g * 100B Arbeitsspeicher zuzüglich Speicher zum Sichern der Werte. Wenn dieser Arbeitsspeicher das gesamte Speicherbudget überschreitet, werden überlaufende Daten auf der Festplatte gespeichert. Dies ist viel weniger Speicher, als die genaue Version verwenden würde, besonders wenn es eine große Anzahl von unterschiedlichen Werten gibt.