MySQL按位运算，布隆过滤器

Question

我想用MySQL实现一个bloom filter（其他建议的替代方案）。

问题如下：

假设我有一个存储8位整数的表，具有以下值：

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

我想找到所有与此相关的结果：

00011000

结果应该是第1行和第5行。

但是，在我的问题中，它们不是8位整数，而是n位整数。我该如何存储，以及如何查询？速度是关键。

Answer 1

使用int列创建一个表（使用this link选择正确的int大小）。不要将数字存储为0和1的序列。

对于您的数据，它将如下所示：

number

154
53
148
38
59
106

你需要找到匹配24的所有条目。

然后你可以运行像这样的查询

SELECT * FROM test WHERE number & 24 = 24

如果你想避免在你的应用程序中转换成10个基数，你可以将它交给mysql：

INSERT INTO test SET number = b'00110101';

并像这样搜索

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

Answer 2

考虑不要使用MySQL。

首先，可能没有超过64位表的内置方法。您必须使用用C编写的用户定义函数。

其次，每个查询都需要进行全表扫描，因为MySQL无法使用索引进行查询。所以，除非你的桌子很小，否则这不会很快。

Answer 3

切换到PostgreSQL并使用bit（n）

Answer 4

Bloom过滤器本质上需要表扫描来评估匹配。在MySQL中，没有布隆过滤器类型。简单的解决方案是将布隆过滤器的字节映射到BitInteger（8字节字）并在查询中执行检查。因此，假设bloom过滤8个字节或更少（一个非常小的过滤器），你可以执行一个准备好的语句，如：

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

并使用您要查找的值替换参数。但是，对于较大的过滤器，您必须创建多个filter列并将目标过滤器拆分为多个单词。您必须转换为unsigned以正确执行检查。

由于许多合理的布隆过滤器的尺寸在Kilo到Megabyte范围内，因此使用blob来存储它们是有意义的。切换到blob后，没有本机机制来执行字节级比较。并且在整个网络中提取整个大型blob表以在本地代码中进行过滤并没有多大意义。

我发现的唯一合理的解决方案是UDF。 UDF应接受char*并迭代它将char*投射到unsigned char*并执行target & candidate = target检查。此代码看起来像：

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

该解决方案已实施并可用here

Answer 5

对于最多64位，您可以使用MySQL整数类型，如tinyint（8b），int（16b），mediumint（24b）和bigint（64b）。使用无符号变体。

高于64b，使用MySQL（VAR）BINARY类型。那些是原始字节缓冲区。例如，BINARY（16）适用于128位。

为了防止表扫描，您需要每个有用位的索引，和/或每组相关位的索引。您可以为其创建虚拟列，并为每个列添加索引。