Opérations bitwise MySQL, filtre bloom

Question

Je voudrais mettre en œuvre un bloom filter en utilisant MySQL (autre une alternative suggérée).

Le problème est le suivant:

Supposons que j'ai une table qui stocke 8 entiers de bits, avec ces valeurs suivantes:

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

Je voudrais trouver tous les résultats qui sont au niveau du bit à ceci:

00011000 

Les résultats devraient être les lignes 1 et 5.

Howev er, dans mon problème, ce ne sont pas des entiers de 8 bits, mais plutôt des entiers de n bits. Comment puis-je stocker cela, et comment puis-je interroger? La vitesse est la clé.

Answer 1

Créer une table avec une colonne int (utilisez this link pour choisir la bonne taille int). Ne pas stocker les numéros comme une séquence de 0 et 1.

Pour vos données, il ressemblera à ceci:

number 

154 
53 
148 
38 
59 
106 

et vous devez trouver toutes les entrées correspondant à 24.

Ensuite, vous pouvez exécuter une requête comme

SELECT * FROM test WHERE number & 24 = 24 

Si vous voulez éviter convertion en 10 numéros de base dans votre application, vous pouvez le remettre à mysql:

INSERT INTO test SET number = b'00110101'; 

et la recherche comme celui-ci

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

Answer 2

Ne tenez pas compte en utilisant MySQL pour cela.

Tout d'abord, il n'existe probablement pas de méthode intégrée pour les tables de plus de 64 bits. Vous devrez recourir à des fonctions définies par l'utilisateur et écrites en C.

Ensuite, chaque requête nécessitera une analyse de table complète, car MySQL ne peut pas utiliser d'index pour votre requête. Donc, à moins que votre table soit très petite, ce ne sera pas rapide.

Answer 3

Passer à PostgreSQL et le bit d'utilisation (n)

Answer 4

filtres Bloom par leur nature exigent des analyses de table pour évaluer les matchs. En MySQL il n'y a pas de type de filtre bloom. La solution simple consiste à mapper les octets du filtre de bloom sur BitInteger (mots de 8 octets) et à effectuer la vérification dans la requête. Donc, en supposant que la floraison Filteris 8 octets ou moins (un très petit filtre), vous pouvez exécuter une instruction préparée comme:

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

et remplacer les paramètres avec la valeur que vous recherchez. Toutefois, pour les filtres plus volumineux, vous devez créer plusieurs colonnes filter et diviser votre filtre cible en plusieurs mots. Vous devez lancer à non signé pour faire le contrôle correctement.

Étant donné que de nombreux filtres de bloom raisonnables ont une taille comprise entre Kilo et Mégaoctet, il est logique d'utiliser des blobs pour les stocker.Une fois que vous passez aux blobs, il n'y a pas de mécanismes natifs pour effectuer les comparaisons au niveau des octets. Et tirer une table entière de gros blobs à travers le réseau pour faire le filtre dans le code localement n'a pas beaucoup de sens.

La seule solution raisonnable que j'ai trouvé est un UDF. L'UDF doit accepter un char* et le parcourir en lançant le char* en unsigned char* et effectuer la vérification target & candidate = target. Ce code ressemblerait à quelque chose comme:

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

Cette solution est mise en œuvre et est disponible à https://github.com/Claudenw/mysql_bloom

Answer 5

Pour jusqu'à 64 bits, vous pouvez utiliser un type entier MySQL, comme tinyint (8b), int (16b), mediumint (24b) et bigint (64b). Utilisez les variantes non signées. Au-dessus de 64b, utilisez le type BINARY de MySQL (VAR). Ce sont des tampons d'octets bruts. Par exemple BINARY (16) est bon pour 128 bits.

Pour éviter les analyses de table, vous avez besoin d'un index par bit utile et/ou d'un index par ensemble de bits associés. Vous pouvez créer des colonnes virtuelles pour cela, et mettre un index sur chacun d'eux.