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: 1255
Venue: PODS
Year: 2002
Pagerank: 0.00014161995
Overall Rank: 771 | 94.72%
DOI: 10.1145/543613.543628

Incoming Non-self Citations Over Time

Authors

1. Kenneth A. Ross (Columbia University; INRIA)

BibTeX Citation

@inproceedings{ross_pods02,
        address = {New York, NY, USA},
        series = {{PODS} '02},
        title = {{Conjunctive Selection Conditions in Main Memory}},
        url = {https://dl.acm.org/doi/10.1145/543613.543628},
        doi = {10.1145/543613.543628},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ross, Kenneth A.},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 15 of 15 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
14	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.0006312782
23	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.00054886415
293	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00022259273
305	GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management	2006	SIGMOD	0.00021872796
813	Adaptive Ordering of Pipelined Stream Filters	2004	SIGMOD	0.00013846487
1,442	An Architecture for Compiling UDF-centric Workflows	2015	VLDB	0.00010778486
1,452	Fast Computation of Database Operations using Graphics Processors	2004	SIGMOD	0.00010745803
1,879	Predictable Performance for Unpredictable Workloads	2009	VLDB	9.5613416e-05
2,094	Tupleware: "Big" Data, Big Analytics, Small Clusters	2015	CIDR	9.1819738e-05
2,202	Quantifying TPC-H Choke Points and Their Optimizations	2020	VLDB	8.9639459e-05
3,727	Staircase Join: Teach a Relational DBMS to Watch its (Axis) Steps	2003	VLDB	7.1689738e-05
5,301	Babelfish: Efficient Execution of Polyglot Queries	2022	VLDB	6.2750553e-05
6,009	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB	6.0113733e-05
6,651	Progressive Indexes: Indexing for Interactive Data Analysis	2019	VLDB	5.8141997e-05
7,412	RTScan: Efficient Scan with Ray Tracing Cores	2024	VLDB	5.624223e-05

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
29	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.00052093615
49	Weaving Relations for Cache Performance	2001	VLDB	0.00043781096
67	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00038461275
74	Cache Conscious Algorithms for Relational Query Processing	1994	VLDB	0.00037330605
109	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.000331207
132	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030378624
204	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00025342994
441	Filtering Algorithms and Implementation for Very Fast Publish/Subscribe Systems	2001	SIGMOD	0.00018407547
987	What happens during a Join? Dissecting CPU and Memory Optimization Effects	2000	VLDB	0.00012814017
5,495	Efficient Main Memory Data Management Using the DBGraph Storage Model	1990	VLDB	6.1987657e-05
7,074	Publish/Subscribe on the Web at Extreme Speed	2000	VLDB	5.7100207e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,858	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS
2	10,169	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS
3	7,842	Processing and Optimizing Main Memory Spatial-Keyword Queries	2016	VLDB
4	7,366	Non-Invasive Progressive Optimization for In-Memory Databases	2016	VLDB
5	9,612	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR
6	434	Query Optimization for Parallel Execution	1992	SIGMOD
7	7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD
8	1,355	Query Processing in Main Memory Database Management Systems	1986	SIGMOD
9	6,009	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
10	9,754	Optimization of Disjunctive Predicates for Main Memory Column Stores	2017	SIGMOD