如何在Postgres/MySQL中按LSH距离快速筛选阈值内的记录

方案选型避坑 #

• 不要继续使用拉全表到JS层逐行计算的逻辑，网络传输+JS计算的双重开销在数据量超过10万条时就会出现明显延迟，数据量到百万级以上完全不可用
• 不推荐拆成35个单字节列存储的方案：TLSH距离是字节差值加权计算逻辑，不是简单的不同字节计数，无法提前预判哪些字节会存在差异，没法建立有效索引过滤候选集，最终还是要逐行遍历计算，性能提升极有限
• 核心优化思路：两层过滤，第一层用数据库索引筛掉99%以上不可能满足距离≤11的记录，只对剩下的极小部分候选集做精确距离计算，整体性能可以比全表计算高2~3个数量级

分数据库实现 #

PostgreSQL 实现 #

1. 存储格式优化
   不要存70位十六进制字符串，直接用bytea定长二进制类型存储35字节的LSH原始值，省去查询时的十六进制转码开销，同时节省存储空间：

CREATE TABLE lsh_records (
    id bigint PRIMARY KEY,
    -- 其他业务字段
    the_lsh bytea NOT NULL CHECK (length(the_lsh) = 35)
);

2. 自定义距离函数
   把你现有JS实现的findDiffBetweenTwoLSH逻辑直接移植为PL/pgSQL自定义函数，命名为tlsh_distance(lsh1 bytea, lsh2 bytea) RETURNS integer，逻辑完全对齐现有JS实现即可——TLSH距离计算全是基础数值运算，PL/pgSQL实现的性能足够支撑小候选集的计算。如果环境允许安装第三方数据库扩展，也可以直接用现成的TLSH扩展，内置了距离计算和更高效的索引支持，不需要自己写函数。
3. 前置分块索引
   TLSH距离≤11的两个值，不可能在所有连续5字节块上都存在较大差异。基于这个特性，把35字节的LSH拆成7个连续的5字节块，对每个块建B树索引，查询时先筛选出任意一个块和目标LSH对应块完全相等的记录作为候选集，这一步可以直接把候选集规模压缩到全表的0.1%以下。
4. 查询语句示例

SELECT * FROM lsh_records
WHERE 
    -- 索引层前置过滤，命中任意一个块的B树索引
    substring(the_lsh from 1 for 5) = substring($1::bytea from 1 for 5)
    OR substring(the_lsh from 6 for 5) = substring($1::bytea from 6 for 5)
    OR substring(the_lsh from 11 for 5) = substring($1::bytea from 11 for 5)
    OR substring(the_lsh from 16 for 5) = substring($1::bytea from 16 for 5)
    OR substring(the_lsh from 21 for 5) = substring($1::bytea from 21 for 5)
    OR substring(the_lsh from 26 for 5) = substring($1::bytea from 26 for 5)
    OR substring(the_lsh from 31 for 5) = substring($1::bytea from 31 for 5)
    -- 对候选集做精确距离校验
    AND tlsh_distance(the_lsh, $1::bytea) <= 11;

语句中$1为传入的、转成bytea格式的目标LSH值。

MySQL 实现 #

核心逻辑和PostgreSQL一致，仅做语法适配：

1. 存储类型用BINARY(35)定长二进制类型，不要用VARCHAR存储十六进制字符串，避免转码和变长存储开销。
2. 距离函数可以用MySQL存储函数移植现有JS逻辑，对性能要求极高的场景可以写C UDF，计算速度会更快。
3. 用生成列自动拆分7个5字节块，直接对生成列建B树索引，不需要业务侧手动维护块字段：

CREATE TABLE lsh_records (
    id bigint PRIMARY KEY,
    -- 其他业务字段
    the_lsh BINARY(35) NOT NULL,
    block1 BINARY(5) GENERATED ALWAYS AS (SUBSTRING(the_lsh, 1, 5)) STORED,
    block2 BINARY(5) GENERATED ALWAYS AS (SUBSTRING(the_lsh, 6, 5)) STORED,
    block3 BINARY(5) GENERATED ALWAYS AS (SUBSTRING(the_lsh, 11, 5)) STORED,
    block4 BINARY(5) GENERATED ALWAYS AS (SUBSTRING(the_lsh, 16, 5)) STORED,
    block5 BINARY(5) GENERATED ALWAYS AS (SUBSTRING(the_lsh, 21, 5)) STORED,
    block6 BINARY(5) GENERATED ALWAYS AS (SUBSTRING(the_lsh, 26, 5)) STORED,
    block7 BINARY(5) GENERATED ALWAYS AS (SUBSTRING(the_lsh, 31, 5)) STORED,
    INDEX idx_block1 (block1),
    INDEX idx_block2 (block2),
    INDEX idx_block3 (block3),
    INDEX idx_block4 (block4),
    INDEX idx_block5 (block5),
    INDEX idx_block6 (block6),
    INDEX idx_block7 (block7)
);

4. 查询时同样先走块索引筛候选集，再调用自定义距离函数做精确校验即可。

性能参考 #

• 单表1000万条记录规模下，上述方案的常规查询延迟在10~50ms区间，完全满足快速响应要求
• 如果需要进一步压缩延迟，可以把块拆得更细（比如拆成10个左右的块，筛选时匹配任意2个块相等），候选集规模会更小，代价是索引占用的存储空间会相应增加
• 不要跳过前置索引直接对全表调用自定义距离函数，即使函数计算性能很高，全表遍历的开销在百万级以上数据量时还是会达到百毫秒到秒级，前置分块索引的投入产出比最高

内容的提问来源于stack exchange，提问作者shal