Index Selection

Formally, let a workload $W = \{Q_1, \dots, Q_n\}$ be a set of representative queries and updates, each with an associated frequency or weight $w_i$ reflecting how often it runs. Let $\mathcal{C} = \{I_1, \dots, I_m\}$ be a set of candidate indexes — physical structures (B+-tree or hash) that could be built on some table's column or column combination. For any subset $S \subseteq \mathcal{C}$ of indexes actually materialized, define $\text{cost}(Q_i, S)$ as the estimated execution cost of query $Q_i$ when exactly the indexes in $S$ exist. The index selection problem is:

subject to a storage budget $B$ on total index size. Notice that $\text{cost}(Q_i, S)$ already folds in update overhead: if $Q_i$ is an `INSERT`/`UPDATE`/`DELETE`, its cost includes maintaining every index in $S$ that covers the modified table, so the objective automatically penalizes over-indexing for write-heavy workloads. This is why index selection cannot be solved by looking at read queries alone — the objective function must be workload-wide, spanning both queries and updates, weighted by relative frequency. The distinctive difficulty of this problem, compared to a textbook Cost Comparison of File Organizations exercise, is that $\text{cost}(Q_i, S)$ is not a closed-form function — it is whatever the query optimizer's cost model says the optimal plan for $Q_i$ costs, given that the indexes in $S$ are available access paths. Evaluating it requires either building the index (too expensive to do for every candidate) or asking the optimizer to simulate having it. This simulation capability is called what-if analysis: the optimizer is given hypothetical index metadata (cardinality, clustering factor, height) without the index existing on disk, and it returns the plan and cost it would choose. What-if analysis is what makes index selection computationally feasible: it decouples "does this index help" from "actually building it and measuring."

A practical index selection pipeline has four stages: workload capture, candidate generation, cost evaluation (what-if), and search over subsets. Each stage prunes or estimates so the final combinatorial search operates on a small, well-scored candidate set rather than the astronomically large space of all possible indexes.

1. Workload capture. The system logs a representative sample of queries and updates over some observation window, along with their execution frequency (or the DBA supplies a synthetic workload). Each query is parsed to identify which columns appear in `WHERE` predicates, join conditions, `ORDER BY`, and `GROUP BY` clauses — these are the only columns for which an index can plausibly help, drastically narrowing the search.

2. Candidate generation. For each query, generate candidate indexes on:

• single columns used in equality or range predicates,
• column combinations used in multi-column predicates or joins (as composite indexes, in the order that maximizes prefix matching),
• covering indexes that include all columns referenced by a query, avoiding a table lookup entirely.

This yields a candidate set $\mathcal{C}$ typically of size linear in the workload size times a small constant, not the exponential set of all column subsets.

3. What-if cost evaluation. For each candidate index $I_j$ and each query $Q_i$, invoke the optimizer's cost estimator with $I_j$'s statistics hypothetically injected into the catalog. The optimizer returns $\text{cost}(Q_i, \{I_j\})$, the cost of the best plan assuming only $I_j$ exists (in addition to indexes already present). Define the benefit of $I_j$ for query $Q_i$ as

and weight by frequency to get workload-level benefit $\sum_i w_i \cdot \text{benefit}(I_j, Q_i)$.

4. Search over subsets. Given benefits (and interaction effects among indexes — an index can also make other indexes redundant, or a composite index can subsume a single-column one), search for the subset $S$ maximizing net benefit under the storage budget $B$. This is the step where the combinatorics bite, and where the greedy algorithm below is the workhorse.

The greedy algorithm

The key structural fact exploited by every practical index selection algorithm is that the benefit function exhibits diminishing returns: adding an index to an already-large set of indexes helps less than adding it to a small set, because some queries are already well-served. Formally, the total benefit function

is (approximately) monotone and submodular: $f(S \cup \{I\}) - f(S) \geq f(T \cup \{I\}) - f(T)$ whenever $S \subseteq T$. This licenses a greedy strategy: repeatedly add the index with the highest marginal benefit per unit storage, until the budget is exhausted. ``` ALGORITHM GreedyIndexSelection(candidates C, workload W, budget B) S ← ∅ // selected index set remainingBudget ← B while remainingBudget > 0 and C ≠ ∅: best ← null bestRatio ← -∞ for each candidate I in C: if size(I) > remainingBudget: continue // cannot afford it // marginal benefit of adding I to current set S gain ← 0 for each (query Qi, weight wi) in W: gain ← gain + wi ( cost(Qi, S) - cost(Qi, S ∪ {I}) ) ratio ← gain / size(I) // benefit per unit storage if gain > 0 and ratio > bestRatio: bestRatio ← ratio best ← I if best = null: break // no beneficial candidate left S ← S ∪ {best} remainingBudget ← remainingBudget − size(best) C ← C − {best} return S ``` Each iteration of the outer loop calls the what-if cost estimator once per remaining candidate per query — this is the expensive step, since `cost(Qi, S)` invokes the query optimizer. Systems cache these calls aggressively and often approximate `cost(Qi, S ∪ {I})` using only $I$'s marginal* effect rather than re-optimizing the whole query from scratch, using atomic configurations: precompute $\text{cost}(Q_i, \{I\})$ once for every single candidate $I$ in isolation, then approximate the cost under a larger set $S$ by taking, for each query, the best single index in $S$ that helps it (a reasonable approximation because most queries are dominated by one index, though it can miss multi-index plans like index intersection).

Knapsack framing

When index interactions are ignored entirely (each index's benefit is independent of which other indexes exist), index selection reduces exactly to the 0/1 knapsack problem: each candidate $I_j$ has a "weight" $\text{size}(I_j)$ and a "value" $\text{benefit}(I_j) = \sum_i w_i \cdot \text{benefit}(I_j, Q_i)$, and we want to maximize total value subject to total weight $\le B$. This connection matters because it tells us precisely how hard the problem is (0/1 knapsack is NP-hard, but has a pseudo-polynomial dynamic program and excellent approximation schemes) and licenses borrowing knapsack solvers — dynamic programming for small budgets, or greedy-by-ratio with a known worst-case bound — whenever interaction effects are weak enough to ignore.

Hardness. The decision version of index selection — "does there exist $S \subseteq \mathcal{C}$ with $\text{size}(S) \le B$ and total cost $\le K$?" — is NP-hard in general. This follows by reduction from weighted set cover: treat each query as an element to be "covered" and each candidate index as covering the set of queries it speeds up past some threshold; choosing a minimum-cost covering set of indexes is exactly weighted set cover, a canonical NP-hard problem. Even the simplified independent-benefit version reduces to 0/1 knapsack (also NP-hard, though only weakly so — it has a pseudo-polynomial DP). So no polynomial-time algorithm is known to find the exact optimum for large instances, and none is expected to exist unless P = NP.

Why greedy is used anyway — the submodularity argument. Although exact optimization is intractable, the benefit function $f(S)$ is monotone ($f(S) \le f(T)$ whenever $S \subseteq T$, since more indexes never hurt query cost — ignoring, for the moment, update overhead) and, when index effects on queries don't strongly interact, submodular: the marginal gain of adding any index shrinks as the current set grows. This is the same structural property behind Buffer Management replacement heuristics and greedy set-cover approximations. For monotone submodular maximization under a cardinality or knapsack constraint, a classical result (Nemhauser–Wolsey–Fisher, 1978) guarantees:

for the cardinality-constrained case, and a similar constant-factor guarantee holds for the budgeted (knapsack) version when the greedy ratio rule (benefit divided by size) is combined with an exhaustive check over small solutions of size 1–3. The proof sketch: let $S_k$ be the greedy solution after $k$ steps and $S^*$ be optimal. Because $S^*$ has at most $k$ elements not yet in $S_k$, and by submodularity each of those elements would contribute at least as much marginally to $S_k$ as it does to smaller sets, one shows $f(S^*) - f(S_k) \le k \cdot (f(S_{k+1}) - f(S_k))$. Unrolling this recursion across all $k$ steps yields the $(1-1/e)$ bound. This is the same guarantee that justifies greedy algorithms for influence maximization and sensor placement — index selection is a direct application of that general theory.

Where the guarantee breaks. The bound assumes true submodularity, but real index benefit functions are only approximately submodular: two indexes can be strictly complementary (an index-only "covering" plan needs both a filter index and included columns; neither alone gives the covering benefit) which can violate the diminishing-returns assumption locally. Update overhead also violates pure monotonicity — adding an index to $S$ can increase total workload cost once write costs dominate, so the objective used in practice is net benefit (read benefit minus write penalty), which is not monotone, and the theoretical guarantee applies only to the read-benefit component, not the full net objective. Practical advisors therefore treat the greedy output as a strong heuristic starting point, then apply local search (swap one index for another, check if net benefit improves) to patch violations.

Complexity of the algorithm itself. With $n$ queries, $m$ candidates, and greedy selecting up to $k \le m$ indexes:

• Each outer iteration scans all remaining candidates: $O(m)$.
• For each candidate, computing marginal gain costs $O(n)$ optimizer calls (one per query), each call assumed $O(P)$ for a cost estimate over plan space of typical size (treated as a constant per query in practice, though real optimizers are themselves exponential in join count without pruning).
• Total: $O(k \cdot m \cdot n)$ what-if cost evaluations.

With workload sizes in the hundreds and candidate sets pruned to tens or low hundreds, this is entirely tractable — the real engineering cost is minimizing redundant optimizer invocations via caching atomic-configuration costs, not the asymptotic complexity itself.

Space. Each what-if index requires only its catalog statistics (estimated cardinality, distinct values, clustering factor, tree height) to be stored, not the index itself — this is the entire point of what-if analysis, and it means the memory footprint of the search is $O(m)$ small metadata records, not $O(m)$ full index structures.

Consider a simplified workload on a table `orders(order_id, customer_id, order_date, amount)` with 1,000,000 rows, and a storage budget $B = 3$ units (each candidate index below costs exactly 1 unit to store, for simplicity).

Workload (query, weight = executions per hour):

Candidates (generated from predicate columns):

Baseline cost with no indexes (full table scans, in abstract page-I/O units): $\text{cost}(Q_1, \emptyset) = 10{,}000$, $\text{cost}(Q_2, \emptyset) = 10{,}000$, $\text{cost}(Q_3, \emptyset) = 10{,}000$ (an update still must scan to find `order_id` without a primary-key index — assume none exists), $\text{cost}(Q_4, \emptyset) = 10{,}000$. What-if evaluation gives per-query costs under each single candidate (illustrative estimator outputs, consistent with B+-tree lookup costs of $O(\log_F N)$ for a fan-out $F$ tree on 1M rows, roughly 20–50 I/Os per lookup, versus 10,000 for a scan):

Note $Q_3$'s cost increases slightly under $I_1$ or $I_3$ because every update must also maintain the index — this is the update-overhead term baked directly into the what-if cost, exactly as the objective requires.

Step 1 — compute weighted net benefit for each candidate alone:

Step 2 — greedy ratio (size = 1 for all, so ratio = benefit): $I_3 > I_1 > I_2$. Greedy picks $I_3$ first, spending 1 of 3 units.

Step 3 — recompute marginal benefit of remaining candidates given $S = \{I_3\}$. Since $I_3$ already answers $Q_1$, $Q_2$, and $Q_4$ nearly optimally (30, 200, 150 respectively — a composite index on `(customer_id, order_date)` serves an equality-then-range predicate and, via prefix matching, a pure `customer_id` equality too), adding $I_1$ or $I_2$ now yields almost no marginal benefit for $Q_1, Q_2, Q_4$ — this is exactly the diminishing-returns (submodularity) effect. The only remaining potential gain is nothing, since $I_3$'s composite key already gives a leading-column match for $I_1$'s workload ($Q_1$) at the same cost as $I_1$ alone (30), and a full match for $Q_2$-style range scans is not achievable via $I_3$ if $Q_2$'s predicate doesn't touch `customer_id` — but our what-if table already shows $I_3$ costs $Q_2$ only 200, matching $I_2$ alone, because the composite index's leading column can still be range-scanned when queries provide both columns or, in this case, the optimizer chose to scan the `order_date` range within the composite tree. Marginal benefit of adding $I_1$ given $S=\{I_3\}$: $\approx 0$ (no query improves further). Marginal benefit of adding $I_2$: $\approx 0$ similarly. Greedy terminates early, returning $S = \{I_3\}$, having used only 1 of 3 budget units — because a single well-chosen composite index dominates two narrower ones for this workload. Total achieved cost:

versus the no-index baseline of $500(10000)+300(10000)+50(10000)+200(10000) = 10{,}500{,}000$ — roughly a 17× workload cost reduction using a single index, illustrating why identifying the right composite candidate (not just single-column ones) is often more valuable than adding more indexes.

Every major relational database ships an automated index-tuning tool built on the pipeline described here. Microsoft SQL Server's Database Engine Tuning Advisor captures a query trace, generates candidate indexes and indexed views, and uses the optimizer's own what-if mode to score them before recommending a configuration. IBM Db2's Design Advisor extends the same machinery to jointly select indexes, materialized query tables, and partitioning schemes. Oracle's SQL Tuning Advisor and Partition Advisor apply analogous what-if costing during automatic workload analysis. Cloud data warehouses such as Amazon Redshift and Google BigQuery apply related automated physical-design logic (sort keys, distribution keys, clustering) to workloads at petabyte scale, where the storage-budget tradeoff becomes a real dollar cost, not just disk capacity. Beyond relational systems, the same submodular-greedy machinery underlies materialized-view selection in OLAP cubes, cache-placement decisions in content delivery networks, and column-store projection design — anywhere a system must choose a bounded set of auxiliary structures to minimize workload cost. Understanding index selection also deepens intuition for Clustered vs Unclustered Indexes, since the choice of which column to cluster on interacts directly with which secondary indexes are worth building, and for Buffer Management, since indexes compete with data pages for the same finite buffer pool.

Ask the tutor: How would index selection change if two candidate indexes are strongly complementary — i.e., a query only speeds up when both are present together?