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: 2671
Venue: SIGMOD
Year: 1992
Pagerank: 0.00013185068
Overall Rank: 924 | 93.67%
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,508	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00010540965
1,676	Feeding Frenzy: Selectively Materializing Users' Event Feeds	2010	SIGMOD	0.00010034449
2,966	Asynchronous View Maintenance for VLSD Databases	2009	SIGMOD	7.9152992e-05
2,968	On-line Reorganization of Sparsely-populated B+-trees	1996	SIGMOD	7.9149281e-05
3,220	Efficient Resumption of Interrupted Warehouse Loads	2000	SIGMOD	7.6272892e-05
3,416	Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases	1996	SIGMOD	7.430628e-05
3,454	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.4001286e-05
3,566	Efficient Bulk Insertion into a Distributed Ordered Table	2008	SIGMOD	7.303217e-05
4,839	Safely and Efficiently Updating References During On-line Reorganization	1998	VLDB	6.4838601e-05
4,928	OODB Bulk Loading Revisited: The Partitioned-List Approach	1995	VLDB	6.4425753e-05
5,493	Principles of Transaction-Based On-Line Reorganization	1992	VLDB	6.1999067e-05
6,622	Compensation-Based On-Line Query Processing	1992	SIGMOD	5.820664e-05
7,459	Efficient Data Ingestion and Query Processing for LSM-Based Storage Systems	2019	VLDB	5.6119467e-05
7,804	Online B-Tree Merging	2005	SIGMOD	5.5415082e-05
7,944	On-line Reorganization in Object Databases	2000	SIGMOD	5.5181056e-05
8,194	Resumable Online Index Rebuild in SQL Server	2017	VLDB	5.469529e-05
9,357	Repeating History Beyond ARIES	1999	VLDB	5.2827941e-05
10,994	MD-MVCC: Multi-version Concurrency Control for Schema Changes in Azure SQL Database	2025	VLDB	5.093636e-05
12,767	Transaction support for indexed summary views	2004	SIGMOD	5.093636e-05
12,901	Group Updates for Relaxed Height-Balanced Trees	1999	PODS	5.093636e-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
214	ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes	1990	VLDB	0.00024680756
958	ARIES/IM: An Efficient and High Concurrency Index Management Method Using Write-Ahead Logging	1992	SIGMOD	0.00012956148
2,081	Efficient and Flexible Methods for Transient Versioning of Records to Avoid Locking by Read-Only Transactions	1992	SIGMOD	9.2021976e-05
5,119	Commit LSN: A Novel and Simple Method for Reducing Locking and Latching in Transaction Processing Systems	1990	VLDB	6.3577506e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,020	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB
2	1,901	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB
3	7,768	The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures	2022	VLDB
4	9,576	Indexing Highly Dynamic Hierarchical Data	2015	VLDB
5	964	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD
6	1,811	Merging What's Cracked, Cracking What's Merged: Adaptive Indexing in Main-Memory Column-Stores	2011	VLDB
7	8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
8	2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS
9	5,903	Concurrency Control for Adaptive Indexing	2012	VLDB
10	1,508	Sorting And Indexing With Partitioned B-Trees	2003	CIDR