Sketche

GoogleSQL for BigQuery unterstützt Daten-Skizzen. Eine Daten-Skizze ist eine kompakte Zusammenfassung einer Datenaggregation. Darin werden alle notwendigen Informationen erfasst, um entweder ein Aggregationsergebnis zu extrahieren, eine Datenaggregation fortzusetzen oder die Skizze mit einer anderen Skizze zusammenzuführen und damit eine neue Aggregation zu ermöglichen.

Die Berechnung eines Messwerts mit einer Skizze ist wesentlich kostengünstiger als die Berechnung eines genauen Werts. Wenn eine Berechnung zu langsam ist oder zu viel temporären Speicher erfordert, können Sie mit Skizzen die Abfragezeit und -ressourcen reduzieren.

Darüber hinaus ist die Berechnung von Kardinalitäten wie der Anzahl eindeutiger Nutzer oder Quantile wie der Medianwert für Besuchsdauer ohne Skizzen in der Regel nur möglich, wenn Jobs für die Rohdaten ausgeführt werden, da bereits aggregierte Daten nicht mehr kombiniert werden können.

Nehmen wir eine Tabelle mit den folgenden Daten:

Die Gesamtzahl der Nutzer für beide Produkte kann nicht berechnet werden, da in der Tabelle nicht angegeben ist, wie viele Nutzer beide Produkte verwendet haben. Ebenso ist die Berechnung des Medianwerts für die Besuchsdauer nicht möglich, da die Verteilung der Besuchsdauern verloren gegangen ist.

Eine Lösung besteht darin, Skizzen in der Tabelle zu speichern. Jede Skizze ist eine ungefähre und kompakte Darstellung eines bestimmten Eingabeattributs (z. B. Kardinalität), die Sie speichern, zusammenführen (neu aggregieren) und für nahezu genaue Ergebnisse abfragen können. Im vorherigen Beispiel können Sie die Anzahl eindeutiger Nutzer für Produkt A und Produkt B schätzen, indem Sie die Skizzen für jedes Produkt erstellen und wieder zusammenführen. Sie können auch den Medianwert der Besuchsdauer mit Quantilskizzen schätzen, die Sie ebenfalls zusammenführen und abfragen können.

In der folgenden Abfrage werden beispielsweise HLL++- und KLL -Skizzen verwendet, um die Anzahl eindeutiger Nutzer und den Medianwert für die Besuchsdauer für YouTube (Produkt A) und Google Maps (Produkt B) zu schätzen:

-- Build sketches for YouTube stats.
CREATE TABLE user.YOUTUBE_ACCESS_STATS
AS
SELECT
  HLL_COUNT.INIT(user_id) AS distinct_users_sketch,
  KLL_QUANTILES.INIT_INT64(visit_duration_ms) AS visit_duration_ms_sketch,
  hour_of_day
FROM YOUTUBE_ACCESS_LOG()
GROUP BY hour_of_day;

-- Build sketches for Maps stats.
CREATE TABLE user.MAPS_ACCESS_STATS
AS
SELECT
  HLL_COUNT.INIT(user_id) AS distinct_users_sketch,
  KLL_QUANTILES.INIT_INT64(visit_duration_ms) AS visit_duration_ms_sketch,
  hour_of_day
FROM MAPS_ACCESS_LOG()
GROUP BY hour_of_day;

-- Query YouTube hourly stats.
SELECT
  HLL_COUNT.EXTRACT(distinct_users_sketch) AS distinct_users,
  KLL_QUANTILES.EXTRACT_POINT_INT64(visit_duration_ms_sketch, 0.5)
  AS median_visit_duration, hour_of_day
FROM user.YOUTUBE_ACCESS_STATS;

-- Query YouTube daily stats.
SELECT
  HLL_COUNT.MERGE(distinct_users_sketch),
  KLL_QUANTILES.MERGE_POINT_INT64(visit_duration_ms_sketch, 0.5)
  AS median_visit_duration, date
FROM user.YOUTUBE_ACCESS_STATS
GROUP BY date;

-- Query total stats across YouTube and Maps.
SELECT
  HLL_COUNT.MERGE(distinct_users_sketch) AS unique_users_all_services,
  KLL_QUANTILES.MERGE_POINT_INT64(visit_duration_ms_sketch, 0.5)
    AS median_visit_duration_all_services,
FROM
  (
    SELECT * FROM user.YOUTUBE_ACCESS_STATS
    UNION ALL
    SELECT * FROM user.MAPS_ACCESS_STATS
  );

Da eine Skizze eine verlustbehaftete Komprimierung der ursprünglichen Daten aufweist, führt sie zu einem statistischen Fehler, der durch ein Fehlerlimit oder Konfidenzintervall (Confidence Interval, CI) dargestellt wird. Bei den meisten Anwendungen ist diese Unsicherheit klein. Eine typische Skizze mit Kardinalitätszählung hat beispielsweise einen relativen Fehler von etwa 1 % in 95 % aller Fälle. Skizzen weisen ein geringeres Maß an Accuracy bzw. Precision zugunsten schnellerer und kostengünstigere Berechnungen auf.

Eine Skizze hat die folgenden wesentlichen Eigenschaften:

• Sie stellt eine ungefähre Zusammenfassung für einen bestimmten Messwert dar.
• Sie ist kompakt.
• Sie ist eine serialisierte Form einer sublinearen Datenstruktur im Speicher.
• Sie ist in der Regel eine feste Größe und asymptotisch kleiner als die Eingabe.
• Sie kann einen statistischen Fehler verursachen, den Sie mit einer Precision-Stufe ermitteln.
• Sie kann mit anderen Skizzen zusammengeführt werden, um die Vereinigung der zugrunde liegenden Datasets zusammenzufassen.

Neuaggregation mit Skizzenzusammenführung

Skizzen ermöglichen das Speichern und Zusammenführen von Daten für eine effiziente Neuaggregation. Dadurch sind Skizzen besonders nützlich für das Speichern vorab berechneter Zusammenfassungen von Datasets, die als materialisierte Ansichten bezeichnet werden. Sie können Skizzen zusammenführen, um eine Zusammenfassung mehrerer Datenstreams basierend auf partiellen Skizzen zu erstellen, die für jeden Stream erstellt wurden.

Wenn Sie beispielsweise eine Skizze für die geschätzte Anzahl eindeutiger Nutzer pro Tag erstellen, können Sie die Anzahl der eindeutigen Nutzer in den letzten sieben Tagen abrufen, indem Sie die täglichen Skizzen zusammenführen. Durch das erneute Zusammenfassen der zusammengeführten täglichen Skizzen müssen Sie nicht die gesamte Eingabe des Datasets lesen.

Die Neuaggregation von Skizzen ist auch bei der analytischen Onlineverarbeitung (OLAP) nützlich. Sie können Skizzen zusammenführen, um ein Rollup eines OLAP-Cube zu erstellen, wobei die Skizze Daten zusammen mit einer oder mehreren bestimmten Dimensionen des Cube zusammenfasst. OLAP-Rollups sind nicht mit echter unterschiedlicher Anzahl möglich.

Welche Art von Skizze sollte ich verwenden?

Verschiedene Skizzenalgorithmen sind für verschiedene Arten von Messwerten konzipiert, z. B. HLL++ für eindeutige Anzahl und KLL für Quantile. GoogleSQL bietet auch ungefähre Aggregatfunktionen, mit denen Sie diese Arten von Daten abfragen können, ohne Abfragedetails wie die Precision Stufe angeben zu müssen.

Die verwendete Skizze hängt von der Art der Daten ab, die Sie schätzen müssen.

Kardinalität schätzen

Wenn Sie die Kardinalität schätzen müssen, verwenden Sie eine HLL++-Skizze.

Verwenden Sie beispielsweise eine HLL++-Skizze, um die Anzahl einzelner Nutzer zu erhalten, die ein Produkt in einem bestimmten Monat aktiv genutzt haben (MAU- oder 28DAU-Messwerte).

Quantil berechnen

Wenn Sie ein Quantil eines Datasets abrufen müssen, verwenden Sie eine KLL-Skizze.

Verwenden Sie beispielsweise eine KLL-Skizze, um den Medianwert für die Besuchsdauer von Kunden in einem Geschäft zu ermitteln oder um das 95. Perzentil der Latenz zu verfolgen, mit der Tickets in einer Warteschlange verbleiben, bevor sie bearbeitet werden.

HLL++-Skizzen

HyperLogLog++ (HLL++) ist ein Skizzenalgorithmus für die Schätzung der Kardinalität. HLL++ basiert auf dem Artikel HyperLogLog in der Praxis, wobei ++ die Erweiterungen angibt, die am HyperLogLog-Algorithmus vorgenommen wurden.

Die Kardinalität ist die Anzahl einzelner Elemente in der Eingabe für eine Skizze. Sie können beispielsweise eine HLL++-Skizze verwenden, um die Anzahl der einzelnen Nutzer abzurufen, die eine Anwendung geöffnet haben.

HLL++ schätzt sehr kleine und sehr große Kardinalitäten. HLL++ umfasst eine 64-Bit-Hash-Funktion, eine dünnbesetzte Darstellung, um die Arbeitsspeicheranforderungen für kleine Kardinalitätsprognosen zu verringern, und eine empirische Verzerrungskorrektur für kleine Kardinalitätsschätzungen.

Precision

HLL++-Skizzen unterstützen benutzerdefinierte Genauigkeit. Die folgende Tabelle zeigt die unterstützten Precision-Werte, die maximale Speichergröße und das Konfidenzintervall (CI) typischer Precision-Stufen:

Sie können die Precision für eine HLL++-Skizze definieren, wenn Sie sie mit der Funktion HLL_COUNT.INIT initialisieren.

Löschen

Sie können keine Werte aus einer HLL++-Skizze löschen.

Weitere Informationen

Eine Liste der Funktionen, die Sie mit HLL++-Skizzen verwenden können, finden Sie unter HLL++-Funktionen.

Einbindung von Skizzen

Sie können HLL++-Skizzen in andere Systeme einbinden. Beispielsweise können Sie Skizzen in externen Anwendungen wie Dataflow, Apache Spark und ZetaSketch erstellen und in GoogleSQL verwenden oder umgekehrt.

Neben GoogleSQL können Sie HLL++-Skizzen mit Java verwenden.

KLL-Skizzen

KLL (kurz für Karnin-Lang-Liberty) ist ein Streamingalgorithmus zum Berechnen von Skizzen für ungefähre Quantile. Er berechnet beliebige Quantile viel effizienter als genaue Berechnungen, allerdings mit einem kleinen Näherungsfehler.

Precision

KLL-Skizzen unterstützen benutzerdefinierte Genauigkeit. Die Precision definiert die Genauigkeit eines zurückgegebenen ungefähren Quantils q.

Standardmäßig kann der Rang eines ungefähren Quantils um maximal ±1/1000 * n abweichen von ⌈Φ * n⌉, wobei n die Anzahl der Zeilen in der Eingabe und ⌈Φ * n⌉ der Rang des genauen Quantils ist.

Wenn Sie eine benutzerdefinierte Precision angeben, kann der Rang des ungefähren Quantils um maximal ±1/precision * n vom Rang des genauen Quantils abweichen. Der Fehler liegt in 99,999% der Fälle innerhalb dieses Fehlerlimits. Diese Fehlergarantie gilt nur für die Differenz zwischen genauen und ungefähren Rängen. Die numerische Differenz zwischen dem genauen und dem ungefähren Wert für ein Quantil kann beliebig groß sein.

Angenommen, Sie möchten den Medianwert Φ = 0.5 ermitteln und verwenden die Standard-Precision 1000. Dann weicht der Rang des von der Funktion KLL_QUANTILES.EXTRACT_POINT zurückgegebenen Werts in 99,999% der Fälle um höchstens n/1000 vom tatsächlichen Rang ab. Mit anderen Worten: Der zurückgegebene Wert liegt fast immer zwischen dem 49,9.und 50,1.Perzentil. Wenn Ihre Skizze 1.000.000 Elemente enthält, liegt der Rang des zurückgegebenen Medianwerts fast immer zwischen 499.000 und 501.000.

Wenn Sie eine benutzerdefinierte Precision von 100 verwenden, um den Medianwert zu ermitteln, weicht der Rang des von der Funktion KLL_QUANTILES.EXTRACT_POINT zurückgegebenen Werts in 99,999% der Fälle um höchstens n/100 vom tatsächlichen Rang ab. Mit anderen Worten: Der zurückgegebene Wert liegt fast immer zwischen dem 49. und 51. Perzentil. Wenn Ihre Skizze 1.000.000 Elemente enthält, liegt der Rang des zurückgegebenen Medianwerts fast immer zwischen 490.000 und 510.000.

Sie können die Precision für eine KLL-Skizze definieren, wenn Sie sie mit der KLL_QUANTILES.INIT Funktion initialisieren.

Größe

Die Größe der KLL-Skizze hängt vom Precision-Parameter und vom Eingabetyp ab. Wenn der Eingabetyp INT64 ist, können die Skizzen zusätzlich optimiert werden, was besonders hilfreich ist, wenn die Eingabewerte aus einem kleinen Universum stammen. Die folgende Tabelle enthält zwei Spalten für INT64. Eine Spalte enthält eine Obergrenze für die Skizzengröße für Elemente aus einem begrenzten Universum der Größe 1 Milliarde und eine zweite Spalte eine Obergrenze für beliebige Eingabewerte.

Phi

Phi (Φ) stellt das zu erstellende Quantil als Anteil der Gesamtzahl der Zeilen in der Skizzeneingabe dar, normalisiert zwischen 0 und 1. Wenn eine Funktion Phi unterstützt, gibt sie einen Wert v zurück, sodass ungefähr Φ * n Eingaben kleiner oder gleich v sind und (1-Φ) * n Eingaben größer oder gleich v sind.

Weitere Informationen

Eine Liste der Funktionen, die Sie mit KLL-Skizzen verwenden können, finden Sie unter KLL-Quantilfunktionen.

Der KLL-Algorithmus ist im Artikel Optimal Quantile Approximation in Streams definiert und nach seinen Autoren Karnin, Lang und Liberty benannt, die den Artikel 2016 veröffentlicht haben. Der KLL-Algorithmus verbessert den älteren MP80-Algorithmus, indem er Puffer mit variabler Größe verwendet, um die Arbeitsspeichernutzung für große Datasets zu reduzieren und die Skizzengröße von O(log n) auf O(1) zu verringern. Aufgrund der nicht deterministischen Natur des Algorithmus sind Skizzen, die für dasselbe Dataset mit derselben Precision erstellt wurden, möglicherweise nicht identisch.

Quantile

Quantile sind Grenzwerte, die den Bereich einer Wahrscheinlichkeitsverteilung in kontinuierliche Intervalle mit gleichen Wahrscheinlichkeiten unterteilen oder die Beobachtungen in einer Stichprobe auf dieselbe Weise unterteilen. Mit einer Skizze, die Quantile unterstützt, können Sie Quantile schätzen, indem Sie diese Intervalle und Wahrscheinlichkeiten in nahezu genaue Quantilergebnisse zusammenfassen.

Quantile werden in der Regel auf zwei Arten definiert:

• Für eine positive Ganzzahl q sind q-Quantile eine Reihe von Werten, die ein Eingabe-Set in q Teilmengen von nahezu gleicher Größe unterteilen. Einige davon haben bestimmte Namen: Das einzelne 2-Quantil ist der Median, die 4-Quantile sind Quartile, die 100-Quantile sind Perzentile usw. KLL-Funktionen geben zusätzlich das (genaue) Minimum und Maximum der Eingabe zurück. Wenn Sie also nach den 2-Quantilen suchen, werden drei Werte zurückgegeben.

• Alternativ können Quantile als einzelne Φ-Quantile betrachtet werden, wobei Φ eine reelle Zahl mit 0 <= Φ <= 1 ist. Das Φ-Quantil x ist ein Element der Eingabe, sodass ein Φ-Anteil der Eingabe kleiner oder gleich x und ein (1-Φ)-Anteil größer oder gleich x ist. In dieser Notation ist der Median das 0, 5-Quantil und das 95. Perzentil das 0, 95-Quantil.

Sie können beispielsweise eine Skizze verwenden, die Quantile unterstützt, um den Medianwert für die Anzahl der Male zu ermitteln, die eine Anwendung von Nutzern geöffnet wird.

Ungefähre Aggregatfunktionen

Als Alternative zu bestimmten Funktionen für die skizzenbasierte Näherung bietet GoogleSQL vordefinierte ungefähre Aggregatfunktionen. Diese ungefähren Aggregatfunktionen unterstützen Skizzen für häufige Schätzungen wie eindeutige Anzahl, Quantile und höchste Anzahl, lassen aber keine benutzerdefinierte Precision zu. Außerdem wird die Skizze nicht für eine Neuaggregation wie anderen Arten von Skizzen freigegeben und gespeichert. Mit den ungefähren Aggregatfunktionen können schnelle skizzenbasierte Abfragen ohne detaillierte Konfiguration ausgeführt werden.

Eine Liste der ungefähren Aggregatfunktionen, die Sie mit skizzenbasierter Näherung verwenden können, finden Sie unter Ungefähre Aggregatfunktionen.