Hamming distanza su stringhe binarie in SQL

Question

Ho una tabella nel mio DB dove devo conservare SHA256 hash in un file binario (32) della colonna. Sto cercando un modo per calcolare la distanza di Hamming delle voci nella colonna a un valore fornito, vale a dire qualcosa come:

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

(nel caso in cui vi state chiedendo, la distanza di Hamming di stringhe A e B è definito come BIT_COUNT(A^B), dove ^ è l'operatore XOR bit a bit e BIT_COUNT restituisce il numero di 1s nella stringa binaria).

Ora, so che sia l'operatore ^ e la funzione BIT_COUNT unica opera su interi e quindi direi che probabilmente l'unico modo per farlo sarebbe quello di rompere le stringhe binarie in sottostringhe, gettato ogni sottostringa binario intero , calcolare la distanza di Hamming sottostringa-saggio e poi aggiungerli. Il problema di questo è che suona terribilmente complicato, non è efficiente e sicuramente non elegante. La mia domanda quindi è: si potrebbe suggerire un modo migliore? (Si ricorda che sono in hosting condiviso e quindi non posso modificare le librerie del server DB o di carico)

modifica (1):. Ovviamente caricare l'intera tabella in PHP e facendo i calcoli non ci sarebbe possibile, ma io preferirei evitarlo perché questa tabella probabilmente crescerà abbastanza grande

modifica (2): Il server DB è MySQL 5.1

modifica (3):. La mia risposta qui sotto contiene il codice che ho appena descritto sopra

modifica (4): Ho appena scoperto che l'uso di 4 BIGINTs per memorizzare l'hash invece di un file binario (32) produce miglioramenti di velocità di massa (più di 100 volte più veloce). Vedere i commenti alla mia risposta qui di seguito.

Answer 1

Sembra che la memorizzazione dei dati in una colonna BINARY è un approccio legato a scarso rendimento. L'unico modo veloce per ottenere prestazioni decenti è quella di dividere il contenuto della colonna BINARY in più colonne BIGINT, ciascuna contenente una stringa di 8 byte dei dati originali.

Nel mio caso (32 byte), ciò significherebbe usando 4 colonne BIGINT e utilizzare questa funzione:

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

Usando questo approccio, nel mio test, è di oltre 100 volte più veloce utilizzando l'approccio BINARY.

---

FWIW, questo è il codice che stavo accennando mentre spiega il problema. modi migliori per realizzare la stessa cosa sono i benvenuti (soprattutto non piace il binario> hex> decimale conversioni):

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

Domanda interessante, ho trovato un modo per fare questo per un binary(3) quel lavoro potrebbe pure per 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;

Il replace rimuove eventuali tutti zeri, e la lunghezza del resto è il numero di quelli. (La conversione omette binari gli zeri, quindi contando gli zeri non funzionerebbe.)

Questa stampe 6, che corrisponde al numero di quelli in

0xAAAAAA ^ 0x888888 = 0x222222 = 0b1000100010001000100010