<p>Improving the performance of data systems for join operations has long been a critical challenge. Recently, substantial attention has been focused on optimizing multi-way join performance, particularly in reducing the overhead caused by generating intermediate tuples that do not contribute to the final result. In this paper, we propose a novel algorithm called SieveJoin, which extends the established Bloomjoin approach to support multi-way joins. SieveJoin sets a new benchmark for the efficiency of join query execution. A key innovation of SieveJoin is its ability to propagate Bloom filters along the join path, allowing the system to terminate early and avoid producing superfluous intermediate results. The primary design objective of SieveJoin is to efficiently estimate join results using Bloom filters, while maintaining minimal memory overhead. We analyze the bottlenecks associated with deferred multi-way joins and detail how Bloom filters are utilized to suppress the creation of redundant intermediate tuples. To assess the effectiveness of SieveJoin, we conduct a comprehensive experimental evaluation using the TPC-H benchmark, citation datasets, and a synthetic dataset. Our results compare SieveJoin with a state-of-the-art column-store database and a worst-case optimal join algorithm, highlighting its advantages in both response time and memory usage.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

SieveJoin: Boosting Multi-way Joins by Filtering Unneeded Intermediate Results

  • Renrui Li,
  • Qingzhi Ma,
  • Xiaomeng Shi,
  • An Liu

摘要

Improving the performance of data systems for join operations has long been a critical challenge. Recently, substantial attention has been focused on optimizing multi-way join performance, particularly in reducing the overhead caused by generating intermediate tuples that do not contribute to the final result. In this paper, we propose a novel algorithm called SieveJoin, which extends the established Bloomjoin approach to support multi-way joins. SieveJoin sets a new benchmark for the efficiency of join query execution. A key innovation of SieveJoin is its ability to propagate Bloom filters along the join path, allowing the system to terminate early and avoid producing superfluous intermediate results. The primary design objective of SieveJoin is to efficiently estimate join results using Bloom filters, while maintaining minimal memory overhead. We analyze the bottlenecks associated with deferred multi-way joins and detail how Bloom filters are utilized to suppress the creation of redundant intermediate tuples. To assess the effectiveness of SieveJoin, we conduct a comprehensive experimental evaluation using the TPC-H benchmark, citation datasets, and a synthetic dataset. Our results compare SieveJoin with a state-of-the-art column-store database and a worst-case optimal join algorithm, highlighting its advantages in both response time and memory usage.