Elasticsearch聚合操作的时间复杂度是O(n)吗？

Elasticsearch | 作者 napoay | 发布于2017年06月27日 | 阅读数：8342

Elasticsearch聚合会过滤所有文档吗？同一个聚合操作，分别在500万、1000万、1500万、2000万、2500万数据量下做测试，响应时间随数据逐渐递增，而match查询并不会随数据量增加而增加，基本上是水平的，而聚合是线性递增的。

4 个回复

kennywu76 - Wood

赞同来自: kwan 、rockybean 、medcl 、wkdx 、byx313 、FFFrp 、cccthought 更多 »

terms聚合的时间复杂度不是一个简单的O能解释的，中间有好几个执行步骤，每个步骤的耗时也有多个决定因素。

最简单的单层terms聚合大致是下面这样一个执行步骤:

为要聚合的字段构造Global Ordinals。 (什么是Global Ordinals参考global-ordinals. )，这个过程的速度不是单纯和文档数量有关系，更多的是取决于索引有多少个段文件，以及字段的不同唯一值的数量(cardinality)。段文件的数量和磁盘IO能力决定了多快能将这些数据读入内存，而字段唯一值的多少决定了需要在内存里生成多少个分桶，唯一值越多，分桶占用的内存越高。
根据match查询的结果，也就是得到的文档ID集合，借助统计字段的doc values，拿到统计字段的值集合。
将统计字段的值集合映射到为global ordinals构建的分桶里。
统计各个分桶里的值个数.
根据聚合设置的size，返回top size的分桶数据。

海量数据场景下，对Terms aggregation性能影响最大的还是对应字段的唯一值的多寡。冷执行的情况下，由于需要读取各个segments的doc values，如果segments非常多，构造global ordinals可能耗时非常长。对于不再更新的索引，将其force merge成一个segment，可以免去global ordinals的构造过程，从而极大提速聚合速度。对于一直在更新的索引，可以延长索引refresh周期，提高global ordinals缓存的有效期。在查询聚合性能要求高于写入性能的场景下，也可以利用eager_global_ordinals来将构建时间移到索引阶段。

如果聚合的场景是从大量的数据中过滤出少量数据进行聚合(百万级)，可以在执行参数里加入execution_hint: map，直接在结果集上用map的方式进行计算，对比默认的global ordinals的计算方式速度可能会高几倍到几十倍。

如果是多层聚合，则又要复杂得多，bucket构建过程分为depth first和breath first两种，建议仔细读一下相关文档，结合数据特性进行测试分析后，选用合适的执行方式。

总结来说对于terms aggregation，ES提供了多种执行方式，各种方式在内存使用方面，速度方面各有取舍。通常来说，默认的执行方式多数场景下都没有什么问题，只有一些比较极端的场景下，ES不会非常智能的自动选择最佳执行路径，需要使用者对数据和ES本身有一定熟悉程度，灵活选择。

medcl - 今晚打老虎。

赞同来自: cccthought

海量数据如果确实要做聚合，在 @kennywu76 建议的基础上，还可以考虑将单次term聚合请求分成多次来执行：
https://www.elastic.co/guide/e ... tions

rockybean - Elastic Certified Engineer, ElasticStack Fans，公众号：ElasticTalk

从你的观察上就可以推断match查询的算法时间复杂度是O(1)的，也就是常数级别的，因为它是使用倒排索引来匹配的。而聚合的时间复杂度是O(n)的，也就是会随数据规模增长而增长，具体原因得去看这个聚合操作的实现了

napoay

对其中的一个字段host做terms聚合：

{

    "size": 0,

    "aggs": {

        "host_group": {

            "terms": {

                "field": "host"

            }

        }

    }

}

那么terms聚合的时间复杂度是O(n) 的吗？terms聚合的内部实现是什么的？

要回复问题请先登录或注册

Elasticsearch聚合操作的时间复杂度是O(n)吗？

4 个回复

发起人

相关问题

问题状态

Elasticsearch聚合操作的时间复杂度是O(n)吗？

与内容相关的链接

4 个回复

发起人

相关问题

问题状态