二次索引

大学で使用した自作の資料等を,手直しの上公開している. クリエイティブ・コモンズ BY NC SA.

リレーショナルデータベースの基礎であるテーブル定義,一貫性制約,SQL,結合と分解,トランザクション,埋め込みSQL,実行計画,二次索引を学ぶ.SQLite 3 を用いて,SQL についての演習も行う.

【サイト内の関連ページ】

  • リレーショナルデータベースの基本まとめ:別ページ »で説明
  • SQL 入門演習(SQLite 3 を使用)(全3回):別ページ »にまとめ

    入門者向け.リレーショナルデータベースを知る.

  • リレーショナルデータベースシステム(スライド資料と SQL 演習)(全15回):別ページ »にまとめ

    入門者向け.設計と利用と運用.MySQL, Access を利用.基本を学ぶ.演習付き.

  • リレーショナルデータベース演習(全15回):別ページ »にまとめ

    入門者向け.設計と利用に関する演習.

  • リレーショナルデータベースの基礎(まとめ) [PDF], [ワードファイル]

    基礎を1つにまとめた資料.











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

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

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

演習で行うこと

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

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

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 テーブルを使う。

下記の操作により、演習用のデータ(1000行)を、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)

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

ここでは,テーブル point3 の属性 xの二次索引を作る. (Generate a secondary index of the table 'point3')
  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;
    

【問い合わせ計画の要点】

上の図から、二次索引が使われていることが確認できる。

二次索引は事前に作成済み。二次索引は多数の索引エントリから構成され、個々の索引エントリは、元のテーブルの各行に対応する。 最初,カーソル番号1のカーソルは二次索引のルートノードにセットされる.(ルートノードとは、個々の二次索引の管理情報を含むノードである)。 次に、「x < 1000000000」という条件式を満たす最小の x を含む行の 索引エントリが、二次索引の中から検索される。この処理は高速である。カーソル番号1のカーソルは、いま検索された索引エントリを指し示すように動く。 その後、カーソル番号1のカーソルを使って、 テーブル point3 の行を取り出しながら、 カーソル番号1のカーソルが,二次索引の中だけを動く. 「x < 1000000000」という条件式を満たすすべての行が取り出し終えたら、処理を終える。

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

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

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

アドレス (addr) オペコード 主なオペランド  
1 Integer P1 = 1000000000, P2 = 1 レジスタ1に,値1000000000をセットする (store 1000000000 into register #1)
3 OpenRead P1 = 0, P2 = 12 ルート・ページが 12 であるようなテーブル (この場合は,テーブル point3) のカーソルを作る. カーソル番号は0 (Open table 'point3' for read, and make a cursor)
4 OpenRead P1 = 0, P2 = 46 ルート・ページが 46 であるような二次索引 (この場合は idx1 ) のカーソルを別に作る. カーソル番号は1
4 Rewind P1 = 1, P2 = 23 P1 = 1 なので、カーソル番号1のカーソルを使う. カーソルを,二次索引 idx のルートノードを指し示すようにする.二次索引が空の場合には,アドレス 23 (「Close」の行)にジャンプする
7 IdxGE P1 = 1, P2 = 23 P1 = 1 なので、カーソル番号1のカーソルを使う. 検索キーの値(この場合は、レジスタ1に入っている「1000000000」)と、 カーソルが指し示している値を比較する。 もし、 「カーソルが指し示している値」 ≧ 「検索キーの値」のときは、アドレス 23 にジャンプする.
11 から 12 Seekなど 二次索引を使って、カーソル0を動かす。
14 から 20 Columnなど id, x, y, z, created_at の値を,それぞれ、レジスタ 4, 5, 6, 7, 8 に格納
21 ResultRow P1 = 4, P2 = 5 レジスタ 4 からレジスタ 8 までの値 (レジスタの個数は,P2 に指定した5個) を1行として出力する (Generate output using registers)
22 Next P2 = 8 もし,カーソルが指し示す二次索引ノードが末端ならば、次の命令に進む. もし,カーソルが指し示す二次索引ノードが末端でなければ、カーソルを1つ進めて、アドレス8 にジャンプする.