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:

Não é possível calcular o número total de usuários dos dois produtos porque não sabemos quantos usuários usaram ambos os produtos na tabela. Da mesma forma, não é possível calcular a duração mediana 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 mediana da visita no YouTube (Produto A) e no 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 visualizações materializadas de conjuntos de dados. É possível mesclar esboços para criar um resumo de vários fluxos de dados com base em esboços 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 tipo de sketch usado depende dos dados que você precisa estimar.

Estimar a 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 extrair um quantil de um conjunto de dados, use um esboço KLL.

Por exemplo, para saber a duração mediana da visita dos clientes em uma loja ou rastrear a latência do 95º percentil dos tíquetes em uma fila antes de serem atendidos, 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 representação esparsa e de função de hash de 64-bits que reduz os requisitos de memória de estimativas cardinais pequenas e de correções de tendência empírica de estimativas cardinais 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:

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

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

Esboços KLL

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 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 q retornado.

Por padrão, a classificação de um quantil aproximado pode ter no máximo ±1/1000 * n de diferença 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 da mediana, Φ = 0.5, e use a precisão padrão de 1000. Então, 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 está quase sempre entre os percentis 49,9 e 50,1. Se você tiver 1.000.000 de itens no seu esboço, a classificação da mediana retornada estará quase sempre entre 499.000 e 501.000.

Se você usar uma precisão personalizada de 100 para encontrar o valor da mediana, a classificação do valor retornado pela função KLL_QUANTILES.EXTRACT_POINT vai diferir 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 esboço, 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 esboço KLL depende do parâmetro de precisão e do tipo de entrada. Se o tipo de entrada for INT64, os esboços poderão usar uma otimização adicional que é especialmente útil se os valores de entrada vierem 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.

Phi

Phi (Φ) representa o quantil a ser produzido como uma fração do número total de linhas na entrada de esboço, normalizada entre 0 e 1. Se uma função aceitar phi, ela vai retornar um valor v de forma 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 quantílicas KLL.

O algoritmo KLL é definido no artigo Optimal Quantile Approximation in Streams (link em inglês) e recebeu o nome dos autores Karnin, Lang e Liberty, que publicaram o artigo em 2016. O algoritmo KLL melhora o MP80 mais antigo usando buffers de tamanho variável para reduzir o uso de memória em grandes conjuntos de dados, diminuindo o tamanho do esboço de O(log n) para O(1). Devido à natureza não determinística 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 forma. Um sketch compatível com quantil permite estimar quantis resumindo esses intervalos e probabilidades em resultados de quantil quase exatos.

Os quantis geralmente são definidos de duas maneiras:

• Para um número inteiro positivo q, os q-quantis 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 2-quantil é a mediana, os 4-quantis são quartis, os 100-quantis são percentis etc. As funções KLL também retornam o mínimo e o máximo (exatos) da entrada. Portanto, ao consultar os 2-quantis, três valores são retornados.

• Outra opção é considerar os quantis como Φ-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 percentil 95 é o quantil 0,95.

Por exemplo, você pode usar um sketch compatível com quantis para receber 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.