Mysql
 sql >> Database >  >> RDS >> Mysql

Distanza di Hamming su stringhe binarie in SQL

Sembra che la memorizzazione dei dati in un BINARY colonna è un approccio destinato a funzionare male. L'unico modo veloce per ottenere prestazioni decenti è dividere il contenuto del BINARY colonna in più BIGINT colonne, ciascuna contenente una sottostringa di 8 byte dei dati originali.

Nel mio caso (32 byte) ciò significherebbe utilizzare 4 BIGINT colonne e utilizzando 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);

L'utilizzo di questo approccio, nei miei test, è oltre 100 volte più veloce rispetto all'utilizzo di BINARY approccio.

FWIW, questo è il codice a cui stavo alludendo mentre spiegavo il problema. Sono benvenuti modi migliori per ottenere la stessa cosa (in particolare non mi piacciono le conversioni binarie> esadecimali> decimali):

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