Como é que a base de dados compreende e executa a sua consulta?

Imagem da capa

Este artigo foi transcriado por Angela Ni.

Uma consulta vetorial em Milvus é o processo de obtenção de vectores através de uma filtragem escalar baseada numa expressão booleana. Com a filtragem escalar, os utilizadores podem limitar os resultados das suas consultas com determinadas condições aplicadas aos atributos dos dados. Por exemplo, se um utilizador procurar filmes lançados entre 1990 e 2010 e com pontuações superiores a 8,5, apenas os filmes cujos atributos (ano de lançamento e pontuação) satisfazem a condição.

Esta publicação tem como objetivo examinar a forma como uma consulta é concluída no Milvus, desde a introdução de uma expressão de consulta até à geração do plano de consulta e à execução da consulta.

Saltar para:

• Expressão de consulta
• Geração do plano AST
• Execução da consulta

Expressão da consulta

A expressão da consulta com filtragem de atributos em Milvus adopta a sintaxe EBNF (Extended Backus-Naur form). A imagem seguinte apresenta as regras de expressão em Milvus.

Sintaxe da expressão

As expressões lógicas podem ser criadas utilizando a combinação de operadores lógicos binários, operadores lógicos unários, expressões lógicas e expressões simples. Uma vez que a sintaxe EBNF é recursiva, uma expressão lógica pode ser o resultado da combinação ou parte de uma expressão lógica maior. Uma expressão lógica pode conter muitas sub-expressões lógicas. A mesma regra aplica-se em Milvus. Se um utilizador precisar de filtrar os atributos dos resultados com muitas condições, pode criar o seu próprio conjunto de condições de filtragem combinando diferentes operadores e expressões lógicas.

Expressão booleana

A imagem acima mostra parte das regras de expressão booleana no Milvus. Os operadores lógicos unários podem ser adicionados a uma expressão. Atualmente, o Milvus apenas suporta o operador lógico unário "not", que indica que o sistema tem de retirar os vectores cujos valores do campo escalar não satisfazem os resultados do cálculo. Os operadores lógicos binários incluem "e" e "ou". As expressões simples incluem expressões de termo e expressões de comparação.

O cálculo aritmético básico como a adição, a subtração, a multiplicação e a divisão também é suportado durante uma consulta no Milvus. A imagem seguinte demonstra a precedência das operações. Os operadores são listados de cima para baixo em precedência decrescente.

Precedência

Como é que uma expressão de consulta sobre determinados filmes é processada no Milvus?

Suponhamos que há uma grande quantidade de dados de filmes armazenados no Milvus e que o utilizador pretende consultar determinados filmes. Por exemplo, os dados de cada filme armazenados no Milvus têm os seguintes cinco campos: ID do filme, ano de lançamento, tipo de filme, pontuação e cartaz. Neste exemplo, o tipo de dados do ID do filme e do ano de lançamento é int64, enquanto as pontuações dos filmes são dados de ponto flutuante. Além disso, os cartazes dos filmes são armazenados no formato de vectores de ponto flutuante e o tipo de filme no formato de dados de cadeia. Nomeadamente, o suporte para o tipo de dados string é uma nova caraterística do Milvus 2.1.

Por exemplo, se um utilizador quiser consultar os filmes com pontuações superiores a 8,5. Os filmes também devem ter sido lançados entre uma década antes de 2000 e uma década depois de 2000 ou os seus tipos devem ser filmes de comédia ou de ação, o utilizador tem de introduzir a seguinte expressão de predicado: score > 8.5 && (2000 - 10 < release_year < 2000 + 10 || type in [comedy,action]).

Ao receber a expressão de consulta, o sistema executá-la-á na seguinte precedência:

1. Consulta de filmes com pontuação superior a 8,5. Os resultados da consulta são designados por "resultado1".
2. Calcular 2000 - 10 para obter o "resultado2" (1990).
3. Calcular 2000 + 10 para obter o "resultado3" (2010).
4. Procurar filmes com o valor de release_year superior a "resultado2" e inferior a "resultado3". Ou seja, o sistema precisa de consultar os filmes lançados entre 1990 e 2010. Os resultados da consulta são designados por "resultado4".
5. Consultar filmes que sejam comédias ou filmes de ação. Os resultados da consulta são designados por "resultado5".
6. Combine "resultado4" e "resultado5" para obter filmes que tenham sido lançados entre 1990 e 2010 ou que pertençam à categoria de comédia ou filme de ação. Os resultados são designados por "resultado6".
7. Pegue na parte comum de "resultado1" e "resultado6" para obter os resultados finais que satisfazem todas as condições.

Exemplo de filme

Geração do plano AST

O Milvus utiliza a ferramenta de código aberto ANTLR (ANother Tool for Language Recognition) para a geração do plano AST (abstract syntax tree). O ANTLR é um poderoso gerador de parser para ler, processar, executar ou traduzir ficheiros estruturados de texto ou binários. Mais especificamente, o ANTLR pode gerar um analisador para construir e percorrer árvores de análise com base em sintaxe ou regras predefinidas. A imagem seguinte é um exemplo em que a expressão de entrada é "SP=100;". LEXER, a funcionalidade de reconhecimento de linguagem incorporada no ANTLR, gera quatro tokens para a expressão de entrada - "SP", "=", "100" e ";". Em seguida, a ferramenta analisará os quatro tokens para gerar a árvore de análise correspondente.

árvore de análise

O mecanismo de análise é uma parte crucial da ferramenta ANTLR. Foi concebido para percorrer todas as árvores de análise para examinar se cada nó obedece às regras de sintaxe ou para detetar determinadas palavras sensíveis. Algumas das APIs relevantes estão listadas na imagem abaixo. Como o ANTLR começa no nó raiz e vai descendo por cada sub-nó até o final, não há necessidade de diferenciar a ordem de como percorrer a árvore de análise.

caminhador da árvore de análise

O Milvus gera o PlanAST para consulta de forma semelhante ao ANTLR. No entanto, o uso do ANTLR requer a redefinição de regras de sintaxe bastante complicadas. Portanto, o Milvus adopta uma das regras mais prevalecentes - regras de expressão booleana, e depende do pacote Expr open sourced no GitHub para consultar e analisar a sintaxe das expressões de consulta.

Durante uma consulta com filtragem de atributos, o Milvus irá gerar uma árvore de planos primitiva não resolvida usando o ant-parser, o método de análise fornecido pelo Expr, ao receber a expressão de consulta. A árvore de planos primitiva que obteremos é uma árvore binária simples. Em seguida, a árvore de planos é ajustada pelo Expr e pelo optimizador incorporado no Milvus. O optimizador em Milvus é bastante semelhante ao mecanismo de caminhada acima mencionado. Uma vez que a funcionalidade de otimização da árvore de planos fornecida pelo Expr é bastante sofisticada, a carga do optimizador incorporado no Milvus é aliviada em grande medida. Em última análise, o analisador analisa a árvore de planos optimizada de forma recursiva para gerar um plano AST na estrutura de buffers de protocolo (protobuf).

Fluxo de trabalho do plano AST

Execução da consulta

A execução da consulta é, na sua origem, a execução do plano AST gerado nas etapas anteriores.

No Milvus, um plano AST é definido numa estrutura proto. A imagem abaixo é uma mensagem com a estrutura protobuf. Existem seis tipos de expressões, entre as quais a expressão binária e a expressão unária, que podem ainda ter expressão lógica binária e expressão lógica unária.

protobuf1

protobuf2

A imagem abaixo é uma imagem UML da expressão de consulta. Demonstra a classe básica e a classe derivada de cada expressão. Cada classe tem um método para aceitar parâmetros de visitante. Este é um padrão típico de conceção de visitantes. O Milvus utiliza este padrão para executar o plano AST, uma vez que a sua maior vantagem é o facto de os utilizadores não terem de fazer nada às expressões primitivas, podendo aceder diretamente a um dos métodos dos padrões para modificar determinada classe de expressão de consulta e elementos relevantes.

UML

Ao executar um plano AST, o Milvus recebe primeiro um nó de plano do tipo proto. Em seguida, obtém um nó de plano do tipo segcore através do analisador interno C++ proto. Após a obtenção dos dois tipos de nós de plano, o Milvus aceita uma série de acessos de classe e, em seguida, modifica e executa a estrutura interna dos nós de plano. Por fim, o Milvus procura em todos os nós do plano de execução para obter os resultados filtrados. Os resultados finais são apresentados no formato de uma máscara de bits. Uma máscara de bits é um conjunto de números de bits ("0" e "1"). Os dados que satisfazem as condições de filtragem são marcados com "1" na máscara de bits, enquanto os que não satisfazem os requisitos são marcados com "0" na máscara de bits.

executar fluxo de trabalho

Sobre a série Deep Dive

Com o anúncio oficial da disponibilidade geral do Milvus 2.0, orquestrámos esta série de blogues Milvus Deep Dive para fornecer uma interpretação aprofundada da arquitetura e do código fonte do Milvus. Os tópicos abordados nesta série de blogues incluem:

• Visão geral da arquitetura do Milvus
• APIs e SDKs Python
• Processamento de dados
• Gestão de dados
• Consulta em tempo real
• Motor de execução escalar
• Sistema QA
• Motor de execução vetorial