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: 5249
Venue: SIGMOD
Year: 2016
Pagerank: 0.00012652548
Overall Rank: 1,312 | 90.88%
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
102	The Case for Learned Index Structures	2018	SIGMOD	0.00049545203
1,087	HOT: A Height Optimized Trie Index for Main-Memory Database Systems	2018	SIGMOD	0.00014162909
1,169	SuRF: Practical Range Query Filtering with Fast Succinct Tries	2018	SIGMOD	0.00013536447
1,375	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00012303141
1,852	Designing Distributed Tree-based Index Structures for Fast RDMA-capable Networks	2019	SIGMOD	0.00010322492
1,888	Dash: Scalable Hashing on Persistent Memory	2020	VLDB	0.00010202743
2,020	Magic mirror in my hand, which is the best in the land? An Experimental Evaluation of Index Selection Algorithms	2020	VLDB	9.762624e-05
2,394	Building a Bw-Tree Takes More Than Just Buzz Words	2018	SIGMOD	8.9001843e-05
2,865	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	7.9862595e-05
2,992	DPTree: Differential Indexing for Persistent Memory	2020	VLDB	7.7693475e-05
3,131	FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems	2022	VLDB	7.4985793e-05
3,470	Evaluating Persistent Memory Range Indexes	2020	VLDB	7.0655357e-05
4,084	APEX: A High-Performance Learned Index on Persistent Memory	2022	VLDB	6.4622113e-05
4,128	Are Updatable Learned Indexes Ready?	2022	VLDB	6.4292373e-05
4,161	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	6.3938006e-05
4,646	CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm	2022	VLDB	6.0250374e-05
5,835	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD	5.30905e-05
6,229	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD	5.1463389e-05
6,477	Fast Algorithms for Denial Constraint Discovery	2023	VLDB	5.0488285e-05
6,492	FILM: a Fully Learned Index for Larger-than-Memory Databases	2023	VLDB	5.042727e-05
6,840	LeanStore: A High-Performance Storage Engine for NVMe SSDs	2024	VLDB	4.9109345e-05
7,080	Zen: a High-Throughput Log-Free OLTP Engine for Non-Volatile Main Memory	2021	VLDB	4.8417653e-05
7,390	Making In-Memory Learned Indexes Efficient on Disk	2024	SIGMOD	4.7431654e-05
7,869	SALI: A Scalable Adaptive Learned Index Framework based on Probability Models	2023	SIGMOD	4.6315248e-05
7,995	BP-tree: Overcoming the Point-Range Operation Tradeoff for In-Memory B-trees	2023	VLDB	4.6109825e-05
8,077	Hyperion: Building the Largest In-memory Search Tree	2019	SIGMOD	4.59165e-05
8,183	Two is Better Than One: The Case for 2-Tree for Skewed Data Sets	2023	CIDR	4.5658208e-05
8,235	SepHash: A Write-Optimized Hash Index On Disaggregated Memory via Separate Segment Structure	2024	VLDB	4.5535352e-05
8,578	Robust and Budget-Constrained Encoding Configurations for In-Memory Database Systems	2022	VLDB	4.4923477e-05
8,655	Adaptive Hybrid Indexes	2022	SIGMOD	4.4739554e-05
9,956	SCompression: Enhancing Database Knob Tuning Efficiency Through Slice-Based OLTP Workload Compression	2025	VLDB	4.2373024e-05
10,038	Understanding Robustness Issues of Updatable Learned Indexes: [Experiments & Analysis]	2026	SIGMOD	4.1945683e-05
10,257	SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory	2026	VLDB	4.1945683e-05
10,396	VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity	2025	SIGMOD	4.1945683e-05
10,484	Femur: A Flexible Framework for Fast and Secure Querying from Public Key-Value Store	2025	SIGMOD	4.1945683e-05
10,562	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	4.1945683e-05
11,036	Blitzcrank: Fast Semantic Compression for In-memory Online Transaction Processing	2024	VLDB	4.1945683e-05
11,229	Blink-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases	2023	VLDB	4.1945683e-05
11,683	HERMIT in Action: Succinct Secondary Indexing Mechanism via Correlation Exploration	2019	VLDB	4.1945683e-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.0014279444
86	The End of an Architectural Era (It's Time for a Complete Rewrite)	2007	VLDB	0.00052563276
87	Hekaton: SQL Server’s Memory-Optimized OLTP Engine	2013	SIGMOD	0.00052389723
137	H-Store: A High-Performance, Distributed Main Memory Transaction Processing System	2008	VLDB	0.00042342967
215	OLTP Through the Looking Glass, and What We Found There	2008	SIGMOD	0.0003354907
408	Database Cracking	2007	CIDR	0.00023953844
823	Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method	1998	VLDB	0.000162378
858	Efficient Transaction Processing in SAP HANA Database – The End of a Column Store Myth	2012	SIGMOD	0.000158756
982	Anti-Caching: A New Approach to Database Management System Architecture	2013	VLDB	0.00014872253
1,035	Bitmap Index Design and Evaluation	1998	SIGMOD	0.00014532778
1,731	Fast Updates on Read-Optimized Databases Using Multi-Core CPUs	2012	VLDB	0.0001073454
2,076	Trekking Through Siberia: Managing Cold Data in a Memory-Optimized Database	2014	VLDB	9.6059442e-05
2,258	SQL Server Column Store Indexes	2011	SIGMOD	9.1678883e-05
2,419	Towards a One Size Fits All Database Architecture	2011	CIDR	8.853712e-05
3,689	Compacting Transactional Data in Hybrid OLTP&OLAP Databases	2012	VLDB	6.8396366e-05
4,386	Indexing on Modern Hardware: Hekaton and Beyond	2014	SIGMOD	6.2320098e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,708	Just-In-Time Data Structures	2015	CIDR	4.953106e-05
3,689	Compacting Transactional Data in Hybrid OLTP&OLAP Databases	2012	VLDB	6.8396366e-05
5,376	Holistic Indexing in Main-memory Column-stores	2015	SIGMOD	5.5417421e-05
1,700	Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads	2016	SIGMOD	0.00010858865
9,498	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD	4.3341665e-05
8,101	Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction	2024	SIGMOD	4.5854141e-05
1,809	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	0.00010483957
233	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00032021526
2,363	Merging What’s Cracked, Cracking What’s Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB	8.9580928e-05
8,655	Adaptive Hybrid Indexes	2022	SIGMOD	4.4739554e-05