Operacje bitowe MySQL, filtr kwitnący

Question

Chciałbym zaimplementować bloom filter przy użyciu MySQL (inne sugerowana alternatywa).

Problem jest następujący:

Załóżmy, że mam tabelę, która przechowuje 8-bitowe liczby całkowite, z tymi następujących wartości:

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

Chciałbym, aby znaleźć wszystkie wyniki, które są bitowe AND aby następująco:

00011000 

wyników należy wiersze 1 do 5.

Howev W moim problemie nie są to 8-bitowe liczby całkowite, ale raczej n-bitowe liczby całkowite. Jak mogę to zapisać i jak wysłać zapytanie? Szybkość jest kluczowa.

Answer 1

Utwórz tabelę z int kolumną (użyj this link, aby wybrać właściwy rozmiar int). Nie przechowywać numery jako ciąg 0 i 1.

dla danych będzie wyglądać następująco:

number 

154 
53 
148 
38 
59 
106 

i trzeba znaleźć wszystkie wpisy pasujące 24.

Następnie można uruchomić kwerendę jak

SELECT * FROM test WHERE number & 24 = 24 

Jeśli chcesz uniknąć konwersja do 10 numerów bazowych w aplikacji można oddać go do mysql:

INSERT INTO test SET number = b'00110101'; 

i szukać jak to

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

Answer 2

nie uznać tego za pomocą MySQL.

Po pierwsze, prawdopodobnie nie ma wbudowanego sposobu na więcej niż 64-bitowych tabel. Trzeba będzie odwoływać się do funkcji zdefiniowanych przez użytkownika, napisanych w C.

Po drugie, każde zapytanie będzie wymagało pełnego skanowania tabeli, ponieważ MySQL nie może użyć indeksu do zapytania. Tak więc, jeśli Twój stół jest bardzo mały, nie będzie to szybkie.

Answer 3

Przełącz na PostgreSQL i wykorzystanie bitowy (n)

Answer 4

filtry Bloom ze swej natury wymaga skanowania tabeli do oceny wyników. W MySQL nie ma typu filtra kwitującego. Prostym rozwiązaniem jest mapowanie bajtów filtru Blooma na BitInteger (8 bajtowych słów) i wykonanie sprawdzenia w zapytaniu. Więc zakładając, że kwitną filteris 8 bajtów lub mniej (bardzo mały filtr) można wykonać przygotowaną instrukcję jak:

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

i zastąpić parametry o wartości którego szukasz. Jednak w przypadku większych filtrów należy utworzyć wiele kolumn filter i podzielić filtr docelowy na wiele wyrazów. Musisz obsłużyć niepodpisane, aby wykonać test prawidłowo.

Ponieważ wiele rozsądnych filtrów kwitnienia ma wielkość Kilo do Megabajtów, warto używać obiektów typu BLOB do ich przechowywania.Po przełączeniu na bloby nie ma natywnych mechanizmów do przeprowadzania porównań poziomów bajtów. Ciągnięcie całej tabeli dużych obiektów w sieci w celu wykonania lokalnego kodu filtra nie ma większego sensu.

Jedynym rozsądnym rozwiązaniem, które znalazłem, jest UDF. UDF powinien zaakceptować numer char* i powtórzyć go, przesyłając char* do unsigned char* i wykonać test target & candidate = target. Ten kod będzie wyglądać następująco:

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

To rozwiązanie jest wdrożony i jest dostępny w https://github.com/Claudenw/mysql_bloom

Answer 5

do 64 bitów, można użyć MySQL całkowitą typu, jak tinyint (8b), int (16b), średni (24b) i bigint (64b). Użyj niepodpisanych wariantów.

Powyżej 64b należy użyć typu BINARIA MySQL (VAR). Są to bufory surowych bajtów. Na przykład BINARY (16) jest dobre dla 128 bitów.

Aby zapobiec skanowaniu tabeli, potrzebny jest indeks na użyteczny bit i/lub indeks na zestaw powiązanych bitów. Możesz utworzyć wirtualne kolumny dla tego i umieścić indeks na każdym z nich.