Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates

Summary: Two algorithms enable building B+-tree-like indexes on very large tables without quiescing updates, maximizing concurrency for both unique and nonunique indexes. Restartable builds and sorts with robust long-sort/merge phases, handling concatenated keys and adapting to primary-key/secondary-index storage layouts. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hfda77deb89bddaf7
Venue: SIGMOD
Year: 1992
Pagerank: 0.00012887578
Overall Rank: 951 | 93.61%
DOI: 10.1145/130283.130337

Incoming Non-self Citations Over Time

Authors

1. C. Mohan (IBM)
2. Inderpal Narang (IBM)

BibTeX Citation

@inproceedings{mohan_sigmod92,
        title = {{Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates}},
        author = {Mohan, C. and Narang, Inderpal},
        series = {{SIGMOD} '92},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/130283.130337},
        url = {https://dl.acm.org/doi/10.1145/130283.130337},
        year = {1992}
}

Incoming Citations (Sorted by Pagerank)

Showing 20 of 20 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,540	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00010311314
1,701	Feeding Frenzy: Selectively Materializing Users' Event Feeds	2010	SIGMOD	9.8324792e-05
3,020	Asynchronous View Maintenance for VLSD Databases	2009	SIGMOD	7.7426205e-05
3,026	On-line Reorganization of Sparsely-populated B+-trees	1996	SIGMOD	7.7353085e-05
3,279	Efficient Resumption of Interrupted Warehouse Loads	2000	SIGMOD	7.4628169e-05
3,483	Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases	1996	SIGMOD	7.2628249e-05
3,511	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.2414794e-05
3,641	Efficient Bulk Insertion into a Distributed Ordered Table	2008	SIGMOD	7.141045e-05
4,961	Safely and Efficiently Updating References During On-line Reorganization	1998	VLDB	6.3361057e-05
5,051	OODB Bulk Loading Revisited: The Partitioned-List Approach	1995	VLDB	6.2955172e-05
5,626	Principles of Transaction-Based On-Line Reorganization	1992	VLDB	6.0581249e-05
6,760	Compensation-Based On-Line Query Processing	1992	SIGMOD	5.6875074e-05
7,593	Efficient Data Ingestion and Query Processing for LSM-Based Storage Systems	2019	VLDB	5.4870235e-05
7,962	Online B-Tree Merging	2005	SIGMOD	5.4157047e-05
8,119	On-line Reorganization in Object Databases	2000	SIGMOD	5.3917406e-05
8,358	Resumable Online Index Rebuild in SQL Server	2017	VLDB	5.3459276e-05
9,072	Repeating History Beyond ARIES	1999	VLDB	5.2261389e-05
11,376	MD-MVCC: Multi-version Concurrency Control for Schema Changes in Azure SQL Database	2025	VLDB	4.9769913e-05
13,063	Transaction support for indexed summary views	2004	SIGMOD	4.9769913e-05
13,197	Group Updates for Relaxed Height-Balanced Trees	1999	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
221	ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes	1990	VLDB	0.00024269058
983	ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging	1992	SIGMOD	0.00012701317
2,052	Efficient and Flexible Methods for Transient Versioning of Records to Avoid Locking by Read-Only Transactions	1992	SIGMOD	9.1169073e-05
5,242	Commit LSN: A Novel and Simple Method for Reducing Locking and Latching in Transaction Processing Systems	1990	VLDB	6.2140724e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,957	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB
2	7,714	The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures	2022	VLDB
3	9,757	Indexing Highly Dynamic Hierarchical Data	2015	VLDB
4	960	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD
5	1,837	Merging What's Cracked, Cracking What's Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB
6	9,110	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
7	2,049	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS
8	6,005	Concurrency Control for Adaptive Indexing	2012	VLDB
9	10,894	Storing and Indexing Multiple Tables by Interesting Orderings: For Efficient Joins, Groupings, and Updates in Relational Databases	2026	VLDB
10	1,540	Sorting And Indexing With Partitioned B-Trees	2003	CIDR