Generalized Measure-Biased Sampling and Priority Sampling
Zhao Chang, Feifei Li, Yulong Shen · IEEE Transactions on Knowledge and Data Engineering · 2023
Query with aggregates is one of the most important classes of ad-hoc queries. Since query response time is critical in many scenarios, small errors are usually tolerable for query processing. In this work, we adopt sampling to provide fast approximate answers to distribution query and subset-sum query. On the one hand, uniform sampler is sub-optimal. On the other hand, both measure-biased sampler and priority sampler need to create a sample for each measure column. It leads to expensive storage cost, when there are dozens or hundreds of measure columns in the table. To address this issue, we generalize both measure-biased sampler and priority sampler, which can compress the samples but still provide fast approximate answers to both distribution query and subset-sum query within a user-specified error bound. Besides, we establish the relationship between measure-biased sampler and priority sampler by constructing a measure-biased sample from a priority sample. We also extend the priority sampler to support multiple types of aggregates for arbitrary subset. In the extensive experimental evaluation, our generalized samplers achieve a remarkable improvement over the original samplers in terms of the error metrics.