nucleation

LIT-1095: An Online Approach to Physical Design Tuning

2 min read

Properties4
StatusActive — read in full 2026-10-15 from the accepted-version PDF that Microsoft Research's publication page for the paper links (www.microsoft.com/en-us/research/wp-content/uploads/2007/01/continuous.pdf, 10 pp., no IEEE pagination). The authors were both at MSR; Unpaywall, OpenAlex and Semantic Scholar list no open copy. Worth reading as the first model in the record that prices organizing ahead and organizing on demand on one schedule. It has a one-time build cost that depends on what is already built, per-statement savings, upkeep as the cost of update statements, a space limit, and a workload known only up to now. Its online rule builds an index once the benefit missed since the last low point equals the build cost, and drops it once the loss since the last high point equals the build cost. For QUESTION-114 it shows that the rule is rent-or-buy in structure but cites no competitive-analysis work, ski rental or Karlin et al. included. Its "three-competitive" result covers one index with no space limit, and is supported only by an example where the ratio approaches 3. By a check of my own it fails when a single statement's saving is large next to the build cost. The general case with space and interacting indexes is heuristic, dropping is free, there is no staleness or deadline, and all costs are optimizer estimates. For CASE-094 it endorses making a bin at once when the bin costs almost nothing, and adds a matching rule for removing one. For CLAIM-307 it replaces "carve when retrieval fails" with "carve when the extra search already spent equals the bin's cost": a cumulative-cost criterion with no deadline.
Tagsdatabases
Cited as “paper” byNOTE-896 — Bruno & Chaudhuri — An online approach to physical design tuning
Cited as “source” byTHEORY-332 — For one index with no space limit, Bruno and Chaudhuri's online tuner, which builds the index once the savings it would have given have risen by its build cost above their last low and drops it once they have fallen by the build cost below their last high, is not three-competitive: when every statement's saving or loss is at most a fraction f of the build cost, a repeated workload makes it cost nearly 3 + 2f times the offline optimum, and one statement whose saving exceeds the build cost makes the ratio unbounded; no upper bound is shown

Graph View

Bruno, N. and Chaudhuri, S. (2007). An online approach to physical design tuning. In Proceedings of the 23rd IEEE International Conference on Data Engineering (ICDE 2007), pp. 826–835. DOI 10.1109/ICDE.2007.367928

Key takeaways

Read in full (NOTE-896). An always-on index tuner for SQL Server. It keeps, for each candidate or existing index, the running sum of what each query would have saved with it (what-if optimizer estimates, with update costs counted as losses). It creates an index once that sum has risen by the index’s build cost above its lowest point, and drops it once the sum has fallen by the build cost from its highest point. For one index with no space limit, the authors call this 3-competitive against the optimal schedule that knows the workload in advance. The proof only gives a workload on which the ratio approaches 3, and the paper cites no competitive-analysis work, ski rental included. The general case (many interacting indexes and a storage limit) uses heuristics with no guarantee. All costs in the experiments are optimizer estimates, on synthetic and TPC-H workloads.

Why this is here

QUESTION-114: is sorting a collection amortized search, and does physical database design give the joint cost model the question on amortized retrieval lacks?

Backlinks