Database researchers have introduced an algorithm named SieveJoin that substantially accelerates complex multi-way relational joins by filtering out unneeded intermediate data before expensive computations occur. Join operations form the computational bedrock of relational database management systems, yet evaluating queries that span three or more relations frequently creates massive volumes of temporary tuples that never reach the final answer. Presenting their design and experimental results in Data Science and Engineering, researchers Renrui Li, Qingzhi Ma, Xiaomeng Shi, and An Liu demonstrated that propagating compact Bloom filters backward along planned join paths allows relational database engines to terminate unpromising data evaluations early. Across comprehensive benchmarks spanning synthetic datasets, standard decision-support workloads, and real-world academic citation graphs, the resulting framework consistently pruned intermediate relation sizes by up to several orders of magnitude, delivering execution runtimes between one and three orders of magnitude faster than conventional relational database engines.
For decades, commercial and open-source database management systems have relied predominantly on binary join plans to process queries joining multiple tables. Binary plans execute joins hierarchically, combining two physical relations at a time into an intermediate result before joining that intermediate table with subsequent relations in a sequence. While binary execution pipelines have undergone extensive performance optimization, theoretical database research has proven that binary join strategies are fundamentally suboptimal for multi-way queries. In low-selectivity queries and interconnected data structures, pairwise combinations routinely generate vast quantities of intermediate tuples that satisfy local two-table conditions but ultimately fail subsequent criteria. This intermediate tuple explosion wastes storage bandwidth, saturates system memory, and inflates query response times. Recent theoretical developments introduced worst-case optimal join algorithms, such as leapfrog triejoin pipelines and hybrid systems like Umbra, yet these techniques can face practical deployment hurdles, complex data structures, and stability concerns during demanding enterprise workloads.
To rigorously diagnose why intermediate join results explode during multi-way execution, the research team formally categorized intermediate join paths into two distinct structural failure modes: acyclic incomplete paths and cyclic mismatch paths. In a standard multi-way join across relations R, S, and T, a complete join path consists of matching tuples drawn from every participating relation. In contrast, an acyclic incomplete path represents an intermediate combination, such as a partial match between R and S, that cannot find any corresponding entry in relation T. In representative cyclic join workloads examined by the researchers, acyclic incomplete paths accounted for seventy-one percent of all generated paths, meaning five out of every seven partial combinations represented wasted processing. Cyclic mismatch paths represent an even more insidious performance bottleneck unique to cyclic queries, where intermediate paths complete the chain across relations R, S, and T but fail the final closing equality condition connecting the final table back to the first. Because these invalid paths satisfy all intermediate pairwise conditions, binary systems generate them fully before discarding them at the final verification step.
SieveJoin attacks both varieties of intermediate bloat by generalizing the concept of Bloomjoin to multi-way queries. A standard Bloom filter represents a space-efficient, probabilistic data structure designed for rapid set membership checks, guaranteeing zero false negatives while tolerating a tunable, minor fraction of false positives. Earlier distributed join optimization techniques, including classic Bloomjoin and spectral variants, harnessed Bloom filters primarily to curtail network transmission costs in two-way distributed joins by transmitting a compact bit array of join keys rather than entire data tables across sites. However, those historic implementations remained confined to single binary join steps or queries operating across identical join attributes, functioning primarily as network transfer accelerators rather than general-purpose multi-way query optimizers. SieveJoin advances this foundational concept by organizing pre-generated Bloom filters into an integrated multi-table execution pipeline that systematically removes non-contributing tuples before relations undergo relational join processing.
The operational framework of SieveJoin divides query processing into two primary stages: a backward propagation phase and an enumeration phase. During the propagation phase, the database engine constructs an initial Bloom filter on the target join attribute of the rightmost relation and propagates that filter backward toward preceding relations along the execution sequence. When an intermediate relation receives this filter, it performs a linear scan of its local join attributes, probing incoming bits on the fly to discard non-qualifying tuples before using the surviving records to generate the next upstream Bloom filter. By cascading this backward filtering process across relations from right to left, the system ensures that each newly constructed filter only represents records capable of completing downstream joins. Following this propagation stage, the enumeration phase employs the resulting compact filters to pre-filter all participating physical relations, allowing the database engine to execute standard join algorithms on aggressively compressed table representations without generating sprawling intermediate states.
To support diverse query structures, the research team designed two distinct propagation mechanics designated as simple propagation and equality propagation. Simple propagation handles acyclic query patterns by conducting sequential scans and approximate equality checks across consecutive relations, using Bloom filter membership tests to weed out tuples that cannot contribute to final results. For cyclic queries where relations form closed loops, simple propagation alone cannot detect cyclic mismatch paths because the closing join condition connects back to the starting relation. To overcome this challenge, SieveJoin introduces equality propagation, which constructs an auxiliary Bloom filter on the closing attribute of the downstream table. Upstream tables then probe two distinct Bloom filters simultaneously—one validating adjacent relational continuity and one validating loop closure. Because Bloom filters verify set existence rather than exact algebraic equality, equality propagation functions as an existence approximation; nevertheless, the researchers found that it eliminates the vast majority of cyclic mismatches without requiring full intermediate table materialization.
The researchers implemented SieveJoin in native C++ using a column-oriented architecture that stores tabular columns as sequential vectors paired with pre-built B-tree indexes on relevant join attributes. The architecture incorporates specialized operational mechanisms to accommodate updates and filter reuse in production database environments. For recurring query workloads with predictable query templates, pre-computed Bloom filters can be cached and reused directly, and sub-query components of larger queries can inherit pre-existing filters while dynamically generating closing filters on the fly. To evaluate transactional maintenance costs, the team analyzed database record insertion dynamics. When a newly inserted record already tests positive against a relation’s existing Bloom filter, no filter update is necessary, requiring only constant O(1) time. When an insertion introduces a previously unseen key, updating neighboring relations across pre-built B-tree structures incurs a computational complexity of O(n log N), where n is the number of relations and N represents relation size. The authors noted that integrating counting Bloom filters would further extend this capability to dynamic record deletions.
Rigorous experimental evaluation of SieveJoin was conducted on an Ubuntu 20.04 server equipped with a sixteen-core, thirty-two-thread AMD 7950X processor, 128 gigabytes of main memory, and four terabytes of solid-state storage. The research team benchmarked SieveJoin against three leading database implementations: the state-of-the-art worst-case optimal multi-way database Umbra, the high-performance column-store engine MonetDB, and the widely used relational database Postgres. Initial experiments evaluated controlled synthetic workloads across three relations where data volume and duplicate counts were systematically varied using scaling parameters r and d. In synthetic tests generating millions of intermediate tuples, Postgres and MonetDB frequently exhausted available system memory and failed to complete queries. In contrast, SieveJoin maintained near-linear scaling, outperforming competing engines by one to two orders of magnitude in query execution time. Evaluating the Relative Size Change metric demonstrated that backward propagation reduced intermediate relation S to just 0.2 percent of its original size, while table R experienced even greater tuple elimination.
Subsequent testing evaluated SieveJoin under the industry-standard TPC-H decision-support benchmark, configuring a five-table acyclic query designed to identify suppliers and customers sharing geographic nations alongside customer purchasing histories. Working at scale factor SF = 1, where the largest table contained approximately six million rows, the researchers generated eight experimental configurations by subsampling the lineitem relation between 100 percent and 0.1 percent, creating intermediate result proportions ranging from 0.6 percent to approximately 95 percent of all generated paths. Across all TPC-H query variations, SieveJoin executed significantly faster than baseline systems while Postgres repeatedly failed due to memory exhaustion. Under the most challenging configuration where unneeded intermediate join results comprised 95 percent of generated paths, SieveJoin pruned the customer relation by two full orders of magnitude and compressed the orders relation by three orders of magnitude, proving that its filtering efficiency scales directly with intermediate data bloat.
To evaluate cyclic performance, the research team examined complex graph clique queries using the real-world arXiv High Energy Physics Phenomenology (HEP-PH) citation network, which encompasses 27,770 academic papers connected by 352,807 citation edges. The team executed 3-clique and 4-clique graph discovery queries to isolate reciprocal citation patterns among interconnected publications. In these intensive cyclic graph benchmarks, parallel SieveJoin achieved between one and three orders of magnitude faster response times than MonetDB and Umbra, while even a single-threaded implementation of SieveJoin surpassed alternative engines by more than tenfold. Pruning acyclic incomplete paths alone reduced the citation table size by 20 percent for 3-clique queries and 25 percent for 4-clique queries. When the authors activated equality propagation to suppress cyclic mismatch paths, final relation sizes collapsed from hundreds of thousands of records down to just 3,639 and 10,396 rows, illustrating the profound impact of filtering cyclic intermediate mismatches.
Despite its demonstrated advantages, the authors documented clear architectural boundaries and limitations inherent to SieveJoin’s current algorithmic design. Because standard Bloom filters rely on bit hashing to evaluate set membership, SieveJoin strictly accelerates equi-joins; queries containing inequality constraints, range predicates, or non-equi join conditions cannot be filtered through this mechanism unless non-equi portions are materialized in advance. Furthermore, SieveJoin delivers its greatest performance improvements when deployed on frequently executed query templates and predictable enterprise workloads where filters can be prepared ahead of execution. When applied to completely ad-hoc queries requiring dynamic filter generation from scratch, query execution speed improvements become marginal or occasionally lag behind baseline systems due to initial setup overheads. Future research directions highlighted by the team include developing parallel Bloom filter training pipelines, formalizing complete elimination of cyclic mismatches through iterative verification, and integrating SieveJoin’s propagative filtering directly into mainstream commercial database engines.
Subject of Research: Multi-way database join optimization using propagative Bloom filters
Article Title: SieveJoin: Boosting Multi-way Joins by Filtering Unneeded Intermediate Results
Article References: Li, R., Ma, Q., Shi, X., & Liu, A. (2026). SieveJoin: Boosting Multi-way Joins by Filtering Unneeded Intermediate Results. Data Science and Engineering, 11(1), 143-154. https://doi.org/10.1007/s41019-025-00325-7
Image Credits: AI Generated
DOI: 10.1007/s41019-025-00325-7
Keywords: database systems, multi-way joins, Bloom filters, query optimization, data management, computer science, relational databases, graph queries, SieveJoin, Boosting, Multi-way, Joins
News Source: Denise Maddox. (November 10, 2026). SieveJoin Accelerates Database Multi-Way Joins by Pruning Intermediate Query Data. Scienmag.
