Tipo de dado QBit

Documentação do tipo de dado QBit no ClickHouse, que permite quantização de granularidade fina para busca vetorial aproximada

O tipo de dado QBit reorganiza o armazenamento de vetores para tornar as buscas aproximadas mais rápidas. Em vez de armazenar juntos os elementos de cada vetor, ele agrupa as mesmas posições de dígitos binários em todos os vetores. Isso armazena os vetores com precisão total e permite escolher o nível de quantização de granularidade fina no momento da busca: leia menos bits para reduzir a E/S e acelerar os cálculos, ou mais bits para obter maior precisão. Você aproveita os ganhos de velocidade da redução da transferência de dados e do processamento proporcionada pela quantização, mas todos os dados originais continuam disponíveis quando necessário.

Para declarar uma coluna do tipo QBit, use a seguinte sintaxe:

column_name QBit(element_type, dimension[, stride])

• element_type – o tipo de cada elemento do vetor. Os tipos permitidos são Int8, BFloat16, Float32 e Float64
• dimension – o número de elementos de cada vetor
• stride – opcional. O número de dimensões armazenadas juntas em um grupo de fluxos. Quando omitido, o padrão é dimension (um único grupo). Quando fornecido, dimension deve ser um múltiplo de stride e, quando stride for menor que dimension, stride deve ser um múltiplo de 8. As dimension dimensões são divididas em dimension / stride grupos contíguos, e os planos de bits de cada grupo são armazenados em fluxos separados. Isso permite que uma busca nas primeiras D dimensões (com D sendo um múltiplo de stride) leia apenas os fluxos dos grupos que abrangem essas dimensões, o que é útil para embeddings Matryoshka.

​

Criando QBit

Usando o tipo QBit na definição de coluna da tabela:

CREATE TABLE test (id UInt32, vec QBit(Float32, 8)) ENGINE = Memory;
INSERT INTO test VALUES (1, [1, 2, 3, 4, 5, 6, 7, 8]), (2, [9, 10, 11, 12, 13, 14, 15, 16]);
SELECT vec FROM test ORDER BY id;

┌─vec──────────────────────┐
│ [1,2,3,4,5,6,7,8]        │
│ [9,10,11,12,13,14,15,16] │
└──────────────────────────┘

​

Convertendo arrays em QBit

Arrays são convertidos em QBit quando o comprimento do array corresponde à dimensão do QBit. O tipo de elemento do array não precisa corresponder ao tipo de elemento do QBit. Qualquer tipo numérico de elemento é convertido automaticamente. Isso permite mover uma coluna existente de embeddings diretamente para uma coluna QBit:

CREATE TABLE embeddings (id UInt32, embedding Array(Float32)) ENGINE = Memory;
INSERT INTO embeddings VALUES (1, [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8]), (2, [0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1]);

CREATE TABLE vectors (id UInt32, vec QBit(Float32, 8)) ENGINE = Memory;
INSERT INTO vectors SELECT id, embedding FROM embeddings;

SELECT * FROM vectors ORDER BY id;

┌─id─┬─vec───────────────────────────────┐
│  1 │ [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8] │
│  2 │ [0.8,0.7,0.6,0.5,0.4,0.3,0.2,0.1] │
└────┴───────────────────────────────────┘

A conversão também pode ser feita explicitamente com CAST, por exemplo CAST(embedding AS QBit(Float32, 8)).

​

Convertendo QBit para arrays

A conversão inversa reconstrói o vetor original a partir da representação transposta em bits; portanto, converter um QBit em um Array retorna os valores armazenados. Isso é o inverso de converter arrays para QBit:

SELECT [1, 2, 3, 4]::QBit(Float32, 4)::Array(Float32) AS vec;

┌─vec───────┐
│ [1,2,3,4] │
└───────────┘

O array reconstruído usa o tipo de elemento de QBit, e seus elementos são então convertidos para o tipo de elemento do array solicitado. Portanto, um cast que também altera o tipo de elemento, como de QBit(Float32, N) para Array(Float64), também funciona.

Uma conversão de ida e volta Array -> QBit -> Array não perde informação para Int8, Float32 e Float64. Para BFloat16, ela corresponde a uma conversão direta para BFloat16 — a única precisão perdida é a do próprio BFloat16.

Quando a dimension não é um múltiplo de 8, os elementos de preenchimento no final presentes na representação interna são descartados, de modo que o resultado sempre tenha exatamente dimension elementos.

​

Conversão entre tipos QBit

Um QBit pode ser convertido em outro QBit desde que a dimension (o número de elementos do vetor) permaneça a mesma. Tanto element_type quanto stride podem mudar; converter para um QBit com uma dimension diferente gera uma exceção, porque isso alteraria o próprio vetor.

Alterar o element_type reconstrói o vetor e converte cada elemento para o novo tipo, exatamente como na conversão correspondente de Array: a ampliação (por exemplo, de QBit(Float32, N) para QBit(Float64, N)) é exata, enquanto a redução perde precisão da mesma forma que uma conversão redutora de Array.

SELECT [1, 2, 3, 4]::QBit(Float32, 4)::QBit(Float64, 4) AS vec;

┌─vec───────┐
│ [1,2,3,4] │
└───────────┘

Alterar apenas o stride (mantendo o mesmo element_type) reagrupa os planos de bits armazenados sem alterar os valores, portanto não há perda de dados:

SELECT range(16)::Array(Float32)::QBit(Float32, 16)::QBit(Float32, 16, 8)::Array(Float32)
     = range(16)::Array(Float32) AS is_lossless;

┌─is_lossless─┐
│           1 │
└─────────────┘

​

Subcolunas do QBit

QBit implementa um padrão de acesso a subcolunas que permite acessar planos de bits individuais dos vetores armazenados. Cada posição de bit pode ser acessada usando a sintaxe .N, em que N é a posição do bit:

CREATE TABLE test (id UInt32, vec QBit(Float32, 8)) ENGINE = Memory;
INSERT INTO test VALUES (1, [0, 0, 0, 0, 0, 0, 0, 0]);
INSERT INTO test VALUES (1, [-0, -0, -0, -0, -0, -0, -0, -0]);
SELECT bin(vec.1) FROM test;

┌─bin(tupleElement(vec, 1))─┐
│ 00000000                  │
│ 11111111                  │
└───────────────────────────┘

O número de subcolunas acessíveis depende do tipo de elemento (e, quando há stride, do número de grupos de stride):

• Int8: 8 subcolunas por grupo de stride (1-8)
• BFloat16: 16 subcolunas por grupo de stride (1-16)
• Float32: 32 subcolunas por grupo de stride (1-32)
• Float64: 64 subcolunas por grupo de stride (1-64)

As subcolunas seguem uma ordem em que o grupo vem primeiro: em geral, vec.N lê o plano de bits (N-1) % element_size do grupo de stride (N-1) / element_size. Por exemplo, com QBit(BFloat16, 4096, 1024), as 4096 dimensões são divididas em 4 grupos de 1024, portanto há 64 subcolunas: vec.1 … vec.16 são os planos de bits do primeiro grupo de stride (dimensões 1–1024), vec.17 … vec.32 pertencem ao segundo grupo (dimensões 1025–2048), e assim por diante.

​

Strides

Por padrão, um QBit armazena cada plano de bits como um único fluxo que abrange todas as dimension dimensões, de modo que uma busca sempre lê os planos de bits completos ao longo de todo o vetor. O parâmetro opcional stride particiona as dimension dimensões em dimension / stride grupos contíguos e armazena os planos de bits de cada grupo em fluxos separados. Isso permite que uma busca restrita às primeiras D dimensões (com D sendo um múltiplo de stride) leia apenas os fluxos dos grupos que cobrem essas dimensões — algo útil para embeddings Matryoshka, em que as dimensões iniciais formam um embedding utilizável de menor dimensionalidade.

CREATE TABLE test (id UInt32, vec QBit(BFloat16, 4096, 1024)) ENGINE = MergeTree ORDER BY id;

Aqui, as 4096 dimensões são divididas em 4 grupos de 1024. As subcolunas seguem uma ordem em que o grupo vem primeiro: com BFloat16 (16 planos de bits), vec.1 … vec.16 são os 16 planos de bits do primeiro grupo de stride (dimensões 1–1024), vec.17 … vec.32 pertencem ao segundo grupo (dimensões 1025–2048), e assim por diante. Em geral, vec.N lê o plano de bits (N-1) % element_size do grupo de stride (N-1) / element_size.

Para executar uma busca em dimensão reduzida, passe o número de dimensões a serem lidas como o quarto argumento das funções de distância transpostas (veja abaixo). O vetor de referência deve ter pelo menos essa quantidade de elementos (quaisquer elementos extras ao final são ignorados), e o valor deve ser um múltiplo de stride.

​

Acesso a elementos e fatiamento

arrayElement (e o operador vec[n]) retorna o enésimo elemento do vetor, reconstruído com a precisão total do tipo de elemento. Apenas os planos de bits do grupo de stride que contém o elemento são lidos. arraySlice retorna um QBit com as dimensões selecionadas (uma projeção para um subconjunto de dimensões); o deslocamento e o comprimento devem ser constantes, pois a dimensão de um QBit faz parte do seu tipo. Um fatiamento alinhado aos limites dos grupos de stride preserva o stride e reutiliza os fluxos de planos de bits armazenados sem copiá-los:

CREATE TABLE test (id UInt32, vec QBit(Float32, 8)) ENGINE = Memory;
INSERT INTO test VALUES (1, [1, 2, 3, 4, 5, 6, 7, 8]);
SELECT vec[3], arraySlice(vec, 2, 3) FROM test;

┌─arrayElement(vec, 3)─┬─arraySlice(vec, 2, 3)─┐
│                    3 │ [2,3,4]               │
└──────────────────────┴───────────────────────┘

​

Funções de busca vetorial

Estas são as funções de distância para busca vetorial por similaridade que usam o tipo de dado QBit:

• L2DistanceTransposed
• cosineDistanceTransposed
• dotProductTransposed

Para um QBit com stride, essas funções aceitam um quarto argumento opcional, used_dims — o número de dimensões iniciais a serem lidas — e leem apenas os grupos de stride que abrangem essas dimensões. O vetor de referência deve ter pelo menos used_dims elementos (quaisquer elementos extras no final são ignorados, portanto um vetor de consulta de tamanho completo pode ser reutilizado para uma busca com dimensão reduzida sem precisar fatiá-lo antes), e used_dims deve ser um múltiplo de stride.