What indexing strategies improve database performance?

// One orders table, several index designs. We count the work each design costs:
// index entries read, and heap fetches (jumps from an index entry to the table row).
let seed = 7;
function rand(n) { seed = (seed * 48271) % 2147483647; return seed % n; }

const rows = [];
for (let id = 0; id < 100000; id++) {
  const r = rand(100);
  const status = r < 2 ? "open" : r < 30 ? "paid" : "shipped";
  rows.push({ id, tenant: 1 + rand(200), day: rand(365), status, amount: 1 + rand(500) });
}

function cmp(a, b) {
  for (let i = 0; i < a.length; i++) { if (a[i] < b[i]) return -1; if (a[i] > b[i]) return 1; }
  return 0;
}
// An index is a sorted list of [key columns..., row id], built only over rows that pass `where`.
function makeIndex(cols, where = () => true) {
  const entries = rows.filter(where).map((r) => [...cols.map((c) => r[c]), r.id]);
  entries.sort(cmp);
  return entries;
}
function lowerBound(idx, prefix) {
  let lo = 0, hi = idx.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    if (cmp(idx[mid].slice(0, prefix.length), prefix) < 0) lo = mid + 1; else hi = mid;
  }
  return lo;
}
// Seek to `start`, read entries while `inRange` holds, keep those passing `filter`.
// heap: "none" (covering), "hits" (fetch matching rows), "all" (filter needs a column the index lacks).
function scan(idx, start, inRange, filter, heap) {
  let read = 0, fetched = 0, hits = 0;
  for (let i = lowerBound(idx, start); i < idx.length && inRange(idx[i]); i++) {
    read++;
    if (heap === "all") fetched++;
    if (filter(idx[i])) { hits++; if (heap === "hits") fetched++; }
  }
  return { read, fetched, hits };
}
const show = (name, r) => console.log(`  ${name.padEnd(36)} entries=${String(r.read).padStart(6)} heap_fetches=${String(r.fetched).padStart(6)} rows=${r.hits}`);

console.log("Q1: SELECT day, amount FROM orders WHERE tenant = 42 AND day >= 300 ORDER BY day");
let hits = rows.filter((r) => r.tenant === 42 && r.day >= 300).length;
console.log(`  ${"no index (full table scan)".padEnd(36)} rows_read=${rows.length} rows=${hits}  (then sort)`);
const byTenant = makeIndex(["tenant"]);
show("INDEX (tenant)", scan(byTenant, [42], (e) => e[0] === 42, (e) => rows[e[1]].day >= 300, "all"));
const tenantDay = makeIndex(["tenant", "day"]);
show("INDEX (tenant, day)", scan(tenantDay, [42, 300], (e) => e[0] === 42, () => true, "hits"));
const dayTenant = makeIndex(["day", "tenant"]);
show("INDEX (day, tenant)  wrong order", scan(dayTenant, [300], () => true, (e) => e[1] === 42, "hits"));
const covering = makeIndex(["tenant", "day", "amount"]);
show("INDEX (tenant, day) INCLUDE (amount)", scan(covering, [42, 300], (e) => e[0] === 42, () => true, "none"));

console.log("\nQ2: SELECT * FROM orders WHERE day = 100   (leftmost-prefix rule)");
show("INDEX (tenant, day): no seek on day", scan(tenantDay, [], () => true, (e) => e[1] === 100, "hits"));
let skip = { read: 0, fetched: 0, hits: 0 };
for (let t = 1; t <= 200; t++) { // skip scan: one seek per distinct leading value
  const r = scan(tenantDay, [t, 100], (e) => e[0] === t && e[1] === 100, () => true, "hits");
  skip = { read: skip.read + r.read, fetched: skip.fetched + r.fetched, hits: skip.hits + r.hits };
}
show("INDEX (tenant, day) + skip scan", skip);
console.log("  (the skip scan made 200 seeks, one per distinct tenant)");
show("INDEX (day, tenant)", scan(dayTenant, [100], (e) => e[0] === 100, () => true, "hits"));

console.log("\nQ3: SELECT * FROM orders WHERE status = 'open' ORDER BY day");
const byStatus = makeIndex(["status", "day"]);
const partial = makeIndex(["day"], (r) => r.status === "open");
show("INDEX (status, day)", scan(byStatus, ["open"], (e) => e[0] === "open", () => true, "hits"));
show("INDEX (day) WHERE status = 'open'", scan(partial, [], () => true, () => true, "hits"));
console.log(`  index sizes: full=${byStatus.length} entries, partial=${partial.length} entries`);

console.log("\nQ4: is the index worth using? (selectivity decides)");
const PAGES = rows.length / 20; // about 20 rows per 8 kB page
const preds = [
  ["id = 12345", (r) => r.id === 12345],
  ["tenant = 42", (r) => r.tenant === 42],
  ["status = 'open'", (r) => r.status === "open"],
  ["status = 'shipped'", (r) => r.status === "shipped"],
];
for (const [label, pred] of preds) {
  const n = rows.filter(pred).length;
  const seqCost = PAGES * 1.0; // read every page in order: seq_page_cost = 1
  const idxCost = n * 4.0;     // worst case one random page per match: random_page_cost = 4
  const pick = idxCost < seqCost ? "index scan" : "sequential scan";
  console.log(`  ${label.padEnd(19)} matches=${String(n).padStart(5)} (${(100 * n / rows.length).toFixed(2).padStart(5)}%)  seq=${seqCost}  index=${String(idxCost).padStart(6)}  -> ${pick}`);
}

console.log("\nQ5: cost of one INSERT as indexes pile up (each index is one more B-tree to update)");
const counts = [0, 1, 3, 6];
console.log("  " + counts.map((k) => `${k} indexes: ${1 + k} writes`).join(", "));