Manticore Search 中直方图在大型IN查询中的性能优化

在数据库查询优化领域，直方图(Histogram)是一种常用的统计信息，用于帮助查询优化器更准确地估计查询条件的选择性。Manticore Search 作为一个高性能的全文搜索引擎，在处理包含大量值的IN查询时，其直方图估算机制遇到了性能瓶颈。

问题背景

当查询中包含带有大量值的IN条件时，例如WHERE id IN (1,2,3,...,1000)，Manticore Search 的查询优化器会使用直方图来估算这个条件的选择性。原始实现中，对于IN列表中的每个值，优化器都会从直方图的起始位置开始重新搜索对应的桶(bucket)，这种线性搜索方式在值数量很大时会导致明显的性能下降。

这种情况在启用批处理的JOIN查询中尤为明显，因为批处理通常会生成包含大量值的IN条件。

技术原理

直方图是一种将数据分布划分为多个桶的数据结构，每个桶代表一个值范围并记录该范围内值的出现频率。在查询优化阶段，优化器使用直方图来估算特定查询条件将匹配多少文档，从而选择最优的执行计划。

原始实现中的性能问题源于对每个IN值的独立处理方式。即使IN列表中的值是连续或接近的，优化器也会为每个值从头开始搜索直方图，而实际上可以利用前一个值的搜索结果来加速当前值的查找。

优化方案

针对这一问题，优化后的实现改进了直方图的搜索策略：

1. 桶重用机制：当处理IN列表中的连续值时，不再每次都从直方图起始位置开始搜索，而是尝试重用前一个值所在的桶或相邻桶。

2. 增量搜索：对于有序的IN列表，采用类似合并排序的策略，在直方图中按顺序前进，避免不必要的回溯。

3. 局部性优化：利用IN列表中值通常具有局部性的特点(相邻值往往落在相同或相近的桶中)，减少直方图遍历的开销。

性能影响

这一优化显著减少了处理大型IN查询时的CPU开销，特别是在以下场景中效果更为明显：

• 包含数百或数千个值的IN条件
• 使用批处理的JOIN查询
• 在大型数据集上执行的复杂查询

虽然这种优化不会改变查询的最终结果，但它使查询规划阶段更加高效，从而降低了整体查询延迟。

实现细节

优化后的算法大致工作流程如下：

1. 对IN列表中的值进行排序(如果尚未有序)
2. 初始化直方图搜索位置
3. 对于每个值：
   • 从当前位置开始搜索，而不是每次都从头开始
   • 如果当前值大于前一个值，则从上一个桶或下一个桶开始搜索
   • 记录当前值所在的桶位置，供下一个值使用

这种优化利用了IN列表中值的局部性原理，大幅减少了不必要的直方图遍历操作。

结论

Manticore Search 的这一优化展示了查询优化器中一个常被忽视但影响重大的性能瓶颈。通过改进直方图在处理大型IN查询时的搜索策略，显著提升了查询规划阶段的效率。这种优化对于使用大量IN条件或批处理JOIN的应用程序尤为重要，能够在不改变查询语义的情况下减少查询延迟。

对于数据库和搜索引擎开发者而言，这个案例也提醒我们，即使在成熟的系统中，查询优化器的性能优化仍然有许多值得挖掘的空间，特别是对于处理大规模数据的场景。