  Many big-data clusters store data in large partitions that support access at
a coarse, partition-level granularity. As a result, approximate query
processing via row-level sampling is inefficient, often requiring reads of many
partitions. In this work, we seek to answer queries quickly and approximately
by reading a subset of the data partitions and combining partial answers in a
weighted manner without modifying the data layout. We illustrate how to
efficiently perform this query processing using a set of pre-computed summary
statistics, which inform the choice of partitions and weights. We develop novel
means of using the statistics to assess the similarity and importance of
partitions. Our experiments on several datasets and data layouts demonstrate
that to achieve the same relative error compared to uniform partition sampling,
our techniques offer from 2.7$\times$ to $70\times$ reduction in the number of
partitions read, and the statistics stored per partition require fewer than
100KB.
