Aggregations: Add children aggregation

Add `children` bucket aggregation that is able to map buckets between parent types and child types based on top of the parent/child support. It is the equivalent of the has_child filter/query in the query dsl.

Example request:
```json
GET /stack/question/_search?search_type=count
{
  "aggs": {
    "top-tags": {
      "terms": {
        "field": "tags",
        "size": 10
      },
      "aggs": {
        "to-answers": {
          "children": {
            "child_type" : "answer"
          },
          "aggs": {
            "top-names": {
              "terms": {
                "field": "owner_display_name",
                "size": 10
              }
            }
          }
        }
      }
    }
  }
}
```

Example response:
```json
{
   "took": 90,
   "timed_out": false,
   "_shards": {
      "total": 5,
      "successful": 5,
      "failed": 0
   },
   "hits": {
      "total": 175275,
      "max_score": 0,
      "hits": []
   },
   "aggregations": {
      "top-tags": {
         "buckets": [
            {
               "key": "windows-7",
               "doc_count": 25365,
               "to-answers": {
                  "doc_count": 36004,
                  "top-names": {
                     "buckets": [
                        {
                           "key": "molly7244",
                           "doc_count": 274
                        },
                        {
                           "key": "chris",
                           "doc_count": 19
                        },
                        {
                           "key": "david",
                           "doc_count": 14
                        },
                        {
                           "key": "dan",
                           "doc_count": 12
                        },
                        {
                           "key": "james",
                           "doc_count": 7
                        },
                        {
                           "key": "b",
                           "doc_count": 5
                        },
                        {
                           "key": "alex",
                           "doc_count": 4
                        },
                        {
                           "key": "peter",
                           "doc_count": 4
                        },
                        {
                           "key": "s",
                           "doc_count": 4
                        },
                        {
                           "key": "cody",
                           "doc_count": 3
                        }
                     ]
                  }
               }
            },
            {
               "key": "linux",
               "doc_count": 18342,
               "to-answers": {
                  "doc_count": 6655,
                  "top-names": {
                     "buckets": [
                        {
                           "key": "abrams",
                           "doc_count": 25
                        },
                        {
                           "key": "ignacio",
                           "doc_count": 25
                        },
                        {
                           "key": "vazquez",
                           "doc_count": 25
                        },
                        {
                           "key": "chris",
                           "doc_count": 9
                        },
                        {
                           "key": "michael",
                           "doc_count": 7
                        },
                        {
                           "key": "basile",
                           "doc_count": 6
                        },
                        {
                           "key": "david",
                           "doc_count": 6
                        },
                        {
                           "key": "alex",
                           "doc_count": 4
                        },
                        {
                           "key": "botykai",
                           "doc_count": 3
                        },
                        {
                           "key": "paul",
                           "doc_count": 3
                        }
                     ]
                  }
               }
            },
            {
               "key": "windows",
               "doc_count": 18119,
               "to-answers": {
                  "doc_count": 24051,
                  "top-names": {
                     "buckets": [
                        {
                           "key": "molly7244",
                           "doc_count": 265
                        },
                        {
                           "key": "david",
                           "doc_count": 27
                        },
                        {
                           "key": "chris",
                           "doc_count": 26
                        },
                        {
                           "key": "diago",
                           "doc_count": 9
                        },
                        {
                           "key": "john",
                           "doc_count": 7
                        },
                        {
                           "key": "paxdiablo",
                           "doc_count": 7
                        },
                        {
                           "key": "ben",
                           "doc_count": 6
                        },
                        {
                           "key": "mark",
                           "doc_count": 6
                        },
                        {
                           "key": "adam",
                           "doc_count": 5
                        },
                        {
                           "key": "c",
                           "doc_count": 5
                        }
                     ]
                  }
               }
            },
            {
               "key": "osx",
               "doc_count": 10971,
               "to-answers": {
                  "doc_count": 5902,
                  "top-names": {
                     "buckets": [
                        {
                           "key": "diago",
                           "doc_count": 4
                        },
                        {
                           "key": "albert",
                           "doc_count": 3
                        },
                        {
                           "key": "asmus",
                           "doc_count": 3
                        },
                        {
                           "key": "molly7244",
                           "doc_count": 3
                        },
                        {
                           "key": "aaron",
                           "doc_count": 2
                        },
                        {
                           "key": "abizern",
                           "doc_count": 2
                        },
                        {
                           "key": "adam",
                           "doc_count": 2
                        },
                        {
                           "key": "duskwuff",
                           "doc_count": 2
                        },
                        {
                           "key": "johnsyweb",
                           "doc_count": 2
                        },
                        {
                           "key": "mark",
                           "doc_count": 2
                        }
                     ]
                  }
               }
            },
            {
               "key": "ubuntu",
               "doc_count": 8743,
               "to-answers": {
                  "doc_count": 8784,
                  "top-names": {
                     "buckets": [
                        {
                           "key": "ignacio",
                           "doc_count": 9
                        },
                        {
                           "key": "abrams",
                           "doc_count": 8
                        },
                        {
                           "key": "molly7244",
                           "doc_count": 8
                        },
                        {
                           "key": "david",
                           "doc_count": 7
                        },
                        {
                           "key": "pate",
                           "doc_count": 6
                        },
                        {
                           "key": "roger",
                           "doc_count": 6
                        },
                        {
                           "key": "chris",
                           "doc_count": 5
                        },
                        {
                           "key": "vazquez",
                           "doc_count": 5
                        },
                        {
                           "key": "paul",
                           "doc_count": 3
                        },
                        {
                           "key": "rob",
                           "doc_count": 3
                        }
                     ]
                  }
               }
            },
            {
               "key": "windows-xp",
               "doc_count": 7517,
               "to-answers": {
                  "doc_count": 13610,
                  "top-names": {
                     "buckets": [
                        {
                           "key": "molly7244",
                           "doc_count": 232
                        },
                        {
                           "key": "chris",
                           "doc_count": 9
                        },
                        {
                           "key": "john",
                           "doc_count": 9
                        },
                        {
                           "key": "david",
                           "doc_count": 8
                        },
                        {
                           "key": "dave",
                           "doc_count": 5
                        },
                        {
                           "key": "b",
                           "doc_count": 4
                        },
                        {
                           "key": "bart",
                           "doc_count": 4
                        },
                        {
                           "key": "joeqwerty",
                           "doc_count": 4
                        },
                        {
                           "key": "mike",
                           "doc_count": 4
                        },
                        {
                           "key": "s",
                           "doc_count": 4
                        }
                     ]
                  }
               }
            },
            {
               "key": "networking",
               "doc_count": 6739,
               "to-answers": {
                  "doc_count": 2076,
                  "top-names": {
                     "buckets": [
                        {
                           "key": "molly7244",
                           "doc_count": 6
                        },
                        {
                           "key": "alnitak",
                           "doc_count": 5
                        },
                        {
                           "key": "chris",
                           "doc_count": 3
                        },
                        {
                           "key": "albin",
                           "doc_count": 2
                        },
                        {
                           "key": "brian",
                           "doc_count": 2
                        },
                        {
                           "key": "everett",
                           "doc_count": 2
                        },
                        {
                           "key": "fishdump",
                           "doc_count": 2
                        },
                        {
                           "key": "m",
                           "doc_count": 2
                        },
                        {
                           "key": "mike",
                           "doc_count": 2
                        },
                        {
                           "key": "p",
                           "doc_count": 2
                        }
                     ]
                  }
               }
            },
            {
               "key": "mac",
               "doc_count": 5590,
               "to-answers": {
                  "doc_count": 999,
                  "top-names": {
                     "buckets": [
                        {
                           "key": "abrams",
                           "doc_count": 2
                        },
                        {
                           "key": "ignacio",
                           "doc_count": 2
                        },
                        {
                           "key": "vazquez",
                           "doc_count": 2
                        },
                        {
                           "key": "adam",
                           "doc_count": 1
                        },
                        {
                           "key": "anon",
                           "doc_count": 1
                        },
                        {
                           "key": "aravindhanarvi",
                           "doc_count": 1
                        },
                        {
                           "key": "arkaaito",
                           "doc_count": 1
                        },
                        {
                           "key": "ballard",
                           "doc_count": 1
                        },
                        {
                           "key": "bart",
                           "doc_count": 1
                        },
                        {
                           "key": "ben",
                           "doc_count": 1
                        }
                     ]
                  }
               }
            },
            {
               "key": "wireless-networking",
               "doc_count": 4409,
               "to-answers": {
                  "doc_count": 6497,
                  "top-names": {
                     "buckets": [
                        {
                           "key": "molly7244",
                           "doc_count": 61
                        },
                        {
                           "key": "chris",
                           "doc_count": 5
                        },
                        {
                           "key": "mike",
                           "doc_count": 5
                        },
                        {
                           "key": "tom",
                           "doc_count": 5
                        },
                        {
                           "key": "bart",
                           "doc_count": 4
                        },
                        {
                           "key": "user48838",
                           "doc_count": 4
                        },
                        {
                           "key": "alex",
                           "doc_count": 2
                        },
                        {
                           "key": "anon31097",
                           "doc_count": 2
                        },
                        {
                           "key": "joeqwerty",
                           "doc_count": 2
                        },
                        {
                           "key": "kevin",
                           "doc_count": 2
                        }
                     ]
                  }
               }
            },
            {
               "key": "windows-8",
               "doc_count": 3601,
               "to-answers": {
                  "doc_count": 4263,
                  "top-names": {
                     "buckets": [
                        {
                           "key": "molly7244",
                           "doc_count": 3
                        },
                        {
                           "key": "msft",
                           "doc_count": 2
                        },
                        {
                           "key": "user172132",
                           "doc_count": 2
                        },
                        {
                           "key": "aj",
                           "doc_count": 1
                        },
                        {
                           "key": "algorithms",
                           "doc_count": 1
                        },
                        {
                           "key": "andersson",
                           "doc_count": 1
                        },
                        {
                           "key": "ashafiee",
                           "doc_count": 1
                        },
                        {
                           "key": "balakrishnan",
                           "doc_count": 1
                        },
                        {
                           "key": "bobby",
                           "doc_count": 1
                        },
                        {
                           "key": "brockschmidt",
                           "doc_count": 1
                        }
                     ]
                  }
               }
            }
         ]
      }
   }
}
```
I think has a significant impact when we replay the child docs later on?
Instead of checking is a bit is set we need to check is a key is set in a
map.


On 18 August 2014 15:00, Adrien Grand <notifications@github.com> wrote:

> In
> src/main/java/org/elasticsearch/search/aggregations/bucket/children/ParentToChildrenAggregator.java:
>
> > +// aggregation, for this reason that collector can't be used
> > +public class ParentToChildrenAggregator extends SingleBucketAggregator implements ReaderContextAware {
> > +
> > +    private final String parentType;
> > +    private final Filter childFilter;
> > +    private final Filter parentFilter;
> > +    private final ValuesSource.Bytes.WithOrdinals.ParentChild valuesSource;
> > +
> > +    // Maybe use PagedGrowableWriter? This will be less wasteful than LongArray, but then we don't have the reuse feature of BigArrays.
> > +    // Also if we know the highest possible value that a parent agg will create then we store multiple values into one slot
> > +    private final LongArray parentOrdToBuckets;
> > +
> > +    // Only pay the extra storage price if the a parentOrd has multiple buckets
> > +    // Most of the times a parent doesn't have multiple buckets, since there is only one document per parent ord,
> > +    // only in the case of terms agg if a parent doc has multiple terms per field this is needed:
> > +    private final LongBitSet parentOrdWithMultipleBuckets;
>
> Maybe we should get rid of that bit set and just rely on the fact that the
> long[] in parentOrdToOtherBuckets is not null?
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/elasticsearch/elasticsearch/pull/6936/files#r16351155>
> .
>



-- 
Met vriendelijke groet,

Martijn van Groningen