nucleation

LIT-1089: The optimal selection of secondary indices is NP-complete

1 min read

Properties4
StatusActive — read in full 2026-10-15 from the scan SIGMOD serves openly on sigmodrecord.org (sigmodrecord.org/publications/sigmodRecord/8301/pdfs/984523.984530.pdf, linked from the January 1983 issue page), 4 pp., printed pages 72–75; the ACM Digital Library refused requests from this environment, and Unpaywall and OpenAlex list no open copy. Worth reading as the first proof that choosing secondary indexes for a known mix of queries and updates, to minimize average transaction cost, is NP-hard, by a half-page reduction from minimum set cover: attributes are the sets, queries the elements, and each index pays a fixed upkeep on updates. For QUESTION-114 it shows that the trade of upkeep against per-query savings under a known workload can be stated exactly and cannot be solved exactly in general, but only as the number of attributes and query types grows; storage, build cost and the file's own order are outside its model, and it does not mention Comer 1978 (LIT-1086), so it is the citation for workload-based hardness and says nothing about what Comer proved.
Tagsdatabases, mathematics
Cited as “paper” byNOTE-902 — Piatetsky-Shapiro — The optimal selection of secondary indices is NP-complete
Cited as “source” byTHEORY-345 — Choosing indexes for a known mix of queries and updates, to minimize query cost plus a per-index upkeep, is NP-hard as the number of attributes and query types grows, and the tools built for it choose one stored order and a set of secondary indexes per table by searching configurations costed with the query optimizer's own estimates, optimal at best relative to those estimates, with no proved guarantee for their heuristics and no term for the one-time cost of building

Graph View

Piatetsky-Shapiro, G. (1983). The optimal selection of secondary indices is NP-complete. ACM SIGMOD Record 13(2), 72–75. DOI 10.1145/984523.984530

Key takeaways

Read in full (NOTE-902). For one relation, a known mix of equality queries and updates, single-attribute secondary indexes, and a fixed upkeep charge per index on each update, choosing the index set that minimizes average transaction cost is NP-hard: minimum set cover reduces to it, each subset becoming an attribute and each element a query that any one of its attributes’ indexes can answer. The paper calls the problem NP-complete but states only the optimization version, and the proof is a sketch of about half a page. Storage is not in the model; the only price of an index is upkeep on updates. A variant with off-line updates under an update-cost budget is asserted NP-complete without proof. The paper does not cite or discuss Comer 1978.

Why this is here

QUESTION-114 cited Comer 1978 for “optimal index selection is NP-complete”. Comer could not be obtained, and a secondary account says it proves something else. This paper is the candidate for the workload-based result.

Backlinks