Secondary Index Optimization

Summary: Proposes a probabilistic model of transactions (queries/updates) to optimize secondary index selection. Derives optimality characterizations and an O(m log m) algorithm (m = attributes) that computes index configurations efficiently. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2082
Venue: SIGMOD
Year: 1975
Pagerank: 5.4346419e-05
Overall Rank: 8,337 | 43.00%
DOI: 10.1145/500080.500106

Incoming Non-self Citations Over Time

Authors

1. Mario Schkolnick (Carnegie Mellon University)

BibTeX Citation

@inproceedings{schkolnick_sigmod75,
        title = {{SECONDARY INDEX OPTIMIZATION}},
        author = {Schkolnick, Mario},
        series = {{SIGMOD} '75},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/500080.500106},
        url = {https://dl.acm.org/doi/10.1145/500080.500106},
        year = {1975}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
13,336	Database Cost Analysis: a Top-Down Approach	1977	SIGMOD	5.0723324e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	156	An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server	1997	VLDB
2	929	Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates	1992	SIGMOD
3	861	Index Selection in a Self-Adaptive Data Base Management System	1976	SIGMOD
4	3,033	On Index Selection Schemes for Nested Object Hierarchies	1994	VLDB
5	1,491	Magic mirror in my hand, which is the best in the land? An Experimental Evaluation of Index Selection Algorithms	2020	VLDB
6	796	Bitmap Index Design and Evaluation	1998	SIGMOD
7	1,516	On the Analysis of Indexing Schemes	1997	PODS
8	2,016	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS
9	12,543	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS
10	6,786	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS