Database Paper Browser

Back to papers

Conjunctive Selection Conditions in Main Memory

Summary: Shows that ordering of conjunctive selection predicates in main-memory databases creates a space of logically equivalent plans with widely differing performance due to CPU branch-misprediction costs. Proposes a branch-misprediction-aware cost model plus optimal and heuristic plan selection algorithms, with case-study evidence of substantial speedups. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1256
Venue
PODS
Year
2002
Pagerank
0.0001659522
Overall Rank
790 | 94.52%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank Citing Paper Year Venue Pagerank
35 MonetDB/X100: Hyper-Pipelining Query Execution 2005 CIDR 0.00076209479
59 Efficiently Compiling Efficient Query Plans for Modern Hardware 2011 VLDB 0.0006445664
238 GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management 2006 SIGMOD 0.00031596093
343 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00026756534
1,041 Adaptive Ordering of Pipelined Stream Filters 2004 SIGMOD 0.00014470785
1,685 Fast Computation of Database Operations using Graphics Processors 2004 SIGMOD 0.0001090924
1,875 An Architecture for Compiling UDF-centric Workflows 2015 VLDB 0.00010243959
2,372 Predictable Performance for Unpredictable Workloads 2009 VLDB 8.940791e-05
2,421 Tupleware: "Big" Data, Big Analytics, Small Clusters 2015 CIDR 8.8471956e-05
2,914 Quantifying TPC-H Choke Points and Their Optimizations 2020 VLDB 7.9197583e-05
4,119 Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps 2003 VLDB 6.4309908e-05
5,741 Babelfish: Efficient Execution of Polyglot Queries 2022 VLDB 5.3450701e-05
6,372 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB 5.0878306e-05
7,000 Progressive Indexes: Indexing for Interactive Data Analysis 2019 VLDB 4.862486e-05
7,482 RTScan: Efficient Scan with Ray Tracing Cores 2024 VLDB 4.7135369e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank Cited Paper Year Venue Pagerank
52 Database Architecture Optimized for the new Bottleneck: Memory Access 1999 VLDB 0.00066322421
80 Weaving Relations for Cache Performance 2001 VLDB 0.00055735291
81 Cache Conscious Algorithms for Relational Query Processing 1994 VLDB 0.00055253195
104 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00049475932
124 DBMSs On A Modern Processor: Where Does Time Go? 1999 VLDB 0.0004501099
140 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00042289025
240 Cache Conscious Indexing for Decision-Support in Main Memory 1999 VLDB 0.00031526134
497 Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems 2001 SIGMOD 0.00021667647
1,077 What happens during a Join? Dissecting CPU and Memory Optimization Effects 2000 VLDB 0.00014224986
5,005 Efficient Main Memory Data Management Using the DBGraph Storage Model 1990 VLDB 5.7599923e-05
7,169 Publish/Subscribe on the Web at Extreme Speed 2000 VLDB 4.8073147e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
1,701 An Efficient Bitmap Encoding Scheme for Selection Queries 1999 SIGMOD 0.00010828605
7,829 Optimization of Multiple-Relation Multiple-Disjunct Queries 1988 PODS 4.6373918e-05
7,693 Processing and Optimizing Main Memory Spatial-Keyword Queries 2016 VLDB 4.6714423e-05
7,462 Non-Invasive Progressive Optimization for In-Memory Databases 2016 VLDB 4.7189301e-05
9,466 Memory Efficient Scheduling of Query Pipeline Execution 2022 CIDR 4.3314303e-05
439 Query Optimization for Parallel Execution 1992 SIGMOD 0.00023183237
9 Implementation Techniques For Main Memory Database Systems 1984 SIGMOD 0.001426258
1,337 Query Processing in Main Memory Database Management Systems 1986 SIGMOD 0.00012515176
6,372 Optimization of Conjunctive Predicates for Main Memory Column Stores 2016 VLDB 5.0878306e-05
9,625 Optimization of Disjunctive Predicates for Main Memory Column Stores 2017 SIGMOD 4.3115918e-05