MySQL或PostgreSQL的汉明距离优化

Question

我试图改进在MySQL数据库中搜索类似图像pHashed。现在我比较pHash计数锤击距离如下：

SELECT * FROM images WHERE BIT_COUNT(hash ^ 2028359052535108275) <= 4

选择（引擎MyISAM）的结果

• 20000行；查询时间<20ms
• 100000行；查询时间~60ms#这很好，直到它达到150000行
• 300000行；查询时间~150ms

所以查询时间的增加取决于表中的行数。

---

我也尝试在stackoverflow上找到的解决方案SQL 中二进制字符串的Hamming距离

SELECT * FROM images WHERE 
BIT_COUNT(h1 ^ 11110011) + 
BIT_COUNT(h2 ^ 10110100) + 
BIT_COUNT(h3 ^ 11001001) + 
BIT_COUNT(h4 ^ 11010001) + 
BIT_COUNT(h5 ^ 00100011) + 
BIT_COUNT(h6 ^ 00010100) + 
BIT_COUNT(h7 ^ 00011111) + 
BIT_COUNT(h8 ^ 00001111) <= 4

行300000；查询时间~240ms

---

我把数据库引擎改成了PostgreSQL。将此MySQL查询转换为PyGreSQL没有成功。行300000；查询时间~18s

---

是否有优化上述查询的解决方案我的意思是优化不取决于行数。

我解决这个问题的方法（工具）有限。到目前为止，MySQL似乎是最简单的解决方案，但我可以在每一个开源数据库引擎上部署代码，这些引擎将在专用机器上使用Ruby。MsSQL有一些现成的解决方案https://stackoverflow.com/a/5930944/766217（未测试）。也许有人知道如何将其翻译成MySQL或PostgreSQL。

请根据一些代码或观察结果发布答案。我们在stackoverflow.com 上有很多关于hamming距离的理论问题

谢谢！

Answer 1

在考虑算法的效率时，计算机科学家使用顺序的概念表示为O（某物），其中某物是n的函数，在这种情况下是计算的事物的数量，即行。因此，随着时间的推移，我们得到了：

• O（1）-与项目数量无关
• O（log（n））-随着项目的对数而增加
• O（n）-项目的比例增加（您拥有的）
• O（n^2）-随着项目的平方增加
• O（n^3）-等
• O（2^n）-呈指数增长
• O（n！）-随数字的阶乘而增加

对于任何合理数量的n（80+），最后2个实际上是不可计算的。

只有最重要的项才是重要的，因为这对大的n so n^2和65*n^2+778*n+456566都是O（n^2）

请记住，这是一个数学结构，算法在使用真实数据的真实硬件上使用真实软件所花费的时间可能会受到其他因素的严重影响（例如，O（n^2）内存操作可能比O（n）磁盘操作花费的时间更少）。

对于您的问题，您需要遍历每一行并计算BIT_COUNT(hash ^ 2028359052535108275) <= 4。这是一个O（n）运算。

唯一可以改进的方法是利用索引，因为b-树索引检索是O（log（n））操作。

但是，因为列字段包含在函数中，所以不能使用该列的索引。你有两种可能性：

1. 这是一个SQL服务器解决方案，我不知道它是否可以移植到MySQL。使用公式BIT_COUNT(hash ^ 2028359052535108275)在表中创建一个持久化的计算列，并对其进行索引。如果需要更改位掩码，这将不适合
2. 找出一种不使用BIT_COUNT函数进行逐位运算的方法

Answer 2

这个解决方案让我的工作更快了一点。它为每个哈希比较生成一个派生表，并且只返回小于火腿距离的结果。这样，它就不会在已经超过火腿的pHash上执行BIT_COUNT。它在大约2.25秒的时间内返回了260万条记录中的所有比赛。

它是InnoDB，我的索引很少。

如果有人能让它更快，我会感谢你的。

SELECT *, BIT_COUNT(pHash3 ^ 42597524) + BC2 AS BC3 
FROM ( 
    SELECT *, BIT_COUNT(pHash2 ^ 258741369) + BC1 AS BC2 
    FROM ( 
        SELECT *, BIT_COUNT(pHash1 ^ 5678910) + BC0 AS BC1 
        FROM ( 
            SELECT `Key`, pHash0, pHash1, pHash2, pHash3, BIT_COUNT(pHash0 ^ 1234567) as BC0 
            FROM files 
            WHERE  BIT_COUNT(pHash0 ^ 1234567) <= 3 
        ) AS BCQ0 
        WHERE BIT_COUNT(pHash1 ^ 5678910) + BC0 <= 3 
    ) AS BCQ1 
    WHERE BIT_COUNT(pHash2 ^ 258741369) + BC1 <= 3 
    ) AS BCQ2 
WHERE BIT_COUNT(pHash3 ^ 42597524) + BC2 <= 3

这是等效的查询，但没有派生表。它的返回时间几乎是原来的3倍。

SELECT `Key`, pHash0, pHash1, pHash2, pHash3 
FROM Files 
WHERE BIT_COUNT(pHash0 ^ 1234567) + BIT_COUNT(pHash1 ^ 5678910) + BIT_COUNT(pHash2 ^ 258741369) + BIT_COUNT(pHash3 ^ 42597524) <=3

请记住，第一个火腿的火腿值越低，它运行的速度就越快。

Answer 3

以下是我的测试结果。Phash是用Python中的imagehash库计算的，并作为两个BIGINT存储在数据库中。

这个测试是在一个不使用分片的mariadb数据库中对858433张图像进行的。我发现分片实际上会减慢进程，但这是函数方法，所以没有它或在大型数据库上可能会有所不同。

这些正在运行的表是一个仅在内存中的表。保存一个本地表，在数据库启动时，id、phash1和phash2被复制到内存中的表中。一旦找到某个内容，就会返回与innodb表匹配的id。

图像总数：858433

图像1:ece0455d6b8e9470

函数HAMMINGISTANCE_16:

RETURN BIT_COUNT(A0 ^ B0) + BIT_COUNT(A1 ^ B1)

方法：HAMMINGISTANCE_16函数

查询：

SELECT `id` FROM `phashs` WHERE HAMMINGDISTANCE_16(filephash_1, filephash_2, CONV(SUBSTRING('ece0455d6b8e9470', 1,  8), 16, 10), CONV(SUBSTRING('ece0455d6b8e9470', 9,  8), 16, 10)) <= 3;

时间：2.1760秒

方法：BIT_COUNT

查询：

SELECT `id` FROM `phashs` WHERE BIT_COUNT(filephash_1 ^ CONV(SUBSTRING('ece0455d6b8e9470', 1,  8), 16, 10)) +  BIT_COUNT(filephash_2 ^ CONV(SUBSTRING('ece0455d6b8e9470', 9,  8), 16, 10)) <= 3; 

时间：0.1547秒

方法：多选BIT_COUNT内部为filephash_1

查询：

SELECT `id` FROM ( SELECT `id`, `filephash_2`, BIT_COUNT(filephash_1 ^ CONV(SUBSTRING('ece0455d6b8e9470', 1, 8), 16, 10)) as BC0 FROM `phashs` WHERE BIT_COUNT(filephash_1 ^ CONV(SUBSTRING('ece0455d6b8e9470', 1, 8), 16, 10)) <= 3 ) BCQ0 WHERE BC0 + BIT_COUNT(filephash_2 ^ CONV(SUBSTRING('ece0455d6b8e9470', 9, 8), 16, 10)) <= 3;

时间：0.1878秒

方法：多选BIT_COUNT内部为filephash_2

查询：

SELECT `id` FROM (SELECT `id`, `filephash_1`, BIT_COUNT(filephash_2 ^ CONV(SUBSTRING('ece0455d6b8e9470', 9,  8), 16, 10)) as BC1 FROM `phashs` WHERE  BIT_COUNT(filephash_2 ^ CONV(SUBSTRING('ece0455d6b8e9470', 9,  8), 16, 10)) <= 3) BCQ1 WHERE BIT_COUNT(filephash_1 ^ CONV(SUBSTRING('ece0455d6b8e9470', 1,  8), 16, 10)) + BC1   <= 3;

时间：0.1860秒

图像2:813ed36913ec8639

函数HAMMINGISTANCE_16:

RETURN BIT_COUNT(A0 ^ B0) + BIT_COUNT(A1 ^ B1)

方法：HAMMINGISTANCE_16函数查询：

SELECT `id` FROM `phashs` WHERE HAMMINGDISTANCE_16(filephash_1, filephash_2, CONV(SUBSTRING('813ed36913ec8639', 1,  8), 16, 10), CONV(SUBSTRING('813ed36913ec8639', 9,  8), 16, 10)) <= 3;

时间：2.1440秒

方法：BIT_COUNT查询：

SELECT `id` FROM `phashs` WHERE BIT_COUNT(filephash_1 ^ CONV(SUBSTRING('813ed36913ec8639', 1,  8), 16, 10)) +  BIT_COUNT(filephash_2 ^ CONV(SUBSTRING('813ed36913ec8639', 9,  8), 16, 10)) <= 3; 

时间：0.1588秒

方法：多选BIT_COUNT内部为filephash_1

查询：

SELECT `id` FROM ( SELECT `id`, `filephash_2`, BIT_COUNT(filephash_1 ^ CONV(SUBSTRING('813ed36913ec8639', 1, 8), 16, 10)) as BC0 FROM `phashs` WHERE BIT_COUNT(filephash_1 ^ CONV(SUBSTRING('813ed36913ec8639', 1, 8), 16, 10)) <= 3 ) BCQ0 WHERE BC0 + BIT_COUNT(filephash_2 ^ CONV(SUBSTRING('813ed36913ec8639', 9, 8), 16, 10)) <= 3;

时间：0.1671秒

方法：多选BIT_COUNT内部为filephash_2

查询：

SELECT `id` FROM (SELECT `id`, `filephash_1`, BIT_COUNT(filephash_2 ^ CONV(SUBSTRING('813ed36913ec8639', 9,  8), 16, 10)) as BC1 FROM `phashs` WHERE  BIT_COUNT(filephash_2 ^ CONV(SUBSTRING('813ed36913ec8639', 9,  8), 16, 10)) <= 3) BCQ1 WHERE BIT_COUNT(filephash_1 ^ CONV(SUBSTRING('813ed36913ec8639', 1,  8), 16, 10)) + BC1   <= 3;

时间：0.1686秒