Distancia de Hamming en cadenas binarias en SQL

Question

Tengo una tabla en mi base de datos donde almaceno hashes SHA256 en una columna BINARY (32). Estoy buscando una manera de calcular la distancia de Hamming de las entradas de la columna a un valor suministrado, es decir, algo así como:

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

(en caso de que se esté preguntando, la distancia de Hamming de cadenas A y B se define como BIT_COUNT(A^B), donde^es el operador XOR bit a bit y BIT_COUNT devuelve el número de 1s en la cadena binaria).

Ahora, sé que tanto el operador^como la función BIT_COUNT solo funcionan en INTEGER, así que diría que probablemente la única forma de hacerlo sería dividir las cadenas binarias en subcadenas, convertir cada subcadena binaria en entero, calcule la distancia de Hamming en subcadena y luego agréguela. El problema con esto es que suena terriblemente complicado, no eficiente y definitivamente no elegante. Mi pregunta, por lo tanto, es: ¿podría sugerir alguna forma mejor? (tenga en cuenta que estoy en alojamiento compartido y por lo tanto no puedo modificar el servidor de base de datos o cargar bibliotecas)

editar (1): Obviamente, cargar toda la tabla en PHP y hacer los cálculos allí sería posible, pero yo preferiría evitarlo porque esta mesa probablemente crecerá bastante.

de edición (2): El servidor de base de datos es MySQL 5.1

edición (3): Mi respuesta a continuación contiene el código que he descrito anteriormente.

editar (4): Acabo de descubrir que usar 4 BIGINT para almacenar el hash en lugar de BINARY (32) produce mejoras de velocidad masivas (más de 100 veces más rápidas). Ver los comentarios a mi respuesta a continuación.

Answer 1

Parece que el almacenamiento de los datos en una columna BINARY es un enfoque obligado a funcionar mal. La única forma rápida de obtener un rendimiento decente es dividir el contenido de la columna BINARY en múltiples columnas BIGINT, cada una con una subcadena de 8 bytes de los datos originales.

En mi caso (32 bytes), esto significaría utilizando 4 BIGINT columnas y el uso de esta función:

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

uso de este enfoque, en mis pruebas, es más de 100 veces más rápido que utilizando el enfoque BINARY.

---

FWIW, este es el código que estaba insinuando al explicar el problema.Mejores maneras de lograr lo mismo son bienvenidas (En especial no les gusta el binario> hex> conversiones decimales):

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

Interesante pregunta, he encontrado una manera de hacer esto para un binary(3) que podría funcionar también para un 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; 

El replace elimina cualquier todos los ceros, y la longitud del resto es el número de unos. (La conversión a omite binarios ceros a la izquierda, por lo que cuentan los ceros no funcionaría.)

Esto imprime 6, que coincide con el número de unos en

0xAAAAAA^0x888888 = 0x222222 = 0b1000100010001000100010