9

我想使用 MySQL 实现一个布隆过滤器（其他建议的替代方案）。

问题如下：

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

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

我想找到所有按位与此的结果：

00011000

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

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

4

6 回答 6

19

创建一个带有 int 列的表（使用此链接选择正确的 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'
于 2008-12-11T21:45:07.947 回答
8

考虑不为此使用 MySQL。

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

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

于 2008-12-14T05:37:13.487 回答
2

切换到 PostgreSQL 并使用 bit(n)

于 2008-12-17T18:23:35.637 回答
2

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

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

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

由于许多合理的布隆过滤器的大小都在千字节到兆字节范围内，因此使用 blob 来存储它们是有意义的。一旦切换到 blob，就没有本地机制来执行字节级别的比较。并且通过网络拉动整个大 blob 表以在本地进行代码过滤并没有多大意义。

我找到的唯一合理的解决方案是 UDF。UDF 应该接受 achar*并对其进行迭代，将其强制转换char*为 anunsigned 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;
}

此解决方案已实施并可在此处获得

于 2015-02-13T11:39:04.083 回答
1

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

64b 以上，使用 MySQL (VAR)BINARY 类型。这些是原始字节缓冲区。例如 BINARY(16) 适用于 128 位。

为了防止表扫描，您需要每个有用位的索引，和/或每组相关位的索引。您可以为此创建虚拟列，并在每个列上放置一个索引。

于 2017-12-17T12:06:41.463 回答
1

要使用数据库实现布隆过滤器，我会以不同的方式考虑它。

我会做一个两级过滤器。使用单个多位散列函数生成一个 id（这将更像是一个散列表桶索引），然后将行中的位用于更经典类型的剩余 k-1 散列函数。在该行内，它可能是（比如说）100bigint列（我也会比较性能与 BLOB）。

它实际上是 N 个单独的 Bloom 过滤器，其中 N 是您的第一个哈希函数的域。这个想法是通过选择散列桶来减小所需的布隆过滤器的大小。它不会具有内存中 Bloom 过滤器的全部效率，但与将所有值放入数据库并对其进行索引相比，它仍然可以大大减少需要存储的数据量。大概首先使用数据库的原因是完整的布隆过滤器内存不足。

于 2019-10-15T15:10:29.313 回答