PolarDB:Filtrar dados usando IMCI

Como o IMCI organiza os dados

O IMCI organiza os dados das colunas em grupos de aproximadamente 64.000 linhas cada, armazenados na ordem de inserção, sem chave de ordenação. Como os dados não possuem ordenação inerente, o IMCI não filtra registros com a mesma precisão dos índices ordenados do InnoDB. Sem o pruning, todas as consultas carregam todos os pacotes de dados relevantes.

Após a avaliação de um pacote de dados por um pruner do IMCI, o pacote entra em um dos três estados seguintes:

O IMCI suporta quatro métodos de pruning: partition pruning, statistics pruning (índices minmax e filtros Bloom), filtros Runtime e índices bitmap.

Escolha um método de pruning

Use a tabela a seguir para selecione um método com base nos seus dados e no tipo de consulta.

O IMCI cria automaticamente índices minmax e filtros Bloom para tipos de colunas suportados. O partition pruning e os índices bitmap exigem configuração explícita. Os filtros Runtime não requerem configuração e são gerados dinamicamente durante a execução da consulta.

Partition pruning

O partition pruning filtra partições inteiras antes da leitura de qualquer dado. Quando uma cláusula WHERE inclui a chave de partição, o IMCI usa metadados da partição para identificar as correspondentes e ignora as demais.

O IMCI suporta três métodos de particionamento:

• RANGE: Divide uma tabela em intervalos com pontos de limite definidos. O IMCI utiliza busca binária para localizar a partição correspondente.

• LIST: Mapeia valores discretos para partições usando tuplas <value, part_id>, também pesquisadas via busca binária.

• HASH: Enumera possíveis valores de entrada, aplica hash e determina em qual partição cada um se enquadra. Eficaz apenas para campos inteiros com poucos valores distintos.

Exemplo: particionamento por intervalo na data do pedido

Se a tabela orders estiver particionada por mês, a consulta a seguir acessará apenas a partição de janeiro de 2022:

SELECT * FROM orders WHERE order_date = '2022-01-01';

O IMCI também aplica partition pruning por inferência de equivalência em junções. Por exemplo, se tanto R quanto S estiverem particionados na coluna a, a condição R.a = S.a AND R.a > 10 permite que o IMCI infira S.a > 10 e realize o pruning também nas partições de S.

Quando usar:

• A maioria das consultas filtra pela chave de partição.

• Você gerencie o ciclo de vida dos dados por partição (por exemplo, removendo partições antigas em vez de excluir linhas).

• São necessárias partições de nível 1 ou nível 2 conforme os requisitos de negócio.

Quando não usar:

• As consultas raramente incluem a chave de partição na cláusula WHERE. Nesse caso, o pruning não tem efeito.

• A tabela é grande e não é possível execute DDL fora do horário de pico. Operações de DDL em tabelas grandes existentes são custosas.

Statistics pruning

O statistics pruning utiliza metadados leves por coluna, armazenados em memória, para decidir se um pacote de dados pode ser ignorado. Como as estatísticas residem na memória, sua avaliação não exige E/S de disco. Essa abordagem assemelha-se aos índices de data skipping no ClickHouse e ao Knowledge Grid do Infobright.

O IMCI fornece dois pruners baseados em estatísticas: índices minmax e filtros Bloom. Ambos são criados automaticamente.

Filtros Runtime

Um filtro Runtime é gerado dinamicamente durante a execução da consulta. Ele captura o conjunto de resultados de um lado da junção (geralmente a tabela de dimensão menor) e o passa como filtro para o outro lado (geralmente a tabela de fatos maior) antes do início da varredura da tabela de fatos. À medida que a consulta avança e o filtro se torna mais restritivo (por exemplo, quando uma consulta TopK encontra melhores candidatos e eleva o limiar mínimo), mais pacotes sofrem pruning dinamicamente.

O IMCI suporta dois tipos de filtros Runtime:

• Filtro Runtime Minmax: Gera uma expressão de intervalo (ex.: id > 1 AND id < 100) a partir dos valores mínimo e máximo do conjunto de resultados do lado de construção (build-side).

• Filtro Runtime Bloom filter: Constrói um filtro Bloom sobre o conjunto de resultados do lado de construção para filtragem baseada em igualdade de colunas do tipo STRING.

Filtros Runtime do tipo Bloom filter aumentam a sobrecarga de memória e não são adequados para grandes conjuntos de resultados.

Exemplo: aceleração de uma hash join

SELECT * FROM sales JOIN items ON sales.item_id = items.id WHERE items.price > 1000

Neste caso, items é a tabela de dimensão (pequena) e sales é a tabela de fatos (grande). O IMCI constrói um filtro Runtime a partir dos valores de item_id que satisfazem price > 1000. Se os IDs resultantes variarem de 1 a 100, o IMCI gera id > 1 AND id < 100 ou IN(id1, id2, id3 ...) e o passa para a varredura de sales, realizando o pruning de linhas antes das sondagens de junção.

Se existir um pruner minmax na coluna filtrada, o IMCI usa o filtro Runtime para realizar pruning adicional nos pacotes de dados, reduzindo tanto as linhas varridas quanto os pacotes carregados.

Filtros Runtime também se aplicam a consultas com GROUP BY e ORDER BY. Em cenários de processamento massivamente paralelo (MPP), eles reduzem o volume de dados transferidos entre nós.

Índices Bitmap

Um índice bitmap atribui um vetor de bits a cada valor distinto em uma coluna. Cada bit indica se aquele valor aparece em uma determinada linha. Para avaliar um predicado de filtro, o IMCI executa operações bitwise AND/OR nos vetores de bits relevantes e recupera diretamente os números das linhas correspondentes, sem carregar pacotes de dados completos.

Os índices bitmap são mais eficazes quando:

• Colunas têm baixa cardinalidade (ex.: status, categoria, segmento de mercado) e os valores estão distribuídos uniformemente entre os pacotes de dados, tornando o statistics pruning ineficaz.

• Consultas combinam múltiplos predicados de filtro com AND ou OR.

• Consultas realizam agregações sem materializar linhas individuais, como SELECT COUNT(*) FROM t WHERE ....

Em comparação com índices B-tree, índices bitmap usam menos espaço de armazenamento para colunas de baixa cardinalidade. No entanto, índices bitmap globais exigem bloqueio de toda a tabela em atualizações de linha, sendo mais adequados para cargas de trabalho com muitas leituras.

Benchmark de desempenho

Os resultados a seguir medem a aceleração por pruners e índices bitmap em 100 GB de dados TPC-H com concorrência 1, usando armazenamento em memória. Cargas de trabalho limitadas por E/S mostram maior melhoria.

Próximos passos

• Implementação do operador TopK no IMCI — Como o IMCI usa estatísticas para acelerar consultas TopK com o padrão ORDER BY ... LIMIT, incluindo como os filtros Runtime se tornam mais restritivos dinamicamente durante a execução da consulta.