Skip to content

Latest commit

 

History

History
295 lines (169 loc) · 8.46 KB

20200421_01.md

File metadata and controls

295 lines (169 loc) · 8.46 KB
Raw

社交、电商、游戏等 推荐系统 (相似推荐) - 阿里云pase smlar索引方案对比

作者

digoal

日期

2020-04-21

标签

PostgreSQL , smlar , pase , 索引 , overlap , hnsw , ivfflat

背景

在社交业务、电商业务、游戏等业务中, 有一些场景会涉及到相似推荐, 例如根据你喜欢的标签给你推荐相应的内容.

  • 内容标签表
  • 用户的标签
  • 你的喜好标签

给你推荐相似内容、相似喜好的群体.

有几种常见的推荐算法:

1、标签重叠个数: overlap
2、标签重叠率: cosine
3、向量距离

对应的模块smlar和pase的差别.

smlar插件算法

索引采用两级过滤, 1、从gin倒排索引找到满足交叠元素个数的heap block id, 2、搜索heap block, 逐条比对, 二次过滤. 当有热点数据时, 可能导致1级过滤取的block 特别多, 性能影响.

例如搜索1,2,3,4,5,100,203,1923, 交错5个以上的.

1、搜索索引

包含1的有哪些heap block id

包含2的有哪些heap block id

...

包含1923的有哪些heap block id

统计哪些heap block id包含了5个以上.

2、回表查询这些heap block id的内容, 逐条判断是否满足5个以上交错, 返回这些记录.

当有热点数据时, 可能导致1级过滤取的block 特别多, 性能影响.

例子

create table a (id int primary key, c int[]);

create or replace function gen_randarr(int,int) as $$
select array_agg((random()*$1)::int) from generate_series(1,$2);
$$ language sql strict;

insert into a select generate_series(1,1000000), gen_randarr(50000,100)||gen_randarr(50,5);  -- 大众标签 -- 热门标签

create extension if not exists smlar;
create index idx_a_1 on a using gin(c _int4_sml_ops);

create or replace function get_res(  
  i_arr int[],     -- 要按相似搜的数组  
  i_lim int8,     -- 限制返回多少条  
  i_thresh_up float4 default 0.8,   -- 相似度阈值初始搜索阈值  
  i_thresh float4 default 0.6,   -- 相似度阈值，低于这个值不再搜  
  i_step float4 default 0.1    -- 相似度递减步长，直至阈值 
  -- text default 'overlap'  -- 相似度算法 cosine, overlap, tfidf 
) returns int[] as $$    
declare    
  len int := array_length(i_arr,1);  
  lim float4 := ceil(i_thresh_up*len)::int;  
  i_res int[]; -- 结果
  v_step int := ceil(i_step*len)::int;

begin    
  -- 判定  
  if not ((i_thresh <= 1 and i_thresh > 0) and (i_step < 1 and i_step > 0) and (i_thresh_up>=i_thresh)) then   
    raise notice 'i_thresh must >0 and <=1';  
    return null;  
  end if;  

  set smlar.type='overlap';  
  set enable_seqscan=off;  

  loop    
    -- 设置相似度阈值    
    perform set_smlar_limit(lim);   -- smlar.threshold 
        
    select array_agg(id) into i_res from (select id from a where c % i_arr limit i_lim) t;    
      
    -- 如果有，则退出loop    
    if array_length(i_res,1) >= i_lim then    
        return i_res;
    end if;    
    
    -- 否则继续，降低阈值    
    -- 当阈值小于i_thresh时，不再降阈值搜索，认为没有相似。    
    if lim <= i_thresh*len then    
      return i_res;    
    else    
      lim := lim - v_step;    
    end if;    
  end loop;    
end;    
$$ language plpgsql strict;    

create or replace function get_res1(  
  i_arr int[],     -- 要按相似搜的数组  
  i_lim int8,     -- 限制返回多少条  
  i_thresh_up float4 default 0.8,   -- 相似度阈值初始搜索阈值  
  i_thresh float4 default 0.6,   -- 相似度阈值，低于这个值不再搜  
  i_step float4 default 0.1    -- 相似度递减步长，直至阈值 
  -- text default 'cosine'  -- 相似度算法 cosine, overlap, tfidf 
) returns int[] as $$    
declare    
  lim float4 := i_thresh_up;  
  i_res int[]; -- 结果

begin    
  -- 判定  
  if not ((i_thresh <= 1 and i_thresh > 0) and (i_step < 1 and i_step > 0) and (i_thresh_up>=i_thresh)) then   
    raise notice 'i_thresh must >0 and <=1';  
    return null;  
  end if;  

  set smlar.type='cosine';  
  set enable_seqscan=off;  

  loop    
    -- 设置相似度阈值    
    perform set_smlar_limit(lim);   -- smlar.threshold 
        
    select array_agg(id) into i_res from (select id from a where c % i_arr limit i_lim) t;    
      
    -- 如果有，则退出loop    
    if array_length(i_res,1) >= i_lim then    
        return i_res;
    end if;    
    
    -- 否则继续，降低阈值    
    -- 当阈值小于i_thresh时，不再降阈值搜索，认为没有相似。    
    if lim <= i_thresh then    
      return i_res;    
    else    
      lim := lim - i_step;    
    end if;    
  end loop;    
end;    
$$ language plpgsql strict;

pase插件算法

同样的业务, 我们可以使用向量搜索, 但是首先要对标签进行向量化.

例如视频标签、个人喜好标签, 两类标签.

方法如下:

设计两级标签:

1级实际上就是向量. 2级是原始标签.

1级标签库容量: 64 (必须设限, 必须固定, 未来如果要扩展维度, 需要重建索引.)
2级标签库容量: 65536 (也可以不设限, 可以超过64K)

2级标签 转换为 1级标签(即向量化):

例子:

2级标签 转换为 1级标签设置一个系数表, 这个表可以人为维护, 也可以由AI系统生成. l2 to l1转换系数映射关系 :

tag_L2_dim1 : tag_L1_v?:0.x , tag_L1_v?:0.y , ...   
tag_L2_dim2 :   
...  
tag_L2_dim64 :

视频2级标签, 个人2级标签:

text[]  
[v1:q1, ...] v1表示tag1, q1表示v1这个标签的权重   
  
例如:   
1:10, 200:20, 192:90, ...

转换为一级标签后应该如下:

[tag_L2_dim1_val, tag_L2_dim2_val, ..., tag_L2_dim64_val]

pase向量索引(L1向量):

[tag_L2_dim1_val, tag_L2_dim2_val, ..., tag_L2_dim64_val]  
L1维度1的值 = sum(L2_tag1权重 * L2_tag1对应L1_dim1的系数 + ... L2_tagn权重 * L2_tagn对应L1_dim1的系数  )    
...  
L1维度64的值 = sum(L2_tag1权重 * L2_tag1对应L1_dim64的系数 + ... L2_tagn权重 * L2_tagn对应L1_dim64的系数  )

对1级标签数组创建rds pase索引. hnsw或ivfflat算法.

搜索, 根据向量距离进行搜索 .

pase 向量距离算法参考文档:
《PostgreSQL 阿里云rds pg发布高维向量索引，支持图像识别、人脸识别 - pase 插件》

《PostgreSQL+MySQL 联合解决方案 - 第11课视频 - 多维向量相似搜索 - 图像识别、相似人群圈选等》

《阿里云PostgreSQL 向量搜索、相似搜索、图像搜索 插件 pase - ivfflat , hnsw , nsg , ssg》

https://help.aliyun.com/document_detail/147837.html

小结

插件 相似算法 优势 劣势
smlar cosine, overlap两种算法, 计算元素重叠度 设计较简单、 索引采用两级过滤, 1、从gin倒排索引找到满足交叠元素个数的heap block id, 2、搜索heap block, 逐条比对, 二次过滤. 当有热点数据时, 可能导致1级过滤取的block 特别多, 性能影响.
pase hnsw和ivfflat算法, 计算向量距离 没有热点的概念, 所有查询条件的响应速度都一样, 可以做到毫秒级 需要提炼、需要一致的维度, 需要标签转化为向量

PostgreSQL 许愿链接

您的愿望将传达给PG kernel hacker、数据库厂商等, 帮助提高数据库产品质量和功能, 说不定下一个PG版本就有您提出的功能点. 针对非常好的提议，奖励限量版PG文化衫、纪念品、贴纸、PG热门书籍等，奖品丰富，快来许愿。开不开森.

9.9元购买3个月阿里云RDS PostgreSQL实例

PostgreSQL 解决方案集合

德哥 / digoal's github - 公益是一辈子的事.

digoal's wechat