Zero-Cost NDV Estimation from Columnar File Metadata

Each language version is independently generated for its own context, not a direct translation.

Imagine que você é um chef de cozinha e precisa preparar um banquete gigante para milhares de pessoas. Antes de começar a cozinhar, você precisa saber duas coisas cruciais: quantos ingredientes diferentes você tem na despensa e quanto espaço na geladeira você vai precisar para guardar tudo isso.

Normalmente, para saber exatamente quantos ingredientes únicos existem, você teria que abrir cada pote, contar um por um e anotar tudo. Isso levaria horas e atrasaria o jantar.

Este artigo apresenta uma "mágica" de culinária: um método para descobrir quantos ingredientes únicos você tem sem nunca abrir os potes, olhando apenas para as etiquetas que já estão coladas neles. E o melhor: isso não custa nada extra e não gasta energia.

Aqui está a explicação simples, usando analogias do dia a dia:

O Problema: A Etiqueta Incompleta

Em arquivos de dados modernos (como o formato Parquet), os dados são guardados em "blocos" (chamados row groups). Cada bloco tem uma etiqueta que diz:

O tamanho total dos dados (se não fossem comprimidos).
O menor e o maior valor encontrado naquele bloco (ex: a pessoa mais baixa e a mais alta do grupo).

O problema é que essas etiquetas não dizem explicitamente: "Existem 500 nomes diferentes aqui". Calcular isso exato exigiria ler todos os dados, o que é lento.

A Solução: Duas "Pistas" Inteligentes

Os autores descobriram que podemos usar duas pistas diferentes nas etiquetas para adivinhar o número de itens únicos, dependendo de como os dados estão organizados.

Pista 1: A Equação do "Espaço na Prateleira" (Inversão do Dicionário)

Imagine que você tem uma lista de compras onde os itens repetidos são substituídos por códigos curtos (ex: "Maçã" vira "A", "Banana" vira "B").

Se você sabe o tamanho total da lista de códigos e sabe o tamanho médio de cada palavra original, você pode fazer uma conta de trás para frente.
A analogia: É como saber que uma mala cheia de roupas ocupa 50kg. Se você sabe que cada camiseta pesa 200g e cada calça 500g, e sabe quantas roupas há no total, consegue estimar quantas camisetas e calças existem, mesmo sem abrir a mala.
Quando funciona: Quando os ingredientes estão bem misturados em todos os blocos (dados "bem distribuídos").

Pista 2: O Jogo das "Fichas Coletadas" (Estatísticas de Mínimo e Máximo)

Agora imagine que você tem 50 caixas de ovos. Em cada caixa, você anota apenas o ovo mais pequeno e o ovo mais grande.

Se as caixas estiverem organizadas por tamanho (a caixa 1 tem ovos pequenos, a caixa 2 tem médios, a caixa 3 tem grandes), os "menores" e "maiores" de cada caixa serão todos diferentes.
A analogia: É como um jogo de "Coletar Figurinhas". Se você tem 50 caixas e cada uma te dá uma figurinha nova e diferente (porque estão organizadas), você sabe que tem pelo menos 50 figurinhas únicas. Se as caixas forem todas iguais, você só vê as mesmas figurinhas repetidas.
Quando funciona: Quando os dados estão organizados ou ordenados (como uma lista telefônica ou dados por data).

O "Detetive de Distribuição"

O grande truque do artigo é um pequeno "detetive" que olha para as etiquetas e decide qual pista usar:

Se os blocos se sobrepõem muito (dados misturados), ele usa a Pista 1 (o tamanho).
Se os blocos são diferentes uns dos outros (dados ordenados), ele usa a Pista 2 (os extremos).
Se não tem certeza, ele pega o maior número das duas estimativas para garantir que não subestime o espaço necessário.

Por que isso é incrível?

Zero Custo: Não precisa ler os dados reais, apenas as metadados (as etiquetas). É instantâneo.
Economia de Memória: Em sistemas de banco de dados modernos (especialmente os que usam placas gráficas/GPU), saber quantos itens únicos existem ajuda a alocar a memória exata necessária. Se você alocar pouco, o sistema trava. Se alocar demais, você desperdiça dinheiro.
Precisão: Em testes reais, esse método errou menos de 10% na maioria dos casos, o que é suficiente para tomar decisões rápidas de otimização.

Resumo da Ópera

Em vez de entrar na biblioteca inteira para contar quantos livros únicos existem, os autores criaram um método que olha para o tamanho da estante e para a capa do primeiro e último livro de cada seção para deduzir, com alta precisão, quantos títulos diferentes existem lá dentro.

Isso permite que computadores tomem decisões inteligentes e rápidas sobre como processar dados gigantescos, sem precisar gastar tempo lendo tudo o que está escrito. É como adivinhar o tamanho da festa olhando apenas para o convite e a lista de convidados mais velhos e mais novos, sem precisar contar cada pessoa na porta.

Each language version is independently generated for its own context, not a direct translation.

Título: Estimação de NDV sem Custo a partir de Metadados de Arquivos Colunares

Autor: Claude Brisson (VoltronData)

1. O Problema

Em motores de consulta distribuídos e acelerados por GPU (como o Theseus, desenvolvido na VoltronData), a otimização baseada em custos depende criticamente de estimativas precisas do Número de Valores Distintos (NDV) de uma coluna.

Limitação Atual: Em formatos colunares como o Apache Parquet, o campo distinct_count (contagem exata de valores distintos) raramente é populado, pois calcular essa métrica é computacionalmente caro e a maioria dos escritores de dados a omite.
Desafio: Métodos alternativos, como amostragem ou manutenção de esboços (sketches) como HyperLogLog, exigem acesso aos dados ou infraestrutura adicional no lado do escritor, o que contradiz o objetivo de planejamento de consultas baseado apenas em metadados (sem leitura de dados).
Objetivo: Desenvolver um método para estimar o NDV global de uma coluna utilizando apenas os metadados existentes do arquivo, sem acesso às páginas de dados e sem armazenamento extra.

2. Metodologia

O artigo propõe uma abordagem híbrida que explora dois sinais implícitos nos metadados do Parquet (e formatos similares), combinando-os através de um detector de distribuição de dados.

A. Inversão da Equação de Tamanho do Dicionário

Princípio: Colunas com cardinalidade baixa a média usam codificação por dicionário. O tamanho descomprimido total ( $S$ ) de um bloco de coluna é a soma do tamanho do dicionário e dos índices.
Equação: $S = ndv \times len + (N - nulls) \times \lceil \log_2(ndv) \rceil / 8$ $S = n d v \times l e n + (N - n u l l s) \times ⌈ lo g_{2} (n d v)⌉ /8$
- Onde $ndv$ é o número de valores distintos, $len$ é o tamanho médio em bytes dos valores, e $N$ é o número de linhas.
Solução: O método inverte essa equação para resolver $ndv$ . Como a função envolve um teto ( $\lceil \cdot \rceil$ ), utiliza-se o método de Newton-Raphson com uma aproximação contínua para a derivada.
Estimativa de $len$ : Para tipos de comprimento variável, o tamanho médio é estimado a partir dos valores mínimos e máximos distintos observados nos metadados de todos os grupos de linhas.
Aplicabilidade: Funciona bem quando os valores distintos estão bem distribuídos entre os grupos de linhas (alta sobreposição de faixas de valores).

B. Diversidade de Mínimos/Máximos (Modelo do Coleccionador de Cupons)

Princípio: Cada grupo de linhas armazena estatísticas de mínimo e máximo. A diversidade desses extremos reflete a cardinalidade subjacente.
Modelo: Utiliza-se o Problema do Colecionador de Cupons para modelar a probabilidade de observar valores distintos ao amostrar $n$ grupos de linhas de uma população de $NDV$ valores.
Equação: $E[m] = NDV \times (1 - e^{-n/NDV})$ , onde $m$ é o número de mínimos (ou máximos) distintos observados.
Solução: Inverte-se a equação via Newton-Raphson para encontrar o $NDV$ .
Aplicabilidade: É robusto para dados ordenados ou particionados, onde cada grupo de linhas cobre uma faixa de valores distinta, gerando muitos extremos únicos. O método de inversão de dicionário falha nestes casos (subestimando o NDV).

C. Detecção de Distribuição e Combinação

Classificador: Um detector leve analisa a sobreposição de faixas ( $overlap\_ratio$ $o v er l a p_r a t i o$ ) e a monotonicidade dos pontos médios entre grupos de linhas para classificar os dados como:
- Bem distribuídos (Well-spread): Alta sobreposição.
- Ordenados/Particionados: Baixa sobreposição, alta monotonicidade.
- Misto.
Estratégia de Fusão: O estimador final toma o máximo entre as duas estimativas ( $ndv_{dict}$ e $ndv_{minmax}$ ), limitado pelo número de linhas não nulas e por restrições de tipo (ex: limites teóricos para inteiros ou strings ASCII). Isso mitiga os modos de falha de cada método individual.

3. Contribuições Principais

Equação Fechada para NDV: Derivação de uma equação que relaciona o NDV ao tamanho de armazenamento do dicionário, resolvida numericamente.
Reconhecimento de Estatísticas como Esboços: Identificação de que as estatísticas de min/max de grupos de linhas funcionam como esboços de cardinalidade implícitos, recuperáveis via inversão do modelo do colecionador de cupons.
Detector de Distribuição: Um mecanismo leve que roteia entre os dois estimadores com base na estrutura dos dados.
Previsão de Memória em Lotes: Aplicação do modelo de colecionador de cupons para prever o tamanho do dicionário necessário para lotes de processamento em GPU sem ler os dados.

4. Resultados e Avaliação

Implementação: A técnica foi implementada e validada em produção no motor de consulta Theseus (VoltronData).
Precisão:
- Para colunas bem distribuídas, os erros foram tipicamente abaixo de 10%.
- Para colunas ordenadas, a abordagem híbrida corrigiu a subestimação sistemática que ocorreria se apenas a inversão de diciário fosse usada.
Custo Computacional: A complexidade é O(n) em relação ao número de grupos de linhas, com uso de espaço O(1). Todas as operações são feitas em uma única passagem sobre os metadados, sem acesso aos dados.
Perda de Dados: O autor nota que os dados experimentais detalhados foram perdidos com a liquidação dos ativos da VoltronData, mas o método foi reconstruído a partir da memória e validado conceitualmente.

5. Significado e Aplicabilidade

Otimização de Consultas: Permite que otimizadores de consulta tomem decisões informadas (como pushdown de agregações e ordenação de junções) sem precisar escanear os dados.
Alocação de Memória GPU: Crucial para motores GPU, permitindo alocar memória para dicionários de forma precisa antes do processamento, evitando overhead ou falhas de memória.
Generalização: Embora demonstrado no Parquet, o método é aplicável a qualquer formato colunar que possua codificação por dicionário e estatísticas de partição (ex: ORC, F3).
Inovação: Transforma metadados projetados para predicate pushdown (min/max) e compressão (dicionário) em uma ferramenta poderosa de perfilamento de dados e estimativa de cardinalidade, eliminando a necessidade de custos adicionais de I/O ou armazenamento.

Em resumo, o artigo apresenta uma solução elegante e de "custo zero" para um problema fundamental em bancos de dados analíticos modernos, permitindo planejamento eficiente de consultas apenas inspecionando o cabeçalho dos arquivos.