基于Lucene查询原理分析Elasticsearch的性能

前言

Elasticsearch是一个很火的分布式搜索系统，提供了非常强大而且易用的查询和分析能力，包括全文索引、模糊查询、多条件组合查询、地理位置查询等等，而且具有一定的分析聚合能力。因为其查询场景非常丰富，所以如果泛泛的分析其查询性能是一个非常复杂的事情，而且除了场景之外，还有很多影响因素，包括机型、参数配置、集群规模等等。本文主要是针对几种主要的查询场景，从查询原理的角度分析这个场景下的查询开销，并给出一个大概的性能数字，供大家参考。

Lucene查询原理

本节主要是一些Lucene的背景知识，了解这些知识的同学可以略过。

Lucene的数据结构和查询原理

Elasticsearch的底层是Lucene，可以说Lucene的查询性能就决定了Elasticsearch的查询性能。关于Lucene的查询原理大家可以参考以下这篇文章：

Lucene查询原理

Lucene中重要的就是它的几种数据结构，这决定了数据是如何被检索的，本文再简单描述一下几种数据结构：

1. FST：保存term字典，可以在FST上实现单Term、Term范围、Term前缀和通配符查询等。
2. 倒排链：保存了每个term对应的docId的列表，采用skipList的结构保存，用于快速跳跃。
3. BKD-Tree：BKD-Tree是一种保存多维空间点的数据结构，用于数值类型(包括空间点)的快速查找。
4. DocValues：基于docId的列式存储，由于列式存储的特点，可以有效提升排序聚合的性能。

组合条件的结果合并

了解了Lucene的数据结构和基本查询原理，我们知道：

1. 对单个词条进行查询，Lucene会读取该词条的倒排链，倒排链中是一个有序的docId列表。
2. 对字符串范围/前缀/通配符查询，Lucene会从FST中获取到符合条件的所有Term，然后就可以根据这些Term再查找倒排链，找到符合条件的doc。
3. 对数字类型进行范围查找，Lucene会通过BKD-Tree找到符合条件的docId集合，但这个集合中的docId并非有序的。

现在的问题是，如果给一个组合查询条件，Lucene怎么对各个单条件的结果进行组合，得到终结果。简化的问题就是如何求两个集合的交集和并集。

1. 对N个倒排链求交集

上面Lucene原理分析的文章中讲过，N个倒排链求交集，可以采用skipList，有效的跳过的doc。

2. 对N个倒排链求并集

处理方式一：仍然保留多个有序列表，多个有序列表的队首构成一个优先队列(小堆)，这样后续可以对整个并集进行iterator(堆顶的队首出堆，队列里下一个docID入堆)，也可以通过skipList的方式向后跳跃(各个子列表分别通过skipList跳)。这种方式适合倒排链数量比较少(N比较小)的场景。

处理方式二：倒排链如果比较多(N比较大)，采用方式一就不够划算，这时候可以直接把结果合并成一个有序的docID数组。

处理方式三：方式二中，直接保存原始的docID，如果docID非常多，很消耗内存，所以当doc数量超过一定值时(32位docID在BitSet中只需要一个bit，BitSet的大小取决于segments里的doc总数，所以可以根据doc总数和当前doc数估算是否BitSet更加划算)，会采用构造BitSet的方式，非常节约内存，而且BitSet可以非常高效的取交/并集。

3. BKD-Tree的结果怎么跟其他结果合并

通过BKD-Tree查找到的docID是无序的，所以要么先转成有序的docID数组，或者构造BitSet，然后再与其他结果合并。

查询顺序优化

如果采用多个条件进行查询，那么先查询代价比较小的，再从小结果集上进行迭代，会更优一些。Lucene中做了很多这方面的优化，在查询前会先估算每个查询的代价，再决定查询顺序。

结果排序

默认情况下，Lucene会按照Score排序，即算分后的分数值，如果指定了其他的Sort字段，就会按照指定的字段排序。那么，排序会非常影响性能吗？首先，排序并不会对所有命中的doc进行排序，而是构造一个堆，保证前(Offset+Size)个数的doc是有序的，所以排序的性能取决于(Size+Offset)和命中的文档数，另外就是读取docValues的开销。因为(Size+Offset)并不会太大，而且docValues的读取性能很高，所以排序并不会非常的影响性能。

各场景查询性能分析

上一节讲了一些查询相关的理论知识，那么本节就是理论结合实践，通过具体的一些测试数字来分析一下各个场景的性能。测试采用单机单Shard、64核机器、SSD磁盘，主要分析各个场景的计算开销，不考虑操作系统Cache的影响，测试结果仅供参考。

单Term查询

ES中建立一个Index，一个shard，无replica。有1000万行数据，每行只有几个标签和一个ID，现在将这些数据写入这个Index中。其中Tag1这个标签只有a和b两个值，现在要从1000万行中找到一条Tag1=a的数据(约500万)。给出以下查询，那么它耗时如何呢：
请求：
{
  "query": {
    "constant_score": {
      "filter": {
        "term": {
          "Tag1": "a"
        }
      }
    }
  },
  "size": 1
}'
响应：
{"took":233,"timed_out":false,"_shards":{"total":1,"successful":1,"skipped":0,"failed":0},"hits":{"total":5184867,"max_score":1.0,"hits":...}