やってみる

アウトプットすべく己を導くためのブログ。その試行錯誤すらたれ流す。

📌 ？
トップ > SQLite3 > SQLite3クエリプランニング（インデックスの働き）

SQLite3クエリプランニング（インデックスの働き）

SQLite3

　SQLite3がどのようにクエリを実行するか。高速化のためにどうすべきか。index, select where, and/or, rowid, order by。

成果物

情報源

　クエリプランナーは無数にあるアルゴリズムの内、最も高速に実行できる方法を選択しようとするAIである。ただしクエリプランナーを使うには、インデックスを使う必要がある。

目次

  1. 検索
    1. インデックスなし
    2. rowid
    3. インデックス
    4. 複数行の結果
    5. and
    6. 複数列インデックス
    7. カバリング・インデックス
    8. or
  2. ソート
    1. rowid
    2. インデックス
    3. カバリング・インデックス
  3. 検索＆ソート
    1. 複数列インデックス
    2. カバリング・インデックス
    3. 部分的ソート（インデックス）
  4. without rowid表

0. 準備

0.sql

CREATE TABLE FruitsForSale(
  Fruit TEXT, -- 果物の名前
  State TEXT, -- 果物を売っている州の名前
  Price REAL  -- 果物の価格
);
insert into FruitsForSale values('Orange','FL',0.85);
insert into FruitsForSale values('Apple','NC',0.45);
insert into FruitsForSale values('Peach','SC',0.60);
insert into FruitsForSale values('Grape','CA',0.80);
insert into FruitsForSale values('Lemon','FL',1.25);
insert into FruitsForSale values('Strawberry','NC',2.45);
insert into FruitsForSale values('Orange','CA',1.05);

1. 検索

1-1. インデックスなし

1-1.sql

.read 0.sql
SELECT price FROM fruitsforsale WHERE fruit='Peach';

0.6

　フルテーブルスキャンされる。（全表スキャン、全表走査）

　このクエリを満たすために、SQLiteはテーブルからすべての行を読み取り、fruit列の値がPeachであるかどうかを確認し、ある場合はその行からprice列を出力する。これは 、対象の1行を見つけるためにテーブルの内容全体を読み取って検査する必要があるため、フルテーブルスキャンと呼ばれるアルゴリズムである。もしテーブルに700万行が含まれる場合、膨大なコンテンツを読み取ることがある。そのため、通常は全表スキャンを回避しようとする。

1-2. rowid

1-2.sql

.read 0.sql
SELECT price FROM fruitsforsale WHERE rowid=4;

0.8

　全表スキャンを回避する方法のひとつ。rowid(integer primary key)による検索。最も高速に検索できる。劇的な差があるため、できるかぎり使うべき。

方法 レコード数に応じた時間
全表スキャン N
rowid N / logN

　N / logNはJavaScriptでN / Math.log(N)で合ってる、のか？

N =
N / Math.log(N) =

　「1000万件のときは約100万倍高速になる」とある。だが、上記に10000000を入力しても620420が出てくる。10000000/620420=16.*であり約16倍。何か間違っているのか？

1-3. インデックス

　rowidは重複しない数値である。これは意味のない値であるため、検索キーワードになりえない。よって、ふつうはrowidを検索条件にはできない。

　今回は検索キーワードにFruit列の値を使いたい。つまり、果物の名前を検索キーワードにしたい。これを効率的にするにはインデックスを作る。

CREATE INDEX Idx1 ON FruitsForSale(Fruit);

　上記のインデックスは以下の表になる。Fruit列はソートキーに使う主キー。rowidはFruitで一意にならないとき一意に特定するための副キー。たとえばFruit=Orangeのレコードは2つあり一意に特定できない。このときrowidを使って一意に特定する。

Fruit rowid
Apple 2
Grape 4
Lemon 5
Orange 1
Orange 7
Peach 3
Strawberry 6 
SELECT price FROM FruitsForSale WHERE Fruit='Peach';

0.6

　上記SQL文は、インデックスidx1とテーブルFruitsForSaleを使って絞り込む。

  1. インデックスIdx1からFruit列の値がPeachの行を取得する
  2. 1で取得した行のrowid列値を取得する
  3. 2に一致するレコードをFruitsForSale表から取得する
  4. 3のPrice列を返す

1-4. 複数行の結果

SELECT Price FROM FruitsForSale WHERE Fruit='Orange';

0.85
1.05

　検索結果が複数行のときでもインデックスは動作する。インデックスの次の行に進んで、順次くりかえす。

1-5. and

　andで条件をさらに絞り込む。

SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA';

1.05

　state列値がFLのレコードまで検索対象にしている。つまり、バイナリ検索回数は1-4. 複数行の結果と同じである。

　stateのインデックスを追加しても同様である。

CREATE INDEX Idx2 ON FruitsForSale(State);

　今度はFruit列の値がOrangeでなくGrapeの行まで取得できてしまい、検索回数は同じく2回。減らせない。

　一意に特定するのに必要なすべての列でインデックスを作る必要がある。

1-6. 複数列インデックス

　andで複数列による絞込をするとき最大パフォーマンスを得るなら、各列のインデックスが必要である。

1_6_0.sql

CREATE INDEX Idx3 ON FruitsForSale(Fruit, State);

　上記のインデックスは以下の表と同じである。

Fruit state rowid
Apple NC 2
Grape CA 4
Lemon FL 5
Orange CA 1
Orange FL 7
Peach SC 3
Strawberry NC 6 
SELECT price FROM FruitsForSale WHERE fruit='Orange' AND state='CA';

　上記の条件でレコードを一意に特定できる。あとはrowidを条件に、FruitsForSaleからレコードを取得するだけ。

　なお、すべての列を使わずともインデックスを使った検索ができる。たとえば以下のように。

SELECT price FROM fruitsforsale WHERE fruit='Peach'

1-7. カバリング・インデックス

　取得する列もインデックスに含めたとき、表の参照を行わずに済む。これをカバリング・インデックスと呼ぶ。

CREATE INDEX Idx4 ON FruitsForSale(Fruit, State, Price);

SELECT price FROM fruitsforsale WHERE fruit='Orange' AND state='CA';

　そのため検索速度は約2倍になる。だが、100万倍となるインデックス使用ほど効果的ではない。

1-8. or

　1-6. 複数列インデックスはandのときのみ有効。orのときの効果は低い。

SELECT price FROM FruitsForSale WHERE fruit='Orange' OR state='CA';

　FuruitとStateのインデックスをunion結合して取得する。

　ただし、もしインデックスがない列をor対象にすると、全表スキャンになってしまう。

2. ソート

　インデックスを使うことで、ソートを高速化できる。そしてソートを使って取得を高速化できる。つまり、インデックスを使うことでソートと取得を高速化できる。

SELECT * FROM FruitsForSale ORDER BY Fruit;

　出力行数がKなら、ソート時間はK * logK。これは全表スキャンよりもはるかに長くなってしまう。容量も圧迫される。

2-1. rowid

　rowidでのソートを指定されたとき、保存されたバイナリ配列と同一のためソートはしない。よって高速。

SELECT * FROM fruitsforsale ORDER BY rowid;

　降順のときも同様。ただし、最初の行から最終行へ向かうのでなく、最終行から最初の行へ向かうようテーブルスキャンする。

SELECT * FROM fruitsforsale ORDER BY rowid DESC;

　もっとも、rowidは一意に特定するためだけであり、ビジネスロジック的には何の意味もない。よって通常は役に立たないため使わない。

2-2. インデックス

CREATE INDEX Idx1 ON FruitsForSale(Fruit);
SELECT * FROM fruitsforsale ORDER BY Fruit;

　ソートキーのインデックスを作った。だが、ソートの速度はインデックスを使わない場合と同じである。ただしFruitsForSale表よりもPrice列などがないためデータ量が少ない点で有利。

2-3. カバリング・インデックス

CREATE INDEX Idx4 ON FruitsForSale(Fruit, State, Price);
SELECT * FROM FruitsForSale ORDER BY Fruit;

　条件と取得、それぞれに使う列がすべてインデックスに含まれている場合、最も高速にソートできる。レコード数Nに比例した速度。

3. 検索＆ソート

　ふつうは検索とソートを同時に行うだろう。

3-1. 複数列インデックス

CREATE INDEX Idx3 ON FruitsForSale(Fruit, State);
SELECT price FROM FruitsForSale WHERE Fruit='Orange' ORDER BY State;
Fruit state rowid
Apple NC 2
Grape CA 4
Lemon FL 5
Orange CA 1
Orange FL 7
Peach SC 3
Strawberry NC 6

　インデックスはソートされた状態で保存されるため、ソートの実行が不要。

  1. Idx3からFruit=Orangeに一致するrowid, 1,7を取得する
  2. 1に一致する行をFruitsForSale表から取得する

3-2. カバリング・インデックス

CREATE INDEX Idx4 ON FruitsForSale(Fruit, State, Price);
SELECT * FROM FruitsForSale WHERE Fruit='Orange' ORDER BY State;

　条件・ソート・取得において、すべての列がIdx4にある。よってFruitsForSaleを参照する必要がない。

Fruit State Price rowid
Apple NC 0.45 2
Grape CA 0.80 4
Lemon FL 1.25 5
Orange CA 1.05 1
Orange FL 0.85 7
Peach SC 0.60 3
Strawberry 2.45 NC 6

　降順にしても同様。

SELECT * FROM FruitsForSale WHERE Fruit='Orange' ORDER BY State DESC;

3-3. 部分的ソート（インデックス）

　上記までのselect文だとPrice列が順不同になる。そこでソート順にPriceを追加する。

CREATE INDEX Idx4 ON FruitsForSale(Fruit, State, Price);
SELECT * FROM FruitsForSale ORDER BY Fruit, Price;

　上記のように完全に順位付けできるよう小さなソートキーも指定したほうが良い。理由は以下。

  1. 複数の小さなソートは、単一の大きなソートよりも少ないCPUサイクルをまとめて使用する
  2. それぞれの小さなソートは独立して実行される。つまり、一時ストレージに保持する必要がある情報は一度に非常に少なくなる
  3. インデックスが原因ですでに正しい順序になっているORDER BYの列は、ソートキーから省略でき、ストレージとCPU時間をさらに削減できる
  4. 出力行は、小さな並べ替えが完了するたびに、テーブルスキャンが完了するかなり前にアプリケーションに返される
  5. LIMIT句が存在する場合、テーブル全体のスキャンを回避できる可能性がある

4. without rowid表

　without rowid表も同様。rowidがprimary keyに置き換えられるだけ。

所感

　RDBMSのインデックスについて理解が進んだ。

　ドキュメントのコードに微妙な脱字が混ざっていた。fruitforsaleのようにfruitsとすべきところsが抜けているところが一部ある。あと、大文字小文字は統一して欲しかった。SQL文脈では無視されるのだろうが。

対象環境

$ uname -a
Linux raspberrypi 4.19.42-v7+ #1218 SMP Tue May 14 00:48:17 BST 2019 armv7l GNU/Linux

前回まで