ReaderMX.
PostgreSQL码农集散地

性能提升100倍, 向量数据库风云再起

Pdigoal约 21 分钟

重磅核弹: 性能提升100倍, 向量数据库再起腥风血雨

用过向量数据库的老司机肯定知道, 向量数据库最难搞的几个点:

1、对于hnsw类图结构的索引:

  • 索引build阶段, 慢. 需要耗费大量算力计算图结构, 需要耗费大量内存.
  • 查询阶段, 性能好. 但是如果要结合其他非向量字段过滤条件, 无法走索引过滤, 需要回表filter, 性能会下降. 通常某些情况下可能采用分区表、条件索引(partial index)解决部分问题.
  • 索引维护阶段, 频繁的实时DML后, 带来膨胀、图结构损坏或断裂问题, 导致召回率下降、性能下降等问题.

2、对于ivfflat类聚集结构的索引:

  • 索引build阶段, 快. 同样需要耗费大量算力计算center ID. 算法单一(通常是k-means)可能导致聚集效果不佳.
  • 查询阶段, 性能相比hnsw略差. 第一步搜索相近的centerIDs, 然后在聚集内扫描和排序. 因聚集内采用非图结构, 简单列表暴力扫描和排序会耗费更多的IO和CPU资源.
  • 索引维护阶段, 实时DML后, 相比hnsw比较容易维护.

3、不管什么索引类型, 索引本身占用空间大(取决于向量维度), 标准向量1个维度32bit, 一个1536维(openai embedding输出的维度)的向量值需要6K空间.

4、向量相似和其他条件共同查询时, 在索引加速定位层面只能二选一.

 中间出现过解决以上问题的方案和项目, 但还不够完美, 例如:  。

1、pgvectorscale 的 DiskANN. 依旧采用图结构, 但是索引内可以选择存储量化后的向量牺牲精度提升性能. 同时索引内支持附加存储labels值, 用于向量+标签过滤. 类似覆盖索引(include index).

2、VectorChord 改良 ivfflat.

改进之处在于:

  • 聚集分层, 类似分区表. 但是聚集点不多的话, 从所有聚集点提取TOP N最近聚集点并不是瓶颈, 所以分区可能对性能提升不明显.
  • 非平衡聚集. 这个可能不算改进点, k-means都是非平衡聚集, 也就是不是按标准距离划网格来生成聚集点.
  • build 阶段, 可配置聚集层数、聚集点数以及每个聚集点采样多少条, 可配置k-means迭代次数.  非常灵活, 有利于构造召回率、性能平衡的索引.
  • 支持采用外部计算的聚集点build index, 可利用GPU提升聚集点计算效率、可扩展聚集点算法(采用相较k-means更优的聚集算法).
  • 残差量化. 聚集点采用原始向量存储, 叶子结点采用tuple vector与聚集点的残差, 并对残差进行量化存储. 更加节省内存, 并在保证召回率的情况下提升性能.
  • rerank, 支持index rerank和table rerank. index rerank采用残差和聚集点回溯后rank(提供优秀的召回率和性能), table rerank回表使用tuple vector进行rank(提供最好的召回率).
  • prefilter, 这个pgvector新版本也支持了, 在返回result前使用filter条件进行过滤.  注意需要回表获取其他filter字段值进行过滤. 保证更好的return.
  • 限制召回. 通过参数控制最多选择多少条候选向量, 从而在保证召回率的情况下, 提升查询效率.
  • 更适合SIMD的紧凑存储结构. 采用更适合现代CPU批量值运算指令集的数据结构, 对残差量化值进行compact存储. 在build index的最后阶段进行compact.

同时增加了以下功能

  • 相比32bit vec和16bit halfvec, 增加8bit scalar vector类型. 在相比binary保留更好精度的同时压缩存储.
  • vec array @# query vec arr操作符. 适合多向量数组近似搜索.
  • 支持l2,ip,cosine三种维度的包含(Radius-based filtering)查询.
  • 预热, 支持预热向量表到内存中. 在内存足够, 并且需要进行高频且大范围的向量搜索时可以先进行预热.

VectorChord 选中cluster 后, 依旧是暴力计算cluster下的所有向量, 虽然采用SIMD进行批量计算.

更多细节参考: 《VectorChord 向量插件学习心得》

一、核爆方案

我这里提出一种新的方案, 要解决的问题是: VectorChord 这类采用了ivfflat结构索引的项目, 在选中cluster 后, 依旧是暴力计算cluster下的所有向量(虽然采用SIMD进行批量计算)的问题.

重点:  也就是在进入cluster后, 还可以采用索引进行高速检索list里的相似向量.  

思路如下:

1、量化

量化方法很多, 例如pgvectorscale项目采用的SBQ方法.

分析采样数据

  • 分析来自原始数据的向量样本，以计算每个维度的统计量
  • 计算每个维度的均值（用于1位量化）
  • 对于多位量化，还会额外计算方差 / 标准差
  • 将这些统计信息作为元数据存储，供后续量化过程中使用

量化过程（Quantization Process）

对于每一个向量的维度，SBQ 使用如下逻辑：

 1位量化（默认方式）  

  • 如果该维度的值高于该维度的均值，则记录为 1
  • 如果低于均值，则记录为 0

这种二进制编码方式提供了向量相对于整个数据集中心位置的紧凑表示。

 多位量化（可选方式） 

为了获得更高的精度，SBQ 可以为每个维度使用更多位数：

1. 计算 z-score（标准分数）：(值 - 均值) / 标准差
2. 将 z-score 的范围（通常为 -2 到 +2）划分为  个区域
3. 使用 n 位来对该值所属的区域进行编码

基于异或的距离度量（XOR-Based Distance Measurement）

两个 SBQ 压缩后的向量之间的距离通过以下方式计算：

  • 对这两个向量执行按位异或（XOR）操作
  • 统计结果中 1 的个数（即汉明距离）
  • 将该统计值作为距离度量指标

2、聚集

和ivfflat一样的方法, 就是先做一遍聚集, 把量化后的向量点(varbit)放入最邻近的聚集中. 用以减少扫描范围.

3、分段

对量化后的varbit进行分段.  例如一个1536维的向量, 如果按1bit量化, 就是1536 bit. 分成64段的话, 每一段就是24 bit(也就是代表了24个维度).

例如:

  • 用8个bit表示哪一段, 最多256段.
  • 用24个bit表示24个维度.
  • 组合起来就得到原始量化后的向量. 采用32bit (即int4)类型的数组, 最多可以表示6144长度的1bit量化后的向量.

int4[64] 即可表示1536维1bit量化后的向量.  (64个int4元素, 每个int的前8bit表示分段位置, 后24bit每个bit表示1个维度.)

如果用int2数组呢?

  • int2[192] 即可表示1536维1bit量化后的向量.  (192个int2元素, 每个int的前8bit表示分段位置, 后8bit每个bit表示1个维度.)

4、gin 倒排过滤

关键的来了, 对分段创建gin索引.

如何表示2个相似度大于1000的向量?  至少1000个bit一样, 对吧?

相似度越高, 表示不同的bit越少.

参考smlar插件.

smlar.threshold  FLOAT  
 Array's with similarity lower than threshold are not similar   
 by % operation  
smlar.type  STRING  
 Type of similarity formula: cosine(default), tfidf, overlap  

用法

set smlar.type = overlap;    
set smlar.threshold = 164;    

select arr1 % arr2;    
-- arr1和arr2至少有164个相同元素(即164个 bits 分段)才会返回true

5、检索过程

以int2[192]为例

首先对输入的向量进行量化和分段处理.

通过聚集过滤到少量center id的list内.

通过倒排索引, 快速检索每个int2元素对应的heap blockids. 也就是每个元素对应的heap表的行号中提取的blockID. ( 这块其实可以直接存储blockid, 不需要存储详细行号. )

开始投票过滤阶段. 每个元素一票, 给每个blockid投票.

192-164=28, 所以超过28票反对票的block就不用再投了, 将投票快速收敛到少数blocks.

返回票数大于等于164票的blockIDs.

搜索这些符合条件的blockIDs上的所有行, 采用bitxor(varbit1, varbit2)进行recheck.    -- 其实这一步应该已经不需要计算多少行了, 已经过滤得差不多了.

PS: 由于采用了GIN倒排索引, 期间还可以使用其他字段的等值过滤条件 ( gin索引不支持范围查询 ), PostgreSQL将对多个索引条件自动采用bitmap过滤

最后一步是 rerank. (因为分段后一个分段有多个bit, 通过分段来判断overlap, 多于一定多, 少于不一定少, 因为1个分段内可能有多个bit不一样.) 可以使用量化值的xor数作为排序基础, 也可以采用原始向量值的距离计算进行排序提高精度.

 把以上方法融入到一个新的gin索引里, 一气呵成就完美了. 当然, 这是需要编码的事情了.  

 我不能再说太多, 懂的都懂, 向量数据库又要掀起腥风血雨了! 

二、测试

我们可以使用pgvector和smlar插件来模拟测试, 对比两者性能差异.

下面的测试使用 《穷鬼玩PolarDB RAC一写多读集群系列 | 在Docker容器中用loop设备模拟共享存储搭建PolarDB RAC》    环境, pgvector更新到0.8.0.

create extension smlar;  
create extension vector;  

postgres=# \dx  
                                                          List of installed extensions  
        Name         | Version |      Schema       |                                         Description                                           
---------------------+---------+-------------------+---------------------------------------------------------------------------------------------  
 smlar               | 1.0     | public            | compute similary of any one-dimensional arrays  
 vector              | 0.8.0   | public            | vector data type and ivfflat and hnsw access methods  
...  
(19 rows)  

1、创建测试表

为突出测试对比重点, 仅需要模拟1536维varbit, 不需要原始向量.

create table tbl (  
  id int primary key,  
  vb bit(1536),   
  c1 int,  -- 其他过滤条件   
  c2 int[], -- 其他过滤条件   
  vb_arr int[]  -- 可选项. 存储vb分段内容, 可以不使用表达式索引.   
);   

-- 使用块内存储  
alter table tbl alter column vb set storage main;   
alter table tbl alter column vb_arr set storage main;   

postgres=# \d+ tbl  
                                            Table "public.tbl"
 Column |   Type    | Collation | Nullable | Default | Storage  | Compression | Stats target | Description   
--------+-----------+-----------+----------+---------+----------+-------------+--------------+-------------  
 id     | integer   |           | not null |         | plain    |             |              |   
 vb     | bit(1536) |           |          |         | main     |             |              |   
 c1     | integer   |           |          |         | plain    |             |              |   
 c2     | integer[] |           |          |         | extended |             |              |   
 vb_arr | integer[] |           |          |         | main     |             |              |   
Indexes:  
"tbl_pkey" PRIMARY KEY, btree (id)  
Access method: heap  

用递归方法, 使用随机24个int8生成1536维随机量化值

with recursive tmp as (  
select ((random()-0.5)*18446744073709551615::numeric)::bigint::bit(64)::varbit as id, 1 as cnt  
union all  
select ((random()-0.5)*18446744073709551615::numeric)::bigint::bit(64)||tmp.id as id, tmp.cnt+1 as cnt from tmp where cnt<24  
)  
select bit_length(id) from tmp where cnt=24;  

1536  

创建一个生成1536维随机量化值的函数, 便于调用

create or replace function gen_rand_1536() returns bit(1536) as $$   
with recursive tmp as (  
select ((random()-0.5)*18446744073709551615::numeric)::bigint::bit(64)::varbit as id, 1 as cnt  
union all  
select ((random()-0.5)*18446744073709551615::numeric)::bigint::bit(64)||tmp.id as id, tmp.cnt+1 as cnt from tmp where cnt<24  
)  
select id from tmp where cnt=24;  
$$ language sql strict;  

postgres=# select bit_length(gen_rand_1536());  
 bit_length   
------------  
       1536  
(1 row)  

创建一个生成随机数组的函数, 便于调用. 模拟生成其他标签字段

create or replace function gen_rand_arr(int, int) returns int[] as $$  
select array(select (random()*$1)::int from generate_series(1,$2));  
$$ language sql strict;  

postgres=# select gen_rand_arr(100,10);  
          gen_rand_arr             
---------------------------------  
 {58,95,90,44,38,79,80,12,20,70}  
(1 row)  

2、创建分段函数

这里采用 int4[64] 把bit(1536)分成64段, 你有兴趣可以再试试 int2/int8 .

CREATE OR REPLACE FUNCTION bit1536_to_int4_array(bit_data bit(1536))  
RETURNS int4[] AS $$  
DECLARE  
    result int4[] := '{}';  -- 初始化空数组  
    segment_id int4;  
    segment_data bit(24);  
    combined_int int4;  
BEGIN  
    -- 检查输入是否为 bit(1536)  
    IF bit_length(bit_data) != 1536 THEN  
        RAISE EXCEPTION 'Input must be bit(1536), got bit(%)', bit_length(bit_data);  
    END IF;  

    -- 分割 bit(1536) 为 64 个 24-bit 分段  
    FOR i IN 0..63 LOOP  
        -- 提取当前 24-bit 分段 (PostgreSQL 的 bit 下标从 1 开始)  
        segment_data := substring(bit_data FROM i*24 + 1 FOR 24);  

        -- 分段 ID 是 i (0-63)，左移 24 位  
        segment_id := i << 24;  

        -- 将 segment_data 转换为整数并与 segment_id 组合  
        combined_int := segment_id | (segment_data::int4);  

        -- 添加到结果数组  
        result := array_append(result, combined_int);  
    END LOOP;  

    RETURN result;  
END;  
$$ LANGUAGE plpgsql IMMUTABLE STRICT;  

生成10万条记录.  因为查询前还会进行聚集, 每个聚集内假设1万条, 1000个聚集点, 就能存下1000万条记录. 假设每次找10个聚集点(probe=10)也就是从10万条记录中进行召回.

insert into tbl select *,bit1536_to_int4_array(vb) from (select generate_series(1,100000) id, gen_rand_1536() vb, random()*100 c1, gen_rand_arr(100,10) c2) t;  

占用56MB空间

postgres=# \dt+ tbl  
                                  List of relations  
 Schema | Name | Type  |  Owner   | Persistence | Access method | Size  | Description   
--------+------+-------+----------+-------------+---------------+-------+-------------  
 public | tbl  | table | postgres | permanent   | heap          | 56 MB |   
(1 row)  

数据例子如下

postgres=# select vb_arr from tbl limit 2;  
                                       vb_arr                                                     
 {13682997,32251777,33554655,53894688,73528400,83914809,112803148,123879424,148311636,165513254,180355105,196297611,211181248,218105764,244132630,267202560,279054245,286174653,304087166,320040557,349996336,352333753,377359465,401317888,418424224,421520206,450887734,464925394,476095136,486578061,517840965,525303808,538298145,568434100,586154036,591900304,612835104,620758905,648088594,658403328,675043211,699171335,715129072,732607284,752823792,754984856,782889727,797224960,812157580,826648557,854589648,867351933,873810128,889220101,918457611,935768064,944192436,963609638,973078692,998413583,1013460432,1023439378,1051468490,1060139008}  
 {14984635,19250546,34603071,55680898,73046608,83913194,112301492,123789312,135979848,161228372,178258128,185381094,201998288,218143952,239280080,262070272,275102977,287124922,301990089,335211927,337612000,352378088,380976096,389496832,414174639,432260375,448790653,456342276,470240736,486564500,508986344,526008320,545870376,563233301,581959900,587682351,620049488,620813886,639276849,655536128,682368629,701665295,707788885,734563564,741811264,755006579,781371196,796807168,809126442,829245078,853540902,871591977,884051584,889219248,917894828,935165952,944371512,972215371,974127272,998352150,1007861200,1023460248,1045422832,1060929536}  
(2 rows)  

配置:

postgres=# show shared_buffers ;  
 shared_buffers   
----------------  
 1GB  
(1 row)  

3、创建索引

PostgreSQL 18 已支持并行创建gin索引, 会非常快.

  • 《PostgreSQL 18 preview - 奇慢无比的GIN索引创建支持并行了》
set maintenance_work_mem='512MB';  
-- 因为有独立字段, 所以不需要使用表达式索引.  create index on tbl using gin (bit1536_to_int4_array(vb) _int4_sml_ops);  
create index on tbl using gin (vb_arr _int4_sml_ops);  

4、(可选, 需要其他条件过滤时使用. 与前面的索引二选一即可.), 创建复合索引, 增加其他过滤字段

set maintenance_work_mem='512MB';  
create extension btree_gin;  
-- 因为有独立字段, 所以不需要使用表达式索引.   create index on tbl using gin (bit1536_to_int4_array(vb) _int4_sml_ops, c1, c2);  
create index on tbl using gin (vb_arr _int4_sml_ops, c1, c2);  

5、性能对比

生成1个测试值(不存在的值)

select vb, bit1536_to_int4_array(vb) from (select gen_rand_1536() as vb) t;  

101001011111000001110111100111010000111010001110100100000000000010101111011011001100100101000100011011111111001001100000000000000001001011101011011011111001110000001011100011010101000000000000011001011010100000001010001001110101101001100101100100000000000000010001011001100110111001100010011110111010100111110000000000001101000110000110100000001100011011100110111000010110000000000000010010001000100010000011100011001010101100011101001100000000000011000101000011001110101001110011000110011001101110000000000000001000111111001100110010001110100110000111001111101011000000000000011000101101111000111011011101111111101111100101110000000000000001011011101110110100000100010101110000011100110010110000000000000001100101001110001001101010111101100001001000110100000000000000000010101001110001101000101000101011110000010011000100000000000011110001000101000001110100101001110001010000001011100000000000000010110101101110010001010100101110000100110101010011000000000000111001000111110011111011101110100101110000001001110000000000000001001010010001100110100111111110000001111011000110010000000000001000101001000001100010101111010111000010011010011101000000000000001010111000100100111001111101100000110011001010101100000000000011110001100001011111111100110110010111110110011000110000000000000111010010101010100011010101101101110000011111100101000000000000010011001001011110101000010110001110011000011100100000000000000001000011111110000001101001100101001111100110011011110000000000001100100000100101000110000111101000010011010000001010000000000000  

{10874999,27070094,42991791,57461060,74445408,83890923,107977739,126701568,140879882,153573989,177209361,191262306,209431024,218157446,243320550,266428416,273188995,294431517,305135813,319613555,337222528,352358348,382265735,389984256,409132603,427293669,448790619,465256725,482462896,486545742,505851745,522403840,537566312,564313107,571474161,588520745,616891104,620768622,642075524,668282880,686062843,700079113,717226058,726034942,738701712,755010113,780858818,795463680,808159545,838208714,850395377,864419638,878667312,889222314,915233648,931024896,944543656,962127388,981467203,1006115429,1010722544,1023461413,1041791507,1061199872}  

取一条已存在值,

select vb , vb_arr from tbl limit 1;  

110100001100100100110101111011000001111110000001000000000000000011011111001101100101111000100000011000011111010001010000000000000111000000111001101110010011110101001100011000100100000000000000110101110000111001010100110111011000100000100110110000000000000000100001101100110100001110001011100101100101111011000000000000000000011110100100100011010010101100010110111011010011000000000000101000100000011110100101000011101010110110111101001000000000000001111110000100110110111001101101110111001000010100110000000000000010111110111001011111100000110001101001111010111010000000000000111100001010010110100000000111111110001101001110111000000000000000110110101101100011001011010010011000001010001010100000000000001001011110001101110111011010000001000101010011111000000000000000000101011100011100100001111000011001110110110100111100000000000000110100010001111010111010010000100001110001111100100000000000000000011101111001101000010000110000010010001111100111000000000000001111000101011110001011101011001000001000000111101000000000000011110000101010101011001100110100110111110010110111110000000000000010011110011000101010011111001011111111100001001011000000000000011010001000101010001100010001011010011111101101111100000000000011010000101100101011110101111101000101010100100011010000000000000110110000000101101111101000110100001011110001101011000000000000010001110011101110110100011011111000010000100110000000000000000010100100100000101001010100001111011010000010110111010000000000000111001000010010101011000010001011001010001100000111000000000000  

{13682997,32251777,33554655,53894688,73528400,83914809,112803148,123879424,148311636,165513254,180355105,196297611,211181248,218105764,244132630,267202560,279054245,286174653,304087166,320040557,349996336,352333753,377359465,401317888,418424224,421520206,450887734,464925394,476095136,486578061,517840965,525303808,538298145,568434100,586154036,591900304,612835104,620758905,648088594,658403328,675043211,699171335,715129072,732607284,752823792,754984856,782889727,797224960,812157580,826648557,854589648,867351933,873810128,889220101,918457611,935768064,944192436,963609638,973078692,998413583,1013460432,1023439378,1051468490,1060139008}  

-- 改3个bit, 都在同一个维度里, 如下.    

110101111100100100110101111011000001111110000001000000000000000011011111001101100101111000100000011000011111010001010000000000000111000000111001101110010011110101001100011000100100000000000000110101110000111001010100110111011000100000100110110000000000000000100001101100110100001110001011100101100101111011000000000000000000011110100100100011010010101100010110111011010011000000000000101000100000011110100101000011101010110110111101001000000000000001111110000100110110111001101101110111001000010100110000000000000010111110111001011111100000110001101001111010111010000000000000111100001010010110100000000111111110001101001110111000000000000000110110101101100011001011010010011000001010001010100000000000001001011110001101110111011010000001000101010011111000000000000000000101011100011100100001111000011001110110110100111100000000000000110100010001111010111010010000100001110001111100100000000000000000011101111001101000010000110000010010001111100111000000000000001111000101011110001011101011001000001000000111101000000000000011110000101010101011001100110100110111110010110111110000000000000010011110011000101010011111001011111111100001001011000000000000011010001000101010001100010001011010011111101101111100000000000011010000101100101011110101111101000101010100100011010000000000000110110000000101101111101000110100001011110001101011000000000000010001110011101110110100011011111000010000100110000000000000000010100100100000101001010100001111011010000010110111010000000000000111001000010010101011000010001011001010001100000111000000000000  

select bit1536_to_int4_array(B'110101111100100100110101111011000001111110000001000000000000000011011111001101100101111000100000011000011111010001010000000000000111000000111001101110010011110101001100011000100100000000000000110101110000111001010100110111011000100000100110110000000000000000100001101100110100001110001011100101100101111011000000000000000000011110100100100011010010101100010110111011010011000000000000101000100000011110100101000011101010110110111101001000000000000001111110000100110110111001101101110111001000010100110000000000000010111110111001011111100000110001101001111010111010000000000000111100001010010110100000000111111110001101001110111000000000000000110110101101100011001011010010011000001010001010100000000000001001011110001101110111011010000001000101010011111000000000000000000101011100011100100001111000011001110110110100111100000000000000110100010001111010111010010000100001110001111100100000000000000000011101111001101000010000110000010010001111100111000000000000001111000101011110001011101011001000001000000111101000000000000011110000101010101011001100110100110111110010110111110000000000000010011110011000101010011111001011111111100001001011000000000000011010001000101010001100010001011010011111101101111100000000000011010000101100101011110101111101000101010100100011010000000000000110110000000101101111101000110100001011110001101011000000000000010001110011101110110100011011111000010000100110000000000000000010100100100000101001010100001111011010000010110111010000000000000111001000010010101011000010001011001010001100000111000000000000');  

{14141749,32251777,33554655,53894688,73528400,83914809,112803148,123879424,148311636,165513254,180355105,196297611,211181248,218105764,244132630,267202560,279054245,286174653,304087166,320040557,349996336,352333753,377359465,401317888,418424224,421520206,450887734,464925394,476095136,486578061,517840965,525303808,538298145,568434100,586154036,591900304,612835104,620758905,648088594,658403328,675043211,699171335,715129072,732607284,752823792,754984856,782889727,797224960,812157580,826648557,854589648,867351933,873810128,889220101,918457611,935768064,944192436,963609638,973078692,998413583,1013460432,1023439378,1051468490,1060139008}  

 查询 

不存在的值, 相交63以上:

使用索引

set enable_seqscan=off;    
set enable_bitmapscan=on;    
set smlar.type = overlap;    
set smlar.threshold = 63;    

select id from tbl where vb_arr % '{10874999,27070094,42991791,57461060,74445408,83890923,107977739,126701568,140879882,153573989,177209361,191262306,209431024,218157446,243320550,266428416,273188995,294431517,305135813,319613555,337222528,352358348,382265735,389984256,409132603,427293669,448790619,465256725,482462896,486545742,505851745,522403840,537566312,564313107,571474161,588520745,616891104,620768622,642075524,668282880,686062843,700079113,717226058,726034942,738701712,755010113,780858818,795463680,808159545,838208714,850395377,864419638,878667312,889222314,915233648,931024896,944543656,962127388,981467203,1006115429,1010722544,1023461413,1041791507,1061199872}'::int[] limit 100;     

 id   
----  
(0 rows)  

Time: 3.920 ms  

不使用索引

set enable_seqscan=on;    
set enable_bitmapscan=off;  
set smlar.type = overlap;    
set smlar.threshold = 63;    

select id from tbl where vb_arr % '{10874999,27070094,42991791,57461060,74445408,83890923,107977739,126701568,140879882,153573989,177209361,191262306,209431024,218157446,243320550,266428416,273188995,294431517,305135813,319613555,337222528,352358348,382265735,389984256,409132603,427293669,448790619,465256725,482462896,486545742,505851745,522403840,537566312,564313107,571474161,588520745,616891104,620768622,642075524,668282880,686062843,700079113,717226058,726034942,738701712,755010113,780858818,795463680,808159545,838208714,850395377,864419638,878667312,889222314,915233648,931024896,944543656,962127388,981467203,1006115429,1010722544,1023461413,1041791507,1061199872}'::int[] limit 100;     

 id   
----  
(0 rows)  

Time: 369.741 ms  

存在的值, 相交63以上:

使用索引

set enable_seqscan=off;    
set enable_bitmapscan=on;  
set smlar.type = overlap;    
set smlar.threshold = 63;    

select id from tbl where vb_arr % '{14141749,32251777,33554655,53894688,73528400,83914809,112803148,123879424,148311636,165513254,180355105,196297611,211181248,218105764,244132630,267202560,279054245,286174653,304087166,320040557,349996336,352333753,377359465,401317888,418424224,421520206,450887734,464925394,476095136,486578061,517840965,525303808,538298145,568434100,586154036,591900304,612835104,620758905,648088594,658403328,675043211,699171335,715129072,732607284,752823792,754984856,782889727,797224960,812157580,826648557,854589648,867351933,873810128,889220101,918457611,935768064,944192436,963609638,973078692,998413583,1013460432,1023439378,1051468490,1060139008}'::int[] limit 100;  

 id   
----  
  1  
(1 row)  

Time: 4.328 ms  

执行计划

postgres=# explain (analyze,verbose,timing,costs,buffers) select id from tbl where vb_arr % '{14141749,32251777,33554655,53894688,73528400,83914809,112803148,123879424,148311636,165513254,180355105,196297611,211181248,218105764,244132630,267202560,279054245,286174653,304087166,320040557,349996336,352333753,377359465,401317888,418424224,421520206,450887734,464925394,476095136,486578061,517840965,525303808,538298145,568434100,586154036,591900304,612835104,620758905,648088594,658403328,675043211,699171335,715129072,732607284,752823792,754984856,782889727,797224960,812157580,826648557,854589648,867351933,873810128,889220101,918457611,935768064,944192436,963609638,973078692,998413583,1013460432,1023439378,1051468490,1060139008}'::int[] limit 100;  


QUERY PLAN                                     

 Limit  (cost=1284.78..1650.59 rows=100 width=4) (actual time=3.602..3.607 rows=1 loops=1)  
   Output: id  
   Buffers: shared hit=194  
   ->  Bitmap Heap Scan on public.tbl  (cost=1284.78..1650.59 rows=100 width=4) (actual time=3.595..3.599 rows=1 loops=1)  
         Output: id  
         Recheck Cond: (tbl.vb_arr % '{14141749,32251777,33554655,53894688,73528400,83914809,112803148,123879424,148311636,165513254,180355105,196297611,211181248,218105764,244132630,267202560,279054245  
,286174653,304087166,320040557,349996336,352333753,377359465,401317888,418424224,421520206,450887734,464925394,476095136,486578061,517840965,525303808,538298145,568434100,586154036,591900304,612835104,6  
20758905,648088594,658403328,675043211,699171335,715129072,732607284,752823792,754984856,782889727,797224960,812157580,826648557,854589648,867351933,873810128,889220101,918457611,935768064,944192436,963  
609638,973078692,998413583,1013460432,1023439378,1051468490,1060139008}'::integer[])  
         Heap Blocks: exact=1  
         Buffers: shared hit=194  
         ->  Bitmap Index Scan on tbl_vb_arr_c1_c2_idx  (cost=0.00..1284.75 rows=100 width=0) (actual time=3.533..3.534 rows=1 loops=1)  
               Index Cond: (tbl.vb_arr % '{14141749,32251777,33554655,53894688,73528400,83914809,112803148,123879424,148311636,165513254,180355105,196297611,211181248,218105764,244132630,267202560,27905  
4245,286174653,304087166,320040557,349996336,352333753,377359465,401317888,418424224,421520206,450887734,464925394,476095136,486578061,517840965,525303808,538298145,568434100,586154036,591900304,6128351  
04,620758905,648088594,658403328,675043211,699171335,715129072,732607284,752823792,754984856,782889727,797224960,812157580,826648557,854589648,867351933,873810128,889220101,918457611,935768064,944192436  
,963609638,973078692,998413583,1013460432,1023439378,1051468490,1060139008}'::integer[])  
               Buffers: shared hit=193  
 Planning:  
   Buffers: shared hit=2  
 Planning Time: 0.637 ms  
 Execution Time: 3.809 ms  
(15 rows)  

不使用索引

set enable_seqscan=on;    
set enable_bitmapscan=off;    
set smlar.type = overlap;    
set smlar.threshold = 63;    


select id from tbl where vb_arr % '{14141749,32251777,33554655,53894688,73528400,83914809,112803148,123879424,148311636,165513254,180355105,196297611,211181248,218105764,244132630,267202560,279054245,286174653,304087166,320040557,349996336,352333753,377359465,401317888,418424224,421520206,450887734,464925394,476095136,486578061,517840965,525303808,538298145,568434100,586154036,591900304,612835104,620758905,648088594,658403328,675043211,699171335,715129072,732607284,752823792,754984856,782889727,797224960,812157580,826648557,854589648,867351933,873810128,889220101,918457611,935768064,944192436,963609638,973078692,998413583,1013460432,1023439378,1051468490,1060139008}'::int[] limit 100;  

 id   
----  
  1  
(1 row)  

Time: 346.017 ms  

复合查询

采用已存在且修改了3个bit的值

postgres=# select c1,c2 from tbl where id=1;  
 c1 |               c2                 
----+--------------------------------  
 62 | {3,52,14,13,51,50,80,12,70,89}  
(1 row)  

使用索引

set enable_seqscan=off;    
set enable_bitmapscan=on;  
set smlar.type = overlap;    
set smlar.threshold = 63;    


select id from tbl where vb_arr % '{14141749,32251777,33554655,53894688,73528400,83914809,112803148,123879424,148311636,165513254,180355105,196297611,211181248,218105764,244132630,267202560,279054245,286174653,304087166,320040557,349996336,352333753,377359465,401317888,418424224,421520206,450887734,464925394,476095136,486578061,517840965,525303808,538298145,568434100,586154036,591900304,612835104,620758905,648088594,658403328,675043211,699171335,715129072,732607284,752823792,754984856,782889727,797224960,812157580,826648557,854589648,867351933,873810128,889220101,918457611,935768064,944192436,963609638,973078692,998413583,1013460432,1023439378,1051468490,1060139008}'::int[]   
and c1=62 and c2 @> '{70,89}'::int[]  
limit 100;  

 id   
----  
  1  
(1 row)  

Time: 5.219 ms  

执行计划

 Limit  (cost=1344.00..1348.02 rows=1 width=4)  
   ->  Bitmap Heap Scan on tbl  (cost=1344.00..1348.02 rows=1 width=4)  
         Recheck Cond: ((vb_arr % '{14141749,32251777,33554655,53894688,73528400,83914809,112803148,123879424,148311636,165513254,180355105,196297611,211181248,218105764,244132630,267202560,279054245,28  
6174653,304087166,320040557,349996336,352333753,377359465,401317888,418424224,421520206,450887734,464925394,476095136,486578061,517840965,525303808,538298145,568434100,586154036,591900304,612835104,6207  
58905,648088594,658403328,675043211,699171335,715129072,732607284,752823792,754984856,782889727,797224960,812157580,826648557,854589648,867351933,873810128,889220101,918457611,935768064,944192436,963609  
638,973078692,998413583,1013460432,1023439378,1051468490,1060139008}'::integer[]) AND (c1 = 62) AND (c2 @> '{70,89}'::integer[]))  
         ->  Bitmap Index Scan on tbl_vb_arr_c1_c2_idx  (cost=0.00..1344.00 rows=1 width=0)  
               Index Cond: ((vb_arr % '{14141749,32251777,33554655,53894688,73528400,83914809,112803148,123879424,148311636,165513254,180355105,196297611,211181248,218105764,244132630,267202560,27905424  
5,286174653,304087166,320040557,349996336,352333753,377359465,401317888,418424224,421520206,450887734,464925394,476095136,486578061,517840965,525303808,538298145,568434100,586154036,591900304,612835104,  
620758905,648088594,658403328,675043211,699171335,715129072,732607284,752823792,754984856,782889727,797224960,812157580,826648557,854589648,867351933,873810128,889220101,918457611,935768064,944192436,96  
3609638,973078692,998413583,1013460432,1023439378,1051468490,1060139008}'::integer[]) AND (c1 = 62) AND (c2 @> '{70,89}'::integer[]))  
(5 rows)  

查询 + rerank

-- 因为前面的查询返回交叉度为63, 实际上修改了3个bit, 所以需要rerank才更精确.

使用索引

set enable_seqscan=off;    
set enable_bitmapscan=on;  
set smlar.type = overlap;    
set smlar.threshold = 63;    

select id,  
length(replace(bitxor(vb, B'110101111100100100110101111011000001111110000001000000000000000011011111001101100101111000100000011000011111010001010000000000000111000000111001101110010011110101001100011000100100000000000000110101110000111001010100110111011000100000100110110000000000000000100001101100110100001110001011100101100101111011000000000000000000011110100100100011010010101100010110111011010011000000000000101000100000011110100101000011101010110110111101001000000000000001111110000100110110111001101101110111001000010100110000000000000010111110111001011111100000110001101001111010111010000000000000111100001010010110100000000111111110001101001110111000000000000000110110101101100011001011010010011000001010001010100000000000001001011110001101110111011010000001000101010011111000000000000000000101011100011100100001111000011001110110110100111100000000000000110100010001111010111010010000100001110001111100100000000000000000011101111001101000010000110000010010001111100111000000000000001111000101011110001011101011001000001000000111101000000000000011110000101010101011001100110100110111110010110111110000000000000010011110011000101010011111001011111111100001001011000000000000011010001000101010001100010001011010011111101101111100000000000011010000101100101011110101111101000101010100100011010000000000000110110000000101101111101000110100001011110001101011000000000000010001110011101110110100011011111000010000100110000000000000000010100100100000101001010100001111011010000010110111010000000000000111001000010010101011000010001011001010001100000111000000000000')::text,'0','')) as diff_bits  
 from tbl where vb_arr % '{14141749,32251777,33554655,53894688,73528400,83914809,112803148,123879424,148311636,165513254,180355105,196297611,211181248,218105764,244132630,267202560,279054245,286174653,304087166,320040557,349996336,352333753,377359465,401317888,418424224,421520206,450887734,464925394,476095136,486578061,517840965,525303808,538298145,568434100,586154036,591900304,612835104,620758905,648088594,658403328,675043211,699171335,715129072,732607284,752823792,754984856,782889727,797224960,812157580,826648557,854589648,867351933,873810128,889220101,918457611,935768064,944192436,963609638,973078692,998413583,1013460432,1023439378,1051468490,1060139008}'::int[]   
and c1=62 and c2 @> '{70,89}'::int[]  
limit 100;  

 id | diff_bits   
----+-----------  
  1 |         3  
(1 row)  

Time: 6.700 ms  

不使用索引

set enable_seqscan=on;    
set enable_bitmapscan=off;  
set smlar.type = overlap;    
set smlar.threshold = 63;    

select id,  
length(replace(bitxor(vb, B'110101111100100100110101111011000001111110000001000000000000000011011111001101100101111000100000011000011111010001010000000000000111000000111001101110010011110101001100011000100100000000000000110101110000111001010100110111011000100000100110110000000000000000100001101100110100001110001011100101100101111011000000000000000000011110100100100011010010101100010110111011010011000000000000101000100000011110100101000011101010110110111101001000000000000001111110000100110110111001101101110111001000010100110000000000000010111110111001011111100000110001101001111010111010000000000000111100001010010110100000000111111110001101001110111000000000000000110110101101100011001011010010011000001010001010100000000000001001011110001101110111011010000001000101010011111000000000000000000101011100011100100001111000011001110110110100111100000000000000110100010001111010111010010000100001110001111100100000000000000000011101111001101000010000110000010010001111100111000000000000001111000101011110001011101011001000001000000111101000000000000011110000101010101011001100110100110111110010110111110000000000000010011110011000101010011111001011111111100001001011000000000000011010001000101010001100010001011010011111101101111100000000000011010000101100101011110101111101000101010100100011010000000000000110110000000101101111101000110100001011110001101011000000000000010001110011101110110100011011111000010000100110000000000000000010100100100000101001010100001111011010000010110111010000000000000111001000010010101011000010001011001010001100000111000000000000')::text,'0','')) as diff_bits  
 from tbl where vb_arr % '{14141749,32251777,33554655,53894688,73528400,83914809,112803148,123879424,148311636,165513254,180355105,196297611,211181248,218105764,244132630,267202560,279054245,286174653,304087166,320040557,349996336,352333753,377359465,401317888,418424224,421520206,450887734,464925394,476095136,486578061,517840965,525303808,538298145,568434100,586154036,591900304,612835104,620758905,648088594,658403328,675043211,699171335,715129072,732607284,752823792,754984856,782889727,797224960,812157580,826648557,854589648,867351933,873810128,889220101,918457611,935768064,944192436,963609638,973078692,998413583,1013460432,1023439378,1051468490,1060139008}'::int[]   
and c1=62 and c2 @> '{70,89}'::int[]  
limit 100;  

 id | diff_bits   
----+-----------  
  1 |         3  
(1 row)  

Time: 365.101 ms  

性能对比

test case
使用索引耗时
不使用索引耗时
记录存在, 向量+其他字段过滤
6.700 ms
365.101 ms
记录不存在
3.920 ms
369.741 ms
记录存在
4.328 ms
346.017 ms

使用索引后有近乎100倍的性能提升.

如果你采用这个方法, 可以让你的向量检索性能再提升一个台阶:

 向量 -> 量化 -> 聚集 -> 分段GIN索引 -> 交叉下降迭代索引检索 + rerank   

三、本方案优势

创建索引快

消耗内存少

维护索引方便

高效的支持实时DML

查询效率高

单机支持更多记录数, 可能能达到10亿级别

gin 支持多字段组合过滤, 既能过滤向量相似(量化后的bit差异位数)、也能过同时滤其他scalar或数组字段(通过倒排).

四、本方案限制

需要rerank (因为分段后一个分段有多个bit, 通过分段来判断overlap, 多于一定多, 少于不一定少, 因为1个分段内可能有多个bit不一样.)

通过求各向bit差异数得到的相似度, 是不是适合所有距离场景: l2,ip,cosin?

五、这个方案利好谁?

支持倒排索引的数据库.

第一个当然是PostgreSQL.

参考

https://deepwiki.com/timescale/pgvectorscale/

https://deepwiki.com/tensorchord/VectorChord/

https://deepwiki.com/jirutka/smlar/

https://www.postgresql.org/docs/current/btree-gin.html

《VectorChord 向量插件学习心得》

https://github.com/jirutka/smlar

以下文章来自: https://github.com/digoal/blog 

《PostgreSQL ghtree实现的海明距离排序索引, 性能不错(模糊图像) - pg-knn_hamming - bit string 比特字符串 相似度搜索》

《PostgreSQL bktree 索引using gist例子 - 海明距离检索 - 短文相似、模糊图像搜索 - bit string 比特字符串 相似度搜索》

《HTAP数据库 PostgreSQL 场景与性能测试之 16 - (OLTP) 文本特征向量 - 相似特征(海明...)查询》

《海量数据,海明(simhash)距离高效检索(smlar) - 阿里云RDS PosgreSQL最佳实践 - bit string 比特字符串 相似度搜索》

查询阶段再提一个优化小技巧: overlap 阶梯查询 , 不足返回条数则继续下移阶梯(例如63,62,61,...逐渐降低).  索引内可以移植到: pgvector/vectorchord 查询阶段的迭代方法

  • 《PostgreSQL 相似搜索设计与性能 - 地址、QA、POI等文本 毫秒级相似搜索实践》

声明

 如果你在任何地方使用了本文提到的方案或思路, 请标注Idea From digoal德哥 

KEEP THE THREAD GOING

更多来源文章