Esboços

O GoogleSQL para BigQuery suporta esboços de dados. Um esboço de dados é um resumo compacto de uma agregação de dados. Ele captura todas as informações necessárias para extrair um resultado de agregação, continuar uma agregação de dados ou mesclá-la com outro esboço, permitindo uma nova agregação.

Calcular uma métrica usando um esboço é muito mais barato do que calcular um valor exato. Se a computação for muito lenta ou precisar de muito armazenamento temporário, use esboços para reduzir o tempo e os recursos de consulta.

Além disso, a computação de cardinalidades, como o número de usuários distintos, ou de quantis, como a duração média da visita, sem esboços geralmente só é possível ao executar jobs nos dados brutos, porque os dados já agregados não podem ser mais combinados.

Considere uma tabela com os seguintes dados:

Produto Número de usuários Duração média da visita
Produto A 500 milhões 10 minutos
Produto B 20 milhões 2 minutos

Não é possível calcular o número total de usuários dos dois produtos porque a tabela não mostra quantos usuários usaram ambos os produtos. Da mesma forma, não é possível calcular a duração média da visita porque a distribuição das durações foi perdida.

Uma solução é armazenar sketches na tabela. Cada esboço é uma representação aproximada e compacta de uma propriedade de entrada específica, como a cardinalidade, que pode ser armazenada, mesclada (ou reagregada) e consultada para resultados quase exatos. No exemplo anterior, é possível estimar o número de usuários distintos para os produtos A e B criando e mesclando (reagregando) os esboços de cada produto. Você também pode estimar a duração média da visita com esboços de quantis que também podem ser combinados e consultados.

Por exemplo, a consulta a seguir usa esboços HLL++ e KLL para estimar usuários distintos e a duração média das visitas ao YouTube (Produto A) e ao Google Maps (Produto 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 um esboço tem compactação com perdas dos dados originais, ele introduz um erro estatístico que é representado por um limite de erro ou intervalo de confiança (CI, na sigla em inglês). Para a maioria das aplicações, essa incerteza é pequena. Por exemplo, um esboço típico de contagem de cardinalidade tem um erro relativo de cerca de 1% em 95% de todos os casos. Um esboço troca alguma acurácia, ou precisão, por cálculos mais rápidos e baratos e menos armazenamento.

Em resumo, um esboço tem as seguintes propriedades principais:

  • Representa um agregado aproximado de uma métrica específica
  • É compacto
  • É uma forma serializada de uma estrutura de dados sublinear na memória
  • Geralmente é um tamanho fixo e assintoticamente menor do que a entrada
  • Pode introduzir um erro estatístico que você determina com um nível de precisão
  • Pode ser mesclado com outros esboços para resumir a união dos conjuntos de dados

Nova agregação com mesclagem de esboços

Os esboços permitem armazenar e mesclar dados para uma nova agregação eficiente. Isso torna os esboços especialmente úteis para armazenar resumos pré-calculados de conjuntos de dados, conhecidos como visualizações materializadas. É possível mesclar sketches para criar um resumo de vários fluxos de dados com base em sketches parciais criados para cada fluxo.

Por exemplo, se você criar um esboço para o número estimado de usuários distintos todos os dias, poderá conferir o número de usuários nos últimos sete dias mesclando esboços diários. A reagregação dos esboços diários mesclados ajuda a evitar a leitura da entrada completa do conjunto de dados.

A reagregação do Sketch também é útil no processamento analítico on-line (OLAP, na sigla em inglês). É possível mesclar esboços para criar uma visualização completa de um cubo de OLAP, em que o esboço resume os dados ao longo de uma ou mais dimensões específicas do cubo. Não é possível fazer visualizações completas de OLAP com contagens verdadeiras distintas.

Qual tipo de esboço devo usar?

Diferentes algoritmos de esboço são projetados para diferentes tipos de métricas, como HLL++ para contagens distintas e KLL para quantis. O GoogleSQL também oferece funções agregadas aproximadas que podem ser usadas para consultar esses tipos de dados sem precisar especificar detalhes da consulta, como o nível de precisão.

O sketch que você usa depende do tipo de dados que você precisa estimar.

Estimar cardinalidade

Se você precisar estimar a cardinalidade, use um esboço HLL++.

Por exemplo, para conferir o número de usuários únicos que usaram ativamente um produto em um determinado mês (métricas MAU ou 28DAU), use um esboço HLL++.

Calcular um quantil

Se você precisar de um quantil de um conjunto de dados, use um esboço KLL.

Por exemplo, para conferir a duração média da visita de clientes em uma loja ou acompanhar a latência do 95º percentil em que os tíquetes permanecem em uma fila antes de serem resolvidos, use um esboço KLL.

Sketches HLL

O HyperLogLog++ (HLL++) é um algoritmo de esboço para estimar a cardinalidade. O HLL++ é baseado no documento HyperLogLog in Practice, em que ++ indica os aumentos feitos no algoritmo HyperLogLog.

A cardinalidade é o número de elementos distintos na entrada de um sketch. Por exemplo, você pode usar um esboço HLL++ para descobrir o número de usuários únicos que abriram um aplicativo.

O HLL++ estima a cardinalidade muito pequena e muito grande. O HLL++ inclui uma função hash de 64 bits, representação esparsa para reduzir os requisitos de memória para estimativas de cardinalidade pequenas e correção de viés empírico para estimativas de cardinalidade pequenas.

Precisão

Os sketches HLL++ são compatíveis com precisão personalizada. A tabela a seguir mostra os valores de precisão compatíveis, o tamanho máximo de armazenamento e o intervalo de confiança (CI) dos níveis de precisão típicos:

Precisão Tamanho máximo de armazenamento CI de 65% CI de 95% CI de 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 (padrão) 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%

É possível definir a precisão de um esboço HLL++ ao inicializá-lo com a função HLL_COUNT.INIT.

Exclusão

Não é possível excluir valores de um esboço HLL++.

Mais detalhes

Para conferir uma lista das funções que podem ser usadas com esboços HLL++, consulte Funções HLL++.

Integração de esboço

É possível integrar esboços HLL++ a outros sistemas. Por exemplo, é possível criar esboços em aplicativos externos, como o Dataflow, Apache Spark e ZetaSketch, e consumi-los no GoogleSQL ou vice-versa.

Além do GoogleSQL, é possível usar esboços HLL++ com Java.

Sketches KLL

O KLL (abreviação de Karnin-Lang-Liberty) é um algoritmo de streaming para calcular esboços de quantis aproximados. Ele calcula quantis arbitrários de maneira muito mais eficiente do que os cálculos exatos, ao custo de um pequeno erro de aproximação.

Precisão

Os sketches KLL são compatíveis com precisão personalizada. A precisão define a exatidão de um quantil aproximado retornado q.

Por padrão, a classificação de um quantil aproximado pode ser no máximo ±1/1000 * n de ⌈Φ * n⌉, em que n é o número de linhas na entrada e ⌈Φ * n⌉ é a classificação do quantil exato.

Se você fornecer uma precisão personalizada, a classificação do quantil aproximado poderá ser, no máximo, ±1/precision * n diferente da classificação do quantil exato. O erro está dentro desse limite em 99,999% dos casos. Essa garantia de erro se aplica apenas à diferença entre classificações exatas e aproximadas. A diferença numérica entre o valor exato e o aproximado de um quantil pode ser arbitrariamente grande.

Por exemplo, suponha que você queira encontrar o valor mediano, Φ = 0.5, e use a precisão padrão de 1000. Em seguida, a classificação do valor retornado pela função KLL_QUANTILES.EXTRACT_POINT difere da classificação verdadeira em, no máximo, n/1000 em 99,999% dos casos. Em outras palavras, o valor retornado quase sempre está entre os percentis 49,9 e 50,1. Se você tiver 1.000.000 de itens no esboço, a classificação da mediana retornada quase sempre estará entre 499.000 e 501.000.

Se você usar uma precisão personalizada de 100 para encontrar o valor mediano, a classificação do valor retornado pela função KLL_QUANTILES.EXTRACT_POINT será diferente da classificação verdadeira em, no máximo, n/100 em 99,999% dos casos. Em outras palavras, o valor retornado está quase sempre entre os percentis 49 e 51. Se você tiver 1.000.000 de itens no seu rascunho, a classificação da mediana retornada será quase sempre entre 490.000 e 510.000.

É possível definir a precisão de um sketch KLL ao inicializá-lo com a função KLL_QUANTILES.INIT.

Tamanho

O tamanho do rascunho KLL depende do parâmetro de precisão e do tipo de entrada. Se o tipo de entrada for INT64, os sketches poderão usar uma otimização adicional, que é especialmente útil se os valores de entrada forem de um universo pequeno. A tabela a seguir contém duas colunas para INT64. Uma coluna fornece um limite superior no tamanho do sketch para itens de um universo limitado de tamanho 1B, e uma segunda coluna fornece um limite superior para valores de entrada arbitrários.

Precisão FLOAT64 INT64 (<1B) INT64 (qualquer)
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 o quantil a ser produzido como uma fração do número total de linhas na entrada do rascunho, normalizado entre 0 e 1. Se uma função for compatível com phi, ela vai retornar um valor v de modo que aproximadamente Φ * n entradas sejam menores ou iguais a v, e (1-Φ) * n entradas sejam maiores ou iguais a v.

Mais detalhes

Para conferir uma lista das funções que podem ser usadas com esboços KLL, consulte Funções de quantil KLL.

O algoritmo KLL é definido no artigo Optimal Quantile Approximation in Streams e recebeu o nome dos autores, Karnin, Lang e Liberty, que publicaram o artigo em 2016. O algoritmo KLL melhora o algoritmo MP80 mais antigo usando buffers de tamanho variável para reduzir o uso de memória em grandes conjuntos de dados, reduzindo o tamanho do esboço de O(log n) para O(1). Devido à natureza não determinista do algoritmo, os esboços criados no mesmo conjunto de dados com a mesma precisão podem não ser idênticos.

Quantis

Quantis são pontos de corte que dividem o intervalo de uma distribuição de probabilidade em intervalos contínuos com probabilidades iguais ou dividem as observações em uma amostra da mesma maneira. Um sketch que aceita quantis permite estimar quantis resumindo esses intervalos e probabilidades em resultados de quantis quase exatos.

Os quantis geralmente são definidos de duas maneiras:

  • Para um número inteiro positivo q, os quantis q são um conjunto de valores que dividem um conjunto de entrada em q subconjuntos de tamanho quase igual. Alguns deles têm nomes específicos: o único quantil 2 é a mediana, os quantis 4 são quartis, os quantis 100 são percentis etc. As funções KLL também retornam o mínimo (exato) e o máximo da entrada. Portanto, ao consultar os quantis 2, três valores são retornados.

  • Como alternativa, os quantis podem ser considerados quantis Φ individuais, em que Φ é um número real com 0 <= Φ <= 1. O quantil Φ x é um elemento da entrada em que uma fração Φ da entrada é menor ou igual a x, e uma fração (1-Φ) é maior ou igual a x. Nessa notação, a mediana é o quantil 0,5, e o 95º percentil é o quantil 0,95.

Por exemplo, é possível usar um sketch que aceita quantis para descobrir a mediana do número de vezes que um aplicativo é aberto pelos usuários.

Funções de agregação aproximada

Como alternativa às funções de aproximação específicas baseadas em esboço, o GoogleSQL fornece funções de agregação aproximada predefinidas. Essas funções agregadas aproximadas são compatíveis com esboços para estimativas comuns, como contagem distinta, quantis e contagem superior, mas não permitem precisão personalizada. Elas também não expõem e armazenam o esboço para nova agregação, como outros tipos de esboços. As funções agregadas aproximadas são projetadas para executar consultas rápidas baseadas em esboços sem configuração detalhada.

Para conferir uma lista de funções agregadas aproximadas que podem ser usadas para aproximação baseada em esboço, consulte Funções agregadas aproximadas.