Freitag, August 08, 2014

APPROX_COUNT_DISTINCT

Eigentlich stand auf meinem Erledigungszettel die Idee, eine kurze Untersuchung der in 12.1.0.2 neu eingeführten APPROX_COUNT_DISTINCT Funktion durchzuführen, mit deren Hilfe man die ungefähre Anzahl der distinkter Werte in einer Spalte effizient ermitteln können soll - aber Luca Canali hat gerade einen entsprechenden Artikel veröffentlicht und so genau wie der Herr Canali hätte ich mir den Fall ohnehin nicht angeschaut. Hingewiesen wird im Artikel unter anderem auf folgende Punkte:
  • beim count(distinct column_value) hängt die Performance entscheidend von der Notwendigkeit großer Sortierungen ab - und damit von der Spaltenbreite und der Anzahl distinkter Werte: je breiter die Spalten und je näher die Anzahl unterschiedlicher Werte an die Satzanzahl heranreicht, desto teurer werden die Sortierungen (inklusive temp I/O waits).
  • APPROX_COUNT_DISTINCT basiert auf einem Verfahren, dass eine geringe Memory-Nutzung erfordert und das gut skaliert. Bezahlt wird diese Optimierung mit einem Verzicht auf vollständige Genauigkeit: wie der Name der Funktion schon andeutet, wird nicht gezählt, sondern überschlagen.
  • In den Tests des Herrn Canali ergibt sich eine massive Beschleunigung der Operationen bei einer recht hohen Genauigkeit. Dabei betrifft die Beschleunigung natürlich in erster Linie die Fälle, in denen das exakte Zählen kostspielig wird (also: viele distinkte Werte, breite Spalten) - für Spalten mit sehr niedriger Kardinalität nähert sich die Laufzeit beider Operationen der Zeit, die für das Lesen der Daten (über FTS oder IFFS) benötigt wird.
  • der APPROX_COUNT_DISTINCT-Aufruf lässt sich sehr gut parallelisieren.
  • hinter der neuen Funktion steht der HyperLogLog (HLL) Algorithmus, den Alex Fatkulin (in einem bei Luca Canali verlinkten Artikel) folgendermaßen erläutert: "in a nutshell, it relies on counting the number of trailing (or leading) zeroes in the binary stream and using that information to estimate number of unique values with a very high degree of accuracy."
  • im Flame Graph der Operation (ohne den zu ergänzen der Herr Canali dieser Tage keinen Artikel beendet) findet man den Aufruf von qesandvHllAdd.
  • nicht ganz klar ist mir, ob der verwendete Algorithmus mit dem des in der Statistikerzeugung verwendeten approximate NDV identisch ist - Christian Antognini scheint das zu verneinen.
Für geeignete Fragestellungen sollte die Funktion jedenfalls ziemlich nützlich sein.

Nachtrag 23.10.2014: Christian Antognini zeigt, dass die Genauigkeit der Funktion für numerische Werte recht gut ist (Abweichung höchstens 4%), bei deutlich reduzierter Ressourcennutzung und erhöhter Performance gegenüber der Standardfunktion.

2 Kommentare:

  1. Gut zu wissen :)

    Vielleicht auch noch interessant: der Key-Value Store Redis (http://redis.io) hat Anfang diesen Jahres auch Unterstützung zu HyperLogLog eingebaut.
    Dazu hat der Author von Redis, Salvatore Sanfilippo , in seinem Blog ein paar anschauliche Erklärungen zum Verfahren gegeben: http://antirez.com/news/75

    T.

    AntwortenLöschen
  2. Hi Thomas,
    Danke für die Ergänzung - das Verfahren wirkt so einfach und elegant, dass ich annehme, dass es bei recht vielen Systemen implementiert werden wird, in denen es zur Zeit noch fehlt.
    Gruß
    Martin

    AntwortenLöschen