Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes

Summary: Two-stage hybrid index for main-memory OLTP: a small ingest-first stage, with periodic migration to a compact, read-optimized second stage. DST shows how to convert any order-preserving index into a hybrid index; applied to four structures, achieving up to 70% memory reduction with comparable throughput. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5250
Venue: SIGMOD
Year: 2016
Pagerank: 0.00012711153
Overall Rank: 1,300 | 90.97%
DOI: 10.1145/2882903.2915222

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 39 of 39 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
101	The Case for Learned Index Structures	2018	SIGMOD	0.00049778866
1,085	HOT: A Height Optimized Trie Index for Main-Memory Database Systems	2018	SIGMOD	0.00014173956
1,169	SuRF: Practical Range Query Filtering with Fast Succinct Tries	2018	SIGMOD	0.00013530267
1,365	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00012379754
1,823	Dash: Scalable Hashing on Persistent Memory	2020	VLDB	0.00010403355
1,834	Designing Distributed Tree-based Index Structures for Fast RDMA-capable Networks	2019	SIGMOD	0.00010364718
2,022	Magic mirror in my hand, which is the best in the land? An Experimental Evaluation of Index Selection Algorithms	2020	VLDB	9.7623022e-05
2,313	Building a Bw-Tree Takes More Than Just Buzz Words	2018	SIGMOD	9.0546844e-05
2,868	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	7.9856878e-05
2,986	DPTree: Differential Indexing for Persistent Memory	2020	VLDB	7.7757727e-05
3,136	FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems	2022	VLDB	7.4926368e-05
3,341	Evaluating Persistent Memory Range Indexes	2020	VLDB	7.1984492e-05
3,945	APEX: A High-Performance Learned Index on Persistent Memory	2022	VLDB	6.605467e-05
4,056	Are Updatable Learned Indexes Ready?	2022	VLDB	6.4905689e-05
4,160	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	6.3886736e-05
4,830	CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm	2022	VLDB	5.8884997e-05
5,847	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD	5.3040014e-05
6,226	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD	5.1413982e-05
6,470	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0439835e-05
6,488	FILM: a Fully Learned Index for Larger-than-Memory Databases	2023	VLDB	5.0378878e-05
6,838	LeanStore: A High-Performance Storage Engine for NVMe SSDs	2024	VLDB	4.906223e-05
7,043	SepHash: A Write-Optimized Hash Index On Disaggregated Memory via Separate Segment Structure	2024	VLDB	4.8480192e-05
7,074	Zen: a High-Throughput Log-Free OLTP Engine for Non-Volatile Main Memory	2021	VLDB	4.8372993e-05
7,389	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	4.7386163e-05
7,870	SALI: A Scalable Adaptive Learned Index Framework based on Probability Models	2023	SIGMOD	4.6271153e-05
7,990	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	4.6086117e-05
8,080	Hyperion: Building the Largest In-memory Search Tree	2019	SIGMOD	4.5872476e-05
8,185	Two is Better Than One: The Case for 2-Tree for Skewed Data Sets	2023	CIDR	4.5614825e-05
8,575	Robust and Budget-Constrained Encoding Configurations for In-Memory Database Systems	2022	VLDB	4.4880409e-05
8,653	Adaptive Hybrid Indexes	2022	SIGMOD	4.4696663e-05
9,955	SCompression: Enhancing Database Knob Tuning Efficiency Through Slice-Based OLTP Workload Compression	2025	VLDB	4.2332427e-05
10,038	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	4.1905499e-05
10,257	SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory	2026	VLDB	4.1905499e-05
10,407	VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity	2025	SIGMOD	4.1905499e-05
10,494	Femur: A Flexible Framework for Fast and Secure Querying from Public Key-Value Store	2025	SIGMOD	4.1905499e-05
10,571	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	4.1905499e-05
11,039	Blitzcrank: Fast Semantic Compression for In-memory Online Transaction Processing	2024	VLDB	4.1905499e-05
11,231	Blink-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases	2023	VLDB	4.1905499e-05
11,688	HERMIT in Action: Succinct Secondary Indexing Mechanism via Correlation Exploration	2019	VLDB	4.1905499e-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
9	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.001426258
87	Hekaton: SQL Server’s Memory-Optimized OLTP Engine	2013	SIGMOD	0.00052844656
88	The End of an Architectural Era (It's Time for a Complete Rewrite)	2007	VLDB	0.0005262025
136	H-Store: A High-Performance, Distributed Main Memory Transaction Processing System	2008	VLDB	0.00042409816
215	OLTP Through the Looking Glass, and What We Found There	2008	SIGMOD	0.00033609709
407	Database Cracking	2007	CIDR	0.00023941779
820	Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method	1998	VLDB	0.00016232743
857	Efficient Transaction Processing in SAP HANA Database – The End of a Column Store Myth	2012	SIGMOD	0.00015840492
980	Anti-Caching: A New Approach to Database Management System Architecture	2013	VLDB	0.00014868633
1,033	Bitmap Index Design and Evaluation	1998	SIGMOD	0.0001453376
1,726	Fast Updates on Read-Optimized Databases Using Multi-Core CPUs	2012	VLDB	0.00010734339
2,075	Trekking Through Siberia: Managing Cold Data in a Memory-Optimized Database	2014	VLDB	9.6115775e-05
2,262	SQL Server Column Store Indexes	2011	SIGMOD	9.1629311e-05
2,414	Towards a One Size Fits All Database Architecture	2011	CIDR	8.8572378e-05
3,686	Compacting Transactional Data in Hybrid OLTP&OLAP Databases	2012	VLDB	6.839208e-05
4,363	Indexing on Modern Hardware: Hekaton and Beyond	2014	SIGMOD	6.2476591e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,708	Just-In-Time Data Structures	2015	CIDR	4.948865e-05
3,686	Compacting Transactional Data in Hybrid OLTP&OLAP Databases	2012	VLDB	6.839208e-05
5,378	Holistic Indexing in Main-memory Column-stores	2015	SIGMOD	5.5379945e-05
1,697	Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads	2016	SIGMOD	0.00010859294
9,499	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD	4.3300131e-05
8,100	Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction	2024	SIGMOD	4.5821762e-05
1,807	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	0.0001047644
235	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00031980259
2,361	Merging What’s Cracked, Cracking What’s Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB	8.9648608e-05
8,653	Adaptive Hybrid Indexes	2022	SIGMOD	4.4696663e-05