Hamming -Entfernung auf binären Zeichenfolgen in SQL

Question

Ich habe einen Tisch in meinem DB, an dem ich SHA256 -Hashes in einer binären (32) Spalte speichere. Ich suche nach einer Möglichkeit, die Hamming -Distanz der Einträge in der Spalte zu einem gelieferten Wert zu berechnen, dh so etwas wie:

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

(Für den Fall, dass Sie sich fragen, wird der Hamming -Abstand der Saiten A und B als definiert als BIT_COUNT(A^B), wobei ^ der bitweise XOR -Operator ist und Bit_Count gibt die Anzahl der 1s in der Binärzapfen zurück).

Nun weiß ich, dass sowohl die Funktion des ^ Operators als auch der Bit_Count nur an Ganzzahlen arbeiten, und ich würde sagen, dass dies wahrscheinlich der einzige Weg ist, die binären Saiten in Substrings aufzubrechen, jedes binäre Substring auf die ganze Zahl zu geben, die Berechnung der Berechnung des Substring-Hamming-Abstand und fügen Sie sie dann hinzu. Das Problem dabei ist, dass es furchtbar kompliziert, nicht effizient und definitiv nicht elegant klingt. Meine Frage ist daher: Könnten Sie einen besseren Weg vorschlagen? (Bitte beachten Sie, dass ich auf Shared Hosting bin und daher den DB -Server oder die Bibliotheken nicht ändern kann.)

Bearbeiten (1): Offensichtlich laden Sie die gesamte Tabelle in PHP und die Berechnungen, aber ich würde es lieber vermeiden, weil diese Tabelle wahrscheinlich ziemlich groß wird.

Bearbeiten (2): Der DB -Server ist MySQL 5.1

Bearbeiten (3): Meine Antwort unten enthält den Code, den ich oben beschrieben habe.

EDIT (4): Ich habe gerade herausgefunden, dass die Verwendung von 4 Bigints zum Speichern des Hashs anstelle eines binären (32) massive Geschwindigkeitsverbesserungen (mehr als 100 -mal schneller) liefert. Siehe die Kommentare zu meiner Antwort unten.

Answer 1

Es scheint, dass das Speichern der Daten in a BINARY Die Säule ist ein Ansatz, der nur schlecht abschneidet. Der einzige schnelle Weg, um eine anständige Leistung zu erzielen, besteht darin, den Inhalt des BINARY Spalte in mehreren BIGINT Spalten, die jeweils eine 8-Byte-Substring der Originaldaten enthalten.

In meinem Fall (32 Bytes) würde dies mit 4 bedeuten BIGINT Spalten und diese Funktion verwenden:

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

Die Verwendung dieses Ansatzes ist bei meinen Tests über 100 -mal schneller als die Verwendung der BINARY sich nähern.

---

FWIW, dies ist der Code, auf den ich das Problem erklärte. Bessere Möglichkeiten, dasselbe zu erreichen, sind willkommen (ich mag besonders nicht die Binärer> Hex> Dezimalkonvertierungen):

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

Interessante Frage, ich habe einen Weg gefunden, dies für a zu tun binary(3) Das könnte auch für a funktionieren 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;

Das replace Entfernt alle Nullen, und der Rest ist die Anzahl derjenigen. (Die Konvertierung in binäre Auslasse führende Nullen, sodass das Zählen der Nullen nicht funktionieren würde.)

Dies druckt 6, was der Anzahl derjenigen entspricht

0xAAAAAA ^ 0x888888 = 0x222222 = 0b1000100010001000100010