PolarDB:Análise do recurso de busca full-text no IMCI

O IMCI utiliza o algoritmo RBM (Roaring Bitmaps) para compactar e computar posting lists (ou seja, conjuntos de IDs de documentos).

A implementação do RBM baseia-se na biblioteca CRoaring e selecione dinamicamente uma estratégia de armazenamento com base na densidade dos dados:

• Se o número de IDs de documentos na posting list for menor que um limiar predefinido, std::array será usado para armazenamento.

• Caso o número exceda o limiar, o armazenamento muda para o tipo roaring::Roaring64Map para lidar com dados esparsos ou densos em grande escala, mantendo uma alta taxa de compactação.

Características de desempenho:

• Suporta buscas com complexidade O(logN) durante a construção do índice.

• Permite aceleração via instruções SIMD para operações de conjuntos, como interseção e união.

• Oferece reorganização de espaço quando os dados são gravados em disco para reduzir fragmentação.

• Possibilita o uso de valores minimum/maximum para filtragem rápida e otimização de iteradores durante as consultas.

O IMCI emprega o algoritmo FST (Finite State Transducer) para construir o dicionário de termos, equilibrando eficiência de tempo e de espaço.

• Eficiência de espaço: Ao compartilhar prefixos e sufixos comuns dos termos, o espaço de armazenamento é efetivamente comprimido.

• Eficiência de tempo: A complexidade de tempo para buscar um termo é O(L), onde L é o comprimento do termo.

Por exemplo, suponha que os termos China, Chinese e love sejam inseridos em ordem e que seus deslocamentos de endereço de posting list sejam 5, 10 e 15. O dicionário construído é mostrado na figura a seguir. A imagem ilustra que o FST não apenas compartilha prefixos e sufixos comuns para economizar espaço, mas também garante que cada transição tenha um valor associado único. Uma consulta começa no estado inicial 0 e verifica cada caractere do termo em busca de uma aresta de saída correspondente. Se a aresta existir, a consulta acumula o valor associado. Caso contrário, verifica se o estado atual é um estado final. Por exemplo, "Chinese" acumula um valor associado de 15 e seu último caractere é um estado final, indicando que o termo existe no dicionário. Além disso, o cálculo de prefixo do FST é baseado em bytes, não em caracteres, suportando codificações como UTF-8.

Quando o índice full-text do PolarDB IMCI é construído com SPIMI, o IMCI lê continuamente os dados do columnstore da coluna alvo, tokeniza cada linha para obter um conjunto de termos e, em seguida, adiciona cada termo e seu número de linha correspondente a uma tabela hash, acumulando um valor de uso de memória. Quando o uso de memória excede o limiar de tamanho de segmento, o IMCI cria um dicionário a partir dos termos e posting lists na tabela hash, redefine a memória e continua com a próxima linha até que todos os dados do columnstore sejam processados. O processo principal para construir um dicionário (FST) a partir da tabela hash (std::unordered_map) é o seguinte: primeiro, ordena-se a tabela hash por termo (chave); depois, serializam-se todas as posting lists da tabela hash para o disco em ordem, registrando seus endereços de deslocamento relativo no disco; em seguida, adiciona-se cada termo e o endereço de deslocamento da posting list desse termo ao algoritmo FST para construir o dicionário; finalmente, compacta-se o dicionário, grava-se no disco e registram-se as informações do segmento atual (incluindo tamanho do dicionário, endereço inicial do dicionário, endereço inicial da posting list e intervalo de números de linha) nos metadados. O PolarDB não constrói um dicionário global para evitar ordenação externa (um dicionário global também precisaria ser dividido por prefixo para permitir a construção de um índice de termos sobre ele). Em vez disso, como o armazenamento columnstore usa um modelo de gravação append-only, o PolarDB adota um método de construção leve que produz múltiplos dicionários locais com base no limiar de memória, conforme mostrado na figura a seguir. Quando houver memória suficiente, aumente o limiar de memória ao máximo. Assim, mais instâncias do mesmo termo cairão no mesmo segmento invertido, economizando espaço e melhorando o desempenho da consulta.

Além da construção normal de índice invertido descrita acima, o índice full-text do PolarDB IMCI também suporta a mesclagem assíncrona de índices invertidos quando o sistema está ocioso em segundo plano. O índice columnstore do PolarDB IMCI é um índice secundário de uma tabela regular. Em operações INSERT, os dados são sempre anexados ao mecanismo de armazenamento columnstore por coluna, na ordem de inserção. DELETE usa marcação para exclusão (mark-for-deletion), e UPDATE é convertido em DELETE seguido de INSERT. O IMCI utiliza o array InsertMask para marcar a versão de inserção de cada linha nos dados do columnstore para verificações de visibilidade, e usa lsm DeleteMask para marcar uma linha existente como excluída. Simultaneamente, operações em segundo plano, como Compactação assíncrona e Reciclagem, reorganizam dados e recuperam espaço. Como parte do mecanismo columnstore, o índice full-text do PolarDB IMCI também usa uma tarefa de Compactação assíncrona de índice invertido em segundo plano para limpar periodicamente os dados marcados como excluídos, economizando espaço e melhorando o desempenho das consultas. A mesclagem de índices invertidos usa o segmento invertido como unidade: múltiplos segmentos invertidos são mesclados em um novo segmento invertido, e os segmentos originais não são modificados. Isso evita que os objetos de snapshot de índice invertido usados pelas consultas se tornem inválidos. Quando a mesclagem termina, um novo snapshot de índice invertido é gerado, e novas consultas passam a usar esse novo snapshot. Graças ao método de construção local e ao design de marcação para exclusão, uma inserção em massa não aciona uma reconstrução global no índice full-text do PolarDB IMCI; apenas a parte incremental é construída. O custo de atualização também é muito baixo, pois requer apenas uma marca de exclusão, de modo que o desempenho de gravação não é afetado mesmo em cenários de atualizações frequentes. Adicionalmente, a mesclagem assíncrona periódica em segundo plano produz índices invertidos mais compactos para melhorar o desempenho das consultas. Combinado com a capacidade de consulta concorrente do column store, isso atende aos requisitos de resposta em nível de milissegundos mesmo em cenários de dados massivos.

O índice full-text do PolarDB IMCI suporta a função oficial MATCH do MySQL e o operador LIKE.

• Função MATCH

  O PolarDB IMCI permite o uso da função MATCH para busca full-text independentemente da existência de um índice full-text no row store. Se não houver índice no row store, a consulta é roteada diretamente para o nó do column store. Se existir um índice no row store, a consulta é distribuída inteligentemente com base na avaliação de custo. Para impedir que operações demoradas desencadeadas por um índice full-text nativo do MySQL durante a fase de otimização — como sincronização de tabelas auxiliares e carregamento de cache — afetem o desempenho do column store, o PolarDB ignora essas operações no início da distribuição da consulta.

  Durante a fase de execução, o IMCI oferece dois métodos de recuperação: o operador FtsTableScan e a expressão MATCH. O primeiro obtém linhas correspondentes diretamente do índice invertido, sendo adequado para cenários com alta taxa de filtragem. O segundo busca o índice por número de linha, sendo ideal para cenários em que condições anteriores já filtraram a maior parte dos dados. A eficiência de execução de ambos os métodos depende da eficácia da filtragem de dados por outros predicados. O otimizador do column store estima a taxa de filtragem com base em estatísticas e selecione dinamicamente a estratégia ideal. Quando o método de operador é escolhido, o sistema reescreve automaticamente a função MATCH para os operadores FtsTableScan + Filter.

  Como o índice full-text é construído de forma assíncrona, pode haver um breve atraso na visibilidade de novos dados. Por padrão, o executor do column store complementa os resultados da consulta com uma varredura completa da tabela sobre dados não indexados para garantir a integridade dos resultados. Um parâmetro controla se essa etapa deve ser ignorada, permitindo equilibrar flexivelmente desempenho e consistência em cenários de alta concorrência e grandes volumes de dados. Também é possível ajustar os parâmetros de construção do índice para aumentar a frequência de sincronização de dados e reduzir o escopo da varredura completa da tabela, melhorando ainda mais a eficiência da consulta.

• Aceleração de LIKE

  Sob condições específicas, o PolarDB IMCI suporta a conversão mútua entre LIKE e MATCH. A conversão de LIKE para MATCH é usada principalmente para acelerar consultas, reduzindo a sobrecarga de comparação linha a linha de grandes quantidades de strings em varreduras completas de tabela.

  Atualmente, essa conversão só entra em vigor quando o índice full-text do columnstore usa o tokenizador ngram e o comprimento do token ngram é menor ou igual ao comprimento da string de padrão do LIKE. Sob essa condição, o otimizador pode reescrever um predicado como LIKE '%abc%' para os operadores FtsTableScan + Filter, usando o índice invertido para filtrar rapidamente as linhas candidatas.

  No entanto, como o mecanismo de correspondência da tokenização ngram difere da semântica do LIKE (por exemplo, "abbc" é tokenizado em ab, bb e bc, que se sobrepõem aos tokens ab e bc de "abc" e podem ser falsamente julgados como correspondência), a expressão LIKE original é mantida como condição de filtro subsequente para verificação exata, garantindo a correção dos resultados.

  Esse mecanismo melhora significativamente o desempenho da consulta, equilibrando eficazmente a precisão semântica e a eficiência de execução.

O índice invertido do PolarDB IMCI consiste em múltiplos segmentos invertidos. Cada segmento invertido contém seus próprios metadados, um dicionário de termos e uma série de posting lists, onde cada termo corresponde unicamente a uma posting list. Os metadados registram informações como os endereços iniciais do dicionário e das posting lists. Esses metadados são pequenos e residem na memória por padrão para acelerar o acesso ao índice.

A recuperação do índice invertido é realizada por segmento invertido. O processo principal inclui ler os dados do dicionário, construir o objeto de dicionário FST (Finite State Transducer), buscar o termo alvo no dicionário e ler a posting list correspondente para construir o objeto de posting list RBM (Roaring Bitmap).

Especificamente, as consultas dividem-se em dois modos:

1. Consulta por operador: Percorre os metadados de todos os segmentos invertidos, obtém o endereço inicial do dicionário, carrega os dados do dicionário, constrói o objeto de dicionário e busca o termo alvo. Se o termo for encontrado, combina o endereço de deslocamento da posting list do termo com o endereço inicial no segmento para ler o objeto completo da posting list.

2. Consulta por expressão: Determina o conjunto de segmentos invertidos com base no número de linha, filtra adicionalmente pelo intervalo de números de linha nos metadados e, em seguida, execute uma busca no dicionário e leitura da posting list semelhante à consulta por operador nos segmentos invertidos correspondentes.

Para melhorar o desempenho, o IMCI suporta cache de dicionário de termos. Ele utiliza um mecanismo de cache LRU (Least Recently Used) independente, e o módulo de agendamento ajusta dinamicamente a cota de memória desse cache. Uma única posting list geralmente é pequena (a maioria requer apenas uma E/S de 4 KB), e as posting lists são numerosas, de modo que a taxa de acerto do cache e o benefício de armazená-las em cache são limitados. Por isso, o cache de posting lists é desativado por padrão para evitar desperdício de recursos de memória.

Esse design equilibra o uso de memória e a sobrecarga de E/S, garantindo a eficiência das consultas.