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

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

kennywu76 - wood@Ctrip

赞同来自: kwan rockybean medcl

terms聚合的时间复杂度不是一个简单的O能解释的,中间有好几个执行步骤,每个步骤的耗时也有多个决定因素。
 
最简单的单层terms聚合大致是下面这样一个执行步骤:
  1. 为要聚合的字段构造Global Ordinals。 (什么是Global Ordinals参考global-ordinals. ), 这个过程的速度不是单纯和文档数量有关系,更多的是取决于索引有多少个段文件,以及字段的不同唯一值的数量(cardinality)。  段文件的数量和磁盘IO能力决定了多快能将这些数据读入内存,而字段唯一值的多少决定了需要在内存里生成多少个分桶,唯一值越多,分桶占用的内存越高。
  2. 根据match查询的结果,也就是得到的文档ID集合,借助统计字段的doc values,拿到统计字段的值集合。
  3. 将统计字段的值集合映射到为global ordinals构建的分桶里。
  4. 统计各个分桶里的值个数.
  5. 根据聚合设置的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本身有一定熟悉程度,灵活选择。

rockybean - Elastic Certified Engineer, ElasticStack Fans,公众号:ElasticTalk,慕课网《ElasticStack 从入门到实践》讲师

赞同来自:

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

napoay - 中科院硕士,《从Lucene到Elasticsearch:全文检索实战》一书作者

赞同来自:

对其中的一个字段host做terms聚合:
{
"size": 0,
"aggs": {
"host_group": {
"terms": {
"field": "host"
}
}
}
}
那么terms聚合的时间复杂度是O(n) 的吗?terms聚合的内部实现是什么的?

medcl - Elastic 🇨🇳 !

赞同来自:

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

要回复问题请先登录注册