SQL中的二进制字符串的锤距

Question

我的DB中有一张桌子，其中将SHA256哈希存储在二进制（32）列中。我正在寻找一种计算列中条目的锤子距离到提供的值的方法，例如：

SELECT * FROM table 
  ORDER BY HAMMINGDISTANCE(hash, UNHEX(<insert supplied sha256 hash here>)) ASC 
  LIMIT 10

（以防万一您想知道，字符串A和B的锤子距离被定义为 BIT_COUNT(A^B), ，其中 ^是位XOR运算符，bit_count返回二进制字符串中的1s的数字）。

现在，我知道 ^ oterator和bit_count函数仅在整数上都起作用，所以我会说，可能要做的唯一方法是打破子字符串中的二进制字符串，将每个二进制子字符串施加到整数，计算锤击距离子字符串，然后添加它们。问题在于，它听起来非常复杂，效率不高，绝对不优雅。因此，我的问题是：您能提出任何更好的方法吗？ （请注意，我在共享托管上，因此我无法修改DB服务器或加载库）

编辑（1）：显然，将整个表加载到PHP中并进行计算，但我宁愿避免使用它，因为该表可能会增长很大。

编辑（2）：DB服务器是MySQL 5.1

编辑（3）：下面的答案包含我刚刚描述的代码。

编辑（4）：我刚刚发现，使用4个bigint存储哈希，而不是二进制（32）可以大大提高速度（更快的速度超过100倍）。请参阅下面的评论。

Answer 1

看来将数据存储在 BINARY 列是绑定不佳的方法。获得体面绩效的唯一快速方法是分割 BINARY 多个列 BIGINT 列，每个列包含原始数据的8字节基因串。

就我而言（32个字节），这意味着使用4 BIGINT 列并使用此功能：

CREATE FUNCTION HAMMINGDISTANCE(
  A0 BIGINT, A1 BIGINT, A2 BIGINT, A3 BIGINT, 
  B0 BIGINT, B1 BIGINT, B2 BIGINT, B3 BIGINT
)
RETURNS INT DETERMINISTIC
RETURN 
  BIT_COUNT(A0 ^ B0) +
  BIT_COUNT(A1 ^ B1) +
  BIT_COUNT(A2 ^ B2) +
  BIT_COUNT(A3 ^ B3);

在我的测试中，使用这种方法比使用 BINARY 方法。

---

FWIW，这是我在解释问题时暗示的代码。欢迎更好地完成同一件事的更好方法（我尤其不喜欢二进制>十六进制>十进制转换）：

CREATE FUNCTION HAMMINGDISTANCE(A BINARY(32), B BINARY(32))
RETURNS INT DETERMINISTIC
RETURN 
  BIT_COUNT(
    CONV(HEX(SUBSTRING(A, 1,  8)), 16, 10) ^ 
    CONV(HEX(SUBSTRING(B, 1,  8)), 16, 10)
  ) +
  BIT_COUNT(
    CONV(HEX(SUBSTRING(A, 9,  8)), 16, 10) ^ 
    CONV(HEX(SUBSTRING(B, 9,  8)), 16, 10)
  ) +
  BIT_COUNT(
    CONV(HEX(SUBSTRING(A, 17, 8)), 16, 10) ^ 
    CONV(HEX(SUBSTRING(B, 17, 8)), 16, 10)
  ) +
  BIT_COUNT(
    CONV(HEX(SUBSTRING(A, 25, 8)), 16, 10) ^ 
    CONV(HEX(SUBSTRING(B, 25, 8)), 16, 10)
  );

Answer 2

有趣的问题，我找到了一种方法 binary(3) 这也可能对 binary(32):

drop table if exists BinaryTest;
create table  BinaryTest (hash binary(3));
insert BinaryTest values (0xAAAAAA);

set @supplied = cast(0x888888 as binary);

select  length(replace(concat(
            bin(ascii(substr(hash,1,1)) ^ ascii(substr(@supplied,1,1))),
            bin(ascii(substr(hash,2,1)) ^ ascii(substr(@supplied,2,1))),
            bin(ascii(substr(hash,3,1)) ^ ascii(substr(@supplied,3,1)))
        ),'0',''))
from    BinaryTest;

这 replace 删除所有零，剩余的长度是零的数量。 （转换为二进制省略零，因此计数零是行不通的。）

这是打印的 6, ，与之匹配的数量

0xAAAAAA ^ 0x888888 = 0x222222 = 0b1000100010001000100010