Mysql
 sql >> Base de Dados >  >> RDS >> Mysql

Distância de Hamming em strings binárias em SQL


Parece que armazenar os dados em um BINARY coluna é uma abordagem destinada a ter um desempenho ruim. A única maneira rápida de obter um desempenho decente é dividir o conteúdo do BINARY coluna em vários BIGINT colunas, cada uma contendo uma substring de 8 bytes dos dados originais.

No meu caso (32 bytes), isso significaria usar 4 BIGINT colunas e usando esta função:
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);

Usar essa abordagem, em meus testes, é mais de 100 vezes mais rápido do que usar o BINARY abordagem.

FWIW, este é o código que eu estava sugerindo ao explicar o problema. Melhores maneiras de realizar a mesma coisa são bem-vindas (eu especialmente não gosto das conversões binárias> hexadecimais> decimais):
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)
  );