nucleation

LIT-1083: An Efficient, Cost-Driven Index Selection Tool for Microsoft SQL Server

2 min read

Properties4
StatusActive — read in full 2026-10-15 from the VLDB Endowment's proceedings PDF (www.vldb.org/conf/1997/P146.PDF, pp. 146–155, a scan with an OCR layer; tables and figures read from page images), which refuses plain requests from this environment (HTTP 403) and was served when the request carried a browser User-Agent. Worth reading as the founding paper of optimizer-driven ("what-if") index selection in practice: at most k indexes chosen for a fixed workload of SQL statements to minimise the unweighted sum of the optimizer's estimated costs, made affordable by per-query candidate selection, Greedy(m, k) enumeration with an exhaustive seed, derived costs from atomic configurations, and two-column indexes grown from single-column winners (4–10 times faster than a baseline, 0–7% worse by estimated cost, on five TPC-D workloads). For QUESTION-114 it prices organizing ahead no differently from Finkelstein et al. (LIT-1084), and in fewer terms: upkeep through the workload's update statements, but no build cost, no storage term, no frequency weights and no changing workload, so "paid once" and staleness stay unpriced; what it adds is that deciding the arrangement has its own cost, and evidence (not a bound) that greedy choice works when index interactions are few and local. For CLAIM-310 it is consistent with the dependence on the query mix by construction and says nothing about what stands out within a bin; its heuristics (consider only sortings best for some search, choose the first carefully and add the rest greedily) carry over to a builder's bins only by analogy.
Tagsdatabases, operations-research
Cited as “paper” byNOTE-900 — Chaudhuri & Narasayya — An efficient, cost-driven index selection tool for Microsoft SQL Server
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

Chaudhuri, S. and Narasayya, V. (1997). An efficient, cost-driven index selection tool for Microsoft SQL Server. In Proceedings of the 23rd International Conference on Very Large Data Bases (VLDB ‘97), pp. 146–155. https://www.vldb.org/conf/1997/P146.PDF

Key takeaways

Read in full (NOTE-900). The AutoAdmin tool picks at most k indexes (single- or two-column, clustered or not) for a given workload of SQL statements, minimising the unweighted sum of the optimizer’s estimated costs of those statements, with hypothetical (“what-if”) indexes made visible to the optimizer by loading their statistics into the catalog. Its contribution is search efficiency: candidates are restricted to indexes in some single query’s best configuration, enumeration is Greedy(m, k) (an exhaustive seed of m indexes, then greedy additions), costs of most configurations are derived from a few “atomic” ones, and two-column indexes are generated only from winning single columns. On five TPC-D workloads this cut running time to 10–24% of a baseline, with estimated-cost quality 0–7% worse, and Greedy(2, 4) matched the exhaustive optimum on four of five workloads and was within 1% on the fifth. The cost model has no build cost, no storage term and no frequency weights, the budget is a count of indexes, the workload is fixed, there is no guarantee for the greedy step, and quality is never measured by executing anything.

Why this is here

QUESTION-114: the practice of workload-driven index selection, after the theory read so far (Finkelstein et al. 1988, Piatetsky-Shapiro 1983).

Backlinks