digoal
2020-04-29
PostgreSQL , 下推 , offset , 过滤 , 叶子 , include index , 随机偏移 , 内核
抛出问题:
特征表, 表示用户的特征, 还有一个权重字段表示优先曝光(付费或者爆点可以让你的权重变大, 优先曝光). 根据相似特征推荐给我好友.
关系表, 用户关联了什么人.
特征表有一个向量索引, 根据特征搜索相似对象若干条. 然后按权重排序, 同时已经被我关联的对象, 不要再推荐给我.
问题在哪?
1、如果使用了向量相似搜索, 那么权重排序无法使用索引
2、如果你已经关联了很多人, 那么按相似搜索出来的对象可能很多都已经被你关联过, 会导致大量无效的索引扫描.
怎么解?
方法1:
将权重也放到特征向量里面, 作为一个维度, 每次查询的时候, 在权重这个维度上填入一个较为随机的值, 从而影响相似度, 每次推荐的记录有一定的随机性. 减少大量无效索引扫描.
打车热点一样的思路，加一个纠偏维度，随机直。干扰要小，例如10%取值范围, 影响小。 例如其他维度取值范围是0到100, 纠偏维度的范围可以是0到10, 减少最终向量距离的影响.
《PostgreSQL 滴滴派单 高峰区域集中打车冲突优化1 - 宇宙大爆炸理论与PostgreSQL实践》
方法2:
ivfflat索引, 支持指定从第N个桶开始返回. 类似offset.
方法3:
ivfflat, hnsw索引, 支持指定从第N条记录开始返回. 类似offset
方法4:
下推, 类似rum索引结构
《PostgreSQL rum 索引结构 - 比gin posting list|tree 的ctid(行号)多了addition info》
在索引的叶子节点中放入额外属性, 例如uid, 权重. 直接在索引中filter, 不需要回表后再filter.
实现思路:
ivfflat, 索引叶子, 可存储额外值(uid, weight), 查询是不仅能支持向量相似, 同时支持hll算子过滤和weight过滤.
这个思路与rum结构相似, 和include索引功能也比较相似.
《PostgreSQL index include - 类聚簇表与应用(append only, IoT时空轨迹, 离散多行扫描与返回)》
《PostgreSQL 12 preview - GiST 索引支持INCLUDE columns - 覆盖索引 - 类聚簇索引》
create index idx on tbl using rum (xx rum_addon_ops) with (addon=y,z) ;
create index idx on tbl using ivfflat (vec) include column(y,z);
select x from tbl where uid not in ... order by vec <?> array[...] limit 100;
-- 这里向量也用索引， uid过滤也在索引内完成.
select x from tbl where uid not in ... order by vec <?> array[...], weight desc limit 100;
-- 这里排序在索引内完成， 优先向量limit 100， 然后weight倒排.
PG 的access method接口非常灵活， 使得可以创造友好的存储结构， 以及对应的搜索和过滤算法。 就好比中国古语： 阴成形，阳化气。存储属阴，算法属阳。天地合而万物生，阴阳合而变化出。
您的愿望将传达给PG kernel hacker、数据库厂商等, 帮助提高数据库产品质量和功能, 说不定下一个PG版本就有您提出的功能点. 针对非常好的提议，奖励限量版PG文化衫、纪念品、贴纸、PG热门书籍等，奖品丰富，快来许愿。开不开森.
