鱒身(Masu_mi)のブログ

知った事をメモする場所。

SQLite を読んで再入門

前回、勢いでデバッガから入ったけど、このままでは整理されないので全体を把握したりインタフェースを確認したりした。

思ったのは提供されている以上、公式のIntroduction, Tutorial, Architecture, C/C++ Interfaceは最初に目を通した方が早い。 ちょっと無理やり進めた感が出てしまうし無駄が大幅に増えた。上を押さえてこそ解析する価値が出る。

アーキテクチャ要点メモ

アーキテクチャ の内容をメモする。

アーキテクチャ

Interface

インタフェースはmain.c, legacy.c, and vdbeapi.c など多くのファイルに散らばっている。 名前の衝突などを除き、基本的に sqlite3_ prefix がつく関数として公開されている。 一覧があるのでここを読む。

SQL Command Processor

バイトコード生成を行う。全体は Tokenizer, Parser, CodeGenerator に分かれている。

Tokenizer

Tokenizer がParser を呼び出す。珍しいらしい。 確かにsqlite3RunParser に先頭のToken情報を渡してParseを開始している。sqlite3RunParser 内でLemonに生成されたsqlite3Parserを呼び出している。 tokenizer.c に書かれている。

Parser

LALR(1)でLemonで生成される。シンタックスエラーでもメモリリークが起きずスレッドセーフらしい。 parse.y に書かれている。

CodeGenerator

VM用のバイトコード(Opcode)を生成する。生成されたバイトコードはsqlite3_stmt として扱われる。 expr.c が全体をハンドリングしている。 attach.c, auth.c, build.c,delete.c, expr.c, insert.c, pragma.c, select.c, trigger.c, update.c, vacuum.c and where.c などが具体的な各ステートメントに対応する。

sqlite3_stmtのライフサイクル

オブジェクトの説明 によるとstmtのライフサイクルは下の通り。 また sqlite3_stmtはvoid*的に扱える らしい。この仕様はどこで定義されているかよく分からなかった。

  1. Create the prepared statement object using sqlite3_prepare_v2().
  2. Bind values to parameters using the sqlite3_bind_*() interfaces.
  3. Run the SQL by calling sqlite3_step() one or more times.
  4. Reset the prepared statement using sqlite3_reset() then go back to step 2. Do this zero or more times.
  5. Destroy the object using sqlite3_finalize().

VirtualMachine

vdbe.cに全てのコードが含まれている。vdbe.h がインタフェース, vdbeInt.h が内部定義を定めている。 vdbemem.c にstrings, integer, floating point numbers, and BLOBs といった単一値が定義されている。

C のcallbackを呼び出す機構が存在しビルトイン関数も同様の仕組みで実装されている。 具体的にはfunc.c, date.c に定義されている。

sqlite3RegisterGlobalFunctions 関数の中でFUNCTION マクロなどを使いFuncDef配列の aBuiltinFunc を定義している。 そしてsqlite3FuncDefInsertを使いグローバル関数を登録している。 グローバル関数はハッシュテーブルで管理されており、そのハッシュテーブル自体はGLOBALマクロ経由でsqlite3_wsd_findによりpGlobalから取得される。 pGlobalにはsqilte3GlobalFunctionsをキーで登録されている。またpGlobalは静的なプロセス固有のストレージになっている。

B-Tree

SQLite はB-Treeを用いてDiskに維持される。実装は btree.cにある。 全てのB-Treeが単一ファイルに格納される。詳細な形式はコメント(btree.c)に記載されている。

PageCache

B-Treeは実際には固定データサイズ単位(default:1KiB, 512〜65536B)で操作を行う。 この単位で変更・コミット・ロールバックを依頼しPageCacheがDiskに反映する。 ファイルシステムの下のブロックデバイスみたいにSQLite中のB-Treeに対するPageCacheの様な位置付け。 pager.c, pager.hに書かれている。

OS Interface

to provide portability between POSIX and Win32 interfaces.

コアの実動作

実行部分は以下の関数が呼ばれる。 高水準関数として sqlite3_exec、低水準関数として sqlite3_prepare, sqlite3_stepが呼ばれる。

sqlite3_prepare
バイトコード生成(CodeGenerator)を担う
sqlite3_step
バイトコードを実行(VirtualMachine)を担う

また sqlite3_prepare に生成された sqlite_stmt は sqlite3_finalize などで後処理される。

CodeGenarator(sqlite3_prepare)

大雑把な呼び出しフローは下になる。 sqlite3PrepareがUTF-8 SQL文をバイトコード(プリペアドステートメント)に変換する。

sqlite3_prepare():
  sqlite3_prepare_v2():
    sqlite3LockAndPrepare():
      sqlite3Prepare():

VirtualMachine(sqlite3_step)

大雑把な呼び出しフローは下になる。sqlite3VdbeExecがバイトコードを実行する仮想マシンの実行ループを持つ。 その中でdoWalCallbacksがコールバック関数を呼び出す。 コールバック関数はdb->xWalCallbackに登録されている

sqlite3_step(): # in sqlite3.h, vdbeapi.c
  sqlite3Step(): # in vdbeapi.c
    sqlite3VdbeExec(): # in vdbeInt.h, vdbe.c
      doWalCallbacks(): # callbackを呼び出す in vdbeapi.c

仮想マシンはレジスタ計算機になっている。 Opcode をみると一覧が押さえられる。

実際のSQLがどのようなOpcodeに翻訳されるかはEXPLAINクエリにより確認できる。

sqlite> .explain
sqlite> EXPLAIN SELECT * FROM sqlite_master;
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     12    0                    00
1     OpenRead       0     1     0     5              00
2     Rewind         0     10    0                    00
3       Column         0     0     1                    00
4       Column         0     1     2                    00
5       Column         0     2     3                    00
6       Column         0     3     4                    00
7       Column         0     4     5                    00
8       ResultRow      1     5     0                    00
9     Next           0     3     0                    01
10    Close          0     0     0                    00
11    Halt           0     0     0                    00
12    Transaction    0     0     1     0              01
13    TableLock      0     1     0     sqlite_master  00
14    Goto           0     1     0                    00

コールバックによる関数呼び出しも可能で、通常関数はOP_Function0集約関数はOP_AggStep0, OP_AggFinal命令が呼ばれて実現する。 具体的にはP4 レジスタに*FuncDefが渡されて呼び出し先が特定される。 呼び出しを実際に確認できる。

sqlite> explain select sum(abs(id)) FROM test;
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     13    0                    00
1     Null           0     1     2                    00
2     OpenRead       0     2     0     1              00
3     Rewind         0     8     0                    00
4       Column         0     0     4                    00
5       Function0      0     4     3     abs(1)         01
6       AggStep0       0     3     1     sum(1)         01
7     Next           0     4     0                    01
8     Close          0     0     0                    00
9     AggFinal       1     1     0     sum(1)         00
10    Copy           1     5     0                    00
11    ResultRow      5     1     0                    00
12    Halt           0     0     0                    00
13    Transaction    0     0     1     0              01
14    TableLock      0     2     0     test           00
15    Goto           0     1     0                    00

.コマンドハンドリング部分

sqlite3 shellではSQL実行以外にもメタコマンドが存在する。 do_meta_command(shell.c l.2638)関数がコマンドのディスパッチする。 1byte目が”.”なのを前提に動く。