二次索引の基礎

---

---

---

---

• 索引 (index)

  索引を用いることで，レコードを効率よく検索することができる．

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

• 主索引 (primary index)

  主キー (Key Primary) の値とレコードとを直接結びつけているような索引構造のことを，この資料では「主索引」と呼ぶことにする．

  各テーブルに，1つの主索引がある（１つのテーブルに２個以上の主索引はありえない）．

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

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

• 二次索引 (secondary index)

  主索引のキー以外の属性による索引構造．

  二次索引は，１つのテーブルに対して任意個作ることができる．二次索引は自由に追加，削除できるのが普通である．

【SQLite 3 の主要なオペコード (Opcode) の要点】

• OpenRead: ルート・ページが P2 であるようなテーブル（または二次索引）のカーソルを作る． P1 にはカーソル番号を設定する． P4 には、テーブルの列数を設定するか， KeyInfo 構造体 (KeyInfo 構造体）と呼ばれる構造体へのポインタを設定する．
• Rewind: 将来の Column, Rowid, Next 命令の実行に備えて，カーソル P1 をテーブルの先頭（または二次索引のルートノード）を指し示すようにする．テーブル（または二次索引）が空の場合には，アドレス P2 にジャンプする．o
• Column: カーソル P1 (cursor P1) が指し示すレコードの P2 番目の桁 (P2-th column) からデータを取り出して，レジスタ P3 に格納する．(列番号は 0 から始まる)
• Rowid: カーソル P1 (cursor P1) が指し示すレコードの主キーの値を，レジスタ P2 に格納する．
• MakeRecord: レジスタP1 から レジスタ(P1+P2-1) までの値を，テーブルの１行、あるいは索引のキー (key) として使うことを示す． P4には column affinity を文字列として指定できる．column affinity の各文字は，SQLite バージョン 3.7.9 では次のように定義されている．

  #define SQLITE_AFF_TEXT     'a'
  #define SQLITE_AFF_NONE     'b'
  #define SQLITE_AFF_NUMERIC  'c'
  #define SQLITE_AFF_integer  'd'
  #define SQLITE_AFF_real     'e'
  

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

* SQLite 3 のオペコードの説明は http://www.hwaci.com/sw/sqlite/opcode.html にある．

* SQLite 3の SQL の説明は http://www.hwaci.com/sw/sqlite/lang.html (English Web Page) にある．

演習で行うこと

• 二次索引の生成

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

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

SQLite 3 の SQL 演習に関連する部分

SQLite 3の SQL の説明は http://www.hwaci.com/sw/sqlite/lang.html (English Web Page) にある．

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

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

• DROP INDEX <index-name>;

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

Sqliteman で既存のデータベースを開く

すでに作成済みのデータベースを，下記の手順で開くことができる．

以下の手順で，既存のデータベースファイルを開く． (Open an existing database file)

1. 「File」→ 「Open」
   
2. データベースファイルを開く

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

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

   

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

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

   要するに，/home/＜ユーザ名＞/SQLite 3の下の mydb を選ぶ．　

   

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

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

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

1. point3 テーブルの定義 (Define a table)

   次の SQL を入力し，「Run SQL」のアイコンをクリック

   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 Editor」のウインドウには，SQL プログラムを書くことができる． In the 'SQL string' window, you can write down SQL program(s).

   
2. コンソールの確認

   エラーメッセージが出ていないことを確認

   

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

以前の授業で定義した point3 テーブルを使う。

下記の操作により、演習用のデータ（１０００行）を、point3 テーブルに格納する。

1. Sqliteman で、point3 を右クリック (right click) し、「Populate Table...」を選ぶ．
   
2. Number of Rows to Populate に「1000」を設定する。 x の行, y の行, z の行は「Random Number」に設定し、 「Populate」をクリック
   
3. 確認

   エラーメッセージが出ていないことを確認

   
4. 「Close」をクリック
   

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

1. sqlite_master をダブルクリック
2. テーブル point3 のルート・ページ番号が分かる

   下の図では、point3　テーブルのルートページ (root page) 番号は 12 になっている。 ルート・ページ番号は，SQLite 3 システムが決める値である。 ルート・ページ番号が 12 以外の値になっていても問題はない。

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

Sqliteman を用いた SQL 問い合わせ計画の表示

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

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

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

SQLite 3の問い合わせ計画については，SQLite Virtual Machine Opcodes の Web ページなどを見てください．

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

  SELECT * FROM point3 WHERE x < 1000000000;
  

  *「1000000000」では、0 は 9個

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

  SQL 文の前に「EXPLAIN」を付ける．

  EXPLAIN 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 を比較．P1 の値 ≧ P2 の値のときに限り，アドレス 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 0 1 2」のところ) にジャンプする．

Sqliteman を用いた二次索引の追加

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

   CREATE INDEX idx1 ON point3( x );
   

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

   

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

2. コンソールの確認

   エラーメッセージが出ていないことを確認

   
3. Sqliteman での二次索引の確認

   下の図のように、テーブルpoint3の「indexes」を展開して、idx1 が出来ていることを確認する。

   

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

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

1. sqlite_master をダブルクリック
   
2. テーブル point3 と二次索引 idx1 のルート・ページ番号が分かる
   
   二次索引 idx1 のルート・ページ番号（上の図では「46」）を確認しておく．ルート・ページ番号は，データベース管理システムが決める値なので，違う値になっているはずである．

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

1. 先ほどと同じ SQL 問い合わせを評価させる． SQL 文の前に「EXPLAIN」を付けている．

   EXPLAIN SELECT * FROM point3 WHERE x < 1000000000;
   

   

二次索引がないとき，テーブルの本体が１行ずつ処理される．テーブルの全ての行について処理が繰り返される． (このことを「tuple at a time」ともいう)。

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

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