Расстояние хэминга на бинарных струнах в 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 в двоичной строке).

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

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

Редактировать (2): сервер DB - MySQL 5.1

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

Редактировать (4): Я только что обнаружил, что использование 4 Bigints для хранения хэша вместо двоичного (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);

Использование этого подхода, в моем тестировании, в 100 раз быстрее, чем использование 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