一些常见的搜索查询树优化方法

搜索引擎服务收到一个Query后,一般引擎这边是这么搞得,解析语法,生成后缀表达式,即查询搜索树(Search Tree)。搜索查询树负责求交、求并和过滤。所以这个地方也是性能关键点。所以在解析语法后,一般要做查询搜索树优化,减少求交,求并和过滤操作的次数,以此来提高搜索服务的QPS和查询Latency。

因为同事在负责新实时索引的性能优化,我正好负责将全量索引格式迁移到新实时索引上面,即实时索引的代码即支持全量索引也支持实时索引,减少运维和代码维护成本。我在查阅代码的同事,顺便与同事沟通了一些优化方法,进入全量索引代码里发现老的全量索引里已经有一些优化方法了,这些方法应该是市面上常见的方法,多数人也是应该知道的,这里记录下吧。主流优化操作主要包括以下四种:

全AND操作

如果父子节点都是AND,则可以合并,如(A & B)& (C & D),优化后为 A & B & C & D ,能提早发现交为空,并退出,如下图所示。

优化后为:

全OR操作

如果父子节点都是OR,则可以合并。如 (A | B)| (C | D),优化后为 A | B | C | D,能提早发现为满并退出。如下图所示:

优化后为:

将子节点的OR上提

如 (A | B) & (C &D),优化后为 A |(B & C | D),查找次数减少。

优化后为:

按照Doc数量排序

如 A & B & C,可以按照Doc数量排序后查询,Sum(A) < Sum(B) < Sum(C),则A & B & C可以尽早发现为空并退出。

当然查询搜索树优化不止这么些方法,比如之前就知道可以使用WAND提升长Query的检索速度,很久没看了,细节记不清了,就不说了。以后需要的时候再研究下。