MySQL operaciones bit a bit, filtro de floración

Question

Me gustaría implementar un bloom filter utilizando MySQL (otra alternativa sugerida).

El problema es el siguiente:

Supongamos que tengo una tabla que almacena 8 bits enteros, con estos valores siguientes:

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

Me gustaría encontrar todos los resultados que son AND bit a bit a esto:

00011000 

los resultados deben ser las filas 1 y 5.

Howev er, en mi problema, no son enteros de 8 bits, sino enteros de n bits. ¿Cómo guardo esto y cómo consulto? La velocidad es la clave.

Answer 1

Cree una tabla con la columna int (use this link para elegir el tamaño int correcto). No guarde los números como una secuencia de 0 y 1.

para los datos que se verá así:

number 

154 
53 
148 
38 
59 
106 

y es necesario encontrar todas las entradas coincidentes 24.

entonces se puede ejecutar una consulta como

SELECT * FROM test WHERE number & 24 = 24 

Si se quiere evitar la conversión en 10 números de base en su aplicación, puede entregarlo a MySQL:

INSERT INTO test SET number = b'00110101'; 

y buscar como esto

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

Answer 2

no considerar el uso de MySQL para esto.

En primer lugar, probablemente no haya una forma incorporada para tablas de más de 64 bits. Tendría que recurrir a funciones definidas por el usuario escritas en C.

En segundo lugar, cada consulta requerirá un escaneo completo de la tabla, porque MySQL no puede usar un índice para su consulta. Entonces, a menos que su mesa sea muy pequeña, esto no será rápido.

Answer 3

Cambiar a PostgreSQL y el uso de bit (n)

Answer 4

filtros Bloom, por su naturaleza requieren recorridos de tablas para evaluar partidos. En MySQL no hay ningún tipo de filtro de floración. La solución simple es mapear los bytes del filtro bloom en BitInteger (palabras de 8 bytes) y realizar la verificación en la consulta. Así que asumiendo que la floración filteris 8 bytes o menos (un pequeño filtro) que podría ejecutar una declaración preparada como:

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

y reemplazar los parámetros con el valor que busca. Sin embargo, para filtros más grandes, debe crear múltiples columnas filter y dividir el filtro de destino en varias palabras. Tienes que lanzar a unsigned para hacer el control correctamente.

Dado que muchos filtros de bloom razonables tienen un tamaño de Kilo a Megabyte, tiene sentido utilizar blobs para almacenarlos.Una vez que cambia a blobs, no hay mecanismos nativos para realizar las comparaciones de nivel de bytes. Y tirando de una tabla completa de blobs grandes a través de la red para hacer el filtro en código localmente no tiene mucho sentido.

La única solución razonable que he encontrado es una UDF. El UDF debe aceptar un char* y repetirlo lanzando el char* a un unsigned char* y realizar el control target & candidate = target. Este código sería algo como:

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

Esta solución se implementa y está disponible en https://github.com/Claudenw/mysql_bloom

Answer 5

Para hasta 64 bits, se puede utilizar un tipo entero de MySQL, como tinyint (8b), int (16b), mediumint (24b) y bigint (64b). Use las variantes sin firmar.

Por encima de 64b, utilice el tipo BINARIO de MySQL (VAR). Esos son buffers de byte sin formato. Por ejemplo, BINARY (16) es bueno para 128 bits.

Para evitar escaneos de tablas, necesita un índice por bit útil y/o un índice por conjunto de bits relacionados. Puede crear columnas virtuales para eso y poner un índice en cada una de ellas.