Diese Seite wurde von der Cloud Translation API übersetzt.

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:

Produkt	Anzahl der Nutzer	Medianwert für die Besuchsdauer
Produkt A	500 Millionen	10 Minuten
Produkt B	20 Millionen	2 Minuten

Die Gesamtzahl der Nutzer für beide Produkte kann nicht berechnet werden, da wir nicht wissen, wie viele Nutzer beide Produkte in der Tabelle verwendet haben. Ebenso ist es nicht möglich, die mittlere Besuchszeit zu berechnen, da die Verteilung der Besuchszeiten 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 der einzelnen Nutzer und die mediane Besuchszeit 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 insbesondere für materialisierte Ansichten von Datasets nützlich. 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 unterschiedliche Arten von Messwerten konzipiert, z. B. HLL++ für die Anzahl der einzelnen Werte und KLL für Quantile. GoogleSQL bietet auch ungefähre Aggregatfunktionen, mit denen Sie diese Datentypen abfragen können, ohne Abfragedetails wie die Genauigkeit angeben zu müssen.

Welchen Sketch Sie verwenden, hängt vom Typ der Daten ab, die Sie schätzen müssen.

Kardinalität schätzen

Wenn Sie die Kardinalität schätzen möchten, 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 Datensatzes abrufen müssen, verwenden Sie einen KLL-Sketch.

Wenn Sie beispielsweise die durchschnittliche Besuchsdauer von Kunden in einem Geschäft ermitteln oder die Latenz im 95. Perzentil verfolgen möchten, die Tickets in einer Warteschlange verbleiben, bevor sie bearbeitet werden, verwenden Sie eine KLL-Skizze.

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:

Precision	Max. Speichergröße	65 % CI	95 % CI	99 % CI
10	1 KiB + 28 B	±3,25 %	±6,50 %	±9,75%
11	2 KiB + 28 B	±2,30 %	±4,60 %	±6,89%
12	4 KiB + 28 B	±1,63 %	±3,25 %	±4,88%
13	8 KiB + 28 B	±1,15 %	±2,30 %	±3,45%
14	16 KiB + 30 B	±0,81 %	±1,63 %	±2,44%
15 (Standard)	32 KiB + 30 B	±0,57 %	±1,15 %	±1,72 %
16	64 KiB + 30 B	±0,41 %	±0,81 %	±1,22 %
17	128 KiB + 30 B	±0,29 %	±0,57 %	±0,86 %
18	256 KiB + 30 B	±0,20 %	±0,41 %	±0,61 %
19	512 KiB + 30 B	±0,14 %	±0,29 %	±0,43 %
20	1.024 KiB + 30 B	±0,10 %	±0,20 %	±0,30%
21	2.048 KiB + 32 B	±0,07 %	±0,14 %	±0,22%
22	4.096 KiB + 32 B	±0,05 %	±0,10 %	±0,15%
23	8.192 KiB + 32 B	±0,04 %	±0,07 %	±0,11%
24	16.384 KiB + 32 B	±0,03 %	±0,05 %	±0,08%

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 Streaming-Algorithmus zum Berechnen von Skizzen für ungefähre Quantile. Es berechnet beliebige Quantile viel effizienter als genaue Berechnungen, allerdings mit einem kleinen Näherungsfehler.

Precision

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

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

Wenn Sie eine benutzerdefinierte Genauigkeit angeben, kann der Rang des geschätzten Quantils höchstens ±1/precision * n vom Rang des genauen Quantils abweichen. Der Fehler liegt in 99,999% der Fälle innerhalb dieser Fehlergrenze. Diese Fehlergarantie gilt nur für die Differenz zwischen genauen und ungefähren Rängen. Die numerische Differenz zwischen dem genauen und dem angenäherten Wert für ein Quantil kann beliebig groß sein.

Angenommen, Sie möchten den Medianwert Φ = 0.5 ermitteln und verwenden die Standardgenauigkeit von 1000. Der Rang des von der Funktion KLL_QUANTILES.EXTRACT_POINT zurückgegebenen Werts weicht dann in 99,999% der Fälle um höchstens n/1000 vom tatsächlichen Rang ab. Der zurückgegebene Wert liegt also fast immer zwischen dem 49,9.und dem 50,1.Perzentil. Wenn Sie 1.000.000 Elemente in Ihrem Sketch haben, liegt der Rang des zurückgegebenen Medians fast immer zwischen 499.000 und 501.000.

Wenn Sie eine benutzerdefinierte Genauigkeit 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. Der zurückgegebene Wert liegt also fast immer zwischen dem 49. und dem 51. Perzentil. Wenn Sie 1.000.000 Elemente in Ihrem Sketch haben, liegt der Rang des zurückgegebenen Medians fast immer zwischen 490.000 und 510.000.

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

Größe

Die Größe des KLL-Sketches hängt vom Genauigkeitsparameter und vom Eingabetyp ab. Wenn Ihr Eingabetyp INT64 ist, können die Skizzen zusätzlich optimiert werden. Das ist besonders hilfreich, 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 mit einer Größe von 1 Mrd. und eine zweite Spalte eine Obergrenze für beliebige Eingabewerte.

Precision	FLOAT64	INT64 (<1B)	INT64 (beliebig)
10	761 B	360 B	717 B
20	1,46 KB	706 B	1,47 KB
50	3,49 KB	1,72 KB	3,60 KB
100	6,94 KB	3,44 KB	7,12 KB
200	13,87 KB	6,33 KB	13,98 KB
500	35,15 KB	14,47 KB	35,30 KB
1000	71,18 KB	27,86 KB	71,28 KB
2000	144,51 KB	55,25 KB	144,57 KB
5.000	368,87 KB	139,54 KB	368,96 KB
10000	749,82 KB	282,27 KB	697,80 KB
20000	1,52 MB	573,16 KB	1,37 MB
50.000	3,90 MB	1,12 MB	3,45 MB
100000	7,92 MB	2,18 MB	6,97 MB

Phi

Phi (Φ) stellt das zu erstellende Quantil als Bruchteil der Gesamtzahl der Zeilen in der Skizzen-Eingabe 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 wird im Artikel Optimal Quantile Approximation in Streams definiert und ist nach seinen Autoren Karnin, Lang und Liberty benannt, die den Artikel 2016 veröffentlicht haben. Der KLL-Algorithmus ist eine Verbesserung des älteren MP80-Algorithmus. Er verwendet Puffer mit variabler Größe, um den Speicherverbrauch bei großen Datasets zu reduzieren. Die Größe des Sketches wird von O(log n) auf O(1) reduziert. Da der Algorithmus nicht deterministisch ist, sind Skizzen, die mit denselben Daten und derselben Genauigkeit 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 einem Quantil-Sketch können Sie Quantile schätzen, indem Sie diese Intervalle und Wahrscheinlichkeiten in nahezu exakte 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 eine Eingabemenge 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 die 2‑Quantile abfragen, werden drei Werte zurückgegeben.

Tipp :Wenn Sie eine Reihe von q-Quantilen extrahieren möchten, wobei q das Argument number ist, verwenden Sie die Funktionen MERGE und EXTRACT in den KLL_QUANTILES.*-Funktionen.
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 Φ-Bruchteil der Eingabe kleiner oder gleich x und ein (1-Φ)-Bruchteil größer oder gleich x ist. In dieser Notation ist der Median das 0, 5-Quantil und das 95. Perzentil das 0, 95-Quantil.

Tipp :Wenn Sie einzelne Φ-Quantile extrahieren möchten, verwenden Sie die quantilefähigen Funktionen MERGE_POINT und EXTRACT_POINT. Dabei ist Φ das phi-Argument.

Sie können beispielsweise eine Skizze mit Unterstützung für Quantile verwenden, um den Median der Anzahl der Male abzurufen, die eine Anwendung von Nutzern geöffnet wird.

Ungefähre Aggregatfunktionen

Als Alternative zu bestimmten skizzenbasierten Näherungsfunktionen 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.