原创

Elasticsearch基础(二三)——聚合分析:遍历算法

本章,我们来讲下Elasticsearch在进行聚合分析时,所用到的两种遍历算法:深度优先遍历广度优先遍历。深度优先遍历和广度优先遍历其实是图的两种基本遍历算法。

一、深度优先

假设我们现在有一些关于电影的数据集,每条doc里面会有一个数组类型的字段,存储着表演该电影的所有演员名字:

{
  "actors" : [
    "Fred Jones",
    "Mary Jane",
    "Elizabeth Worthing"
  ]
}

如果我们想要先按演员分组,找到出演影片最多的10个演员;然后,对于每个子组再找出与当前演员合作最多的5个演员,那么可以像下面这样构造请求:

{
  "aggs" : {
    "actors" : {
      "terms" : {
         "field" : "actors",
         "size" :  10
      },
      "aggs" : {
        "costars" : {
          "terms" : {
            "field" : "actors",
            "size" :  5
          }
        }
      }
    }
  }
}

但是, 这个看上去简单的查询可以轻而易举地消耗大量内存,我们可以通过在内存中构建一个树来查看这个 terms 聚合。 actors 聚合会构建树的第一层,每个演员都有一个桶。然后,内套在第一层的每个节点之下, costar 聚合会构建第二层,每个联合出演一个桶,这意味着每部影片会生成 nxn 个桶!



上述聚合分析,只是希望得到前10位演员和与他们联合出演者,但是为了得到最终的结果,我们创建了一个有nxn桶的树,然后对其排序,取 top10。如果我们有 2 亿doc,想要得到前 100 位演员以及与他们合作最多的 20 位演员,可以推测,聚合出来的分组数非常大。上述这种遍历方式就是深度优先。

二、广度优先

Elasticsearch 允许我们改变聚合的 集合模式 ,就是为了应对这种状况。 我们之前展示的策略叫做 深度优先 ,它是默认设置, 先构建完整的树,然后修剪无用节点。 深度优先 的方式对于大多数聚合都能正常工作,但对于上述情形就不太适用。

为了应对这些特殊的应用场景,我们应该使用另一种集合策略叫做 广度优先 。这种策略的工作方式有些不同,它先执行第一层聚合, 然后先做修剪,再执行下一层聚合。

在我们的示例中, actors 聚合会首先执行,在这个时候,我们的树只有一层,但我们已经知道了前 10 位的演员,这就没有必要保留其他的演员信息,因为它们无论如何都不会出现在前十位中。





要使用广度优先,只需简单的通过参数 collect_mode 开启:

{
  "aggs" : {
    "actors" : {
      "terms" : {
         "field" : "actors",
         "size" : 10,
         "collect_mode" : "breadth_first" 
      },
      "aggs" : {
        "costars" : {
          "terms" : {
            "field" : "actors",
            "size" :  5
          }
        }
      }
    }
  }
}

广度优先仅仅适用于每个组的聚合数量远小于当前总组数的情况,因为广度优先会在内存中缓存裁剪后的每个组的所有数据,如果裁剪后的每个组下的数据量非常大,广度优先就不是一个好的选择,这也是为什么深度优先作为默认策略的原因。

三、总结

本章,我们介绍了Elasticsearch的聚合分析遍历策略,主要有深度优先遍历和广度优先遍历,默认采用深度优先遍历。如果读者对这两种算法感兴趣,可以进一步阅读我的传统算法系列

正文到此结束
本文目录