Cache Conscious Algorithms for Relational Query Processing

Summary: Cache-conscious redesign of relational query processing leverages CPU cache hierarchies to narrow the DRAM–CPU gap. Demonstrates 8–200% speedups over traditional algorithms by reordering and structuring operators to maximize cache reuse. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h61beedc242b01a32
Venue: VLDB
Year: 1994
Pagerank: 0.00036821827
Overall Rank: 77 | 99.49%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Ambuj Shatdal (University of Wisconsin)
2. Chander Kant (University of Wisconsin)
3. Jeffrey F. Naughton (University of Wisconsin)

BibTeX Citation

@article{shatdal_vldb94,
        title = {{Cache Conscious Algorithms for Relational Query Processing}},
        author = {Shatdal, Ambuj and Kant, Chander and Naughton, Jeffrey F.},
        journal = {PVLDB},
        series = {{VLDB} '94},
        pages = {510--521},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 53 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
14	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.00063972112
48	Weaving Relations for Cache Performance	2001	VLDB	0.00043770511
68	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00037861537
111	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.00032621499
167	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027156235
209	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00024915373
212	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024786576
250	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023080446
304	GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management	2006	SIGMOD	0.00021569633
360	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00019959166
548	Improving Index Performance through Prefetching	2001	SIGMOD	0.00016534019
610	Relational Joins on Graphics Processors	2008	SIGMOD	0.00015540189
671	Rethinking Database Algorithms for Phase Change Memory	2011	CIDR	0.00014912266
702	Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct	2009	VLDB	0.0001464107
766	Conjunctive Selection Conditions in Main Memory	2002	PODS	0.00014105436
885	Rack-Scale In-Memory Join Processing using RDMA	2015	SIGMOD	0.00013222753
887	Analyzing the Energy Efficiency of a Database Server	2010	SIGMOD	0.00013214226
943	Buffering Database Operations for Enhanced Instruction Cache Performance	2004	SIGMOD	0.0001293608
1,044	Generic Database Cost Models for Hierarchical Memory Systems	2002	VLDB	0.0001232071
1,454	Fast Computation of Database Operations using Graphics Processors	2004	SIGMOD	0.0001058211
1,646	Data Morphing: An Adaptive, Cache-Conscious Storage Technique	2003	VLDB	9.9748468e-05
1,737	Improving the Performance of List Intersection	2009	VLDB	9.7383962e-05
1,782	Ibex—An Intelligent Storage Engine with Support for Advanced SQL Off-loading	2014	VLDB	9.6551269e-05
2,125	Revisiting Co-Processing for Hash Joins on the Coupled CPU-GPU Architecture	2013	VLDB	8.9903827e-05
2,447	A Case for Staged Database Systems	2003	CIDR	8.4378829e-05
2,707	Database Servers on Chip Multiprocessors: Limitations and Opportunities	2007	CIDR	8.0920389e-05
2,808	GPL: A GPU-based Pipelined Query Processing Engine	2016	SIGMOD	7.962315e-05
2,827	To Partition, or Not to Partition, That is the Join Question in a Real System	2021	SIGMOD	7.9486247e-05
3,441	Cache-Conscious Radix-Decluster Projections	2004	VLDB	7.2786711e-05
3,495	In-Cache Query Co-Processing on Coupled CPU-GPU Architectures	2015	VLDB	7.237656e-05
3,622	Triton Join: Efficiently Scaling to a Large Join State on GPUs with Fast Interconnects	2022	SIGMOD	7.1350619e-05
3,775	Hardware-conscious Query Processing in GPU-accelerated Analytical Engines	2019	CIDR	7.0079979e-05
3,785	Parallelizing Query Optimization	2008	VLDB	7.0012696e-05
4,042	Cache-conscious Frequent Pattern Mining on a Modern Processor	2005	VLDB	6.8217193e-05
4,751	MQJoin: Efficient Shared Execution of Main-Memory Joins	2016	VLDB	6.42279e-05
5,169	The 3D Hash Join: Building On Non-Unique Join Attributes	2022	CIDR	6.2335575e-05
5,637	FPGA-based Multithreading for In-Memory Hash Joins	2015	CIDR	6.0383864e-05
5,721	Efficiently Processing Joins and Grouped Aggregations on GPUs	2025	SIGMOD	6.0008904e-05
5,897	MCJoin: A Memory-Constrained Join for Column-Store Main-Memory Databases.	2012	SIGMOD	5.9382329e-05
5,927	Inspector Joins	2005	VLDB	5.9281216e-05
6,228	Data Partitioning for In-Memory Systems: Myths, Challenges, and Opportunities	2019	CIDR	5.8261473e-05
6,804	STEPS Towards Cache-Resident Transaction Processing	2004	VLDB	5.66191e-05
6,851	The Drill Down Benchmark	1998	VLDB	5.6483671e-05
7,122	Design and Analysis of a Processing-in-DIMM Join Algorithm: A Case Study with UPMEM DIMMs	2023	SIGMOD	5.580601e-05
7,931	Cache-Oblivious Query Processing	2007	CIDR	5.4076475e-05
7,942	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	5.4055234e-05
8,247	The HV-tree: a Memory Hierarchy Aware Version Index	2010	VLDB	5.3548467e-05
9,088	EaseDB: A Cache-Oblivious In-Memory Query Processor	2007	SIGMOD	5.2094186e-05
9,093	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB	5.208561e-05
9,361	Databases in the Era of Memory-Centric Computing	2025	CIDR	5.174177e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00081781676
223	AlphaSort: A RISC Machine Sort	1994	SIGMOD	0.00024059196

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,642	Revisiting Reuse in Main Memory Database Systems	2017	SIGMOD
2	3,854	Query Processing in Tertiary Memory Databases	1995	VLDB
3	4,855	ReCache: Reactive Caching for Fast Analytics over Heterogeneous Data	2018	VLDB
4	9,088	EaseDB: A Cache-Oblivious In-Memory Query Processor	2007	SIGMOD
5	2,928	Database Architectures for New Hardware	2004	VLDB
6	1,106	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB
7	111	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB
8	7,931	Cache-Oblivious Query Processing	2007	CIDR
9	27	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB
10	943	Buffering Database Operations for Enhanced Instruction Cache Performance	2004	SIGMOD