Тип данных QBit

Тип данных QBit реорганизует хранение векторов, чтобы ускорить приближенный поиск. Вместо того чтобы хранить элементы каждого вектора вместе, он группирует одинаковые позиции битов во всех векторах. При этом векторы хранятся с полной точностью, а во время поиска вы можете выбирать уровень квантования: считывать меньше битов, чтобы сократить I/O и ускорить вычисления, или больше битов для более высокой точности. Это дает выигрыш в скорости за счет уменьшения объема передаваемых данных и вычислений благодаря квантованию, при этом все исходные данные при необходимости остаются доступными.

Чтобы объявить столбец типа QBit, используйте следующий синтаксис:

column_name QBit(element_type, dimension[, stride])

• element_type – тип каждого элемента вектора. Допустимые типы: Int8, BFloat16, Float32 и Float64
• dimension – размерность, то есть число элементов в каждом векторе
• stride – необязательный параметр. Число размерностей, хранящихся вместе в одной группе потоков. Если не указано, по умолчанию используется dimension (одна группа). Если указано, dimension должно быть кратно stride, а если stride меньше dimension, то stride должно быть кратно 8. Размерности dimension разбиваются на dimension / stride последовательных групп, а битовые плоскости каждой группы хранятся в отдельных потоках. Это позволяет при поиске по первым D размерностям (где D кратно stride) считывать только потоки тех групп, которые охватывают эти размерности, что полезно для эмбеддингов Matryoshka.

Использование типа QBit при определении столбца таблицы:

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] │
└──────────────────────────┘

Массивы преобразуются в QBit, если длина массива соответствует размерности QBit. Тип элементов массива не обязательно должен совпадать с типом элементов QBit. Любой числовой тип элементов автоматически преобразуется в нужный тип. Это позволяет напрямую перенести существующий столбец эмбеддингов в столбец 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] │
└────┴───────────────────────────────────┘

Явное преобразование также работает с CAST, например CAST(embedding AS QBit(Float32, 8)).

Обратное преобразование восстанавливает исходный вектор из битово-транспонированного представления, поэтому приведение QBit к Array возвращает сохранённые значения. Это обратная операция к преобразованию массивов в QBit:

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

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

Восстановленный массив использует тип элементов QBit, после чего его элементы преобразуются в запрошенный тип элементов массива. Поэтому работает и приведение, которое одновременно меняет тип элементов, например из QBit(Float32, N) в Array(Float64).

Преобразование по цепочке Array -> QBit -> Array не приводит к потере данных для Int8, Float32 и Float64. Для BFloat16 оно соответствует прямому преобразованию в BFloat16 — единственная потеря точности связана с самим BFloat16.

Когда dimension не кратна 8, конечные элементы дополнения, присутствующие во внутреннем представлении, отбрасываются, поэтому результат всегда содержит ровно dimension элементов.

QBit можно привести к другому QBit, если размерность (число элементов вектора) остается прежней. При этом и element_type, и stride могут изменяться; приведение к QBit с другой размерностью вызывает исключение, поскольку это привело бы к изменению самого вектора.

Изменение element_type заново строит вектор и преобразует каждый элемент в новый тип, в точности как при соответствующем преобразовании Array: расширение (например, из QBit(Float32, N) в QBit(Float64, N)) происходит без потери точности, тогда как сужение приводит к потере точности так же, как и сужающее приведение Array.

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

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

Изменение только stride (при сохранении того же element_type) перегруппировывает сохранённые битовые плоскости, не затрагивая значения, поэтому потерь данных не возникает:

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

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

QBit реализует шаблон доступа к подстолбцам, который позволяет обращаться к отдельным битовым плоскостям сохранённых векторов. Доступ к каждой битовой позиции можно получить с помощью синтаксиса .N, где N — это позиция бита:

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                  │
└───────────────────────────┘

Количество доступных подстолбцов зависит от типа элементов (а при использовании stride — от числа групп stride):

• Int8: 8 подстолбцов на группу stride (1-8)
• BFloat16: 16 подстолбцов на группу stride (1-16)
• Float32: 32 подстолбца на группу stride (1-32)
• Float64: 64 подстолбца на группу stride (1-64)

Подстолбцы упорядочены в порядке групп: в общем случае vec.N считывает битовую плоскость (N-1) % element_size группы stride (N-1) / element_size. Например, в QBit(BFloat16, 4096, 1024) 4096 размерностей разбиваются на 4 группы по 1024, поэтому всего получается 64 подстолбца: vec.1 … vec.16 — это битовые плоскости первой группы stride (размерности 1–1024), vec.17 … vec.32 относятся ко второй группе (размерности 1025–2048), и так далее.

По умолчанию QBit хранит каждую битовую плоскость как один поток, охватывающий все dimension размерностей, поэтому при поиске всегда считываются целые битовые плоскости по всему вектору. Необязательный параметр stride разбивает dimension размерностей на dimension / stride последовательных групп и хранит битовые плоскости каждой группы в отдельных потоках. Это позволяет при поиске только по первым D размерностям (где D кратно stride) считывать только потоки тех групп, которые покрывают эти размерности, — это полезно для эмбеддингов Matryoshka, где начальные размерности образуют пригодный для использования эмбеддинг меньшей размерности.

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

Здесь 4096 размерностей разбиты на 4 группы по 1024. Подстолбцы идут в порядке групп: для BFloat16 (16 битовых плоскостей) vec.1 … vec.16 — это 16 битовых плоскостей первой группы stride (размерности 1–1024), vec.17 … vec.32 относятся ко второй группе (размерности 1025–2048) и так далее. В общем случае vec.N считывает битовую плоскость (N-1) % element_size группы stride (N-1) / element_size.

Чтобы выполнить поиск с уменьшенной размерностью, передайте число считываемых размерностей в качестве четвёртого аргумента транспонированных функций расстояния (см. ниже). Опорный вектор должен содержать как минимум столько элементов (любые дополнительные конечные элементы игнорируются), а это значение должно быть кратно stride.

arrayElement (и оператор vec[n]) возвращает n-й элемент вектора, восстановленный с полной точностью типа элемента. Считываются только битовые плоскости группы stride, содержащей этот элемент. arraySlice возвращает QBit по выбранным размерностям (проекцию на подмножество размерностей); смещение и длина должны быть константами, поскольку размерность QBit является частью его типа. Срез, выровненный по границам групп stride, сохраняет stride и повторно использует сохранённые потоки битовых плоскостей без копирования:

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]               │
└──────────────────────┴───────────────────────┘

Это функции расстояния для поиска по векторному сходству, использующие тип данных QBit:

• L2DistanceTransposed
• cosineDistanceTransposed
• dotProductTransposed

Для QBit со stride эти функции принимают необязательный четвёртый аргумент used_dims — число начальных размерностей для чтения, — при этом читаются только группы stride, охватывающие эти размерности. Опорный вектор должен содержать как минимум used_dims элементов (любые дополнительные элементы в конце игнорируются, поэтому вектор запроса полной размерности можно повторно использовать для поиска в уменьшенной размерности, не обрезая его заранее), а used_dims должен быть кратен stride.