MySQL bitweise Operationen, Bloom Filter

Question

Ich würde gerne eine bloom filter mit MySQL (andere eine vorgeschlagene Alternative) implementieren.

Das Problem ist wie folgt:

Angenommen, ich habe eine Tabelle, die 8-Bit-Integer speichert, mit diesen folgenden Werte:

1: 10011010 
2: 00110101 
3: 10010100 
4: 00100110 
5: 00111011 
6: 01101010 

Ich möchte alle Ergebnisse finden, die bitweise und an dies:

00011000 

Die Ergebnisse sollten die Zeilen 1 und 5.

Howev sein In meinem Problem sind sie keine 8-Bit-Ganzzahlen, sondern ganze Zahlen mit n Bit. Wie kann ich dies speichern und wie frage ich? Geschwindigkeit ist der Schlüssel.

Answer 1

Erstellen Sie eine Tabelle mit int-Spalte (verwenden Sie this link, um die richtige int-Größe auszuwählen). Bewahren Sie keine Zahlen als eine Folge von 0 und 1

Für Ihre Daten, die sie wie folgt aussehen:

number 

154 
53 
148 
38 
59 
106 

und Sie müssen alle Einträge finden passende 24.

Dann können Sie eine Abfrage wie

SELECT * FROM test WHERE number & 24 = 24 

Wenn Sie convertion in 10 Basenzahlen in der Anwendung vermeiden möchten, dass Sie es über mysql geben kann:

INSERT INTO test SET number = b'00110101'; 

und suchen wie diese

SELECT bin(number) FROM test WHERE number & b'00011000' = b'00011000' 

Answer 2

Erwägen Sie den Einsatz von MySQL nicht für diese.

Zunächst einmal gibt es wahrscheinlich keine integrierte Möglichkeit für mehr als 64-Bit-Tabellen. Sie müssten auf benutzerdefinierte Funktionen zurückgreifen, die in C geschrieben sind. Zweitens benötigt jede Abfrage einen vollständigen Tabellenscan, da MySQL keinen Index für Ihre Abfrage verwenden kann. Also, wenn dein Tisch nicht sehr klein ist, wird das nicht schnell sein.

Answer 3

Wechsle zu PostgreSQL und Verwendung Bit (n)

Answer 4

Bloom Filter durch ihre Natur erfordern Tabellen-Scans Spiele zu bewerten. In MySQL gibt es keinen Bloomfiltertyp. Die einfache Lösung besteht darin, die Bytes des Bloom-Filters auf BitInteger (8-Byte-Wörter) abzubilden und die Überprüfung in der Abfrage durchzuführen. So unter der Annahme, dass die Blüte filteris 8 Bytes oder weniger (ein sehr kleiner Filter) Sie konnten eine vorbereitete Anweisung wie ausführen:

SELECT * FROM test WHERE cast(filter, UNSIGNED) & cast(?, UNSIGNED) = cast(?, UNSIGNED)

und ersetzen Sie die Parameter mit dem Wert, den Sie suchen. Bei größeren Filtern müssen Sie jedoch mehrere filter Spalten erstellen und den Zielfilter in mehrere Wörter aufteilen. Sie müssen in unsigned umwandeln, um die Überprüfung ordnungsgemäß durchzuführen.

Da viele brauchbare Bloom-Filter im Kilo- bis Megabyte-Bereich liegen, ist es sinnvoll, sie mit Blobs zu speichern.Sobald Sie zu Blobs wechseln, gibt es keine systemeigenen Mechanismen, um die Byte-Level-Vergleiche durchzuführen. Und eine ganze Tabelle mit großen Blobs über das Netzwerk zu ziehen, um den Filter im Code lokal auszuführen, macht wenig Sinn.

Die einzige vernünftige Lösung, die ich gefunden habe, ist eine UDF. Die UDF sollte eine char* akzeptieren und iterieren über die char* zu einer unsigned char* Gießen und die target & candidate = target Überprüfung durchführen. Dieser Code würde in etwa so aussehen:

my_bool bloommatch(UDF_INIT *initid, UDF_ARGS *args, char* result, unsigned long* length, char *is_null, char *error) 
{ 
    if (args->lengths[0] > args->lengths[1]) 
    { 
     return 0; 
    } 
    char* b1=args->args[0]; 
    char* b2=args->args[1]; 
    int limit = args->lengths[0]; 
    unsigned char a; 
    unsigned char b; 
    int i; 
    for (i=0;i<limit;i++) 
    { 
     a = (unsigned char) b1[i]; 
     b = (unsigned char) b2[i]; 
     if ((a & b) != a) 
     { 
      return 0; 
     } 
    } 
    return 1; 
} 

Diese Lösung implementiert und ist bei https://github.com/Claudenw/mysql_bloom

Answer 5

für bis zu 64 Bit, Sie einen MySQL-Integer-Typen verwenden können, wie Tinyint (8b), int (16b), Mediumint (24b) und Bigint (64b). Verwenden Sie die unsignierten Varianten.

Verwenden Sie über 64b den MySQL (VAR) BINARY-Typ. Das sind rohe Bytepuffer. Zum Beispiel ist BINARY (16) gut für 128 Bits.

Um Tabellenscans zu verhindern, benötigen Sie einen Index pro nützliches Bit und/oder einen Index pro Satz verwandter Bits. Sie können dafür virtuelle Spalten erstellen und ihnen einen Index zuweisen.