複合インデックス

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

索引を1列ずつ張るのと、2列まとめて1本張るのは別物になる。まとめた索引は列を並べた順に辞書のように並ぶので、左端から連続して指定したぶんだけ位置を決められる。1万行の表で測ると、両方指定なら10件だけ見て済むのに、左端を欠くと1万件ぜんぶなめた。列の順を入れ替えるだけで、同じ条件が500件から50件になる。

この章で作るもの

セカンダリインデックスで張ったのは1列だけの索引だった。だが実際の問い合わせは WHERE a = 5 AND b = 3 のように、複数の列を同時に指定することのほうが多い。

このとき張り方は2通りある。a の索引と b の索引を1本ずつ張るか、 (a, b) をまとめた1本を張るか。後者が複合インデックスで、 この2つは足し算の関係になっていない。まとめた索引は列を並べた順に並ぶので、 どの列を先に置いたかで、使える条件が変わってしまう。

電話帳が「姓, 名」の順に並んでいるのと同じだ。姓が分かればページを開ける。 姓と名の両方が分かればもっと絞れる。だが名だけ分かっても、どこを開けばいいか分からない。

  索引 (a, b) の中身(値の組 → 主キー)

   a=4 ┬ b=0 …        a が決まる = 開く場所が決まる
       ├ b=1 …
       └ b=9 …
   a=5 ┬ b=0 …  ←┐
       ├ b=3 … ←─┼─ a=5 かつ b=3 は、この一点に降りられる
       └ b=9 …   │
   a=6 ┬ b=0 …   │
       └ …       └─ a=5 だけなら、この固まり(100件)を見る

  b=3 だけ与えられた場合
   a=0 の中に b=3、a=1 の中にも b=3、… と全体に散っている
   → どこを開けばいいか決まらない

(a, b) の順に張った索引の並び。a でまとまり、その中が b で並ぶ。a が決まれば固まりの位置が決まるが、b だけ決まっても固まりは選べない

順に見ていく。

1. 左端から連続した分しか使えない: 途中が抜けると、そこから先は位置決めに使えない
2. 範囲が来たら、そこで打ち切り: 等値は続けられるが、範囲を1つ挟むと後ろが死ぬ
3. 索引はタダではない: 1本増やすごとに、書き込みで触るページが増える

① 左端から連続した分しか使えない

まず、測れる最小の形で持つ。行は3列、索引は「列の値の組と主キー」を並べたものになる。 1ページに入るのは本体が100行、索引が500件で、セカンダリインデックスと同じ比率にしてある:

// 1ページに入る件数。索引は列の値と主キーしか持たないので、行より多く入る。
const (
	RowsPerPage    = 100
	EntriesPerPage = 500
)

// Row は3列の行。
type Row struct {
	ID      int
	A, B, C int
}

// Cond は1つの条件。Op は "=" か ">=" のどちらか。
type Cond struct {
	Col string
	Op  string
	Val int
}

// Entry は索引の1件。Key は列を並べた順の値。
type Entry struct {
	Key []int
	ID  int
}

// Index は複合インデックス。Cols の順がすべてを決める。
type Index struct {
	Cols    []string
	entries []Entry

	reads int
	// Scanned は索引の中で読み進めた件数。位置を決められないほど増える。
	Scanned int
}

索引を張るところは、指定された列の順にキーを並べて整列するだけだ。 この cols の順が、以降のすべてを決める:

// NewRows は n 行を作る。aVals / bVals はそれぞれの列がとる値の種類の数。
func NewRows(n, aVals, bVals int) []Row {
	rows := make([]Row, n)
	for i := range rows {
		rows[i] = Row{ID: i, A: i % aVals, B: (i / aVals) % bVals, C: i}
	}
	return rows
}

func value(r Row, col string) int {
	switch col {
	case "a":
		return r.A
	case "b":
		return r.B
	default:
		return r.C
	}
}

// Build は cols の順で索引を張る。
func Build(rows []Row, cols ...string) *Index {
	es := make([]Entry, len(rows))
	for i, r := range rows {
		k := make([]int, len(cols))
		for j, c := range cols {
			k[j] = value(r, c)
		}
		es[i] = Entry{Key: k, ID: r.ID}
	}
	sort.Slice(es, func(i, j int) bool {
		for k := range cols {
			if es[i].Key[k] != es[j].Key[k] {
				return es[i].Key[k] < es[j].Key[k]
			}
		}
		return es[i].ID < es[j].ID
	})
	return &Index{Cols: cols, entries: es}
}

// Height は根から葉まで降りるのに読むページ数。
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, ix.Scanned = 0, 0 }

ここで言う「位置決めに使える」を、はっきりさせておく。 索引は並んでいるので、先頭の列の値が決まれば、その値の固まりがどこから始まるかを二分探索で決められる。 次の列の値も決まっていれば、その固まりの中でさらに絞れる。 だが途中の列が抜けると、そこから先は決められない。 抜けた列の値が何であれ条件に合う可能性があるので、範囲を狭められないからだ。

規則にすると1つの関数に収まる:

// Usable は、条件のうち索引で位置決めに使える本数を返す。
//
// 使えるのは「列の並びの左端から連続する等値」まで。そのあとに範囲が1つ来たら
// それも使えるが、そこで打ち切りになる。1つでも抜けたら、そこから先は使えない。
func (ix *Index) Usable(conds []Cond) int {
	byCol := map[string]Cond{}
	for _, c := range conds {
		byCol[c.Col] = c
	}
	n := 0
	for _, col := range ix.Cols {
		c, ok := byCol[col]
		if !ok {
			break // 抜けている。ここから先は位置決めに使えない
		}
		n++
		if c.Op != "=" {
			break // 範囲。ここで打ち切り
		}
	}
	return n
}

引くほうは、位置決めに使えたぶんで見る範囲を決め、残りの条件はその中を1件ずつふるいにかける:

// Plan は1回の問い合わせで読んだページ数の内訳。
type Plan struct {
	// Usable は位置決めに使えた列の本数。
	Usable int
	// Scanned は索引の中で読み進めた件数。
	Scanned int
	// IndexReads は索引を読んだページ数。
	IndexReads int
	// Rows は最後に返した件数。
	Rows int
}

// Lookup は条件で索引を引く。
//
// 位置決めに使えた列で範囲を絞り、残りの条件はそこから1件ずつふるいにかける。
// 使えた本数が少ないほど、なめる件数が増える。
func (ix *Index) Lookup(conds []Cond) Plan {
	ix.ResetStats()
	u := ix.Usable(conds)
	byCol := map[string]Cond{}
	for _, c := range conds {
		byCol[c.Col] = c
	}

	// 位置決めに使えたぶんで、見る範囲を決める。
	lo, hi := 0, len(ix.entries)
	if u > 0 {
		lo = sort.Search(len(ix.entries), func(i int) bool {
			return !less(ix.entries[i].Key, ix.Cols, byCol, u)
		})
		hi = lo
		for hi < len(ix.entries) && inRange(ix.entries[hi].Key, ix.Cols, byCol, u) {
			hi++
		}
		ix.reads += ix.Height()
	} else {
		// どこを開けばいいか分からないので、索引をぜんぶなめる。
		ix.reads += ix.Height()
	}

	scanned := hi - lo
	ix.Scanned = scanned
	if scanned > 1 {
		ix.reads += (scanned - 1) / EntriesPerPage
	}

	// 使えなかった条件は、なめながらふるいにかける。
	rows := 0
	for _, e := range ix.entries[lo:hi] {
		if matches(e.Key, ix.Cols, byCol) {
			rows++
		}
	}
	return Plan{Usable: u, Scanned: scanned, IndexReads: ix.reads, Rows: rows}
}

// less は key が、使えた条件の下限より手前かを返す。
func less(key []int, cols []string, byCol map[string]Cond, u int) bool {
	for i := 0; i < u; i++ {
		c := byCol[cols[i]]
		if key[i] != c.Val {
			return key[i] < c.Val
		}
	}
	return false
}

// inRange は key が、使えた条件の範囲に収まっているかを返す。
func inRange(key []int, cols []string, byCol map[string]Cond, u int) bool {
	for i := 0; i < u; i++ {
		c := byCol[cols[i]]
		if c.Op == "=" && key[i] != c.Val {
			return false
		}
		if c.Op == ">=" && key[i] < c.Val {
			return false
		}
	}
	return true
}

// matches は全条件を満たすかを返す。
func matches(key []int, cols []string, byCol map[string]Cond) bool {
	for i, col := range cols {
		c, ok := byCol[col]
		if !ok {
			continue
		}
		if c.Op == "=" && key[i] != c.Val {
			return false
		}
		if c.Op == ">=" && key[i] < c.Val {
			return false
		}
	}
	return true
}

// ScanPages は索引を使わず表を全部読んだときのページ数。
func ScanPages(rows []Row) int { return (len(rows) + RowsPerPage - 1) / RowsPerPage }

1万行の表で測った。a は100種類、b は10種類の値をとるので、a = 5 AND b = 3 に当たるのは10件になる。 索引は (a, b) の順に張ってある。

条件	位置決めに使えた列	なめた件数	索引ページ	当たり
a = 5 AND b = 3	2	10	2	10
a = 5	1	100	2	100
b = 3	0	10,000	21	1,000

1000倍。b = 3 は当たりが1,000件しかないのに、索引の1万件を全部なめている。 左端の a が無いせいでどこを開けばいいか決まらず、索引を端から端まで読んで 1件ずつふるいにかけるしかないからだ。索引はあるのに、索引としては働いていない。

同じ条件でも、索引を (b, a) の順に張り替えれば話が変わる。b が左端になるので位置決めに使え、 なめる件数は1,000件、つまり当たりそのものになる。テストで、この10分の1への落ち方を固定した。

索引を張るかどうかより、どの順で並べるかのほうが効く。これが複合インデックスの中心になる。

② 範囲が来たら、そこで打ち切り

左端から連続していれば良い、と書いたが、条件はもう1つある。 等値(=)は連ねられるが、範囲(>= など)を1つ挟むと、その後ろは位置決めに使えない。

理由は並び方を見れば分かる。a = 5 なら a が 5 の固まりは1か所にまとまっているので、 その中は b の順に並んでいる。だが a >= 95 は a が 95、96、97… と複数の固まりにまたがる。 それぞれの固まりの中では b 順に並んでいても、またいだ全体としては b の順になっていない。 だから b で範囲を狭められない。

(a, b) の索引で、同じ2つの条件を順序だけ変えて測った。

条件	使えた列	なめた件数	当たり
a = 5 AND b >= 8(等値 → 範囲)	2	20	20
a >= 95 AND b = 3(範囲 → 等値)	1	500	50

上は、なめた件数が当たりとぴったり同じだ。無駄が1件も無い。 下は50件のために500件なめている。a が 95 から 99 までの5つの固まり(各100件)を全部読み、 そこから b が 3 のものを拾っているからだ。

これも列の順で直る。(b, a) に張り替えると、b が等値で左端に来るので両方が使える:

索引の列順	a >= 95 AND b = 3	使えた列	当たり
(a, b)	500 件なめる	1	50
(b, a)	50 件なめる	2	50

当たりは50件のまま変わらず、なめる件数だけが10分の1になった。 テストで、返る件数が両者で一致することも合わせて固定してある。

ここから実務の定石が出てくる。等値で使う列を先に、範囲で使う列を後に置く。 どちらも同じ2列の索引なのに、順を間違えると片方が働かない。

③ 索引はタダではない

ここまでは引く側の話だった。索引には書く側の代償がある。

本体に1行足すとき、触るのは本体のページだけではない。張ってある索引を全部更新する。 索引が1本あれば葉に1ページ、4本あれば4ページ。数えると次のようになる:

// WriteCost は1行足すときに触るページ数を返す。
//
// 本体に1ページ、索引1本につき葉が1ページ。**索引は引くのを速くする代わりに、
// 書くのを重くする**。張った本数がそのまま書き込みに乗る。
func WriteCost(indexes int) int { return 1 + indexes }

// InsertPages は n 行入れたときに触るページ数の合計を返す。
func InsertPages(n, indexes int) int { return n * WriteCost(indexes) }

索引の本数	1行あたりに触るページ	1万行入れると
0	1	10,000
1	2	20,000
2	3	30,000
4	5	50,000

索引を4本張ると、書き込みは5倍になる。テストでこの比を固定した。

ここに複合インデックスのもう1つの利点がある。(a, b) の索引1本は、 a だけの索引を兼ねる。左端から連続していれば使えるのだから、a 単独の条件でも位置決めできる。 つまり a と (a, b) の2本を張るのは無駄で、(a, b) の1本で足りる。 複合1本で複数の問い合わせを賄えれば、索引の本数を減らせて書き込みが軽くなる。

逆に b 単独で引きたいなら、(a, b) は役に立たない。b の索引をもう1本張るか、 b を左端にした索引に変えるかを選ぶことになり、その判断は 「どの問い合わせが何回来るか」と「書き込みがどれだけ重くなるか」の釣り合いで決まる。

動かす

下のデモは、この実装をそのまま移植している。索引の列順と条件を切り替えると、 位置決めに使えた列の本数と、索引の中でなめた件数が変わる。同じ条件でも列順を入れ替えると なめる件数が落ちること、b だけの条件では (a, b) が索引として働かないことが見える。 「書き込み」に切り替えると、索引の本数がそのまま書き込みのページ数に乗るのが確かめられる。

デモ列の順で、なめる件数が変わる10,000 行 / 索引の高さ 2

引く書き込み

条件a = 5 AND b = 3a = 5b = 3a = 5 AND b >= 8a >= 95 AND b = 3

a は 100 種類 / b は 10 種類 ・ 索引は 1ページ 500 件

(a, b) 位置決め 0 列 10,000 件

(b, a) 位置決め 1 列 1,000 件

索引の中でなめた件数そのうち当たり(1,000 件)読んだ索引ページ (a, b) 21 ・ (b, a) 3

(b, a) なら 1,000 件で済むが、(a, b) では 10,000 件なめる。当たりはどちらも 1,000 件で同じ

位置決めに使えるのは、列の並びの左端から連続して指定した分だけになる。途中が抜けると、 そこから先は範囲を狭められない。等値は連ねられるが、範囲を1つ挟むとその後ろも使えなくなる。 なめた件数と当たりが一致していれば、その索引には無駄が無い。

設計の観点

• 順がすべてを決める: 同じ2列でも (a, b) と (b, a) は別の索引になる。張るかどうかより、どう並べるかの判断のほうが効く
• 等値が先、範囲が後: 範囲を挟むとその後ろは位置決めに使えない。範囲の列は最後に置く
• 左端の索引は兼ねられる: (a, b) は a を兼ねるので、a 単独の索引を別に張るのは無駄になる
• 本数は書き込みに乗る: 索引は引くのを速くする代わりに書くのを重くする。複合1本にまとめられるなら、その分だけ書き込みが軽い
• なめた件数と当たりを分けて数える: 「索引が効いている」は主張なので、当たり件数となめた件数を別々に出す。両者が一致していれば無駄が無い
• 並べ替えにも効く: この章では触れないが、索引の並び順は ORDER BY の並べ替えを省ける条件にもなる。列の順の設計は絞り込みだけの話ではない

対照と実例

論点	この章	実物
左端を欠いた条件	索引を全部なめる	MySQL は原則その索引を使わない(最左プレフィックス)。PostgreSQL は索引全体を走査する道を選べて、表の全走査より速いことがある
1列ずつ2本張る	扱わない	bitmap index scan(PostgreSQL)や index merge(MySQL)で2本を組み合わせられる。ただし複合1本より遅いことが多い
列の順の決め方	手で指定する	等値で使う列を先、範囲を後。同点なら問い合わせの頻度で決める
左端の飛ばし読み	無い	skip scan。先頭列がとる値の種類が少ないときだけ効く
索引に列を足す	キーとして足す	並べ替えには使わず本体へ戻らないためだけに載せる指定がある(INCLUDE)

裏どり:

• 最左プレフィックス: MySQL の用語。索引 (a, b, c) は (a) と (a, b) の索引を兼ねるが、(b) や (b, c) は兼ねない。列を足した索引を1本置けば単独索引を減らせるのは、この性質による
• 範囲で打ち切られる: 範囲条件の列より後ろは位置決めに使えない。この章の測定(a >= 95 AND b = 3 で500件なめるのに対し、列順を変えると50件)がそのまま理由になる。IN は等値の集まりとして扱えるので、実物では範囲と違って打ち切りにならないことがある
• skip scan: 先頭列の値ごとに部分的な探索を繰り返すことで、左端を欠いた条件でも索引を使う最適化。Oracle が 9i で導入し、MySQL は 8.0.13 から、PostgreSQL は 18 で B-Tree に入った。先頭列の種類が少ないときにしか得にならないので、列の順を設計しなくてよくなるわけではない
• カバリングとの重なり: 複合索引は複数の列を持つので、欲しい列が索引に揃っていればセカンダリインデックスで見た「本体に戻らない索引」に自然になる。(a, b) の索引に SELECT b WHERE a = 5 が答えられるのはこのため
• 索引の本数は運用の指標: 使われていない索引は書き込みを重くするだけになる。PostgreSQL の pg_stat_user_indexes や MySQL の sys.schema_unused_indexes は、そのために使用回数を出している

簡略化したこと

• 索引は配列: 実際には B-Tree だが、高さの計算だけ真似ている。分割も再平衡も無い
• 本体へ戻る回数を数えない: この章は索引の中でなめる件数に絞った。索引から本体へ戻る代償はセカンダリインデックスで測っている
• 条件は等値と >= だけ: BETWEEN、前方一致、IN は扱わない
• 索引を組み合わせない: 2本の索引を突き合わせる道(bitmap index scan / index merge)は無い
• skip scan なし: 左端を欠いた条件は、素直に全部なめる
• プランナが無い: どの索引を使うかは指定する。実物は統計から当たる件数を見積もって選ぶ
• 更新の中身は数えない: 書き込みの代償はページ数の勘定だけで、実際に索引を更新する処理は無い

参考資料

• Use The Index, Luke: Concatenated Keys — 列の順がなぜ効くかの定番解説
• MySQL: Multiple-Column Indexes — 最左プレフィックスの規則
• MySQL: Skip Scan Range Access — 左端を欠いた条件を救う最適化
• PostgreSQL: Multicolumn Indexes — 先頭列が無いときの振る舞い
• 実装: db/composite