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.00012845453
Overall Rank: 956 | 93.60%
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,543	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00010277834
1,705	Feeding Frenzy: Selectively Materializing Users' Event Feeds	2010	SIGMOD	9.8056169e-05
3,029	Asynchronous View Maintenance for VLSD Databases	2009	SIGMOD	7.7174537e-05
3,035	On-line Reorganization of Sparsely-populated B+-trees	1996	SIGMOD	7.7099361e-05
3,290	Efficient Resumption of Interrupted Warehouse Loads	2000	SIGMOD	7.4383411e-05
3,492	Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases	1996	SIGMOD	7.2390768e-05
3,518	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.2204376e-05
3,647	Efficient Bulk Insertion into a Distributed Ordered Table	2008	SIGMOD	7.1176467e-05
4,983	Safely and Efficiently Updating References During On-line Reorganization	1998	VLDB	6.3153393e-05
5,072	OODB Bulk Loading Revisited: The Partitioned-List Approach	1995	VLDB	6.2747182e-05
5,639	Principles of Transaction-Based On-Line Reorganization	1992	VLDB	6.0381153e-05
6,778	Compensation-Based On-Line Query Processing	1992	SIGMOD	5.6687058e-05
7,609	Efficient Data Ingestion and Query Processing for LSM-Based Storage Systems	2019	VLDB	5.46888e-05
7,979	Online B-Tree Merging	2005	SIGMOD	5.3978271e-05
8,137	On-line Reorganization in Object Databases	2000	SIGMOD	5.3739121e-05
8,373	Resumable Online Index Rebuild in SQL Server	2017	VLDB	5.3282795e-05
9,092	Repeating History Beyond ARIES	1999	VLDB	5.2088581e-05
11,429	MD-MVCC: Multi-version Concurrency Control for Schema Changes in Azure SQL Database	2025	VLDB	4.9605343e-05
13,104	Transaction support for indexed summary views	2004	SIGMOD	4.9605343e-05
13,238	Group Updates for Relaxed Height-Balanced Trees	1999	PODS	4.9605343e-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.0002420049
985	ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging	1992	SIGMOD	0.00012661135
2,059	Efficient and Flexible Methods for Transient Versioning of Records to Avoid Locking by Read-Only Transactions	1992	SIGMOD	9.0923662e-05
5,262	Commit LSN: A Novel and Simple Method for Reducing Locking and Latching in Transaction Processing Systems	1990	VLDB	6.1935451e-05

Semantically Similar Papers

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