Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases

Summary: Two online index-modification techniques for shared-nothing DBs: OAT (one-at-a-time) and BULK (bulk). BULK: order-of-magnitude faster with sequential prefetch I/O; OAT uses ≤1 extra page; with 1–2 indexes OAT preserves transactional performance; for >2 indexes both degrade similarly. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2939
Venue: SIGMOD
Year: 1996
Pagerank: 7.430628e-05
Overall Rank: 3,416 | 76.57%
DOI: 10.1145/233269.233326

Incoming Non-self Citations Over Time

Authors

1. Kiran J. Achyutuni (Informix)
2. Edward Omiecinski (Georgia Institute of Technology)
3. Shamkant B. Navathe (Georgia Institute of Technology)

BibTeX Citation

@inproceedings{achyutuni_sigmod96,
        title = {{Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases}},
        author = {Achyutuni, Kiran J. and Omiecinski, Edward and Navathe, Shamkant B.},
        series = {{SIGMOD} '96},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/233269.233326},
        url = {https://dl.acm.org/doi/10.1145/233269.233326},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,508	Sorting And Indexing With Partitioned B-Trees	2003	CIDR	0.00010540965
1,852	Automated Partitioning Design in Parallel Database Systems	2011	SIGMOD	9.6134443e-05
3,454	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.4001286e-05
4,839	Safely and Efficiently Updating References During On-line Reorganization	1998	VLDB	6.4838601e-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,075	Online Reorganization in Read Optimized MMDBS	2011	SIGMOD	5.4929858e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 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
924	Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates	1992	SIGMOD	0.00013185068
5,428	Dynamic File Allocation in Disk Arrays	1991	SIGMOD	6.2222186e-05
5,493	Principles of Transaction-Based On-Line Reorganization	1992	VLDB	6.1999067e-05
7,688	Incremental File Reorganization Schemes	1985	VLDB	5.5671639e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	471	Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems	2012	SIGMOD
2	1,334	Improving Optimistic Concurrency Control Through Transaction Batching and Operation Reordering	2019	VLDB
3	3,837	Database Buffer Size Investigation for OLTP Workloads	1997	SIGMOD
4	8,641	Automatic Workload Driven Index Defragmentation	2011	VLDB
5	5,903	Concurrency Control for Adaptive Indexing	2012	VLDB
6	9,324	Main-Memory Operation Buffering for Efficient R-Tree Update	2007	VLDB
7	1,901	A Generic Approach to Bulk Loading Multidimensional Index Structures	1997	VLDB
8	10,067	Shared Load(ing): Efficient Bulk Loading into Optimized Storage	2020	CIDR
9	5,304	An Evaluation of Generic Bulk Loading Techniques	2001	VLDB
10	964	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD