Accelerate Distributed Joins with Predicate Transfer
Open Access
- 17 June 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (3) , 1-27
Abstract
Join is one of the most critical operators in query processing. One effective way to optimize multi-join performance is to pre-filter rows that do not contribute to the query output. Techniques that reflect this principle include predicate pushdown, semi-join, Yannakakis algorithm, Bloom join, predicate transfer, etc. Among these, predicate transfer is the state-of-the-art pre-filtering technique that removes most non-contributing rows through a series of Bloom filters thereby delivering significant performance improvement. However, the existing predicate transfer technique has several limitations. First, the current algorithm works only on a single-threaded system while real analytics databases for large workloads are typically distributed across multiple nodes. Second, some predicate transfer steps may not filter out any rows in the destination table thus introduces performance overhead with no speedup. This issue is exacerbated in a distributed environment, where unnecessary predicate transfers lead to extra network latency and traffic. In this paper, we aim to address both limitations. First, we explore the design space of distributed predicate transfer and propose cost-based adaptive execution to maximize the performance for each individual transfer step. Second, we develop a pruning algorithm to effectively remove unnecessary transfers that do not have positive contribution to performance. We implement both techniques and evaluate on a distributed analytics query engine. Results on standard OLAP benchmarks including TPC-H and DSB with a scale factor up to 400 show that distributed predicate transfer can improve the query performance by over 3×, and reduce the amount of data exchange by over 2.7×.Keywords
This publication has 36 references indexed in Scilit:
- FlexpushdownDB: rethinking computation pushdown for cloud OLAP DBMSsThe VLDB Journal, 2024
- Optimizing Bloom Filter: Challenges, Solutions, and ComparisonsIEEE Communications Surveys & Tutorials, 2018
- Flow-Join: Adaptive skew handling for distributed joins over high-speed networks2016
- Theory and Practice of Bloom Filters for Distributed SystemsIEEE Communications Surveys & Tutorials, 2011
- Improving hash join performance through prefetchingACM Transactions on Database Systems, 2007
- Using parallel semi-join reduction to minimize distributed query response time2002
- Data placement in shared-nothing parallel database systemsThe VLDB Journal, 1997
- A graph theoretical approach to determine a join reducer sequence in distributed query processingIEEE Transactions on Knowledge and Data Engineering, 1994
- Combining joint and semi-join operations for distributed query processingIEEE Transactions on Knowledge and Data Engineering, 1993
- Improvement Algorithms for Semijoin Query Processing Programs in Distributed Database SystemsIEEE Transactions on Computers, 1984