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.00012893557
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,539	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00010316015
1,701	Feeding Frenzy: Selectively Materializing Users' Event Feeds	2010	SIGMOD	9.8371359e-05
3,019	Asynchronous View Maintenance for VLSD Databases	2009	SIGMOD	7.7461391e-05
3,025	On-line Reorganization of Sparsely-populated B+-trees	1996	SIGMOD	7.7388813e-05
3,278	Efficient Resumption of Interrupted Warehouse Loads	2000	SIGMOD	7.4661193e-05
3,482	Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases	1996	SIGMOD	7.2662396e-05
3,511	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.244841e-05
3,639	Efficient Bulk Insertion into a Distributed Ordered Table	2008	SIGMOD	7.1444069e-05
4,959	Safely and Efficiently Updating References During On-line Reorganization	1998	VLDB	6.3390968e-05
5,048	OODB Bulk Loading Revisited: The Partitioned-List Approach	1995	VLDB	6.2984943e-05
5,625	Principles of Transaction-Based On-Line Reorganization	1992	VLDB	6.060992e-05
6,755	Compensation-Based On-Line Query Processing	1992	SIGMOD	5.6901652e-05
7,594	Efficient Data Ingestion and Query Processing for LSM-Based Storage Systems	2019	VLDB	5.4879453e-05
7,958	Online B-Tree Merging	2005	SIGMOD	5.4182694e-05
8,112	On-line Reorganization in Object Databases	2000	SIGMOD	5.3942942e-05
8,353	Resumable Online Index Rebuild in SQL Server	2017	VLDB	5.3484595e-05
9,532	Repeating History Beyond ARIES	1999	VLDB	5.1644268e-05
11,370	MD-MVCC: Multi-version Concurrency Control for Schema Changes in Azure SQL Database	2025	VLDB	4.9793485e-05
13,057	Transaction support for indexed summary views	2004	SIGMOD	4.9793485e-05
13,191	Group Updates for Relaxed Height-Balanced Trees	1999	PODS	4.9793485e-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.00024274803
983	ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging	1992	SIGMOD	0.00012706526
2,052	Efficient and Flexible Methods for Transient Versioning of Records to Avoid Locking by Read-Only Transactions	1992	SIGMOD	9.1199209e-05
5,237	Commit LSN: A Novel and Simple Method for Reducing Locking and Latching in Transaction Processing Systems	1990	VLDB	6.2170143e-05

Semantically Similar Papers

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