WARF TECHNOLOGIES

UW-Madison researchers have created a method called predicate transfer, that optimizes join performance by pre-filtering tables to reduce the join input sizes. Predicate transfer generalizes Bloom join, which conducts pre-filtering within a single join operation, to multi-table joins such that the filtering benefits can be significantly increased. Predicate transfer is inspired by the method using semi-joins to pre-filter acyclic queries. Predicate transfer executes a query in two phases. Phase 1: Predicate Transfer Phase. In this phase, a join graph is constructed for a query, where each vertex is a table and each edge is a join operation. A local predicate is constructed as a filter (e.g., a Bloom filter) and be transferred across the join graph. Phase 2: Join Phase. After the transfer phase finishes, each table has multiple filters, including both local filters and transferred filters. The database can now apply the filters and perform regular joins. The actual inputs of each join will be substantially smaller if the transferred filters are selective.

For More Information About the Inventors

• Xiangyao Yu
• Paraschos Koutris

Tech Fields

• Information Technology : Computing methods, software & machine learning