TSDB indices could speed up cardinality aggregations on dimension fields

[jpountz]

Description

The Kubernetes integration comes with dashboards where some of the slower visualizations are powered by queries that have this shape:

{
  "size": 0,
  "query": {
    "bool": {
      "filter": [
        { /* range query on @timestamp */ },
        { /* match query on data_stream.dataset (constant_keyword), which rewrites to a match_all or match_none */}
      ]
    }
  },
  "aggs": {
    "date_histo": {
      "date_histogram": {
        "field": "@timestamp",
        "fixed_interval": /* some interval */
      },
      "aggs": {
        "card": {
          "cardinality": {
            "field": /* a field that is a dimension */
          }
        }
      }
    }
  }
}

Cardinality aggregations on dimension fields have an interesting property: all documents that have the same TSID are guaranteed to also have the same value for the dimension field. This means that we only need to visit one document per TSID to be able to compute the cardinality of the dimension field across the entire set of matching documents.

And since TSDB indices are sorted by TSID, it's easy to skip documents that would have the same TSID. For instance say you have a top-level cardinality aggregation and just collected a document. You can look up the ordinal of the TSID field and then do an exponential search to find the first document that has a different TSID. All documents up to this document can be skipped safely. Assuming that the number of unique TSIDs is much lower than the number of documents that match the query, this would yield a massive speedup.

Lucene already has a mechanism to enable this via the LeafCollector#competitiveIterator API, which allows collectors to tell the query to skip documents that are not interesting to them.

We could implement this LeafCollector#competitiveIterator API on cardinality aggregations, and this should cover all cases when the cardinality aggregation is collected directly via the IndexSearcher, ie. for either top-level cardinality aggregations or second-level cardinality aggregations where the filter-by-filter execution mode is applicable, such as the above query.

[elasticmachine]

Pinging @elastic/es-perf (Team:Performance)

[elasticmachine]

Pinging @elastic/es-analytics-geo (Team:Analytics)

[elasticsearchmachine]

Pinging @elastic/es-storage-engine (Team:StorageEngine)