When an index beats a scan

How it behaves

One input on the horizontal axis, the others held fixed.

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

• 10⁶ pages, s = 1, r = 4 → k < 250,000 rows (0.25%)
• r = 1.1 on NVMe → ≈ 909,000 rows (0.9%)
• 8 million rows × 4 = 32,000,000 units against 1,000,000
• row for row with 1.0 and 4.0 → 25%
• 100 rows per page, c_rand/c_seq = 4 → 0.25%
• sequential 1, scattered 5 per MB → crossover at s = 0.2
• delta rows 10× a scanned row → break-even at 10% of the base

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

• Indexing

  When does a separate "where is it?" structure pay for itself, and what does it cost to keep it true?

  $$k\cdot r<N\cdot s\to k/N<s/r$$

  Read it in place →

• Query Planning & Optimization

  How does a system choose a plan for a question when the facts that decide the best plan are unknown until the plan has run?

  $$s^{\ast }\approx \frac{P\times c_{\text{seq}}}{n\times c_{\text{rand}}}=\frac{1}{\text{rows per page}}\times \frac{c_{\text{seq}}}{c_{\text{rand}}}$$

  c_seq = $s$ · c_rand = $r$ · P (pages) = $N$

  Read it in place →

• Query Planning & Optimization

  How does a system choose a plan for a question when the facts that decide the best plan are unknown until the plan has run?

  $$\text{late wins when }s\times c_{\text{scattered}}<c_{\text{sequential}}$$

  s (selectivity) = $k/N$ · scattered fetch cost = $r$ · sequential decode cost = $s$

  Read it in place →

• Caching

  What happens when we deliberately keep a second copy of data that no protocol forces to be correct?

  $$\text{incremental wins when }d\cdot c_{\text{random}}<B\cdot c_{\text{seq}}$$

  d (delta rows) = $k$ · B (base rows) = $N$

  Read it in place →