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. Captura todas as informações necessárias para extrair um resultado de agregação, continuar uma agregação de dados ou fundi-lo com outro esboço, o que permite a reagregação.

Calcular uma métrica usando um esboço é substancialmente menos dispendioso do que calcular um valor exato. Se o cálculo for demasiado lento ou exigir demasiado armazenamento temporário, use esboços para reduzir o tempo de consulta e os recursos.

Além disso, o cálculo de cardinalidades, como o número de utilizadores distintos, ou quantis, como a duração mediana da visita, sem esboços, normalmente, só é possível através da execução de tarefas sobre os dados não processados, uma vez que os dados já agregados não podem ser combinados.

Considere uma tabela com os seguintes dados:

Produto Número de utilizadores Duração mediana 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 utilizadores para ambos os produtos porque não sabemos quantos utilizadores 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 das visitas foi perdida.

Uma solução é armazenar esboços na tabela. Cada esboço é uma representação aproximada e compacta de uma propriedade de entrada específica, como a cardinalidade, que pode armazenar, unir (ou voltar a agregar) e consultar para obter resultados quase exatos. No exemplo anterior, pode estimar o número de utilizadores distintos para o produto A e o produto B criando e unindo (reagregando) os esboços para cada produto. Também pode estimar a duração mediana das visitas com esboços de quantis que também pode unir e consultar.

Por exemplo, a seguinte consulta usa esboços HLL++ e KLL para estimar utilizadores distintos e a duração mediana da visita para o YouTube (Produto A) e o 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
  );

Uma vez que um esboço tem uma compressão com perdas dos dados originais, introduz um erro estatístico representado por um limite de erro ou um intervalo de confiança (IC). Para a maioria das aplicações, esta incerteza é pequena. Por exemplo, um esboço de contagem de cardinalidade típico tem um erro relativo de cerca de 1% em 95% de todos os casos. Um esboço troca alguma precisão, ou precisão, por cálculos mais rápidos e menos caros, e menos armazenamento.

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

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

Reagregação com a união de esboços

Os esboços permitem-lhe armazenar e unir dados para uma nova agregação eficiente. Isto torna os esboços particularmente úteis para vistas materializadas de conjuntos de dados. Pode unir esboços para construir um resumo de várias streams de dados com base em esboços parciais criados para cada stream.

Por exemplo, se criar um esboço para o número estimado de utilizadores distintos todos os dias, pode obter o número de utilizadores distintos durante os últimos sete dias ao unir os esboços diários. A reagregação dos esboços diários unificados ajuda a evitar a leitura da entrada completa do conjunto de dados.

A reagregação de esboços também é útil no processamento analítico online (OLAP). Pode unir esboços para criar um resumo detalhado de um cubo OLAP, onde o esboço resume os dados ao longo de uma ou mais dimensões específicas do cubo. As agregações OLAP não são possíveis com contagens distintas verdadeiras.

Que tipo de esboço devo usar?

Os diferentes algoritmos de esboços são concebidos para diferentes tipos de métricas, como o HLL++ para contagens distintas e o KLL para quantis. O GoogleSQL também fornece funções agregadas aproximadas que pode usar para consultar estes tipos de dados sem ter de especificar detalhes da consulta, como o nível de precisão.

O esboço que usa depende do tipo de dados que precisa de estimar.

Estimativa da cardinalidade

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

Por exemplo, para obter o número de utilizadores únicos que usaram ativamente um produto num determinado mês (métricas UAM ou 28 UAD), use um esboço de HLL++.

Calcule um quantil

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

Por exemplo, para obter a duração mediana da visita dos clientes numa loja ou para acompanhar a latência do percentil 95 que os pedidos permanecem numa fila antes de serem resolvidos, use um esboço KLL.

Esboços de HLL++

O HyperLogLog++ (HLL++) é um algoritmo de esboço para estimar a cardinalidade. O HLL++ baseia-se no artigo HyperLogLog in Practice, onde o ++ denota os aumentos feitos ao algoritmo HyperLogLog.

A cardinalidade é o número de elementos distintos na entrada de um esboço. Por exemplo, pode usar um esboço HLL++ para obter o número de utilizadores únicos que abriram uma aplicação.

O HLL++ estima cardinalidades muito pequenas e muito grandes. O HLL++ inclui uma função de hash de 64 bits, uma representação esparsa para reduzir os requisitos de memória para estimativas de cardinalidade pequenas e uma correção de parcialidade empírica para estimativas de cardinalidade pequenas.

Precisão

Os esboços de HLL++ suportam a precisão personalizada. A tabela seguinte mostra os valores de precisão suportados, o tamanho máximo de armazenamento e o intervalo de confiança (IC) dos níveis de precisão típicos:

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

Pode definir a precisão de um esboço HLL++ quando o inicializa com a função HLL_COUNT.INIT.

Eliminação

Não pode eliminar valores de um esboço HLL++.

Detalhes adicionais

Para ver uma lista de funções que pode usar com esboços HLL++, consulte as funções HLL++.

Integração do Sketch

Pode integrar esboços HLL++ com outros sistemas. Por exemplo, pode criar esboços em aplicações externas, como o Dataflow, o Apache Spark e o ZetaSketch, e, em seguida, consumi-los no GoogleSQL ou vice-versa.

Além do GoogleSQL, pode usar esboços de HLL++ com Java.

Esboços KLL

KLL (abreviatura de Karnin-Lang-Liberty) é um algoritmo de streaming para calcular esboços para quantis aproximados. Calcula quantis arbitrários de forma muito mais eficiente do que os cálculos exatos, ao preço de um pequeno erro de aproximação.

Precisão

Os esboços KLL suportam a precisão personalizada. A precisão define a exatidão de um quantil aproximado q devolvido.

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

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

Por exemplo, suponhamos que quer encontrar o valor mediano, Φ = 0.5, e usa a precisão predefinida de 1000. Em seguida, a classificação do valor devolvido pela função KLL_QUANTILES.EXTRACT_POINT difere da classificação verdadeira, no máximo, em n/1000 em 99,999% dos casos. Por outras palavras, o valor devolvido está quase sempre entre os percentis 49,9 e 50,1. Se tiver 1 000 000 de itens no seu esboço, a classificação da mediana devolvida está quase sempre entre 499 000 e 501 000.

Se usar uma precisão personalizada de 100 para encontrar o valor mediano, a classificação do valor devolvido pela função KLL_QUANTILES.EXTRACT_POINT difere da classificação verdadeira em, no máximo, n/100 em 99,999% dos casos. Por outras palavras, o valor devolvido está quase sempre entre os percentis 49 e 51. Se tiver 1 000 000 de itens no seu esboço, a classificação da mediana devolvida está quase sempre entre 490 000 e 510 000.

Pode definir a precisão de um esboço KLL quando o inicializa 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 podem usar uma otimização adicional que é especialmente útil se os valores de entrada provirem de um pequeno universo. A tabela seguinte contém duas colunas para INT64. Uma coluna fornece um limite superior no tamanho do esboço 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 mil milhões 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 produzir como uma fração do número total de linhas na entrada do esboço, normalizada entre 0 e 1. Se uma função suportar phi, a função devolve um valor v tal que aproximadamente Φ * n entradas são inferiores ou iguais a v e (1-Φ) * n entradas são superiores ou iguais a v.

Detalhes adicionais

Para ver uma lista de funções que pode usar com esboços KLL, consulte o artigo Funções de quantil KLL.

O algoritmo KLL é definido no artigo Optimal Quantile Approximation in Streams e tem o nome dos seus autores, Karnin, Lang e Liberty, que publicaram o artigo em 2016. O algoritmo KLL melhora o algoritmo MP80 mais antigo através da utilização de buffers de tamanho variável para reduzir a utilização de memória para grandes conjuntos de dados, reduzindo 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

Os 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 numa amostra da mesma forma. Um esboço com suporte de quantis permite-lhe estimar quantis resumindo esses intervalos e probabilidades em resultados de quantis quase exatos.

Normalmente, os quantis são definidos de duas formas:

  • 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 destes têm nomes específicos: o 2-quantil único é a mediana, os 4-quantis são quartis, os 100-quantis são percentis, etc. As funções KLL devolvem adicionalmente o mínimo (exato) e o máximo da entrada, pelo que, quando consulta os 2-quantis, são devolvidos três valores.

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

Por exemplo, pode usar um esboço com suporte de quantis para obter a mediana do número de vezes que uma aplicação é aberta pelos utilizadores.

Funções de agregação aproximadas

Como alternativa a funções de aproximação específicas baseadas em esboços, o GoogleSQL fornece funções agregadas aproximadas predefinidas. Estas funções de agregação aproximadas suportam esboços para estimativas comuns, como a contagem distinta, os quantis e a contagem superior, mas não permitem uma precisão personalizada. Também não expõem nem armazenam o esboço para reagregação, como outros tipos de esboços. As funções agregadas aproximadas destinam-se a executar consultas rápidas baseadas em esboços sem configuração detalhada.

Para ver uma lista de funções agregadas aproximadas que pode usar com a aproximação baseada em esboços, consulte o artigo Funções agregadas aproximadas.