  Interactive analytics increasingly involves querying for quantiles over
sub-populations of high cardinality datasets. Data processing engines such as
Druid and Spark use mergeable summaries to estimate quantiles, but summary
merge times can be a bottleneck during aggregation. We show how a compact and
efficiently mergeable quantile sketch can support aggregation workloads. This
data structure, which we refer to as the moments sketch, operates with a small
memory footprint (200 bytes) and computationally efficient (50ns) merges by
tracking only a set of summary statistics, notably the sample moments. We
demonstrate how we can efficiently and practically estimate quantiles using the
method of moments and the maximum entropy principle, and show how the use of a
cascade further improves query time for threshold predicates. Empirical
evaluation on real-world datasets shows that the moments sketch can achieve
less than 1 percent error with 15 times less merge overhead than comparable
summaries, improving end query time in the MacroBase engine by up to 7 times
and the Druid engine by up to 60 times.
