DBScholar

Back to papers

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.00036891569
Overall Rank
76 | 99.50%
DOI
-

Incoming Non-self Citations Over Time

Authors

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.00064013679
48 Weaving Relations for Cache Performance 2001 VLDB 0.00043795812
68 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00037957995
110 DBMSs On A Modern Processor: Where Does Time Go? 1999 VLDB 0.00032696785
166 On Supporting Containment Queries in Relational Database Management Systems 2001 SIGMOD 0.00027241844
206 Cache Conscious Indexing for Decision-Support in Main Memory 1999 VLDB 0.00024981343
210 Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs 2009 VLDB 0.00024844328
251 Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited 2014 VLDB 0.00023136934
304 GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management 2006 SIGMOD 0.00021598803
362 Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs 2011 SIGMOD 0.00019999596
547 Improving Index Performance through Prefetching 2001 SIGMOD 0.00016575635
616 Relational Joins on Graphics Processors 2008 SIGMOD 0.00015554627
670 Rethinking Database Algorithms for Phase Change Memory 2011 CIDR 0.00014959574
702 Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct 2009 VLDB 0.00014668058
761 Conjunctive Selection Conditions in Main Memory 2002 PODS 0.00014138079
890 Rack-Scale In-Memory Join Processing using RDMA 2015 SIGMOD 0.00013241413
902 Analyzing the Energy Efficiency of a Database Server 2010 SIGMOD 0.00013178114
939 Buffering Database Operations for Enhanced Instruction Cache Performance 2004 SIGMOD 0.00012964695
1,041 Generic Database Cost Models for Hierarchical Memory Systems 2002 VLDB 0.00012354465
1,454 Fast Computation of Database Operations using Graphics Processors 2004 SIGMOD 0.00010596726
1,642 Data Morphing: An Adaptive, Cache-Conscious Storage Technique 2003 VLDB 0.00010002341
1,730 Improving the Performance of List Intersection 2009 VLDB 9.7686642e-05
1,779 Ibex—An Intelligent Storage Engine with Support for Advanced SQL Off-loading 2014 VLDB 9.6575635e-05
2,124 Revisiting Co-Processing for Hash Joins on the Coupled CPU-GPU Architecture 2013 VLDB 9.0041425e-05
2,441 A Case for Staged Database Systems 2003 CIDR 8.4611767e-05
2,699 Database Servers on Chip Multiprocessors: Limitations and Opportunities 2007 CIDR 8.1161623e-05
2,816 GPL: A GPU-based Pipelined Query Processing Engine 2016 SIGMOD 7.9740083e-05
2,818 To Partition, or Not to Partition, That is the Join Question in a Real System 2021 SIGMOD 7.9703078e-05
3,432 Cache-Conscious Radix-Decluster Projections 2004 VLDB 7.300628e-05
3,491 In-Cache Query Co-Processing on Coupled CPU-GPU Architectures 2015 VLDB 7.2586387e-05
3,628 Triton Join: Efficiently Scaling to a Large Join State on GPUs with Fast Interconnects 2022 SIGMOD 7.1490678e-05
3,775 Hardware-conscious Query Processing in GPU-accelerated Analytical Engines 2019 CIDR 7.0261504e-05
3,777 Parallelizing Query Optimization 2008 VLDB 7.0240115e-05
4,026 Cache-conscious Frequent Pattern Mining on a Modern Processor 2005 VLDB 6.8430008e-05
4,732 MQJoin: Efficient Shared Execution of Main-Memory Joins 2016 VLDB 6.4439712e-05
5,144 The 3D Hash Join: Building On Non-Unique Join Attributes 2022 CIDR 6.2542377e-05
5,629 FPGA-based Multithreading for In-Memory Hash Joins 2015 CIDR 6.0574868e-05
5,881 MCJoin: A Memory-Constrained Join for Column-Store Main-Memory Databases. 2012 SIGMOD 5.9575926e-05
5,915 Inspector Joins 2005 VLDB 5.9472868e-05
6,153 Efficiently Processing Joins and Grouped Aggregations on GPUs 2025 SIGMOD 5.8669913e-05
6,216 Data Partitioning for In-Memory Systems: Myths, Challenges, and Opportunities 2019 CIDR 5.8451996e-05
6,790 STEPS Towards Cache-Resident Transaction Processing 2004 VLDB 5.6801599e-05
6,833 The Drill Down Benchmark 1998 VLDB 5.6670599e-05
7,099 Design and Analysis of a Processing-in-DIMM Join Algorithm: A Case Study with UPMEM DIMMs 2023 SIGMOD 5.5991152e-05
7,920 Cache-Oblivious Query Processing 2007 CIDR 5.4250739e-05
7,927 NOCAP: Near-Optimal Correlation-Aware Partitioning Joins 2023 SIGMOD 5.4234567e-05
8,229 The HV-tree: a Memory Hierarchy Aware Version Index 2010 VLDB 5.3726119e-05
9,068 EaseDB: A Cache-Oblivious In-Memory Query Processor 2007 SIGMOD 5.2267013e-05
9,073 A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory 2023 VLDB 5.2258409e-05
9,717 Chimera: Mitigating Ownership Transfers in Multi-Primary Shared-Storage Cloud-Native Databases 2025 VLDB 5.1346445e-05
Previous Page 1 / 2 Next

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.00081971778
223 AlphaSort: A RISC Machine Sort 1994 SIGMOD 0.00024120979
Previous Page 1 / 1 Next

Semantically Similar Papers

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