Bocetos

GoogleSQL para BigQuery admite bocetos de datos. Un boceto de datos es un resumen compacto de una agregación de datos. Recoge toda la información necesaria para extraer un resultado de agregación, continuar una agregación de datos o combinarla con otro boceto, lo que permite volver a agregar.

Calcular una métrica mediante un boceto es mucho menos caro que calcular un valor exacto. Si el cálculo es demasiado lento o requiere demasiado almacenamiento temporal, usa bocetos para reducir el tiempo de consulta y los recursos.

Además, calcular cardinalidades, como el número de usuarios únicos, o cuantiles, como la duración media de las visitas, sin bocetos solo suele ser posible ejecutando trabajos sobre los datos sin procesar, ya que los datos agregados no se pueden combinar.

Supongamos que tenemos una tabla con los siguientes datos:

Producto	Número de usuarios	Duración mediana de la visita
Producto A	500 millones	10 minutos
Producto B	20 millones	2 minutos

No es posible calcular el número total de usuarios de ambos productos porque no sabemos cuántos usuarios han usado ambos productos en la tabla. Del mismo modo, no se puede calcular la duración media de las visitas porque se ha perdido la distribución de las duraciones de las visitas.

Una solución es almacenar los bocetos en la tabla. Cada boceto es una representación aproximada y compacta de una propiedad de entrada concreta, como la cardinalidad, que puedes almacenar, combinar (o volver a agregar) y consultar para obtener resultados casi exactos. En el ejemplo anterior, puede estimar el número de usuarios distintos de los productos A y B creando y combinando (reagregando) los bocetos de cada producto. También puede estimar la duración media de las visitas con bocetos de cuantiles que puede combinar y consultar.

Por ejemplo, la siguiente consulta usa los bocetos HLL++ y KLL para estimar el número de usuarios únicos y la duración media de las visitas de YouTube (Producto A) y Google Maps (Producto 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
  );

Como un boceto tiene una compresión con pérdida de los datos originales, introduce un error estadístico que se representa mediante un margen de error o un intervalo de confianza (IC). En la mayoría de las aplicaciones, esta incertidumbre es pequeña. Por ejemplo, un boceto de recuento de cardinalidad típico tiene un error relativo de aproximadamente el 1% en el 95% de los casos. Un boceto sacrifica algo de precisión para realizar cálculos más rápidos y menos costosos, y para ocupar menos espacio de almacenamiento.

En resumen, un boceto tiene estas propiedades principales:

• Representa un agregado aproximado de una métrica específica.
• Es compacta
• Es una forma serializada de una estructura de datos sublineal en memoria.
• Suele tener un tamaño fijo y ser asintóticamente más pequeño que la entrada
• Puede introducir un error estadístico que se determina con un nivel de precisión.
• Se puede combinar con otros bocetos para resumir la unión de los conjuntos de datos subyacentes

Reagregación con fusión de bocetos

Los bocetos te permiten almacenar y combinar datos para volver a agregarlos de forma eficiente. Esto hace que los bocetos sean especialmente útiles para las vistas materializadas de conjuntos de datos. Puedes combinar bocetos para crear un resumen de varios flujos de datos a partir de los bocetos parciales creados para cada flujo.

Por ejemplo, si creas un boceto del número estimado de usuarios distintos cada día, puedes obtener el número de usuarios distintos de los últimos siete días combinando los bocetos diarios. Volver a agregar los bocetos diarios combinados te ayuda a evitar leer la entrada completa del conjunto de datos.

La reagregación de bocetos también es útil en el procesamiento analítico online (OLAP). Puedes combinar bocetos para crear un resumen de un cubo OLAP, donde el boceto resume los datos de una o varias dimensiones específicas del cubo. No se pueden hacer resúmenes OLAP con recuentos distintos reales.

¿Qué tipo de boceto debo usar?

Se han diseñado diferentes algoritmos de creación de bocetos para distintos tipos de métricas, como HLL++ para recuentos distintos y KLL para cuantiles. GoogleSQL también proporciona funciones de agregación aproximadas que puedes usar para consultar estos tipos de datos sin tener que especificar detalles de la consulta, como el nivel de precisión.

El boceto que utilices dependerá del tipo de datos que necesites estimar.

Estimar la cardinalidad

Si necesitas estimar la cardinalidad, usa un esquema de HLL++.

Por ejemplo, para obtener el número de usuarios únicos que han usado activamente un producto en un mes determinado (métricas UAM o UAD de 28 días), utilice un boceto de HLL++.

Calcular un cuantil

Si necesitas obtener un cuantil de un conjunto de datos, usa un gráfico KLL.

Por ejemplo, para obtener la duración media de las visitas de los clientes a una tienda o para monitorizar el percentil 95 de la latencia que permanecen las incidencias en una cola antes de resolverse, usa un boceto de KLL.

Esquemas de HLL++

HyperLogLog++ (HLL++) es un algoritmo de creación de bocetos para estimar la cardinalidad. HLL++ se basa en el artículo HyperLogLog in Practice, donde ++ denota las mejoras realizadas en el algoritmo HyperLogLog.

La cardinalidad es el número de elementos distintos de la entrada de un boceto. Por ejemplo, puedes usar un boceto HLL++ para obtener el número de usuarios únicos que han abierto una aplicación.

HLL++ estima cardinalidades muy pequeñas y muy grandes. HLL++ incluye una función hash de 64 bits, una representación dispersa para reducir los requisitos de memoria de las estimaciones de cardinalidad pequeñas y una corrección empírica del sesgo para las estimaciones de cardinalidad pequeñas.

Precisión

Los esquemas de HLL++ admiten una precisión personalizada. En la siguiente tabla se muestran los valores de precisión admitidos, el tamaño máximo de almacenamiento y el intervalo de confianza (IC) de los niveles de precisión habituales:

Precisión	Tamaño máximo de almacenamiento	65% CI	IC del 95 %	IC del 99 %
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 (predeterminado)	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	1024 KiB + 30 B	±0,10%	±0,20%	±0,30%
21	2048 KiB + 32 B	±0,07%	±0,14%	±0,22%
22	4096 KiB + 32 B	±0,05%	±0,10%	±0,15%
23	8192 KiB + 32 B	±0,04%	±0,07%	±0,11%
24	16384 KiB + 32 B	±0,03%	±0,05%	±0,08%

Puedes definir la precisión de un esquema de HLL++ cuando lo inicializas con la función HLL_COUNT.INIT.

Eliminación

No puedes eliminar valores de un esquema de HLL++.

Detalles adicionales

Para ver una lista de las funciones que puedes usar con los esquemas de HLL++, consulta Funciones de HLL++.

Integración con Sketch

Puedes integrar los esquemas de HLL++ con otros sistemas. Por ejemplo, puedes crear bocetos en aplicaciones externas, como Dataflow, Apache Spark y ZetaSketch, y, después, usarlos en GoogleSQL o viceversa.

Además de GoogleSQL, puedes usar esquemas de HLL++ con Java.

Bocetos de KLL

KLL (acrónimo de Karnin-Lang-Liberty) es un algoritmo de streaming para calcular bocetos de cuantiles aproximados. Calcula cuantiles arbitrarios de forma mucho más eficiente que los cálculos exactos, a cambio de un pequeño error de aproximación.

Precisión

Los esquemas KLL admiten una precisión personalizada. La precisión define la exactitud de un cuantil aproximado q devuelto.

De forma predeterminada, el rango de un cuantil aproximado puede desviarse como máximo ±1/1000 * n de ⌈Φ * n⌉, donde n es el número de filas de la entrada y ⌈Φ * n⌉ es el rango del cuantil exacto.

Si proporcionas una precisión personalizada, el rango del cuantil aproximado puede diferir en ±1/precision * n como máximo del rango del cuantil exacto. El error se encuentra dentro de este margen de error en el 99,999% de los casos. Esta garantía de error solo se aplica a la diferencia entre las clasificaciones exactas y aproximadas. La diferencia numérica entre el valor exacto y el aproximado de un cuantil puede ser arbitrariamente grande.

Por ejemplo, supongamos que quieres encontrar el valor mediano, Φ = 0.5, y usas la precisión predeterminada de 1000. En ese caso, la clasificación del valor devuelto por la función KLL_QUANTILES.EXTRACT_POINT difiere de la clasificación real en un máximo de n/1000 en el 99,999% de los casos. En otras palabras, el valor devuelto casi siempre está entre los percentiles 49,9 y 50,1. Si tienes 1.000.000 elementos en tu boceto, el rango de la mediana devuelta casi siempre estará entre 499.000 y 501.000.

Si usa una precisión personalizada de 100 para encontrar el valor mediano, el rango del valor devuelto por la función KLL_QUANTILES.EXTRACT_POINT difiere del rango real en un máximo de n/100 en el 99,999% de los casos. Es decir, el valor devuelto casi siempre está entre los percentiles 49 y 51. Si tienes 1.000.000 de elementos en tu boceto, el rango de la mediana devuelta casi siempre estará entre 490.000 y 510.000.

Puedes definir la precisión de un boceto de KLL cuando lo inicializas con la función KLL_QUANTILES.INIT.

Tamaño

El tamaño del boceto de KLL depende del parámetro de precisión y del tipo de entrada. Si el tipo de entrada es INT64, los bocetos pueden usar una optimización adicional que resulta especialmente útil si los valores de entrada proceden de un universo pequeño. La siguiente tabla contiene dos columnas para INT64. Una columna proporciona un límite superior del tamaño del boceto para los elementos de un universo limitado de tamaño 1000 millones, y una segunda columna proporciona un límite superior para los valores de entrada arbitrarios.

Precisión	FLOAT64	INT64 (<1000 millones)	INT64 (cualquiera)
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
5000	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
50000	3,90 MB	1,12 MB	3,45 MB
100000	7,92 MB	2,18 MB	6,97 MB

Phi

Phi (Φ) representa el cuantil que se va a generar como una fracción del número total de filas de la entrada del boceto, normalizado entre 0 y 1. Si una función admite phi, devuelve un valor v de forma que aproximadamente Φ * n entradas sean menores o iguales que v y (1-Φ) * n entradas sean mayores o iguales que v.

Detalles adicionales

Para ver una lista de las funciones que puedes usar con bocetos de KLL, consulta Funciones de cuantiles de KLL.

El algoritmo KLL se define en el artículo Optimal Quantile Approximation in Streams (Aproximación óptima de cuantiles en flujos) y recibe el nombre de sus autores, Karnin, Lang y Liberty, que publicaron el artículo en el 2016. El algoritmo KLL mejora el antiguo algoritmo MP80 mediante el uso de búferes de tamaño variable para reducir el uso de memoria en conjuntos de datos grandes, lo que reduce el tamaño del boceto de O(log n) a O(1). Debido a la naturaleza no determinista del algoritmo, es posible que los bocetos creados con el mismo conjunto de datos y la misma precisión no sean idénticos.

Cuantiles

Los cuantiles son puntos de corte que dividen el intervalo de una distribución de probabilidad en intervalos continuos con probabilidades iguales o que dividen las observaciones de una muestra de la misma forma. Un boceto que admite cuantiles te permite estimar cuantiles resumiendo esos intervalos y probabilidades en resultados de cuantiles casi exactos.

Los cuantiles suelen definirse de dos formas:

• Para un entero positivo q, los q-cuantiles son un conjunto de valores que dividen un conjunto de entrada en q subconjuntos de tamaño casi igual. Algunos de estos tienen nombres específicos: el único cuantil 2 es la mediana, los cuantiles 4 son cuartiles, los cuantiles 100 son percentiles, etc. Las funciones KLL también devuelven el mínimo y el máximo (exactos) de la entrada, por lo que, al consultar los cuantiles 2, se devuelven tres valores.

  Nota: Para extraer un conjunto de q-cuantiles donde q es el argumento number, usa las funciones MERGE y EXTRACT en las funciones KLL_QUANTILES.*.

• También se pueden considerar los cuantiles como Φ-cuantiles individuales, donde Φ es un número real con 0 <= Φ <= 1. El Φ-cuantil x es un elemento de la entrada de forma que una fracción Φ de la entrada es menor o igual que x, y una fracción (1-Φ) es mayor o igual que x. En esta notación, la mediana es el cuantil 0,5 y el percentil 95 es el cuantil 0,95.

  Nota: Para extraer cuantiles Φ individuales, usa las funciones MERGE_POINT y EXTRACT_POINT, que admiten cuantiles, donde Φ es el argumento phi.

Por ejemplo, puedes usar un boceto que admita cuantiles para obtener la mediana del número de veces que los usuarios abren una aplicación.

Funciones de agregación aproximada

Como alternativa a las funciones de aproximación basadas en bocetos específicas, GoogleSQL proporciona funciones de agregación aproximada predefinidas. Estas funciones de agregación aproximada admiten bocetos para estimaciones comunes, como el recuento de valores distintos, los cuantiles y el recuento de los valores más frecuentes, pero no permiten una precisión personalizada. Tampoco exponen ni almacenan el boceto para la reagregación como otros tipos de bocetos. Las funciones de agregación aproximada se han diseñado para ejecutar consultas rápidas basadas en bocetos sin una configuración detallada.

Para ver una lista de las funciones de agregación aproximada que puedes usar con la aproximación basada en bocetos, consulta Funciones de agregación aproximada.