- ブラウザURL入力
- DNS名前→IP
- ルータ経路選択
- ロードバランサ振り分け
- Nginx受け口
- アプリ処理
- DB保存今ここ
前回、並びは ORDER BY で宣言したときだけ保証されることを見ました。今回は、索引という「速く探すための仕組み」を足したとき、何が変わり何が変わらないかを実機で見ます。
まず結論
SQL の問い合わせに書くのは「どんな行が欲しいか」という条件だけで、どうやって探すかという道筋は書きません。だから索引を作っても消しても、返ってくる行の集合は変わりません。
変わるのは道筋のほうで、道筋によっては行の並びも変わります。データベースが守るのは宣言された条件だけで、宣言していない並びは自由に決めてよいからです。
10万行の表に `SELECT id, v, note FROM items WHERE v < 8;` を投げたあと、列 v に索引を作り、同じ文をもう一度投げます。2回の結果はどうなるでしょうか。
当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。
条件を書き、道筋は書かない
SELECT id, v, note FROM items WHERE v < 8; という文が言っているのは「v が 8 未満の行の、id と v と note が欲しい」だけです。表を端から読むのか、どこから探し始めるのかは書いていません。
この「書かない」は偶然ではありません。関係モデルを提案した Codd の 1970 年の論文は、当時のシステムの問題として索引への依存を挙げています。
From an informational standpoint, an index is a redundant component of the data representation.
情報として見れば、索引は冗長です。無くても答えは決まります。そのうえで Codd は問います。
Can application programs and terminal activities remain invariant as indices come and go?
索引が増えたり消えたりしても、プログラムは同じままでいられるか。当時の IDS というシステムでは、索引を速さのために使うプログラムは索引のチェーンを名前で参照する必要があり、Such programs do not operate correctly if these chains are later removed. でした。道筋を書いたプログラムは、道筋が消えると壊れます。
SQL は道筋を名指ししません。道筋を選ぶのはデータベースの側です。PostgreSQL 18 の公式文書はこう書きます。
Once an index is created, no further intervention is required: the system will update the index when the table is modified, and it will use the index in queries when it thinks doing so would be more efficient than a sequential table scan.
索引を作ったら、あとは何もしなくてよい。使うかどうかはシステムが決める。選んだ道筋は実行計画と呼ばれ、EXPLAIN を先頭に付けると表示されます。
- ・索引は情報としては冗長。足しても消しても条件を満たす行は変わらない
- ・並びを決めたいなら ORDER BY で宣言する
同じ文を、索引の前と後に投げる
PostgreSQL 18.6 で、10万行の表を作りました。v は id が増えるほど減るように入れてあります(v = 100001 - id)。わざと、表の中の並びが v の大きい順になるようにしています。 この条件が並びの結果に効くので、真似するときは同じ作り方にしてください。
DROP TABLE IF EXISTS items;CREATE TABLE items (id integer, v integer, note text);INSERT INTO items SELECT i, 100001 - i, 'item ' || i FROM generate_series(1, 100000) AS i;ANALYZE items;EXPLAIN (costs off) SELECT id, v, note FROM items WHERE v < 8;SELECT id, v, note FROM items WHERE v < 8;CREATE INDEX items_v_idx ON items (v);ANALYZE items;EXPLAIN (costs off) SELECT id, v, note FROM items WHERE v < 8;SELECT id, v, note FROM items WHERE v < 8;
6行目と10行目が一字違わず同じ SELECT であること、間で表に加えた変更は索引を作る7行目だけであることを確かめてください(ANALYZE は統計を更新するコマンドです)。出力は次のとおりです(冒頭の DROP〜ANALYZE の4文とその応答は省略。それ以外は生出力のまま)。
EXPLAIN (costs off) SELECT id, v, note FROM items WHERE v < 8;QUERY PLAN-------------------Seq Scan on itemsFilter: (v < 8)(2 rows)SELECT id, v, note FROM items WHERE v < 8;id | v | note--------+---+-------------99994 | 7 | item 9999499995 | 6 | item 9999599996 | 5 | item 9999699997 | 4 | item 9999799998 | 3 | item 9999899999 | 2 | item 99999100000 | 1 | item 100000(7 rows)CREATE INDEX items_v_idx ON items (v);CREATE INDEXANALYZE items;ANALYZEEXPLAIN (costs off) SELECT id, v, note FROM items WHERE v < 8;QUERY PLAN---------------------------------------Index Scan using items_v_idx on itemsIndex Cond: (v < 8)(2 rows)SELECT id, v, note FROM items WHERE v < 8;id | v | note--------+---+-------------100000 | 1 | item 10000099999 | 2 | item 9999999998 | 3 | item 9999899997 | 4 | item 9999799996 | 5 | item 9999699995 | 6 | item 9999599994 | 7 | item 99994(7 rows)
索引の前は Seq Scan on items、後は Index Scan using items_v_idx on items。道筋が変わりました。返った行は、どちらも id 99994〜100000 の同じ7行です。集合は変わらず、並びだけが逆になりました。 前は 99994 | 7 から、後は 100000 | 1 から始まります。
実演で、索引を作る前と後の SELECT 文はどう違っていましたか。
守られるのは、宣言した分だけ
集合が変わらないのは、条件 v < 8 を宣言したからです。データベースはどの道筋を通っても、条件を満たす行を過不足なく返します。
並びが変わってよいのは、並びを宣言していないからです。PostgreSQL 18 の公式文書は、並べ替えを指定しない場合について書いています。
The actual order in that case will depend on the scan and join plan types and the order on disk, but it must not be relied on.
順序は計画の種類とディスク上の順序に依存する、と公式が書いています。索引で計画が変われば並びは変わりえます。ただし「索引を作ると並びが揃う」とは言えません。
Codd は同じ節で、索引は improve response to queries and updates 一方、slow down response to insertions and deletions とも書いています。索引は答えを変えずに、問い合わせ・更新の速さと、挿入・削除の速さを交換する仕組みです。
答えを変えず、速さだけ変わるもう一つの例
同じ形は CPU にもあります。CPU は、メモリより小さく速い記憶(キャッシュ)を手元に持っています。次の2つのループはどちらも2次元配列の全要素を足します。キャッシュは別コースの『キャッシュと記憶階層』の回で扱います。
// 速い: 行に沿って読む(ストライド1)for (i = 0; i < N; i++)for (j = 0; j < N; j++)sum += a[i][j];// 遅い: 列に沿って読む(ストライドN)for (j = 0; j < N; j++)for (i = 0; i < N; i++)sum += a[i][j];
同じ回は「この2つは同じ答えを出し、命令数もほぼ同じです」と述べ、図に「答えは同じ。違うのは速度だけ」と添えています。コードにはキャッシュを使えとはどこにも書いていません。キャッシュが効くかどうかは、書いたものの外で決まります。
違いもあります。ループの順番はプログラマが書いたもので、速い書き方を選ぶのはプログラマです。SQL では道筋を書かないので、選ぶのはデータベースです。
「v に索引を作ったら v の小さい順に返ってきた。だからこのクエリの ORDER BY v は消してよい」という判断は妥当ですか。
SQL と索引
WHERE v < 8 は条件だけを宣言しています。索引を作ると計画が Seq Scan から Index Scan に変わり、同じ7行が逆の並びで返りました。道筋を選んだのはデータベースです。
項目 索引の前 索引の後SQL 文 同じ 同じ計画 Seq Scan Index Scan返った行 id 99994〜100000 id 99994〜100000並び v = 7,6,…,1 v = 1,2,…,7
C のループとキャッシュ
2つのループは同じ合計を出し、速さだけが違います。コードはキャッシュを名指ししていません。こちらは読む順番をプログラマが書くので、速い道筋を選ぶのもプログラマです。
SQL の索引と CPU のキャッシュ。どちらも「速くする仕組み」ですが、答えとの関係で共通しているのは何でしょうか。
それぞれ、書いた文やコードの中に仕組みの名前が出てくるかを見てください。
この章のまとめ
- SQL は条件を書き、道筋を書かない。道筋(実行計画)はデータベースが選び、
EXPLAINで見える。 - Codd 1970 は、情報の観点では索引を
a redundant componentと呼び、道筋を名前で参照するプログラムは索引が消えると壊れると書いた。 - 実演では同じ文のまま Seq Scan から Index Scan に変わり、同じ7行が逆の並びで返った(v を降順に入れた表での結果)。
- 並びは宣言していないので道筋次第。値をばらばらに入れた表では、索引を使っても並びは変わらなかった。並びは ORDER BY でしか保証されない。
- データベースが守るのは宣言したことだけ。索引は答えの集合を変えず、道筋を変える。
自分の現場で確かめる
読んだだけでは身につきません。手元の環境で実際に見てみてください。
理解度チェック
読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。
Codd の 1970 年の論文は、情報という観点から見た索引を何と呼んでいますか。
用語集(4語)
- 索引(インデックス)
- 表とは別に持つ、探すための構造。Codd 1970 は情報の観点では `a redundant component` と呼ぶ。消しても答えは変わらない。
- WHERE
- SELECT で、欲しい行の条件を書く句。条件だけを書き、探し方は書かない。
- 実行計画
- データベースが選んだ、問い合わせの実際の処理手順。Seq Scan(表を端から順に読む)や Index Scan(索引をたどる)などの組み合わせ。
- EXPLAIN
- 問い合わせの実行計画を表示させるコマンド。本レッスンでは PostgreSQL 18.6 で `(costs off)` を付け、見積もりの数値を出さない形で使った。