Cache-Efficient Aggregation: Hashing Is Sorting

Summary: Hashing and sorting share the same cache efficiency in the external memory model, within a unified aggregation framework. Hardware-aware switching between hashing and sorting yields a cache-friendly, parallel aggregation; near memory bandwidth, beating state-of-the-art by up to 3.7x. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5101
Venue: SIGMOD
Year: 2015
Pagerank: 8.8694486e-05
Overall Rank: 2,250 | 84.57%
DOI: 10.1145/2723372.2747644

Incoming Non-self Citations Over Time

Authors

1. Ingo Müller (Karlsruhe Institute of Technology; SAP)
2. Peter Sanders (Karlsruhe Institute of Technology)
3. Arnaud Lacurie (SAP)
4. Wolfgang Lehner (Technical University of Dresden)
5. Franz Färber (SAP)

BibTeX Citation

@inproceedings{muller_sigmod15,
        title = {{Cache-Efficient Aggregation: Hashing Is Sorting}},
        author = {Müller, Ingo and Sanders, Peter and Lacurie, Arnaud and Lehner, Wolfgang and Färber, Franz},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2747644},
        url = {https://dl.acm.org/doi/10.1145/2723372.2747644},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
694	Cardinality Estimation Done Right: Index-Based Join Sampling	2017	CIDR	0.00014911698
2,343	Understanding the Effect of Data Center Resource Disaggregation on Production DBMSs	2020	VLDB	8.7213493e-05
3,344	RUMA has it: Rewired User-space Memory Access is Possible!	2016	VLDB	7.4980897e-05
4,607	Adaptive NUMA-aware data placement and task scheduling for analytical workloads in main-memory column-stores	2017	VLDB	6.6088324e-05
5,765	Charting the Design Space of Query Execution using VOILA	2021	VLDB	6.0953705e-05
7,396	Fast Detection of Denial Constraint Violations	2022	VLDB	5.6257228e-05
7,774	Building Advanced SQL Analytics From Low-Level Plan Operators	2021	SIGMOD	5.5468469e-05
7,899	Modularis: Modular Relational Analytics over Heterogeneous Distributed Platforms	2021	VLDB	5.5195553e-05
9,100	Chasing Similarity: Distribution-aware Aggregation Scheduling	2019	VLDB	5.3250075e-05
10,593	Global Hash Tables Strike Back! An Analysis of Parallel GROUP BY Aggregation	2026	VLDB	5.093636e-05
11,200	High-Performance Query Processing with NVMe Arrays: Spilling without Killing Performance	2024	SIGMOD	5.093636e-05
11,348	Cache-Efficient Top-k Aggregation over High Cardinality Large Datasets	2024	VLDB	5.093636e-05

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
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00083340894
14	MonetDB/X100: Hyper-Pipelining Query Execution	2005	CIDR	0.0006312782
23	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.00054886415
29	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.00052093615
165	DB2 with BLU Acceleration: So Much More than Just a Column Store	2013	VLDB	0.00027693424
209	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024932174
252	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023242719
423	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00018725853
632	Adaptive Aggregation on Chip Multiprocessors	2007	VLDB	0.00015575286
959	Memory-Efficient Hash Joins	2015	VLDB	0.00012953588
1,177	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011808761
1,596	Adaptive Parallel Aggregation Algorithms	1995	SIGMOD	0.00010247091
1,809	Hash joins and hash teams in Microsoft SQL Server	1998	VLDB	9.7034998e-05
3,406	Cache-Conscious Radix-Decluster Projections	2004	VLDB	7.4392655e-05
5,356	Code generation for efficient query processing in managed runtimes	2014	VLDB	6.2498397e-05
6,113	Patience is a Virtue: Revisiting Merge and Sort on Modern Processors	2014	SIGMOD	5.9715554e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	252	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB
2	4,668	Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor	1991	VLDB
3	4,177	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB
4	1,278	A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing	2016	VLDB
5	1,177	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD
6	10,593	Global Hash Tables Strike Back! An Analysis of Parallel GROUP BY Aggregation	2026	VLDB
7	209	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB
8	3,011	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD
9	360	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD
10	801	Query Execution Techniques for Caching Expensive Methods	1996	SIGMOD