ApproxJoin: Approximate Distributed Joins
ApproxJoin: Approximate Distributed Joins
复制标题
DOI：
10.1145/3267809.3267834
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
D. Quoc;Istemi Ekin Akkus;Pramod Bhatotia;Spyros Blanas;Ruichuan Chen;C. Fetzer;T. Strufe
中科院分区：
文献类型：
--
作者：
D. Quoc;Istemi Ekin Akkus;Pramod Bhatotia;Spyros Blanas;Ruichuan Chen;C. Fetzer;T. Strufe
分布式连接是并行处理海量数据集的基本操作。不幸的是，即使并行完成，计算此类数据集的等连接也是非常消耗资源的。考虑到这一成本，等连接运算符成为使用近似技术进行优化的自然候选者，该技术允许用户以准确性换取延迟。然而，找到正确的连接近似技术是一项具有挑战性的任务。特别是采样不能直接用于连接；天真地对数据集样本执行联接不会保留查询结果的统计属性。为了解决这个问题，我们引入了 ApproxJoin。我们将布隆过滤器草图和分层采样与新运算符中的连接计算交织在一起，该运算符保留了连接输出上聚合的统计属性。 ApproxJoin 利用布隆过滤器来避免在网络中混洗不可连接的数据项，然后应用分层采样来获取连接输出的代表性样本。我们在 Apache Spark 中实现了 ApproxJoin，并使用微基准和实际工作负载对其进行了评估。我们的评估表明，ApproxJoin 可以很好地扩展并显着减少数据移动，而不会牺牲最终结果准确性的严格误差范围。在相同的采样率下，ApproxJoin 比未经修改的基于 Spark 的连接实现了高达 9 倍的加速。此外，加速还伴随着洗牌数据量的显着减少，比未经修改的基于 Spark 的连接减少了 82 倍。
A distributed join is a fundamental operation for processing massive datasets in parallel. Unfortunately, computing an equi-join over such datasets is very resource-intensive, even when done in parallel. Given this cost, the equi-join operator becomes a natural candidate for optimization using approximation techniques, which allow users to trade accuracy for latency. Finding the right approximation technique for joins, however, is a challenging task. Sampling, in particular, cannot be directly used in joins; naïvely performing a join over a sample of the dataset will not preserve statistical properties of the query result. To address this problem, we introduce ApproxJoin. We interweave Bloom filter sketching and stratified sampling with the join computation in a new operator that preserves statistical properties of an aggregation over the join output. ApproxJoin leverages Bloom filters to avoid shuffling non-joinable data items around the network, and then applies stratified sampling to obtain a representative sample of the join output. We implemented ApproxJoin in Apache Spark, and evaluated it using microbenchmarks and real-world workloads. Our evaluation shows that ApproxJoin scales well and significantly reduces data movement, without sacrificing tight error bounds on the accuracy of the final results. ApproxJoin achieves a speedup of up to 9x over unmodified Spark-based joins with the same sampling ratio. Furthermore, the speedup is accompanied by a significant reduction in the shuffled data volume, which is up to 82x less than unmodified Spark-based joins.