nucleation

LIT-1084: Physical database design for relational databases

2 min read

Properties4
StatusActive — read in full 2026-10-15 from the publisher's typeset PDF (ACM TODS 13(1), pp. 91–128), which ACM serves free at dl.acm.org/doi/pdf/10.1145/42201.42205 (bronze) but which refused requests from this environment (HTTP 403; the Internet Archive capture could not be fetched), so the copy was the same ACM PDF as posted by the University of Crete course CS-460 (www.csd.uoc.gr/~hy460/pdf/p91-finkelstein.pdf). Worth reading as the classic statement of index selection as a workload-weighted cost model: one clustered order per table ("records can be ordered only one way") plus secondary indices, chosen to minimise the weighted sum of access, tuple-update and index-maintenance costs plus weighted storage under a page limit, with every cost taken from the optimizer's own estimates; exact over atomic configurations and optimal only relative to those estimates, with heuristic pruning and no measurement of actual execution. For QUESTION-114 it supplies the joint model for standing arrangements (bins, filed items), but it has no term for the one-time cost of sorting or building an index and does not cover precomputed answers (speed bugs, reused inferences); for CLAIM-310 it is an instance of "one arrangement" and of dependence on the query mix, has no analogue of a bin budget k, and nothing corresponding to pop-out within a bin.
Tagsdatabases, operations-research
Cited as “paper” byNOTE-898 — Finkelstein, Schkolnick & Tiberio — Physical database design for relational databases
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

Finkelstein, S., Schkolnick, M. and Tiberio, P. (1988). Physical database design for relational databases. ACM Transactions on Database Systems 13(1), 91–128. DOI 10.1145/42201.42205

Key takeaways

Read in full (NOTE-898). DBDSGN chooses, for each table, one clustered (ordering) index and a set of nonclustered indices to minimise a frequency-weighted sum of per-statement costs (access, tuple update, index maintenance) plus a weighted storage term, under an optional page limit, taking every cost from the System R optimizer’s own estimates rather than an external model. Statement costs for any configuration are computed exactly from “atomic” configurations with at most one index per table (Propositions 1 and 2), so the optimizer is consulted a linear rather than exponential number of times per table; with no elimination heuristics and a full search the tool finds the optimum, but only with respect to the optimizer’s estimates. The paper gives one worked example and no measurement of actual execution, and its claims that the heuristics usually find the best solutions are not backed by reported data. The model is steady-state over a period: it has no term for the one-time cost of building an index or sorting a table, so it prices upkeep against retrieval, not a one-off sort against later retrievals.

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