  Improving data systems' performance for join operations has long been an
issue of great importance. More recently, a lot of focus has been devoted to
multi-way join performance and especially on reducing the negative impact of
producing intermediate tuples, which in the end do not make it in the final
result. We contribute a new multi-way join algorithm, coined SieveJoin, which
extends the well-known Bloomjoin algorithm to multi-way joins and achieves
state-of-the-art performance in terms of join query execution efficiency.
SieveJoin's salient novel feature is that it allows the propagation of Bloom
filters in the join path, enabling the system to `stop early' and eliminate
useless intermediate join results. The key design objective of SieveJoin is to
efficiently `learn' the join results, based on Bloom filters, with negligible
memory overheads. We discuss the bottlenecks in delaying multi-way joins, and
how Bloom filters are used to remove the generation of unnecessary intermediate
join results. We provide a detailed experimental evaluation using various
datasets, against a state-of-the-art column-store database and a multi-way
worst-case optimal join algorithm, showcasing SieveJoin's gains in terms of
response time.
