Bitset

Este tópico introduz o mecanismo de bitset que ajuda a permitir funcionalidades chave como filtragem de atributos e operações de eliminação em Milvus.

Visão geral

Um conjunto de bits é um conjunto de bits. Os bits são elementos com apenas dois valores possíveis, normalmente 0 e 1, ou valores booleanos true e false. No Milvus, os conjuntos de bits são matrizes de números de bits 0 e 1 que podem ser utilizados para representar determinados dados de forma compacta e eficiente, por oposição a ints, floats ou chars. Um número de bits é 0 por defeito e só é definido para 1 se cumprir determinados requisitos.

As operações em conjuntos de bits são efectuadas com lógica booleana, segundo a qual um valor de saída é válido ou inválido, também denotado por 1 e 0, respetivamente. Por exemplo, o operador lógico AND pode ser utilizado para comparar dois conjuntos de bits com base em itens nas mesmas posições de índice e produz um novo conjunto de bits com os resultados. Se dois itens numa posição forem iguais, então, no novo conjunto de bits, 1 será escrito nessa posição; 0 se forem diferentes.

Implementação

O conjunto de bits é um mecanismo simples, mas poderoso, que ajuda o Milvus a efetuar a filtragem de atributos, a eliminação de dados e a consulta com o Time Travel.

Filtragem de atributos

Como os bitsets contêm apenas dois valores possíveis, são perfeitos para armazenar resultados de filtragem de atributos. Os dados que cumprem os requisitos de um determinado filtro de atributos são marcados com 1.

Eliminação de dados

Os conjuntos de bits são uma forma compacta de armazenar informação sobre se uma linha num segmento foi eliminada. As entidades eliminadas são marcadas com 1 no conjunto de bits correspondente, que não será computado durante uma pesquisa ou consulta.

Exemplos

Aqui apresentamos três exemplos que ilustram como os bitsets são usados no Milvus, com referências às três principais implementações de bitsets discutidas acima. Nos três casos, há um segmento com 8 entidades e, em seguida, uma série de eventos de linguagem de manipulação de dados (DML) ocorre na ordem mostrada abaixo.

• Quatro das entidades, cujos primary_keys são [1, 2, 3, 4] respetivamente, são inseridas quando o carimbo de data/hora ts é igual a 100.
• As restantes quatro entidades, cujos primary_keys são [5, 6, 7, 8], são inseridas quando o carimbo de data/hora ts é igual a 200.
• As entidades cujos primary_keys são [7, 8] são eliminadas quando o carimbo de data/hora ts é igual a 300.
• Apenas as entidades, cujos primary_keys são [1, 3, 5, 7], satisfazem as condições de filtragem de atributos.

Ordem dos eventos DML

Caso um

Neste caso, um utilizador define time_travel como 150, o que significa que o utilizador efectua uma consulta sobre dados que satisfazem ts = 150. O processo de geração do conjunto de bits é ilustrado na Figura 1.

Durante a fase inicial de filtragem, o filter_bitset deve ser [1, 0, 1, 0, 1, 0, 1, 0], em que as entidades [1, 3, 5, 7] são marcadas como 1 porque são resultados de filtragem válidos.

No entanto, as entidades [4, 5, 6, 7] não foram inseridas na base de dados do vetor quando ts é igual a 150. Por conseguinte, estas quatro entidades devem ser marcadas como 0, independentemente da condição de filtragem. Agora, o resultado do conjunto de bits deve ser [1, 0, 1, 0, 0, 0, 0, 0].

Conforme discutido em Eliminação de dados, as entidades marcadas com 1 são ignoradas durante uma pesquisa ou consulta. O resultado do conjunto de bits precisa agora de ser invertido para ser combinado com o mapa de bits de eliminação, o que nos dá [0, 1, 0, 1, 1, 1, 1, 1].

Quanto ao conjunto de bits de eliminação del_bitset, o valor inicial deve ser [0, 0, 0, 0, 0, 0, 1, 1]. No entanto, as entidades 7 e 8 não são eliminadas até que ts seja 300. Portanto, quando ts é 150, as entidades 7 e 8 ainda são válidas. Como resultado, o valor de del_bitset após a Viagem no Tempo é [0, 0, 0, 0, 0, 0, 0, 0].

Agora temos dois conjuntos de bits após a viagem no tempo e a filtragem de atributos: filter_bitset [0, 1, 0, 1, 1, 1, 1, 1] e del_bitset [0, 0, 0, 0, 0, 0, 0, 0] . Combine estes dois conjuntos de bits com o operador lógico binário OR. O valor final de result_bitset é [0, 1, 0, 1, 1, 1, 1, 1], o que significa que apenas as entidades 1 e 3 serão computadas na fase seguinte de pesquisa ou consulta.

Figura 1. Pesquisa com viagem no tempo = 150.

Caso dois

Neste caso, o utilizador define time_travel como 250. O processo de geração do conjunto de bits é ilustrado na Figura 2.

Tal como no caso um, o filter_bitset inicial é [1, 0, 1, 0, 1, 0, 1, 0].

Todas as entidades estão na base de dados vetorial quando ts = 250. Por conseguinte, o filter_bitset permanece o mesmo quando se considera o carimbo de data/hora. Mais uma vez, temos de inverter o resultado e obter [0, 1, 0, 1, 0, 1, 0, 1].

Quanto ao conjunto de bits de eliminação del_bitset, o valor inicial é [0, 0, 0, 0, 0, 0, 1, 1]. No entanto, as entidades 7 e 8 não foram eliminadas até ts ser 300. Por conseguinte, quando ts é 250, as entidades 7 e 8 ainda são válidas. Como resultado, o del_bitset após a Viagem no Tempo é [0, 0, 0, 0, 0, 0, 0, 0].

Agora temos dois conjuntos de bits após a Viagem no Tempo e a filtragem de atributos: filter_bitset [0, 1, 0, 1, 0, 1, 0, 1] e del_bitset [0, 0, 0, 0, 0, 0, 0, 0] . Combine esses dois conjuntos de bits com o operador lógico binário OR. O conjunto de bits resultante é [0, 1, 0, 1, 0, 1, 0, 1]. Ou seja, apenas as entidades [1, 3, 5, 7] serão computadas na fase de pesquisa ou consulta seguinte.

Figura 2. Pesquisa com Viagem no Tempo = 250.

Caso três

Neste caso, o utilizador define time_travel como 350. O processo de geração do conjunto de bits é ilustrado na Figura 3.

Tal como nos casos anteriores, o filter_bitset inicial é [0, 1, 0, 1, 0, 1, 0, 1].

Todas as entidades estão na base de dados vetorial quando ts= 350. Assim, o filter_bitset final, invertido, é [0, 1, 0, 1, 0, 1, 0, 1], tal como no caso dois.

Quanto ao conjunto de bits de eliminação del_bitset, uma vez que as entidades 7 e 8 já foram eliminadas em ts = 350, o resultado de del_bitset é [0, 0, 0, 0, 0, 0, 1, 1].

Agora temos dois conjuntos de bits após a viagem no tempo e a filtragem de atributos: filter_bitset [0, 1, 0, 1, 0, 1, 0, 1] e del_bitset [0, 0, 0, 0, 0, 0, 1, 1] . Combine estes dois conjuntos de bits com o operador lógico binário OR. O último result_bitset é [0, 1, 0, 1, 0, 1, 1, 1]. Ou seja, apenas as entidades [1, 3, 5] serão computadas na fase de pesquisa ou consulta seguinte.

Figura 3. Pesquisa com Viagem no Tempo = 350.

O que se segue

Agora que já sabe como funcionam os conjuntos de bits no Milvus, talvez também queira:

• Aprender a usar strings para filtrar os resultados da pesquisa, ou consultar a Pesquisa Híbrida na nossa documentação.
• Compreender como os dados são processados em Milvus.