Расстояние Хэмминга в бинарных строках в SQL

У меня есть таблица в моей БД, где я храню хэши SHA256 в столбце BINARY (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 в двоичной строке).

Теперь я знаю, что и функция operator ^, и функция BIT_COUNT работают только с INTEGER, поэтому я бы сказал, что, вероятно, единственный способ сделать это - разбить двоичные строки в подстроках, отбросить каждую двоичную подстроку на целое число, вычислите расстояние Хэмминга подстрокой, а затем добавьте их. Проблема в том, что это звучит ужасно сложно, неэффективно и определенно не изящно. Поэтому мой вопрос: можете ли вы предложить лучший способ? (учтите, что я нахожусь на общем хостинге, поэтому я не могу изменять сервер БД или загружать библиотеки)

edit (1): Очевидно, что загрузка всей таблицы на PHP и выполнение вычислений было бы возможно, но я бы предпочел избежать этого, потому что эта таблица, вероятно, будет расти довольно.

edit (2): Сервер БД - это MySQL 5.1

edit (3): Мой ответ ниже содержит код, который я только что описал выше.

edit (4): Я только узнал, что использование 4 BIGINT для хранения хэша вместо BINARY (32) дает значительные улучшения скорости (более чем в 100 раз быстрее). См. Комментарии к моему ответу ниже.

Ответы

Ответ 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);

Использование этого подхода в моем тестировании более чем в 100 раз быстрее, чем при использовании подхода BINARY.

FWIW, это код, на который я намекал, объясняя проблему. Лучше всего использовать одно и то же, приветствуются (особенно мне не нравятся двоичные преобразования > hex > decimal):

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)
  );

Ответ 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