セカンダリインデックス

実装: db/secondary/ / 実行: go test ./db/secondary/

主キー以外で引くための索引は、値から主キーへの、もう1本の木でしかない。だが索引を引いても行は手に入らないので、主キーを持って本体へ戻ることになる。戻る回数は当たった件数ぶん積み上がるので、1万行の表では当たる件数が1%を超えたところで全走査に負けた。10%では10倍読んでいる。欲しい列を索引に載せて戻らずに済ませると、同じ問い合わせが2ページで返る。

この章で作るもの

ミニSQLでは WHERE id = k しか扱えなかった。主キーで引くのは B-Treeページストアで作ったからだ。だが実際の問い合わせは「年齢が30の人」のように、主キー以外で引くほうが多い。

そのための索引がセカンダリインデックスで、中身は「その列の値 → 主キー」を並べたもう1本の木でしかない。作るのは簡単だが、代償がはっきりしている。

順に見ていく。

木を2回降りる: 索引を引いても行は手に入らない。主キーを持って本体へ戻る
戻る回数は件数ぶん: 当たる件数が増えると、どこかで全走査に負ける
戻らない道がある: 本体を索引の順に並べるか、欲しい列を索引に持たせる

① 木を2回降りる

まず、本体の表と索引を測れる最小の形で持つ。本体は主キー順に行が詰まったページの列、索引は「値と主キー」の組の列になる:


// PageSize はディスクの読み書きの最小単位に入る件数。
//
// 行そのものは大きいので1ページに 100 行、索引は「値と主キー」しか持たないので
// 1ページに 500 件、という比率にしてある。**索引が小さいことが効き目の源**になる。
const (
	RowsPerPage    = 100
	EntriesPerPage = 500
)

// Row は1行。
type Row struct {
	ID   int
	Age  int
	Name string
}

// Table は行をページに詰めて持つ。ID の順に並んでいる。
type Table struct {
	rows  []Row
	reads int
}

// NewTable は n 行の表を作る。年齢は 0..spread-1 を配る。
//
// 同じ年齢の行は表のあちこちに散る。行が入ってきた順に置かれる、普通の表になる。
func NewTable(n, spread int) *Table {
	rows := make([]Row, n)
	for i := range rows {
		rows[i] = Row{ID: i, Age: i % spread, Name: "user"}
	}
	return &Table{rows: rows}
}

// NewClustered は、行そのものを年齢の順に並べた表を作る。
//
// 同じ年齢の行が隣り合うので、まとめて読める。これがクラスタ化された表で、
// **1つの表につき1つの並びしか持てない**のがそのまま制約になる。
func NewClustered(n, spread int) *Table {
	rows := make([]Row, n)
	per := n / spread
	if per == 0 {
		per = 1
	}
	for i := range rows {
		age := i / per
		if age >= spread {
			age = spread - 1
		}
		rows[i] = Row{ID: i, Age: age, Name: "user"}
	}
	return &Table{rows: rows}
}

// Len は行数を返す。
func (t *Table) Len() int { return len(t.rows) }

// Pages は表が占めるページ数を返す。
func (t *Table) Pages() int { return (len(t.rows) + RowsPerPage - 1) / RowsPerPage }

// Reads は読んだページ数の累計を返す。
func (t *Table) Reads() int { return t.reads }

// ResetStats は数え直す。
func (t *Table) ResetStats() { t.reads = 0 }

索引に載るのは「値と主キー」だけなので、行そのものよりずっと小さい。ここでは本体が1ページ100行、索引が1ページ500件という比率にしてある。索引が効くのは、この小ささのおかげになる。


// Entry は索引の1件。並べたい値と、そこから本体を引くための主キー。
type Entry struct {
	Key int
	ID  int
	// Extra は索引が持っている追加の列。ここに欲しいものが揃っていれば、
	// 本体を読みに戻らなくて済む(カバリングインデックス)。
	Extra string
}

// Index は「値 → 主キー」を並べた、もう1本の木。
type Index struct {
	entries []Entry
	reads   int
}

// Build は表の Age で索引を張る。値が同じものは主キーの順に並ぶ。
func Build(t *Table, extra bool) *Index {
	es := make([]Entry, len(t.rows))
	for i, r := range t.rows {
		es[i] = Entry{Key: r.Age, ID: r.ID}
		if extra {
			es[i].Extra = r.Name
		}
	}
	sort.Slice(es, func(i, j int) bool {
		if es[i].Key != es[j].Key {
			return es[i].Key < es[j].Key
		}
		return es[i].ID < es[j].ID
	})
	return &Index{entries: es}
}

// Height は根から葉まで降りるのに読むページ数。
//
// 1ページに EntriesPerPage 件入るので、件数が増えても対数でしか伸びない。
func (ix *Index) Height() int {
	h, n := 1, len(ix.entries)
	for n > EntriesPerPage {
		n = (n + EntriesPerPage - 1) / EntriesPerPage
		h++
	}
	return h
}

// Reads は読んだページ数の累計を返す。
func (ix *Index) Reads() int { return ix.reads }

// ResetStats は数え直す。
func (ix *Index) ResetStats() { ix.reads = 0 }

// Lookup は key に一致する件を索引から拾い、主キーの並びを返す。
//
// 根から葉まで降りて、そこから横に読み進める。読むページは
// 「高さ + ヒットが載っている葉の数」になる。
func (ix *Index) Lookup(key int) []Entry {
	lo := sort.Search(len(ix.entries), func(i int) bool { return ix.entries[i].Key >= key })
	hi := lo
	for hi < len(ix.entries) && ix.entries[hi].Key == key {
		hi++
	}
	ix.reads += ix.Height()
	if n := hi - lo; n > 1 {
		// 葉をまたいで続くぶん。1枚目は降りるときに読んでいる。
		ix.reads += (n - 1) / EntriesPerPage
	}
	return ix.entries[lo:hi]
}

  「年齢が 42 の人」

  ┌─ 索引(年齢 → 主キー)─┐        ┌─ 本体(主キー順)─┐
  │  …                    │        │  page 0: id 0..99  │
  │  41 → 7301            │        │  page 1: id 100..  │
  │  42 → 4218  ──────────┼───────▶│  page 42: id 4200..│  ← ここを読む
  │  43 → 118             │        │  …                 │
  └───────────────────────┘        └────────────────────┘
     高さ 2 ページ                     もう 1 ページ

  索引は「どこにあるか」しか知らない。行を取るには本体へ戻る

セカンダリインデックスで引く道。索引を降りて主キーを拾い、その主キーで本体をもう一度引く。索引だけでは行にたどり着かない

1万行の表で、1件だけ当たる問い合わせを測った。

	索引	本体	合計
全走査	0	100	100 ページ
索引 + 本体	2	1	3 ページ

33倍。1件しか当たらないなら、索引は圧倒的に有利になる。索引の高さは件数が増えても対数でしか伸びず、テストで 1000万件でも高さ3であることを固定した。

② 戻る回数は件数ぶん

問題は、当たる件数が増えたときだ。全走査は当たる件数に関係なく100ページで固定だが、索引経由は当たった件数ぶん本体へ戻る。同じ1万行の表で、 1つの値に当たる件数だけを変えて測った。

当たる率	件数	全走査	索引 + 本体
0.01%	1	100	3
0.1%	10	100	12
0.5%	50	100	52
1.0%	100	100	102
2.0%	200	100	202
5.0%	500	100	502
10.0%	1,000	100	1,003

逆転するのは 1%。表の1割に当たる問い合わせでは、索引を使うほうが10倍読んでいる。テストで、この逆転点が表の1割に届く前に来ることを固定した。

理由は単純で、行が表のあちこちに散っているからだ。100件当たれば、たまたま同じページに入っていない限り100ページ読むことになる。全走査なら同じ100ページで全部読めるのに、索引経由では100件のためだけに100ページ読む。

これが、実物のプランナが「索引があるのに使わない」判断をする理由になる。ミニSQLの engine は WHERE の有無だけで道を決めていたが、 本物は当たる件数を見積もってから決めている。

③ 戻らない道がある

戻ることが代償なら、戻らなければいい。道は2つある。


// Plan は1回の問い合わせで読んだページ数の内訳。
type Plan struct {
	Name string
	// IndexReads は索引を読んだページ数。
	IndexReads int
	// TableReads は本体を読んだページ数。
	TableReads int
	Rows       int
}

// Total は合計。
func (p Plan) Total() int { return p.IndexReads + p.TableReads }

// ByScan は索引を使わず、全ページを読む。
func ByScan(t *Table, key int) Plan {
	t.ResetStats()
	rows := t.Scan(func(r Row) bool { return r.Age == key })
	return Plan{Name: "全走査", TableReads: t.Reads(), Rows: len(rows)}
}

// BySecondary は索引で主キーを拾い、そのぶん本体を読みに戻る。
//
// 主キーの並びがバラバラなので、1行につき1ページ読むことになりやすい。
func BySecondary(t *Table, ix *Index, key int) Plan {
	t.ResetStats()
	ix.ResetStats()
	es := ix.Lookup(key)
	for _, e := range es {
		t.Fetch(e.ID) // 1件ずつ本体へ戻る
	}
	return Plan{Name: "索引 + 本体", IndexReads: ix.Reads(), TableReads: t.Reads(), Rows: len(es)}
}

// ByClustered は本体が索引と同じ順に並んでいる場合(NewClustered で作った表)。
//
// 拾った主キーが固まっているので、同じページの行はまとめて読める。
func ByClustered(t *Table, ix *Index, key int) Plan {
	t.ResetStats()
	ix.ResetStats()
	es := ix.Lookup(key)
	ids := make([]int, len(es))
	for i, e := range es {
		ids[i] = e.ID
	}
	sort.Ints(ids)
	t.FetchAll(ids)
	return Plan{Name: "並びをそろえた索引", IndexReads: ix.Reads(), TableReads: t.Reads(), Rows: len(es)}
}

// ByCovering は欲しい列が索引に揃っている場合。本体を読まない。
func ByCovering(t *Table, ix *Index, key int) Plan {
	t.ResetStats()
	ix.ResetStats()
	es := ix.Lookup(key)
	for _, e := range es {
		_ = e.Extra // 索引の中で用が足りる
	}
	return Plan{Name: "本体に戻らない索引", IndexReads: ix.Reads(), Rows: len(es)}
}

1つめは、本体を索引と同じ順に並べる。同じ値の行が隣り合うので、まとめて読める。同じ測定を並べるとこうなった。

当たる率	件数	全走査	索引 + 本体	並びをそろえた索引
0.1%	10	100	12	3
1.0%	100	100	102	3
5.0%	500	100	502	7
10.0%	1,000	100	1,003	13

どの選択率でも全走査に負けない。テストでこれを固定した。ただし決定的な制約がある。1つの表につき、並びは1つしか持てない。年齢の順に並べたら、名前の順にはできない。

2つめは、欲しい列を索引に持たせる。索引の中で用が足りるなら、本体へ戻る必要がない。 1つの値に100件当たる設定で測った。

	索引	本体	合計
全走査	0	100	100 ページ
索引 + 本体	2	100	102 ページ
本体に戻らない索引	2	0	2 ページ

51倍。テストで、返す件数が同じであること、本体を1ページも読まないことを固定した。代償は索引が太ることで、持たせた列のぶんだけ1ページに入る件数が減り、書き込みのたびに更新する量も増える。

動かす

当たる件数を変えると、4つの道の読むページ数が入れ替わる。色の濃い部分が索引、薄い部分が本体になる。

デモ索引を使うか、全部読むか当たる 100 件(1.0%)

当たる件数110501002005001000

10000 行 = 100 ページ・索引の高さ 2 ・ 1ページに本体 100 行 / 索引 500 件

全走査100 ページ

索引 + 本体102 ページ

並びをそろえた索引3 ページ

本体に戻らない索引2 ページ

索引を読んだぶん本体を読んだぶん

索引を使うほうが 102 ページ、全走査は 100 ページ。当たる件数が表の 1% を超えたあたりで、索引経由のほうが読むページが多くなる

索引を引いても行そのものは手に入らないので、主キーを持って本体へ戻ることになる。戻る回数は当たった件数ぶん積み上がるので、当たる件数が増えるほど不利になる。本体を索引と同じ順に並べるか、欲しい列を索引に持たせるかすれば、戻る回数を減らせる。

設計の観点

索引は場所しか知らない: 行が要るなら戻る。戻る回数を減らすのが設計のほぼ全部になる
当たる件数で決まる: 索引を張るかどうかは列の性質ではなく、その列で何件当たるかで決まる
並びは1つしか持てない: どの列でそろえるかは、表につき1回しか使えない切り札になる
持たせるか、戻るか: 索引に列を足すと引くのは速くなるが、索引が太って書き込みが重くなる
見積もりが要る: 逆転点があるということは、どちらが得かを事前に見積もる仕組みが要るということ
読む回数を数える口を作る: 「索引が効く」は主張なので、索引と本体を分けて数える

対照と実例

	索引が指すもの	本体へ戻る	並びをそろえられるか
この章	主キー	件数ぶん	1つだけ
InnoDB(MySQL)	主キー	件数ぶん(主キーの木をもう一度降りる)	主キーで必ずクラスタ化
PostgreSQL	行の物理位置(ctid)	件数ぶん	`CLUSTER` で一度だけ並べ替え
SQL Server	主キー、または行の位置	件数ぶん	クラスタ化索引は1本まで
転置インデックス	文書ID	件数ぶん	文書順に並ぶ
LSM ツリー	主キー	件数ぶん	書いた順ではなくキー順

裏どり:

InnoDB は主キーを指す: セカンダリインデックスの葉に入っているのは行の位置ではなく主キーの値になる。だから本体へ戻るのは「主キーの木をもう一度根から降りる」ことで、この章の1ページより高くつく。主キーを短くしろと言われるのは、全セカンダリインデックスに主キーが載るからになる
PostgreSQL は位置を指す: 葉に入るのは ctid(ページ番号と行番号)。直接その場所を読めるが、行が更新されて移動すると索引を更新することになる。HOT 更新はこれを避ける仕組みで、同じページ内に収まるなら索引を触らない
index-only scan には条件がある: PostgreSQL で本体に戻らずに済むのは、visibility map でそのページが「全員に見える」と分かっているときだけになる。MVCC の可視性判定に行そのものが要るため
逆転点は実測されている: プランナは統計(値ごとの件数の分布)から当たる件数を見積もり、ランダム読みと順次読みの費用比で判断する。PostgreSQL の random_page_cost / seq_page_cost がその比率になる。SSD ではこの比が縮んだので、既定値の見直しが議論されている
カバリングは明示できる: PostgreSQL の INCLUDE、SQL Server の INCLUDE は、並べ替えには使わないが索引に載せる列を指定する。引くためではなく、戻らないために載せるという使い方になる

簡略化したこと

索引は配列: 実際には B-Tree だが、高さの計算だけ真似ている。分割も再平衡も無い
更新なし: 索引を張ったあと、行を足したり消したりしない。書き込みの代償は測っていない
等値だけ: 範囲(BETWEEN)や前方一致は扱わない
1列だけ: 複数の列をまとめた索引と、その列の順は複合インデックスで扱う
統計を持たない: 当たる件数を事前に見積もる仕組みは作っていない
キャッシュなし: バッファプールに載っていれば読み直さないが、ここでは毎回数える
NULL・重複キーの扱いなし: 実物はここに規則がある

参考資料

Use The Index, Luke — 索引の使われ方を SQL の書き方から説明する定番
PostgreSQL: Index-Only Scans — 本体へ戻らない条件
MySQL: Clustered and Secondary Indexes — セカンダリの葉に主キーが載る話
実装: db/secondary

セカンダリインデックス ​

この章で作るもの ​

① 木を2回降りる ​

② 戻る回数は件数ぶん ​

③ 戻らない道がある ​

動かす ​

設計の観点 ​

対照と実例 ​

簡略化したこと ​

参考資料 ​