数据库算子与布隆过滤器，如何应用于检索？

数据库中的“哈希函数与布隆过滤器” 布隆过滤器的本质，就是一个有限长度的位数组（Bit Array）加上 \(k\) 个独立的哈希函数。 哈希函数决定了数据如何在这个位数组中留下“指纹”。 1. 核心映射关系：数据到比特位的“寻址器” 布隆过滤器本身不存储实际的数据库记录（如 user_id = 'Alice'），它只是一排初始值为 0 的比特位。哈希函数的作用，就是充当寻址器，将任意长度、任意类型的数据映射为这个位数组中的具体索引位置。 写入阶段（Insertion）： 当数据库要把一个值（例如 'Alice'）加入布隆过滤器时，会将这个值分别输入到 \(k\) 个不同的哈希函数中。每个哈希函数都会计算出一个整数结果，对位数组的长度 \(m\) 取模后，得到 \(k\) 个位置索引。然后，将位数组中这 \(k\) 个位置的值全部置为 1。 查询阶段（Lookup / Probe）： 当数据库要查 'Alice' 是否存在时，再次用同样的 \(k\) 个哈希函数计算出 \(k\) 个位置。 如果这 \(k\) 个位置中哪怕有一个是 0，说明 'Alice' 绝对没有被写入过（即 100% 不存在）。 如果这 \(k\) 个位置全是 1，说明 'Alice' 可能存在（因为这些 1 可能是其他数据写入时碰巧叠加留下的，这就是假阳性 False Positive 的来源）。 2. 为什么要用“多个”（\(k\) 个）哈希函数？ 如果只用 \(1\) 个哈希函数，由于哈希碰撞（Hash Collision）的存在，两个不同的值很容易映射到同一个位置，导致极高的假阳性率。 引入 \(k\) 个不同的哈希函数，相当于让每个数据留下 \(k\) 个特征指纹。 制衡机制： 只有当要查询的数据的 \(k\) 个指纹与位数组中的 \(k\) 个 1 完全吻合时，才判定为“可能存在”。这就极大地降低了偶然碰撞的概率。 双刃剑： 但哈希函数也不是越多越好。如果 \(k\) 太大，每插入一个元素就会把太多的 0 变成 1。位数组很快就会被“填满”，导致后续所有的查询都返回“可能存在”，布隆过滤器就彻底失效了。 3. 数据库工程实现中的哈希函数选择 在数据库内核开发中，布隆过滤器对哈希函数的选择极其苛刻，这也是非常好的文档素材。 绝对不用加密哈希（No Cryptographic Hashes）： 像 MD5、SHA-1 或 SHA-256 这样的加密哈希函数，虽然分布极其均匀且极难碰撞，但计算速度太慢。在数据库每秒数千万次的 Scan 或 Join 操作中，CPU 算力极其宝贵。 首选非加密的高速哈希（Non-Cryptographic Fast Hashes）： 现代数据库（如 ClickHouse, RocksDB, StarRocks）通常采用 MurmurHash (如 MurmurHash3)、CityHash 或 xxHash。 这些哈希函数的设计目标就是快（低 CPU 周期），且具有极好的雪崩效应（Avalanche Effect，即输入改变一个 bit，输出改变一半以上的 bit），能保证位数组的分布足够均匀。 工程优化技巧（Kirsch-Mitzenmacher 优化）： 在实际代码实现中，为了节省 CPU 开销，数据库内核通常不会真的去计算 \(k\) 个完全不同的哈希函数。标准的工程做法是：只计算两个基础哈希值（比如 \(h_1(x)\) 和 \(h_2(x)\)），然后通过线性组合来模拟生成剩余的哈希值： \(g_i(x) = h_1(x) + i \cdot h_2(x) \pmod m\) （其中 \(i\) 从 \(0\) 取到 \(k-1\)）。这在不增加假阳性率的前提下，大幅降低了计算成本 哪些算子使用了布隆过滤器 1. 连接算子 (Hash Join 与 Runtime Filter) 这是现代分布式数据库（如 Doris, StarRocks, ClickHouse, Spark SQL）提升 Join 性能的杀手锏。 执行流程： 构建阶段 (Build Phase)： 数据库读取小表（Build 端）的数据，将其拉取到内存中构建 Hash 表。与此同时，顺手把这些 Join Key 喂给一个布隆过滤器，生成一个很小的位图（Bitmap）。 下推传递 (Pushdown)： 优化器将这个布隆过滤器发送（或广播）给负责扫描大表（Probe 端）的底层 Scan 算子。 探测与过滤 (Probe & Filter)： * 大表开始扫描数据。在把数据向上层发送去进行昂贵的 Hash 计算之前，先用这个布隆过滤器过一遍。