Funciones HyperLogLog++ en SQL estándar

El algoritmo HyperLogLog++ (HLL++) estima la cardinalidad de los esbozos. Si no deseas trabajar con esbozos y no necesitas una precisión personalizada, considera usar funciones de agregación aproximadas con una precisión definida por el sistema.

Las funciones HLL++ son funciones de agregación aproximadas. La agregación aproximada suele requerir menos memoria que las funciones de agregación exacta, como COUNT(DISTINCT), pero también introduce la incertidumbre estadística. Esto hace que las funciones HLL++ sean apropiadas en grandes flujos de datos para los que el uso de la memoria lineal es poco práctico y para los datos que ya son aproximados.

BigQuery admite las siguientes funciones HLL++:

HLL_COUNT.INIT

HLL_COUNT.INIT(input [, precision])

Descripción

Una función agregada que toma uno o más valores input y los agrega en un esbozo HLL++. Cada esbozo se representa con el tipo de datos BYTES. Luego, puedes combinar los bocetos con HLL_COUNT.MERGE o HLL_COUNT.MERGE_PARTIAL. Si no es necesaria la combinación, puedes extraer el recuento final de los valores distintos del boceto con HLL_COUNT.EXTRACT.

Esta función admite un parámetro opcional, precision. Este parámetro define la precisión de la estimación a costo de memoria adicional necesaria para procesar los bocetos o almacenarlos en el disco. La siguiente tabla muestra los valores de precisión permitidos, el tamaño máximo del boceto por grupo y el intervalo de confianza (IC) de las precisiones típicas:

Precisión Tamaño máx. del boceto (KiB) IC 65% IC 95% IC 99%
10 1 ±1.63% ±3.25% ±6.50%
11 2 ±1.15% ±2.30% ±4.60%
12 4 ±0.81% ±1.63% ±3.25%
13 8 ±0.57% ±1.15% ±1.72%
14 16 ±0.41% ±0.81% ±1.22%
15 (predeterminada) 32 ±0.29% ±0.57% ±0.86%
16 64 ±0.20% ±0.41% ±0.61%
17 128 ±0.14% ±0.29% ±0.43%
18 256 ±0.10% ±0.20% ±0.41%
19 512 ±0.07% ±0.14% ±0.29%
20 1,024 ±0.05% ±0.10% ±0.20%
21 2,048 ±0.04% ±0.07% ±0.14%
22 4096 ±0.03% ±0.05% ±0.10%
23 8192 ±0.02% ±0.04% ±0.07%
24 16384 ±0.01% ±0.03% ±0.05%

Si la entrada es NULL, esta función muestra NULL.

Para obtener más información, consulta HyperLogLog en la práctica: Ingeniería algorítmica de un algoritmo de estimación de cardinalidad de última generación.

Tipos de entrada admitidos

INT64, NUMERIC, STRING, BYTES

Tipo de datos que se muestra

BYTES

Ejemplo

SELECT
  HLL_COUNT.INIT(respondent) AS respondents_hll,
  flavor,
  country
FROM UNNEST([
  STRUCT(1 AS respondent, "Vanilla" AS flavor, "CH" AS country),
  (1, "Chocolate", "CH"),
  (2, "Chocolate", "US"),
  (2, "Strawberry", "US")])
GROUP BY flavor, country;

HLL_COUNT.MERGE

HLL_COUNT.MERGE(sketch)

Descripción

Una función de agregación que muestra la cardinalidad de varios esbozos de conjuntos HLL++ mediante el cálculo de su unión.

Cada sketch debe tener la misma precisión y debe inicializarse en el mismo tipo. Los intentos de combinar bocetos con diferentes precisiones o para diferentes tipos dan como resultado un error. Por ejemplo, no puedes combinar un boceto inicializado a partir de datos INT64 con uno inicializado a partir de datos STRING.

Esta función ignora los valores NULL durante la combinación de bocetos. Si la combinación se realiza en cero filas o solo en valores NULL, la función muestra 0.

Tipos de entrada admitidos

BYTES

Tipo de datos que se muestra

INT64

Ejemplo

SELECT HLL_COUNT.MERGE(respondents_hll) AS num_respondents, flavor
FROM (
  SELECT
    HLL_COUNT.INIT(respondent) AS respondents_hll,
    flavor,
    country
  FROM UNNEST([
    STRUCT(1 AS respondent, "Vanilla" AS flavor, "CH" AS country),
    (1, "Chocolate", "CH"),
    (2, "Chocolate", "US"),
    (2, "Strawberry", "US")])
  GROUP BY flavor, country)
GROUP BY flavor;

HLL_COUNT.MERGE_PARTIAL

HLL_COUNT.MERGE_PARTIAL(sketch)

Descripción

Una función de agregación que toma una o más entradas de sketch HLL++ y las combina en un esbozo nuevo.

Esta función muestra NULL si no hay entrada o si todas las entradas son NULL.

Tipos de entrada admitidos

BYTES

Tipo de datos que se muestra

BYTES

Ejemplo

SELECT HLL_COUNT.MERGE_PARTIAL(respondents_hll) AS num_respondents, flavor
FROM (
  SELECT
    HLL_COUNT.INIT(respondent) AS respondents_hll,
    flavor,
    country
  FROM UNNEST([
    STRUCT(1 AS respondent, "Vanilla" AS flavor, "CH" AS country),
    (1, "Chocolate", "CH"),
    (2, "Chocolate", "US"),
    (2, "Strawberry", "US")])
  GROUP BY flavor, country)
GROUP BY flavor;

HLL_COUNT.EXTRACT

HLL_COUNT.EXTRACT(sketch)

Descripción

Una función escalar que extrae una estimación de cardinalidad de un solo esbozo HLL++.

Si sketch es NULL, esta función muestra una estimación de cardinalidad de 0.

Tipos de entrada admitidos

BYTES

Tipo de datos que se muestra

INT64

Ejemplo

SELECT
  flavor,
  country,
  HLL_COUNT.EXTRACT(respondents_hll) AS num_respondents
FROM (
  SELECT
    HLL_COUNT.INIT(respondent) AS respondents_hll,
    flavor,
    country
  FROM UNNEST([
    STRUCT(1 AS respondent, "Vanilla" AS flavor, "CH" AS country),
    (1, "Chocolate", "CH"),
    (2, "Chocolate", "US"),
    (2, "Strawberry", "US")])
  GROUP BY flavor, country);

+------------+---------+-----------------+
| flavor     | country | num_respondents |
+------------+---------+-----------------+
| Vanilla    | CH      | 1               |
| Chocolate  | CH      | 1               |
| Chocolate  | US      | 1               |
| Strawberry | US      | 1               |
+------------+---------+-----------------+

Información acerca del algoritmo HLL++

El algoritmo HLL++ mejora el algoritmo HLL ya que estima con más precisión las cardinalidades muy pequeñas y grandes. El algoritmo HLL++ incluye una función hash de 64 bits, una representación dispersa que reduce los requisitos de memoria para las estimaciones de cardinalidad pequeña y una corrección del sesgo empírico para las estimaciones de cardinalidad pequeña.

Información acerca de los esbozos

Un esbozo es un resumen de un gran flujo de datos. Se pueden extraer estadísticas de un esbozo a fin de estimar estadísticas particulares de los datos originales, o fusionar esbozos para resumir múltiples flujos de datos. Un esbozo tiene estas características:

  • Se comprimen datos sin procesar en una representación de memoria fija.
  • Es asintóticamente más pequeño que la entrada.
  • Es la forma serializada de una estructura de datos sublineal en memoria.
  • En general, requiere menos memoria que la entrada que se usó para crearla.

Los esbozos permiten la integración con otros sistemas. Por ejemplo, es posible compilar esbozos en aplicaciones externas, como Cloud Dataflow, o Apache Spark y consumirlos en BigQuery o viceversa. Los esbozos también permiten construir agregaciones intermedias para funciones no aditivas como COUNT(DISTINCT).