二次索引

---

---

---

---

• 索引 (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 using Sqliteman)

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

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

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

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

   データベースファイル /home/ubuntuuser/mydb を選び， 「開く」をクリック (Click '開く' after choosing the database file "/home/ubuntuuser/mydb2")

   

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

   データベースファイル C:\SQLite\mydb を選び， 「開く」をクリック (Click '開く' after choosing the database file "C:\SQLite\mydb")

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

   

SQL を用いたテーブル定義と一貫性制約の記述 (Table definition and integrity constraint specification using SQL)

SQL を用いて，point3 テーブルを定義し，一貫性制約を記述する． (Define 'point3' table and specify integrity constrants of the table using SQL)

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

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

   次の SQL を入力し，「Run SQL」のアイコンをクリック (Write the following SQL, and click "Run SQL" icon).

   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. コンソールの確認 (Inspect console)

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

   

SQL を用いたテーブルへの行の挿入 (Insert rows into a table using SQL)

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

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

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

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

   
4. 「Close」をクリック
   

データベースの構造の確認 (Database Structure)

1. sqlite_master をダブルクリック (Double-click 'sqlite_master)
2. テーブル point3 のルート・ページ番号が分かる (Root page number of each table)

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

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

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

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

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

データベース管理システムは， SQL 文をコンパイルし，SQL 問い合わせ計画を作る． SQL 問い合わせ計画とは，データベースに関する基本的なオペレータの並びである． (Database management system compliles a SQL statement into a SQL query plan. SQL query plan is a sequence or a tree of database operations ).

SQLite 3の問い合わせ計画については，SQLite Virtual Machine Opcodes の Web ページなどを見てください．(please refer to https://www.sqlite.org/opcode.html for SQLite opcodes)

• SQL の問い合わせの発行と評価結果の確認 (Issue SQL queries and inspect the results)

  SELECT * FROM point3 WHERE x < 1000000000;
  

  ※「1000000000」では、0 は 9個

  
• SQL 問い合わせ計画の表示 (SQL query plan)

  SQL 文の前に「EXPLAIN」を付ける．(Add 'EXPLAIN' before a SQL statement)

  EXPLAIN SELECT * FROM point3 WHERE x < 1000000000;
  

  

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

  アドレス (addr)	オペコード	主なオペランド
  1	Integer	P1 = 1000000000, P2 = 1	レジスタ1に，値1000000000をセットする (store 1000000000 into register #1)
  3	OpenRead	P2 = 12	ルート・ページが 12 であるようなテーブル (この場合は，テーブル point3) のカーソルを作る (Open table 'point3' for read, and make a cursor)
  4	Rewind	P2 = 18	カーソルを，テーブル point3 の先頭を指し示すようにする．テーブルが空の場合には，アドレス 18 （「Close」の行）にジャンプする (Use the first row. If the first row is empty then jump to '18')
  5	Column	P2 = 1, P3 = 2	列番号1の値 (つまり x の値) を，レジスタ 2 に格納する．(Save #1 column value into the register #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 にジャンプする． (jump to 17 if and only if register #1 ≧ #2)
  8 から 15	Columnなど		id, x, y, z, created_at の値を，それぞれ、レジスタ 4, 5, 6, 7, 8 に格納
  16	ResultRow	P1 = 4, P2 = 5	レジスタ 4 からレジスタ 8 までの値 (レジスタの個数は，P2 に指定した5個) を１行として出力する (Generate output using registers)
  17	Next	P2 = 5	もし，カーソルが指し示すレコードが末端レコードならば、次の命令に進む． もし，カーソルが指し示すレコードが末端レコードでなければ、カーソルを１つ進めて、アドレス5 （「Column 0 1 2」のところ) にジャンプする． (Advance cursor to the next tow. If there are more rows, then jump to the address '5')

Sqliteman を用いた二次索引の追加 (generate a secondary index using Sqliteman)

1. CREATE INDEX を用いた二次索引の生成 (Generate a secondary index using 'CREATE INDEX')

   CREATE INDEX idx1 ON point3( x );
   

   「idx1は索引名である．索引の管理（索引の削除など）に使用される． ('idx1' is index name).

   

   索引は数秒以内で生成される．(The secondary index will be generated in a several seconds)

2. コンソールの確認 (Inspect console)

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

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

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

   

二次索引による問い合わせ計画の変化 (secondary index and query plan)

■ データベースの構造の確認 (Database Structure)

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

   (Inspect the root page number of the secondary index 'idx1'. The number is automatically decided by the database management system)

■ SQL 問い合わせ計画の表示 (SQL query plan)

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

   EXPLAIN SELECT * FROM point3 WHERE x < 1000000000;
   

   

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

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

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