Including Bloom Filters in Bottom-up Optimization

Tim Zeyl, Qi Cheng, Reza Pournaghi, Jason Lam, Weicheng Wang, Calvin Wong, Chong Chen, Per-Åke Larson

TL;DR

This paper introduces a novel approach to integrate Bloom filters into bottom-up query optimizers, a significant advancement over existing top-down methods. By considering Bloom filters during the optimization process, they achieve substantial query latency reductions, demonstrating that a more intelligent placement of these filters can lead to significantly better query plans.

What Problem Does This Paper Address?

Query optimizers are crucial for efficient database performance, and Bloom filters are a popular technique for early data reduction, speeding up queries by probabilistically filtering out irrelevant data. However, traditional query optimizers often apply Bloom filters after the optimal query plan has already been determined. This "post-processing" approach can miss opportunities for significant performance gains because the optimal join order might change when Bloom filters are considered from the outset. Existing work has explored integrating Bloom filters into top-down optimizers, but this paper tackles the challenge of doing so within a bottom-up cost-based optimizer, which has different structural properties and optimization strategies.

Methods

The core contribution is a two-phase bottom-up optimization approach, termed BF-CBO.

  1. Marking Bloom Filter Candidates: The process begins by identifying potential Bloom filter applications based on join clauses. Heuristics are applied to limit the number of candidates, such as only considering the larger relation in a join or skipping filters for tables below a certain size.
  2. First Bottom-Up Phase: This phase simulates the standard bottom-up process but focuses on identifying potential "delta" sets ($\delta$) – the sets of relations that must be present on the build side of a hash join for a Bloom filter to be resolved. This phase defers actual costing.
  3. Costing Bloom Filter Sub-plans: New sub-plans are created for scans that incorporate Bloom filters. Their cardinality and cost are estimated based on the identified $\delta$ sets and Bloom filter properties. Several heuristics are used here to prune sub-plans that are too large, too selective, or offer minimal benefit.
  4. Second Bottom-Up Phase: This phase proceeds with full costing and planning. It incorporates the Bloom filter sub-plans, but with additional constraints: Bloom filter sub-plans must be on the probe side of a hash join, and the join method must be a hash join if the build side provides the necessary relations for the Bloom filter.

This two-phase approach aims to manage the increased search space introduced by Bloom filters by delaying full costing and pruning until it's possible to resolve the Bloom filter's dependencies.

Datasets

The experiments were conducted using the TPC-H dataset at a scale factor of 100 (approximately 100 GB).

Key Insights and Ideas

  • Bloom Filters Matter for Join Order: The most significant insight is that the optimal join order can drastically change when Bloom filters are considered during optimization, not just as an afterthought. This challenges the assumption that post-processing Bloom filters is sufficient.
  • Bottom-Up Integration is Tricky: Incorporating Bloom filters into bottom-up optimizers is complex because the dependencies for resolving a Bloom filter (the $\delta$ set) are not known until later in the planning process. This requires a novel two-phase approach to manage this dependency.
  • Heuristics are Crucial: The paper emphasizes the necessity of heuristics to prune the search space. Without them, the optimization time would become prohibitively long. These heuristics balance the potential gains from Bloom filters against the cost of optimization.
  • Cardinality Estimation Improvement: By integrating Bloom filters into the cost model, the paper demonstrates a significant improvement in the accuracy of cardinality estimates for intermediate plan nodes.

Key Results

  • Significant Latency Reduction: BF-CBO achieved a 32.8% further reduction in query latency compared to a post-processing approach (BF-Post), and a 52.2% reduction compared to no Bloom filters at all.
  • Improved Cardinality Estimation: The Mean Absolute Error (MAE) for cardinality estimates of intermediate plan nodes was 78.8% lower with BF-CBO compared to BF-Post.
  • Trade-off in Planning Time: While BF-CBO significantly improves query latency, it does incur an overhead in planning time (540.7 ms vs. 254.3 ms for BF-Post in their experiments). This trade-off is acknowledged as being more suitable for long-running analytical queries.
  • Example-Driven Improvements: Specific query examples (TPC-H Q7 and Q12) are used to illustrate how BF-CBO leads to better join orders and more effective predicate transfer, resulting in substantial latency improvements.

Limitations and Future Work

  • Multi-Node Deployments: The current implementation is for single-node SMP systems. Extending BF-CBO to multi-node distributed systems, where Bloom filters might need to be transferred and merged across nodes, is a key future direction.
  • Multi-Column Bloom Filters: The current work focuses on single-column Bloom filters. Supporting multi-column Bloom filters could offer further optimization opportunities.
  • Heuristic Tuning: The paper acknowledges that the heuristics used are a starting point and could benefit from further tuning to optimize the trade-off between planning time and query latency.
  • Runtime Monitoring: Future work could involve runtime monitoring of Bloom filter bit vector saturation to adapt to poor estimation of distinct entries.
  • Query Types: While the method applies to all query types, the experiments focused on TPC-H. Further validation on diverse query workloads would be beneficial.

Summary updated

Abstract

Bloom filters are used in query processing to perform early data reduction and improve query performance. The optimal query plan may be different when Bloom filters are used, indicating the need for Bloom filter-aware query optimization. To date, Bloom filter-aware query optimization has only been incorporated in a top-down query optimizer and limited to snowflake queries. In this paper, we show how Bloom filters can be incorporated in a bottom-up cost-based query optimizer. We highlight the challenges in limiting optimizer search space expansion, and offer an efficient solution. We show that including Bloom filters in cost-based optimization can lead to better join orders with effective predicate transfer between operators. On a 100 GB instance of the TPC-H database, our approach achieved a 32.8% further reduction in latency for queries involving Bloom filters, compared to the traditional approach of adding Bloom filters in a separate post-optimization step. Our method applies to all query types, and we provide several heuristics to balance limited increases in optimization time against improved query latency.
BibTeX
@inproceedings{zeyl2025including,
  author = {Tim Zeyl and Qi Cheng and Reza Pournaghi and Jason Lam and Weicheng Wang and Calvin Wong and Chong Chen and Per-Åke Larson},
  title = {{Including Bloom Filters in Bottom-up Optimization}},
  booktitle = {Sigmod Conference Companion},
  year = {2025},
  doi = {10.1145/3722212.3724440},
}
Figure