Estimativa de valores frequentes¶

Visão geral¶

O Snowflake fornece uma implementação do algoritmo Space-Saving apresentado em Computação eficiente de elementos frequentes e Top-k em fluxos de dados por Metwally, Agrawal e Abbadi. Ele é implementado através da família APPROX_TOP_K de funções.

Além disso, a função APPROX_TOP_K_COMBINE utiliza o algoritmo Space-Saving paralelo delineado por Cafaro, Pulimeno e Tempesta.

A porcentagem de erro para o algoritmo depende muito da inclinação dos dados e do número de contadores utilizados no algoritmo. Conforme os dados se tornam mais inclinados, ou mais contadores são utilizados, a saída será mais precisa.

Funções SQL¶

As seguintes Funções de agregação são fornecidas para usar o Space-Saving para estimar valores frequentes:

• APPROX_TOP_K: Retorna uma aproximação dos valores frequentes na entrada.

• APPROX_TOP_K_ACCUMULATE: Pula a etapa de estimativa final e retorna o estado Space-Saving no final de uma agregação.

• APPROX_TOP_K_COMBINE: Combina (ou seja, funde) os estados de entrada em um único estado de saída.

• APPROX_TOP_K_ESTIMATE: Compila uma estimativa de cardinalidade de um estado Space-Saving produzida por APPROX_TOP_K_ACCUMULATE e APPROX_TOP_K_COMBINE.

Detalhes de implementação¶

Cada contador em nossa implementação rastreia um item e sua frequência. Notavelmente, nossa implementação não rastreia os valores ípsilon dos contadores, pois eles só são úteis para dar garantias sobre a saída do algoritmo; eles não são usados para o algoritmo em si.

O número máximo de contadores está definido em 100 mil. Neste caso, há 100 mil contadores armazenados na memória, mas apenas uma fração destes são armazenados em um estado exportado.

O número máximo de k é de 100 mil. Este valor é automaticamente reduzido se os valores não puderem todos caber na saída.

Na maioria dos casos, o tempo de execução de nossa implementação não depende do número de contadores. Nossa implementação garante que o número de contadores não tenha um efeito perceptível sobre o tempo de execução do algoritmo.

Cada contador em cada estado de agregação utiliza uma quantidade constante de sobrecarga de memória de cerca de 100 bytes. Assim, se uma agregação usar c contadores e houver g grupos de agregação, a agregação usará c * g * 100B de memória, mais memória para armazenar os valores. Se esta memória exceder o orçamento total de memória, a memória é vazada para o disco. Isto é muito menos memória do que a versão exata usaria, especialmente quando há um grande número de valores únicos.