120_breadth_vs_depth.asciidoc

Preventing Combinatorial Explosions

The terms bucket dynamically builds buckets based on your data…​ it doesn’t know up front how many buckets will be generated. While this is fine with a single aggregation, think about what can happen when one aggregation contains another aggregation, contains another aggregation, etc. The combination of unique values in each of these aggregations can lead to an explosion in the number of buckets generated.

Imagine we have a modest data set which represents movies. Each document lists the actors in that movie:

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

If we want to determine the top 10 actors and their top co-stars, that’s trivial with an aggregation:

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

This will return a list of the top ten actors, and for each actor, a list of their top five co-stars. This seems like a very modest aggregation…​ only fifty values will be returned!

However, this seemingly innocuous query can easily consume a vast amount of memory. You can visualize a terms aggregation as building a tree in memory. The "actors" aggregation will build the first level of the tree, with a bucket for every actor. Then, nested under each node in the first level, the "costars" aggregation will build a second level, with a bucket for every co- star. That means that a single movie will generate n² buckets!

TODO: graph of tree structures

To use some real numbers, imagine each movie has 10 actors on average. Each movie will then generate 10² == 100 buckets. If you have 20,000 movies, that’s roughly 2,000,000 generated buckets.

Now, remember…​ our aggregation is simply asking for the top 10 actors and their co-stars, totaling 50 values. To get the final results, we have to generate that tree of 2,000,000 buckets, sort it, and finally prune it such that only the top 10 actors are left.

At this point you should be quite distraught. Twenty thousand documents is paltry, and the aggregation is pretty tame. What if you had 200 million documents, wanted the top 100 actors and their top 20 co-stars, as well as the co-stars' co-stars?

You can appreciate how quickly combinatorial expansion can grow, making this strategy untenable. There is not enough memory in the world to support uncontrolled combinatorial explosions.

Depth-first vs Breadth-first

Elasticsearch allows you to change the collection mode of an aggregation, for exactly this situation. The strategy we outlined above — building the tree fully and then pruning — is called depth-first and it is the default. Depth-first works well for the majority of aggregations, but can fall apart in situations like above.

For these special cases, you should use an alternative collection strategy called breadth-first. This strategy works a little differently. It executes the first layer of aggregations, then performs a pruning phase before continuing.

In our example, the "actors" aggregation would be executed first. At this point, we have a single layer in the tree, but we already know who the top 10 actors are! There is no need to keep the other actors since they won’t be in the top 10 anyway.

TODO: graphs of tree

Therefore, breadth-first will prune everything except the top 10. Once pruned, it will execute the next layer of aggregations, etc. This prevents the combinatorial explosion of buckets and drastically reduces memory requirements.

To use breadth-first, simply enable it via the collect parameter:

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

1. Enable breadth_first on a per-aggregation basis.

Breadth-first should only be used when you expect more buckets to be generated than documents landing in the buckets. Breadth-first works by "caching" document data at the bucket level, then "replaying" those documents to child aggregations after the pruning phase.

The memory requirement of a breadth-first aggregation is linear to the number of documents in each bucket prior to pruning. For many aggregations, the number of documents in each bucket is very large. Think of a histogram with monthly intervals: you might have thousands or hundreds of thousands of documents per bucket. This makes breadth-first a bad choice, and is why depth-first is default.

But for the actor example — situations where you generate a large number of buckets but each bucket has relatively few documents — breadth-first is much more memory efficient, and allows you to build aggregations that would otherwise fail.