Résumés

GoogleSQL pour BigQuery est compatible avec les résumés de données. Un résumé de données est un résumé compact d'une agrégation de données. Il capture toutes les informations nécessaires pour extraire un résultat d'agrégation, pour poursuivre une agrégation de données, ou les fusionner avec une autre, ce qui permet la réagrégation.

Le calcul d'une métrique à l'aide d'un résumé est souvent beaucoup moins coûteux qu'un calcul de valeur exacte. Si votre calcul est trop lent ou nécessite trop d'espace de stockage temporaire, utilisez des résumés pour réduire le temps de requête et les ressources.

En outre, le calcul des cardinalités, telles que le nombre d'utilisateurs distincts ou les quantiles, tels que la durée moyenne des visites, sans résumé, n'est généralement possible qu'en exécutant des jobs sur les données brutes, car les données déjà agrégées ne peuvent plus être combinées.

Prenons l'exemple d'une table contenant les données suivantes :

Il n'est pas possible de calculer le nombre total d'utilisateurs des deux produits, car nous ne savons pas combien d'utilisateurs ont utilisé les deux produits dans la table. De même, il est impossible de calculer la durée médiane des visites, car la distribution des durées des visites a été perdue.

Une solution consiste à stocker les résumés dans la table. Chaque résumé est une représentation approximative et compacte d'une propriété d'entrée particulière, telle que la cardinalité, que vous pouvez stocker, fusionner (ou réagréger) et interroger pour obtenir des résultats quasi exacts. Dans l'exemple précédent, vous pouvez estimer le nombre d'utilisateurs distincts pour les produits A et B en créant et en fusionnant (réagrégeant) les résumés de chaque produit. Vous pouvez aussi estimer la durée médiane d'une visite avec des résumés de quantiles que vous pouvez également fusionner et interroger.

Par exemple, la requête suivante utilise les résumés HLL++ et KLL pour estimer le nombre d'utilisateurs distincts et la durée médiane des visites pour YouTube (produit A) et Google Maps (produit B) :

-- 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
  );

Étant donné qu'un résumé comporte une compression avec perte des données d'origine, il introduit une erreur statistique représentée par une limite d'erreur ou un intervalle de confiance (CI). Pour la plupart des applications, cette incertitude est minime. Par exemple, un résumé classique de la cardinalité compte une erreur relative d'environ 1 % dans 95 % des cas. Un résumé apporte une certaine exactitude, ou précision, les opérations de calcul sont plus rapides, moins coûteuses et utilisent moins d'espace de stockage.

En bref, un résumé comporte les propriétés suivantes :

• Représente une agrégation approximative pour une métrique spécifique
• Est compact
• Est une forme sérialisée d'une structure de données sous-linéaire en mémoire
• Généralement de taille fixe et asymptotiquement plus petite que l'entrée
• Peut introduire une erreur statistique que vous déterminez avec un niveau de précision
• Peut être fusionné avec d'autres résumés pour résumer l'union des ensembles de données sous-jacents

Réagrégation avec la fusion de résumés

Les résumés vous permettent de stocker et de fusionner des données pour une réagrégation efficace. Cela rend les résumés particulièrement utiles pour les vues matérialisées d'ensembles de données. Vous pouvez fusionner des résumés pour créer un résumé de plusieurs flux de données basés sur des résumés partiels créés pour chaque flux.

Par exemple, si vous créez un résumé pour le nombre estimé d'utilisateurs distincts chaque jour, vous pouvez obtenir le nombre d'utilisateurs distincts au cours des sept derniers jours en fusionnant des résumés quotidiens. La réagrégation des résumés quotidiens fusionnés vous permet d'éviter la lecture de l'entrée complète de l'ensemble de données.

La réagrégation de résumé est également utile dans le traitement analytique en ligne (OLAP). Vous pouvez fusionner des résumés pour créer un cumul d'un cube OLAP, où le résumé récapitule les données avec une ou plusieurs dimensions spécifiques du cube. Les cumuls OLAP ne sont pas possibles avec des décomptes distincts réels.

Quel type de croquis dois-je utiliser ?

Différents algorithmes de résumé sont conçus pour différents types de métriques, comme HLL++ pour les décomptes distincts et KLL pour les quantiles. GoogleSQL fournit également des fonctions d'agrégation approximatives que vous pouvez utiliser pour interroger ces types de données sans avoir à spécifier les détails de la requête, tels que le niveau de précision.

Le sketch que vous utilisez dépend du type de données que vous devez estimer.

Estimer la cardinalité

Si vous devez estimer la cardinalité, utilisez un résumé HLL++.

Par exemple, pour obtenir le nombre d'utilisateurs uniques qui ont activement utilisé un produit au cours d'un mois donné (métriques UAM ou 28DAU), utilisez un résumé HLL++.

Calculer un quantile

Si vous devez obtenir un quantile d'un ensemble de données, utilisez un sketch KLL.

Par exemple, pour obtenir la durée médiane des visites des clients dans un magasin ou pour suivre la latence du 95e centile des tickets dans une file d'attente avant d'être traités, utilisez un résumé KLL.

Résumés HLL++

HyperLogLog++ (HLL++) est un algorithme de résumé permettant d'estimer la cardinalité. HLL++ est basé sur l'article HyperLogLog dans la pratique, où ++ désigne les augmentations apportées à l'algorithme HyperLogLog.

La cardinalité correspond au nombre d'éléments distincts dans l'entrée d'un résumé. Par exemple, vous pouvez utiliser un résumé HLL++ pour obtenir le nombre d'utilisateurs uniques qui ont ouvert une application.

HLL++ estime des cardinalités très petites ou très volumineuses. L'algorithme HLL++ inclut une fonction de hachage 64 bits, une représentation creuse pour réduire les besoins en mémoire, ainsi que la correction de biais empirique pour les faibles estimations de cardinalité.

Précision

Les résumés HLL++ sont compatibles avec la précision personnalisée. Le tableau suivant indique les valeurs de précision acceptées, la taille de stockage maximale et l'intervalle de confiance (CI) des niveaux de précision types :

Vous pouvez définir la précision d'un résumé HLL++ lorsque vous l'initialisez à l'aide de la fonction HLL_COUNT.INIT.

Suppression

Vous ne pouvez pas supprimer des valeurs d'un résumé HLL++.

Informations supplémentaires

Pour obtenir une liste des fonctions que vous pouvez utiliser avec les résumés HLL++, consultez la page Fonctions HLL++.

Intégration de résumé

Vous pouvez intégrer des résumés HLL++ à d'autres systèmes. Par exemple, vous pouvez créer des résumés dans des applications externes, telles que Dataflow, Apache Spark et ZetaSketch, puis les utiliser dans GoogleSQL ou inversement.

En plus de GoogleSQL, vous pouvez utiliser des résumés HLL++ avec Java.

Résumés KLL

KLL (Karnin-Lang-Liberty) est un algorithme de streaming permettant de calculer des résumés pour les quantiles approximatifs. Il calcule des quantiles arbitraires beaucoup plus efficacement que les calculs exacts, au prix d'une petite erreur d'approximation.

Précision

Les résumés KLL sont compatibles avec la précision personnalisée. La précision définit l'exactitude d'un quantile approximatif q renvoyé.

Par défaut, le rang d'un quantile approximatif peut être au maximum ±1/1000 * n de ⌈Φ * n⌉, où n correspond au nombre de lignes dans l'entrée et ⌈Φ * n⌉ au rang du quantile exact.

Si vous fournissez une précision personnalisée, le rang du quantile approximatif ne peut pas être supérieur à ±1/precision * n par rapport au rang du quantile exact. L'erreur se situe dans cette limite d'erreur dans 99,999 % des cas. Cette garantie d'erreur ne s'applique qu'à la différence entre les classements exacts et approximatifs. La différence numérique entre la valeur exacte et la valeur approximative d'un quantile peut être arbitrairement grande.

Par exemple, supposons que vous souhaitiez trouver la valeur médiane Φ = 0.5 et que vous utilisiez la précision par défaut de 1000. Le rang de la valeur renvoyée par la fonction KLL_QUANTILES.EXTRACT_POINT diffère alors du rang réel d'au plus n/1000 dans 99,999 % des cas. En d'autres termes, la valeur renvoyée se situe presque toujours entre le 49,9e et le 50,1e centile. Si votre sketch contient 1 000 000 d'éléments, le rang de la médiane renvoyée est presque toujours compris entre 499 000 et 501 000.

Si vous utilisez une précision personnalisée de 100 pour trouver la valeur médiane, le rang de la valeur renvoyée par la fonction KLL_QUANTILES.EXTRACT_POINT diffère du rang réel d'au plus n/100 dans 99,999 % des cas. En d'autres termes, la valeur renvoyée se situe presque toujours entre le 49e et le 51e centiles. Si votre sketch contient 1 000 000 d'éléments, le rang de la médiane renvoyée est presque toujours compris entre 490 000 et 510 000.

Vous pouvez définir la précision d'un résumé KLL lorsque vous l'initialisez à l'aide de la fonction KLL_QUANTILES.INIT.

Size (Taille)

La taille du sketch KLL dépend du paramètre de précision et du type d'entrée. Si votre type d'entrée est INT64, les plans peuvent utiliser une optimisation supplémentaire particulièrement utile si les valeurs d'entrée proviennent d'un petit univers. Le tableau suivant contient deux colonnes pour INT64. Une colonne fournit une limite supérieure de la taille du sketch pour les éléments d'un univers limité de taille 1 milliard, et une deuxième colonne fournit une limite supérieure pour les valeurs d'entrée arbitraires.

Phi

Phi (Φ) représente le quantile à produire sous la forme d'une fraction du nombre total de lignes dans l'entrée du sketch, normalisée entre 0 et 1. Si une fonction accepte phi, elle renvoie une valeur v telle qu'environ Φ * n entrées sont inférieures ou égales à v, et (1-Φ) * n entrées sont supérieures ou égales à v.

Informations supplémentaires

Pour obtenir la liste des fonctions que vous pouvez utiliser avec les résumés KLL, consultez Fonctions de quantile KLL.

L'algorithme KLL est défini dans l'article Optimal Quantile Approximation in Streams. Il porte le nom de ses auteurs, Karnin, Lang et Liberty, qui l'ont publié en 2016. L'algorithme KLL améliore l'ancien algorithme MP80 en utilisant des tampons de taille variable pour réduire l'utilisation de la mémoire pour les grands ensembles de données, en réduisant la taille du sketch de O(log n) à O(1). En raison de la nature non déterministe de l'algorithme, les résumés créés sur le même ensemble de données avec la même précision peuvent ne pas être identiques.

Quantiles

Les quantiles sont des points de coupure qui divisent la plage d'une distribution de probabilité en intervalles continus de probabilités égales, ou qui divisent les observations d'un échantillon de la même manière. Un sketch prenant en charge les quantiles vous permet d'estimer les quantiles en résumant ces intervalles et ces probabilités en résultats de quantile quasi exacts.

Les quantiles sont généralement définis de deux manières :

• Pour un entier positif q, les q-quantiles sont un ensemble de valeurs qui partitionnent un ensemble d'entrée en q sous-ensembles de taille presque égale. Certains d'entre eux ont des noms spécifiques : le 2-quantile unique est la médiane, les 4-quantiles sont des quartiles, les 100-quantiles sont des centiles, etc. Les fonctions KLL renvoient également le minimum (exact) et le maximum de l'entrée. Ainsi, lorsque vous interrogez les 2-quantiles, trois valeurs sont renvoyées.

• Les quantiles peuvent également être considérés comme des Φ-quantiles individuels, où Φ est un nombre réel avec 0 <= Φ <= 1. Le quantile Φ x est un élément de l'entrée tel qu'une fraction Φ de l'entrée est inférieure ou égale à x, et qu'une fraction (1-Φ) est supérieure ou égale à x. Dans cette notation, la médiane correspond au quantile 0,5 et le 95e centile au quantile 0,95.

Par exemple, vous pouvez utiliser un sketch compatible avec les quantiles pour obtenir la médiane du nombre de fois qu'une application est ouverte par les utilisateurs.

Fonctions d'agrégation approximative

À la place des fonctions d'approximation spécifiques basées sur des résumés, GoogleSQL fournit des fonctions d'agrégation approximative prédéfinies. Ces fonctions d'agrégation approximative acceptent des résumés pour les estimations courantes telles que le décompte distinct, les quantiles et le décompte principal, mais ils ne permettent pas une précision personnalisée. Ils ne permettent pas non plus d'exposer et de stocker les résumés à des fins de réagrégation, comme les autres types de résumés. Les fonctions d'agrégation approximative sont conçues pour exécuter des requêtes rapides basées sur des résumés sans configuration détaillée.

Pour obtenir la liste des fonctions d'agrégation approximative que vous pouvez utiliser avec les approximations basées sur les résumés, consultez la section Fonctions d'agrégation approximative.