二次索引の基礎

---

---

---

---

索引の基礎

• 索引 (index)

  索引を用いることで、レコードを効率よく検索できる。

  ただし、レコードデータの更新時には索引の維持 (maintenance) を行わなければならないので、索引を増やしすぎるのはよくない。

• 主索引 (primary index)

  主キー (primary key) の値とレコードとを直接結びつけているような索引構造のことを、この資料では「主索引」と呼ぶ。

  各テーブルに主索引が一つある（一つのテーブルに二個以上の主索引はありえない）。

  テーブル定義において「primary key」と指定した属性が主キーになるのが普通である。

  テーブル定義が「primary key」を含まない場合には、データベース管理システムがテーブルの各行を識別する識別番号を自動生成し、それを主索引のキーとして使うのが普通である。

• 二次索引 (secondary index)

  主索引のキー以外の属性による索引構造である。

  二次索引は、一つのテーブルに対して任意個作成できる。二次索引は自由に追加、削除できるのが普通である。

SQLite 3 の主要なオペコード (opcode)

• OpenRead: ルート・ページが P2 であるようなテーブル（または二次索引）のカーソルを作る。P1 にはカーソル番号を設定する。P4 には、テーブルの列数、または KeyInfo 構造体（照合順序などの情報をもつ構造体）へのポインタを設定する。
• Rewind: これから実行する Column、Rowid、Next 命令に備えて、カーソル P1 をテーブルの先頭（または索引の先頭）を指し示すようにする。テーブル（または索引）が空の場合には、アドレス P2 にジャンプする。
• Column: カーソル P1 が指し示すレコードの P2 番目の列（列番号は 0 から始まる）からデータを取り出して、レジスタ P3 に格納する。
• Rowid: カーソル P1 が指し示すレコードの主キーの値を、レジスタ P2 に格納する。
• MakeRecord: レジスタ P1 からレジスタ(P1+P2-1) までの値を、テーブルの一行、あるいは索引のキー (key) として使うことを示す。P4 には column affinity（列の型親和性）を文字列として指定できる。column affinity の各文字は、SQLite の版により次のように定義されている。

  #define SQLITE_AFF_BLOB     'A'
  #define SQLITE_AFF_TEXT     'B'
  #define SQLITE_AFF_NUMERIC  'C'
  #define SQLITE_AFF_INTEGER  'D'
  #define SQLITE_AFF_REAL     'E'
  

• IdxInsert: 索引 P1 にデータを挿入する。
• ResultRow: レジスタ P1 からレジスタ(P1+P2-1) までの値を一行として出力する。
• SeekGE: カーソル P1 がテーブルを指し示しているときは、レジスタ P3 の値を検索キーとして使う。カーソル P1 が索引を指し示すときは、レジスタ P3 からレジスタ(P3+P4-1) までを検索キーとして使う。カーソル P1 の位置を、検索キー以上という条件を満たすなかで最小の要素を指し示すように動かす。そのような要素がない場合にはアドレス P2 にジャンプする。
• IdxGE: レジスタ P3 からレジスタ(P3+P4-1) までを検索キーとして使う。現在 P1 が指し示している索引エントリ (index entry) と検索キーを比較する。索引エントリが検索キー以上であれば、アドレス P2 にジャンプする。そうでなければ次に進む。
• Eq: レジスタ P1 の値とレジスタ P3 の値が等しいときに限り、アドレス P2 にジャンプする。
• Ne: レジスタ P1 の値とレジスタ P3 の値が等しくないときに限り、アドレス P2 にジャンプする。
• Ge: レジスタ P3 の値がレジスタ P1 の値以上のときに限り、アドレス P2 にジャンプする。
• Next: カーソル P1 が指し示すレコードが末端レコードならば、次の命令に進む。末端レコードでなければ、カーソル P1 を一つ進めて、アドレス P2 にジャンプする。
• Goto: アドレス P2 にジャンプする。

SQLite Manager Tool で既存のデータベースを開く

すでに作成済みのデータベースを、下記の手順で開く。

1. ツールバーの「DBオープン (Ctrl+O)」ボタンをクリックする。
   
2. データベースファイルを開く

   Ubuntu での実行例（「/home/ubuntuuser/mydb」を開く場合）

   データベースファイル /home/ubuntuuser/mydb を選び、「開く」をクリックする。

   

   Windows での実行例（「C:\SQLite\mydb」を開く場合）

   データベースファイル C:\SQLite\mydb を選び、「開く」をクリックする。

   

SQL を用いたテーブル定義と一貫性制約の記述

SQL を用いて、point3 テーブルを定義し、一貫性制約を記述する。

リレーショナル・スキーマ (relational schema): point3(id, x, y, z, created_at)

1. point3 テーブルの定義

   次の SQL を入力し、「▶ SQL実行 (F5)」を押下する。

   create table point3 (
       id          integer  primary key autoincrement not null,
       x           real not null,
       y           real not null,
       z           real not null,
       created_at  datetime not null );
   

   「SQLエディタ」欄には、SQL プログラムを書くことができる。

   
2. 出力欄の確認

   「出力」欄にエラーメッセージが表示されていないことを確認する。

   

SQL を用いたテーブルへの行の挿入

先に定義した point3 テーブルを使う。下記の操作により、演習用のデータ（1000行）を point3 テーブルに格納する。

1. 演習用データ（1000行分のCSVファイル）を用意する。
   
2. ツールバーの「CSV読込」ボタンをクリックするか、「SQLエディタ」に次のドットコマンドを記述し、「▶ SQL実行 (F5)」を押下する。

   x の値、y の値、z の値は、あらかじめ乱数で生成しておいたCSVファイルの値を使用する。

   .import "point3.csv" "point3"
   

   
3. 確認

   「出力」欄にエラーメッセージが表示されていないことを確認する。

   
4. 読込完了のメッセージを確認する。
   

データベースの構造の確認

1. 「SQLエディタ」に「SELECT * FROM sqlite_master;」と入力し、「▶ SQL実行 (F5)」を押下する。
2. 「出力」欄にデータベーススキーマが表示されるので、テーブル point3 のルート・ページ番号を確認する。

   この資料の実行例では、point3 テーブルのルート・ページ (root page) 番号は 12 になっている。ルート・ページ番号は SQLite 3 が決める値である。ルート・ページ番号が 12 以外の値になっていても問題はない。

この資料では、point3 テーブルのルート・ページは 12 になっているものとして説明を続ける。

SQLite Manager Tool を用いた SQL 問い合わせ計画の表示

単一テーブルに対する問い合わせの SQL 問い合わせ計画の表示例

ここでは、条件を満たす行のみを表示する SQL の問い合わせ計画の表示例を示す。

データベース管理システムは、SQL 文をコンパイルし、問い合わせ計画を作る。問い合わせ計画とは、データベースに関する基本的なオペレータの並びである。

• SQL の問い合わせの発行と評価結果の確認

  「SQLエディタ」に次の SQL を入力し、「▶ SQL実行 (F5)」を押下する。「出力」欄で評価結果を確認する。

  SELECT * FROM point3 WHERE x < 1000000000;
  

  「1000000000」では、0 は 9個である。

  
• SQL 問い合わせ計画の表示

  「SQLエディタ」に上記の SQL 文を記述したまま、ツールバーの「実行計画解析 (F6)」を押下する。

  SELECT * FROM point3 WHERE x < 1000000000;
  

  

  【表示された問い合わせ計画の要点】

  アドレス (addr)	オペコード	主なオペランド
  1	Integer	P1 = 1000000000, P2 = 1	レジスタ 1 に、値 1000000000 をセットする
  3	OpenRead	P2 = 12	ルート・ページが 12 であるようなテーブルのカーソルを作る
  4	Rewind	P2 = 18	カーソルを、テーブル point3 の先頭を指し示すようにする。テーブルが空の場合には、アドレス 18（「Close」の行）にジャンプする
  5	Column	P2 = 1, P3 = 2	列番号 1 の値（つまり x の値）を、レジスタ 2 に格納する。 列番号 0 : id 列番号 1 : x 列番号 2 : y 列番号 3 : z 列番号 4 : created_at
  7	Ge	P1 = 1, P2 = 17, P3 = 2	条件付きジャンプ。レジスタ 1 の値とレジスタ 2 の値を比較する。レジスタ 2 の値がレジスタ 1 の値以上のときに限り、アドレス 17 にジャンプする（条件を満たさない行を読み飛ばす）
  8 から 15	Column など		id, x, y, z, created_at の値を、それぞれレジスタ 4, 5, 6, 7, 8 に格納する
  16	ResultRow	P1 = 4, P2 = 5	レジスタ 4 からレジスタ 8 までの値（レジスタの個数は、P2 に指定した 5 個）を一行として出力する
  17	Next	P2 = 5	カーソルが指し示すレコードが末端レコードならば、次の命令に進む。末端レコードでなければ、カーソルを一つ進めて、アドレス 5（「Column」のところ）にジャンプする

SQLite Manager Tool を用いた二次索引の追加

ここでは、テーブル point3 の属性 x の二次索引を作る。

1. CREATE INDEX を用いた二次索引の生成

   「SQLエディタ」に次の SQL を入力し、「▶ SQL実行 (F5)」を押下する。

   CREATE INDEX idx1 ON point3( x );
   

   「idx1」は索引名である。索引の管理（索引の削除など）に使用される。

   

   索引は数秒以内で生成される。

2. 出力欄の確認

   「出力」欄にエラーメッセージが表示されていないことを確認する。

   
3. SQLite Manager Tool での二次索引の確認

   下の図のように、「スキーマナビゲータ」でテーブル point3 の索引一覧に idx1 ができていることを確認する。

   

二次索引による問い合わせ計画の変化

データベースの構造の確認

1. 「SQLエディタ」に「SELECT * FROM sqlite_master;」と入力し、「▶ SQL実行 (F5)」を押下する。
   
2. テーブル point3 と二次索引 idx1 のルート・ページ番号が分かる。
   
   二次索引 idx1 のルート・ページ番号（上の図では「46」）を確認しておく。ルート・ページ番号はデータベース管理システムが決める値なので、違う値になっているはずである。

SQL 問い合わせ計画の表示

1. 先ほどと同じ SQL 問い合わせを評価させる。「SQLエディタ」に SQL 文を記述したまま、ツールバーの「実行計画解析 (F6)」を押下する。

   SELECT * FROM point3 WHERE x < 1000000000;
   

   

二次索引がないときは、テーブルの本体が一行ずつ処理される。テーブルのすべての行について処理が繰り返される（このことを「tuple at a time」ともいう）。

二次索引を使うときは、テーブルの本体が一行ずつすべて処理されるわけではない。このことで、データベース処理がより高速になることが期待できる。

【表示された問い合わせ計画の要点】

演習

• 二次索引の生成

  CREATE INDEX <index-name> ON <table-name> ( <column-name の並び> )

  テーブル名と属性名を指定して、二次索引を生成する。「index-name」は二次索引の名前で、後で二次索引を削除するときなどに使う。

• 二次索引の削除

  DROP INDEX <index-name>;

  索引名を指定して二次索引を削除する。