DBScholar

Back to papers

Bitvector-aware Query Optimization for Decision Support Queries

Summary: Bitvector filtering speeds decision-support queries; naive optimization explodes the plan space, but for star/snowflake/right-deep queries the optimal plan comes from a linear set. A linear-candidate join-order algorithm, implemented as a DBMS-X transformation, yields 22–64% CPU savings overall and up to 100× on some queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
6046
Venue
SIGMOD
Year
2020
Pagerank
6.4803828e-05
Overall Rank
4,849 | 66.74%
DOI
10.1145/3318464.3389769

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{ding_sigmod20,
        title = {{Bitvector-aware Query Optimization for Decision Support Queries}},
        author = {Ding, Bailu and Chaudhuri, Surajit and Narasayya, Vivek},
        series = {{SIGMOD} '20},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3318464.3389769},
        url = {https://dl.acm.org/doi/10.1145/3318464.3389769},
        year = {2020}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank Citing Paper Year Venue Pagerank
1,832 DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems 2021 VLDB 9.6607418e-05
5,010 Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server 2023 VLDB 6.4023732e-05
5,284 SQLite: Past, Present, and Future 2022 VLDB 6.2827906e-05
6,593 Simple Adaptive Query Processing vs. Learned Query Optimizers: Observations and Analysis 2023 VLDB 5.8297039e-05
8,439 New Query Optimization Techniques in the Spark Engine of Azure Synapse 2022 VLDB 5.4248071e-05
8,494 POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance 2024 VLDB 5.4142129e-05
8,721 Accelerate Distributed Joins with Predicate Transfer 2025 SIGMOD 5.3772617e-05
9,183 Extending SQL to Return a Subdatabase 2025 SIGMOD 5.3058708e-05
9,279 Including Bloom Filters in Bottom-up Optimization 2025 SIGMOD 5.2934632e-05
10,135 I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server 2026 CIDR 5.093636e-05
10,529 Robust Predicate Transfer with Dynamic Execution 2026 VLDB 5.093636e-05
10,985 Scaling GPU-Accelerated Databases beyond GPU Memory Size 2025 VLDB 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
80 Hashing Methods and Relational Algebra Operations 1984 VLDB 0.00036536643
316 Measuring the Complexity of Join Enumeration in Query Optimization 1990 VLDB 0.0002141607
744 Fundamental Techniques for Order Optimization 1996 SIGMOD 0.00014411295
794 Bitmap Index Design and Evaluation 1998 SIGMOD 0.00013969303
1,013 Dynamic Programming Strikes Back 2008 SIGMOD 0.00012652549
1,037 Cost-Based Optimization for Magic: Algebra and Implementation 1996 SIGMOD 0.00012494928
1,298 Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products 2006 VLDB 0.00011259156
1,621 Orca: A Modular Query Optimizer Architecture for Big Data 2014 SIGMOD 0.00010203114
2,736 Efficient Execution of Joins in a Star Schema 2002 SIGMOD 8.1891265e-05
3,510 Performance-Optimal Filtering: Bloom Overtakes Cuckoo at High Throughput 2019 VLDB 7.3561488e-05
3,813 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 7.1051056e-05
4,416 Query Optimization in Oracle 12c Database In-Memory 2015 VLDB 6.7150543e-05
4,652 On Parallel Execution Of Multiple Pipelined Hash Joins 1994 SIGMOD 6.5851924e-05
5,014 Applying Hash Filters to Improving the Execution of Bushy Trees 1993 VLDB 6.4002123e-05
7,090 Optimizing Queries over Partitioned Tables in MPP Systems 2014 SIGMOD 5.706401e-05
7,162 Processing Star Queries on Hierarchically-Clustered Fact Tables 2002 VLDB 5.6851725e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 11,453 Asymptotically Better Query Optimization Using Indexed Algebra 2023 VLDB
2 6,009 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB
3 6,451 Efficient Search of Multidimensional B-Trees 1995 VLDB
4 1,286 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD
5 434 Query Optimization for Parallel Execution 1992 SIGMOD
6 1,464 An Efficient Bitmap Encoding Scheme for Selection Queries 1999 SIGMOD
7 3,813 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD
8 2,593 Cost-Based Optimization of Decision Support Queries using Transient-Views 1998 SIGMOD
9 10,296 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD
10 1,894 Optimizing Queries On Compressed Bitmaps 2000 VLDB