跳到主要內容
Jasonmel Online

系統設計

把資料結構放大到好幾台機器

主題 · 資料庫查詢執行計畫

資料庫查詢執行計畫

同一句 SQL，資料庫可以用很多種方式執行：全表掃描還是走索引、巢狀迴圈、雜湊還是合併連接（JOIN）。執行計畫說明它實際選了哪一種、讀了多少資料，也解釋為什麼加一個索引能快上千倍，或完全沒用。

查詢
索引
SELECT * FROM orders WHERE user_id = 42;
規劃器考慮過的每一種計畫，以及各自實際要花多少
計畫估計成本實際成本估計列數實際列數
Seq Scan30030059
Index Scan ✓ 選用284459
選用的計畫：資料由下往上流，從掃描一路到最上層
  • Index Scan using orders_user_id on orders
    Index Cond: (user_id = 42)
    估計 5 列 · 28 → 實際 9 列 · 44

規劃器估計每一種計畫的成本，挑最便宜的：Index Scan，估計 28、實際 44。次佳的是 Seq Scan，估計 300。 索引只讀幾頁就找到使用者 42 的訂單，不必讀完整張表 200 頁。估計是 5 列（每位使用者的平均訂單數），這位實際有 9 列。

EXPLAIN ANALYZE
Index Scan using orders_user_id on orders  (cost=27.85 rows=5) (actual cost=44.09 rows=9)
  Index Cond: (user_id = 42)
  Pages: 0 sequential, 11 random

users 有 2,000 列、orders 有 10,000 列，每頁 50 列；主鍵一定有索引。成本用 PostgreSQL 的單位：循序讀一頁 1、隨機讀一頁 4、處理一列 0.01。規劃器的統計資料是精確的，估計只會在「假設值平均分布」的地方失準。

亮起來的是這一步執行的程式碼
type Row = number[];
type Entry = [key: number, row: number];
 
const SEQ_PAGE = 1, RANDOM_PAGE = 4, TUPLE = 0.01;
const ROWS_PER_PAGE = 50, FANOUT = 100;
 
function seqScan(table: Row[], pred: (r: Row) => boolean): Row[] {
  const out: Row[] = [];
  for (const r of table) if (pred(r)) out.push(r);
  return out;
}
 
// Rows whose key is in [lo, hi): binary search to the first, then walk right.
function indexScan(index: Entry[], table: Row[], lo: number, hi: number): Row[] {
  let a = 0, b = index.length;
  while (a < b) {
    const mid = (a + b) >> 1;
    if (index[mid][0] < lo) a = mid + 1; else b = mid;
  }
  const out: Row[] = [];
  for (let i = a; i < index.length && index[i][0] < hi; i++)
    out.push(table[index[i][1]]);
  return out;
}
 
// For each outer row, look up its matches (an index scan, or a full rescan).
function nestedLoop(outer: Row[], lookup: (r: Row) => Row[]): Row[] {
  const out: Row[] = [];
  for (const o of outer)
    for (const i of lookup(o)) out.push([...o, ...i]);
  return out;
}
 
function hashJoin(build: Row[], buildKey: number, probe: Row[], probeKey: number): Row[] {
  const table = new Map<number, Row[]>();
  for (const b of build) {
    const bucket = table.get(b[buildKey]) ?? [];
    bucket.push(b);
    table.set(b[buildKey], bucket);
  }
  const out: Row[] = [];
  for (const p of probe)
    for (const b of table.get(p[probeKey]) ?? []) out.push([...b, ...p]);
  return out;
}
 
// Both inputs sorted on the key; keys on the left are unique.
function mergeJoin(left: Row[], leftKey: number, right: Row[], rightKey: number): Row[] {
  const out: Row[] = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    const a = left[i][leftKey], b = right[j][rightKey];
    if (b < a) j++;
    else if (b > a) i++;
    else out.push([...left[i], ...right[j++]]);
  }
  return out;
}
 
function btreeHeight(n: number): number {
  let nodes = Math.ceil(n / FANOUT), height = 1;
  while (nodes > 1) { nodes = Math.ceil(nodes / FANOUT); height++; }
  return height;
}
 
// Expected distinct pages that k rows at random places fall on.
function expectedPages(pages: number, k: number): number {
  return pages * (1 - Math.pow(1 - 1 / pages, k));
}
 
function seqScanCost(n: number): number {
  return Math.ceil(n / ROWS_PER_PAGE) * SEQ_PAGE + n * TUPLE;
}
 
function indexScanCost(n: number, k: number): number {
  const random = btreeHeight(n) + expectedPages(Math.ceil(n / ROWS_PER_PAGE), k);
  const leaves = Math.max(0, Math.ceil(k / FANOUT) - 1);
  return random * RANDOM_PAGE + leaves * SEQ_PAGE + k * TUPLE;
}
 
// n rows in the table, k expected to match: the cheaper estimate wins.
function chooseScan(n: number, k: number): string {
  return indexScanCost(n, k) < seqScanCost(n) ? "index" : "seq";
}

模型假設與範圍

  • 這是可重現的教學模型；延遲、容量、故障率與工作負載是設定或樣本，不能直接當作正式系統的效能承諾。
  • 以固定資料、簡化頁數與操作成本比較掃描、join 和索引；不使用真實 optimizer，未涵蓋統計誤差、buffer cache 與磁碟延遲。

什麼時候用

  • 查詢變慢時先看執行計畫：PostgreSQL 和 MySQL 都用 EXPLAIN ANALYZE，看它選了什麼、估計和實際差多少。
  • 為 WHERE、JOIN、ORDER BY 常用的欄位建索引，但只對「篩掉大部分資料」的條件有用；只篩掉一半的條件，資料庫寧可全表掃描。
  • 大量匯入或刪除之後跑 ANALYZE：規劃器靠統計資料估計列數，統計過時就會選錯計畫。

和其他主題的關係

時間與空間複雜度（Big O）

操作平均最差
Seq Scan
讀完整張表
O(n)O(n)
Index Scan
k 是符合的列數；每列可能是一次隨機讀頁
O(log n + k)O(log n + k)
Nested Loop（內層用索引）
m 是外層列數；內層沒有索引就是 O(m·n)
O(m log n)O(m·n)
Hash Join
雜湊表要放得進記憶體；所有鍵都相同時退化
O(m + n)O(m·n)
Merge Join
多半花在排序；輸入已排序就是 O(m + n)
O(m log m + n log n)O(m log m + n log n)

空間：O(m)，Hash Join 的雜湊表放較小的一邊

Big O 實測：n 變大時步數怎麼長

數的是：用主鍵找一列要讀的頁數（n 列的表）

Big On = 1,000n = 10,000n = 100,000成長倍數：實測（理論）
Index Scan（B-tree）O(log n)334×1.3 (×1.7)
Seq ScanO(n)202002,000×100 (×100)

B-tree 每頁 100 個鍵，十萬列也只有 3 層，再加讀一頁資料；全表掃描則隨表的大小線性成長。

和其他做法比

沒有額外索引三個索引都有快幾倍
單點：user_id = 42Seq Scan · 300Index Scan · 446.8×
範圍：amount < 5（0.5%）Seq Scan · 300Index Scan · 1601.9×
範圍：amount < 100（10%）Seq Scan · 300Seq Scan · 3001.0×
JOIN：u.id = 42Nested Loop + Seq Scan · 312Nested Loop + Index Scan · 565.6×
JOIN：country = 'TW'Hash Join · 466Hash Join · 4661.0×
GROUP BY user_idHashAggregate · 420Index Only Scan + GroupAggregate · 3071.4×

每格是規劃器選用的計畫與它實際的成本（循序讀頁 1、隨機讀頁 4、每列 0.01）。點查、小範圍查詢和只有一位使用者的 JOIN 有索引就比較便宜；範圍一大、或要讀很多列的 JOIN，有索引也不會用。

真實世界裡的它

  • PostgreSQL 的 random_page_cost 預設 4、seq_page_cost 預設 1，就是這裡用的成本；資料都在 SSD 或記憶體時常把前者調低到 1.1 左右，索引就更常被選用。
  • MySQL 的 InnoDB 把整張表存成主鍵的 B+ tree，次要索引存主鍵值；所以 Index Scan 要先查次要索引、再查一次主鍵（回表）。
  • Index Only Scan 在 PostgreSQL 還要查 visibility map 確認該頁所有列都可見（見 MVCC），剛大量更新過的表會退回讀表。

取捨與陷阱

  • 對欄位套函式會讓索引失效：WHERE lower(email) = … 用不到 email 的索引，要建 lower(email) 的運算式索引。
  • 規劃器假設欄位之間互相獨立：city = '台北' AND country = 'TW' 會把列數估得太少，進而選了巢狀迴圈；PostgreSQL 可以用 CREATE STATISTICS 補上關聯。
  • 索引不是免費的：每個索引都讓每次寫入多更新一棵 B-tree，也要占空間。用不到的索引應該刪掉。