Biscuit索引：PostgreSQL LIKE模式匹配的专用优化引擎

在 PostgreSQL 的生产环境中，LIKE和ILIKE模式匹配查询一直是性能优化的痛点。当查询包含前导通配符%时，传统的 B-tree 索引完全失效，而pg_trgm扩展虽然能提供一定加速，但其重新检查（recheck）开销在大量查询时仍显沉重。Biscuit 索引应运而生，这是一个专门为LIKE模式匹配设计的 PostgreSQL 索引访问方法（IAM），通过字符位置位图、Roaring Bitmaps 压缩和 12 项优化技术，实现了真正的 O (log n) 性能。

核心架构：字符位置位图的双向索引

Biscuit 的核心创新在于构建了两类字符位置位图，为每个字符串建立完整的正向和负向索引：

正向索引（Forward Indices）

记录字符c在位置p出现的所有记录 ID。例如字符串 "Hello" 会生成：

• H@0 → {记录 ID 集合}
• e@1 → {记录 ID 集合}
• l@2 → {记录 ID 集合}
• l@3 → {记录 ID 集合}
• o@4 → {记录 ID 集合}

负向索引（Backward Indices）

记录字符c在位置-p（从字符串末尾计数）出现的所有记录 ID：

• o@-1 → {记录 ID 集合}（最后一个字符）
• l@-2 → {记录 ID 集合}（倒数第二个字符）
• l@-3 → {记录 ID 集合}
• e@-4 → {记录 ID 集合}
• H@-5 → {记录 ID 集合}

长度位图（Length Bitmaps）

为了快速过滤，Biscuit 还维护两类长度位图：

• 精确长度位图：length[5] → 所有长度为 5 的字符串
• 最小长度位图：length_ge[3] → 所有长度≥3 的字符串

这种双向索引结构使得 Biscuit 能够高效处理各种LIKE模式：

• 前缀匹配'abc%'：使用正向索引检查位置 0-2
• 后缀匹配'%xyz'：使用负向索引检查位置 - 3 到 - 1
• 子串匹配'%abc%'：检查所有位置，通过 OR 操作合并结果

12 项性能优化技术详解

Biscuit 实现了 12 项关键优化，这些优化在查询执行时自动启用：

1. 跳过通配符交集

对于模式"a_c"（下划线表示任意字符），传统方法需要检查 256 个字符在位置 1 的交集。Biscuit 直接跳过位置 1，只检查a@0和c@2。

2. 空结果早期终止

在执行位图交集时，如果中间结果为空，立即终止处理：

result = bitmap[a][0];
result &= bitmap[b][1];
if (result.empty()) return empty;  // 不处理剩余字符

3. 避免冗余位图拷贝

在位图操作中，Biscuit 尽可能进行原地操作，只在分支时才进行拷贝，减少内存分配开销。

4. 单部分模式优化

为常见模式提供快速路径：

• 精确匹配'abc'：检查位置 0-2 且长度 = 3
• 前缀匹配'abc%'：检查位置 0-2 且长度≥3
• 后缀匹配'%xyz'：检查负向位置 - 3 到 - 1
• 子串匹配'%abc%'：检查所有位置，OR 结果

5. 跳过不必要的长度操作

对于纯通配符模式，如"%%%___%%"（3 个下划线），Biscuit 直接返回length_ge[3]，无需字符检查。

6. TID 排序实现顺序堆访问

将结果 TID 按(block_number, offset)排序，将随机 I/O 转换为顺序 I/O：

• 超过 5000 个 TID 时使用基数排序
• 少于 5000 个 TID 时使用快速排序

7. 批量 TID 插入

对于位图扫描，以批次方式插入 TID：

for (i = 0; i < num_results; i += 10000) {
    tbm_add_tuples(tbm, &tids[i], batch_size, false);
}

8. 直接 Roaring 迭代

避免将位图转换为数组的中间步骤，直接使用迭代器：

roaring_uint32_iterator_t *iter = roaring_create_iterator(bitmap);
while (iter->has_value) {
    process(iter->current_value);
    roaring_advance_uint32_iterator(iter);
}

9. 阈值批量清理

删除记录时标记为 "墓碑"，当墓碑数量达到阈值（默认 1000）时批量清理：

if (tombstone_count >= 1000) {
    for each bitmap:
        bitmap &= ~tombstones;  // 批量操作
    tombstones.clear();
}

10. 聚合查询检测

对于COUNT(*)、EXISTS等聚合查询，跳过 TID 排序：

if (!scan->xs_want_itup) {
    skip_sorting = true;  // 节省排序时间
}

11. LIMIT 感知的 TID 收集

如果查询包含LIMIT子句，只收集所需数量的 TID：

if (limit_hint > 0 && collected >= limit_hint)
    break;  // 提前终止

12. 多列查询优化与谓词重排序

Biscuit 自动分析多列查询的选择性，重新排序谓词执行顺序。选择性评分公式为：

score = 1.0 / (concrete_chars + 1)
      - (underscore_count × 0.05)
      + (partition_count × 0.15)
      - (anchor_strength / 200)

优先级分为 6 个层级：

1. 0-10：精确匹配，多个下划线
2. 10-20：非 % 模式带下划线
3. 20-30：强锚定模式（前缀 / 后缀）
4. 30-40：弱锚定模式
5. 40-50：多分区模式
6. 50-60：子串模式（最低优先级）

实际部署参数与监控要点

安装与配置

-- 从源码安装
git clone https://github.com/Crystallinecore/biscuit.git
cd biscuit
make
sudo make install

-- 在数据库中启用
CREATE EXTENSION biscuit;

-- 创建Biscuit索引
CREATE INDEX idx_users_name ON users USING biscuit(name);

-- 多列索引
CREATE INDEX idx_products_search 
ON products USING biscuit(name, description, category);

支持的数据类型

Biscuit 自动转换各种类型为可搜索文本：

• 文本类型：原生支持
• 数值类型：转换为可排序字符串
• 日期 / 时间类型：转换为时间戳字符串
• 布尔类型：转换为 't'/'f'

性能基准测试

在 100 万行测试数据上的对比结果：

索引类型	创建时间	查询性能提升
pg_trgm	20,358.655 ms	基准
Biscuit	2,734.310 ms	7.5 倍

典型查询场景：

-- 单列简单模式
EXPLAIN ANALYZE
SELECT * FROM benchmark WHERE name LIKE '%abc%' LIMIT 100;

-- 多列复杂模式
EXPLAIN ANALYZE
SELECT * FROM benchmark 
WHERE name LIKE '%a%b' 
  AND description LIKE '%bc%cd%'
ORDER BY score DESC 
LIMIT 10;

-- 聚合查询
EXPLAIN ANALYZE
SELECT COUNT(*) FROM benchmark 
WHERE name LIKE 'a%l%' 
  AND category LIKE 'f%d';

监控与诊断

Biscuit 提供内置的诊断函数：

-- 检查版本
SELECT biscuit_version();

-- 查看构建信息
SELECT * FROM biscuit_build_info();

-- 检查Roaring Bitmap支持
SELECT biscuit_has_roaring();

-- 查看索引统计
SELECT biscuit_index_stats('idx_biscuit'::regclass);

诊断视图biscuit_status提供：

• 扩展版本
• CRoaring 启用状态
• 使用的位图后端
• Biscuit 索引总数
• 总磁盘索引大小

适用场景与限制

适用场景

1. 电子商务产品搜索：多字段LIKE查询
2. 日志分析：错误日志模式匹配
3. 客户支持 / CRM：工单多字段搜索
4. 代码搜索：文件名和内容模式匹配
5. 分析查询：COUNT(*)等聚合操作

技术限制

1. 不支持正则表达式：仅支持LIKE/ILIKE模式
2. 基于字节的字符串比较：不支持特定区域设置的排序规则
3. 不支持原生有序扫描：amcanorder = false
4. 内存使用较高：位图存储在内存中
5. 写入性能权衡：INSERT 类似 B-tree，UPDATE 需要两次操作

与 pg_trgm 的对比

特性	Biscuit	pg_trgm (GIN)
通配符模式	✔ 原生，精确	✔ 近似
重新检查开销	✔ 无（确定性）	✗ 总是需要
多列支持	✔ 优化	⚠️ 通过 btree_gist
聚合查询	✔ 优化	✗ 相同成本
ORDER BY + LIMIT	✔ 表现良好	✔ 有序扫描
正则表达式支持	✗ 否	✔ 是
相似性搜索	✗ 否	✔ 是
ILIKE 支持	✔ 完整	✔ 原生

生产环境部署建议

内存管理

Biscuit 索引主要存储在内存中，建议：

• 监控shared_buffers使用情况
• 定期使用REINDEX重建索引
• 对于大型数据集，考虑分区策略

写入性能优化

• 批量插入：使用COPY命令而非单条INSERT
• 更新策略：避免频繁更新索引列
• 删除处理：利用墓碑批量清理机制

查询优化配置

虽然 Biscuit 自动优化，但可以：

1. 确保统计信息最新：定期运行ANALYZE
2. 监控查询计划：使用EXPLAIN ANALYZE
3. 调整工作内存：适当增加work_mem

故障排除

启用 PostgreSQL 调试日志：

SET client_min_messages = DEBUG1;
SET log_min_messages = DEBUG1;

-- 运行查询查看Biscuit内部日志
SELECT * FROM test WHERE name LIKE '%pattern%';

架构演进与未来方向

Biscuit 的当前架构已经相当成熟，但仍有改进空间：

短期改进

1. 实现amcanorder支持：提供原生有序扫描
2. 统计信息收集：改进成本估计
3. 更多数据类型支持：JSON、数组等

长期愿景

1. 并行索引构建：利用多核 CPU
2. 索引压缩选项：提供更多压缩策略
3. 自适应优化：根据工作负载动态调整

结论

Biscuit 索引代表了 PostgreSQL 模式匹配优化的一个重要里程碑。通过字符位置位图、Roaring Bitmaps 压缩和 12 项优化技术，它解决了LIKE查询的核心性能问题。虽然存在内存使用较高和不支持正则表达式等限制，但在通配符模式匹配场景下，其性能优势是显著的。

对于需要高效LIKE查询的生产系统，Biscuit 提供了一个值得考虑的解决方案。特别是在电子商务搜索、日志分析和客户支持等场景中，其多列优化和消除重新检查开销的特性，能够带来实质性的性能提升。

关键决策点：

• 如果主要使用LIKE/ILIKE通配符查询 → 选择 Biscuit
• 如果需要正则表达式或相似性搜索 → 选择 pg_trgm
• 如果内存充足且查询密集 → Biscuit 优势明显
• 如果写入频繁且内存受限 → 需要谨慎评估

Biscuit 的出现，让 PostgreSQL 在模式匹配领域拥有了更专业的工具，为开发者在性能与功能之间提供了新的平衡点。

---

资料来源：

1. GitHub: CrystallineCore/Biscuit - 官方项目文档
2. Medium: Performance Optimisation for Wildcards Search in Postgres - 性能优化背景