SQLiteではレジスタ型仮想マシンのバイト命令がBTreeを操作している。 またバイトコード生成はLALR(1)構文解析器の(cmd)非終端記号の還元時(reduce)に生成されていた。

仮想マシンは仮想データベースエンジン(VDBE)と呼ばれておりBTreeコンポーネントを操作する。 今回はバイトコード実行時のVDBEの挙動を調べる。

命令(OpCode)や変数が多くて辛いため、簡単なSQLを実際に追いながら命令や変数を説明する形で進める。

目次

仮想マシンの動きを追う準備

仮想マシンの動きを追う2.8をベースにしている資料がある。 今更だけど、これを読むのが早い気がする。ただ3系と2系では一部の命令(ResultRow, Callback)が異なる。 各命令資料はOpCodeにまとまっている。

用語の事前準備

まずは頻出する概念の説明をしておく。

仮想データベースエンジン(VDBE)

命令列・メモリ・プログラムカウンタを積んだ仮想マシンでBTree処理を駆動する

命令列

VDBEが解釈して実効する命令でSQLの内部表現

オペコード

命令列を構成する命令

レジスタ

オペコードの引数(p1..p5がある)

プログラムカウンタ

実行中(タイミングによっては次の)の命令を指すポインタ

BTree

テーブル・インデックスの内部表現

カーソル

BTreeに対するイテレータ(繰り返しの抽象化)

メモリ

処理が進むにあたり一時的にデータを格納する領域 レコード情報・比較に使うためのインデックス値などが格納される

デバッグオプションを有効にビルドする

調べるにあたりデバッグオプションを有効にしておくと何かと便利なので初めにデバッグオプションを有効にしてビルドする。 ./configureac_user_optsに利用可能なビルドオプションが列挙されている。 enable-debugを有効にして以下の様にビルドする。

$ ./configure --enable-load-extension --enable-debug
$ ./gmake

バイト命令の表示

仮想マシンの挙動を追うのに便利なのはバイトコードを表示したり終えたりすること。 表示は以下の様にEXPLAINで実現できる。 またデバッグオプションの恩恵で以前までよりもcommentが詳しい。

sqlite> .explain on
sqlite> EXPLAIN select * from test;
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     9     0                    00  Start at 9
1     OpenRead       0     2     0     1              00  root=2 iDb=0; test
2     Explain        0     0     0     SCAN TABLE test  00
3     Rewind         0     7     0                    00
4       Column         0     0     1                    00  r[1]=test.id
5       ResultRow      1     1     0                    00  output=r[1]
6     Next           0     4     0                    01
7     Close          0     0     0                    00
8     Halt           0     0     0                    00
9     Transaction    0     0     4     0              01  usesStmtJournal=0
10    TableLock      0     2     0     test           00  iDb=0 root=2 write=0
11    Goto           0     1     0                    00

プロファイリング

生成されたバイトコードの各命令が何回実行されるかなどの確認は以下を行う。 各命令と引数・コメントが出力される。またメモリ領域(REG)の変更なども記録されている。 昔のバージョンではStackが使われている

sqlite> pragma vdbe_trace=on
...
sqlite> select * from test;
SQL: [select * from test;]
VDBE Trace:
   0 Init             0    9    0               00 Start at 9
   9 Transaction      0    0    4 0             01 usesStmtJournal=0
  10 TableLock        0    2    0 test          00 iDb=0 root=2 write=0
  11 Goto             0    1    0               00
   1 OpenRead         0    2    0 1             00 root=2 iDb=0; test
   2 Explain          0    0    0 SCAN TABLE test 00
   3 Rewind           0    7    0               00
   4 Column           0    0    1               00 r[1]=test.id
REG[1] =  i:1
   5 ResultRow        1    1    0               00 output=r[1]
REG[1] =  i:1
1
   6 Next             0    4    0               01
   4 Column           0    0    1               00 r[1]=test.id
REG[1] =  i:2
   5 ResultRow        1    1    0               00 output=r[1]
REG[1] =  i:2
2
   6 Next             0    4    0               01
   4 Column           0    0    1               00 r[1]=test.id
REG[1] =  i:3
   5 ResultRow        1    1    0               00 output=r[1]
REG[1] =  i:3
3
   6 Next             0    4    0               01
   4 Column           0    0    1               00 r[1]=test.id
REG[1] =  i:5
   5 ResultRow        1    1    0               00 output=r[1]
REG[1] =  i:5
5
   6 Next             0    4    0               01
   4 Column           0    0    1               00 r[1]=test.id
REG[1] =  r:5.8
   5 ResultRow        1    1    0               00 output=r[1]
REG[1] =  r:5.8
5.8
   6 Next             0    4    0               01
   4 Column           0    0    1               00 r[1]=test.id
REG[1] =  r:-5.8
   5 ResultRow        1    1    0               00 output=r[1]
REG[1] =  r:-5.8
-5.8
   6 Next             0    4    0               01
   7 Close            0    0    0               00
   8 Halt             0    0    0               00

バイトコード処理の全体像

初めにバイトコードが処理される全体像と関わる変数を説明する。

バイトコードの駆動はsqlite3VdbeExec(Vdbe*)関数に仮想マシンを渡す事で実行される。 実際にバイトコードがどの様にsrc/vdbe.c:sqlite3VdbeExec()の中で処理されるか確認する。

コード実行に関わる変数

仮想データベースエンジン(VDBE)はVdbe型のインスタンスで表現されている。 処理はVdbeのメンバ・sqlite3VdbeExecのローカル変数で管理される。

Vdbeのメンバ

詳細な仮想マシン定義はsrc/vdbeInt.hにある。 重要な事は仮想マシンがバイトコードをロードしておりレジスタ・プログラムカウンタ・メモリなどを保持しているメンバ。

フィールド 内容
((Vdbe*)p)->aOp Op* バイトコード列先頭へのポインタ
((Vdbe*)p)->nOp int バイトコード列のサイズ
((Vdbe*)p)->pc int プログラムカウンタ
((Vdbe*)p)->aMem Mem* メモリ領域
((Vdbe*)p)->nMem int 確保されているメモリ領域の数
((Vdbe*)p)->Cursor int 確保されているメモリ領域の数

sqlite3VdbeExecのローカル変数

実行中の大半の情報はsqlite3VdbeExecの変数に格納される。

ローカル変数 内容
pOp Op* 現在のバイトコード命令

実行ループ

実行は以下の様にpOpをプログラムカウンタとするループになっている。 大雑把には以下の構造になる。(乗せた命令は後述するSQLの骨になる一部の命令)

sqlite3VdbeExec(Vdbe*) {
Op * aOp = p->aOp;
Op * pOp = aOp;
for(pOp=&aOp[p->pc]; rc==SQLITE_OK; pOp++){
  switch(pOp->opcode) {
  // ...
  case OP_Init:
  case OP_Halt:
  case OP_Transaction:
  case OP_TableLock:
  case OP_Goto:
  }
}

実際にバイトコードを追う

ここからはSQLのバイトコードを表示して、命令に対応するソースコードを読んで簡単な説明を加えていくことで具体的に理解を進める。 以降はenable-debugを無効にしているバイナリでExplainした結果を使う。 (単に、最初デバッグオプションを有効にせず調べていたため)

基本的なSELECT文

基本的なSELECT文を通してレコード毎の処理がどの様に実現されているかを確認する。

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

基本的な命令(Init, Halt, Transaction, TableLock, Goto)

処理の最初のInitと、末尾のHalt, Transaction, TableLock, GotoはどんなSQLにも存在している。 内容は以下になる。

OpCode 意味
Init 初期化
Halt プログラム停止
Transaction トランザクション設定を行う
TableLock テーブルロックを行う
Goto プログラムカウンタを変更する
Gosub プログラムカウンタを変更する

ref. OpCode

Init

Initが本当の初期設定を行いその中でgoto文でGosub命令の最後にジャンプしている。 GoSubではp2レジスタ指定行にジャンプする。 これはHalt以降にあるTransactionを指している。

case OP_Init:
  // 初期化
  if (pOp->p2) goto jump_to_p2;
  break;
case OP_Gosub:
  // ...
  jump_to_p2:
  // p2レジスタの1つ前にプログラムカウンタを合わせる
  pOp = &aOp[pOp->p2 -1]
  break;

Transaction, TableLock

Transaction命令はトランザクションの開始を担っている。 特にsqlite3BtreeBeginTrans()関数によってテーブルロックを獲得している。

  1. sqlite3BtreeEnterは処理全体を保護する
  2. sqlite3PagerBeginは必要な場合に各Pagerに対してwritelockを取得する
  3. sqlite3PagerWriteを経由して各ページをジャーナル対象にする
  4. sqlite3BtreeLeave関数から脱出前にBTree操作の保護を解く

SQLiteのロック・トランザクション関連仕様の整理がロック・トランザクションについて日本語でわかりやすく整理している。

TableLockは*p2テーブルのロックしている。

Goto

Goto はp2指定行のバイトコードにジャンプする。 上記のバイトコードではOpenReadに飛ぶ。 またGosubと異なり割り込みの確認などを行っている。 またコード上は行数を-1してpOpに格納しているが、これはforループでインクリメントされる事を見越している。

case OP_Goto:
  jump_to_p2_and_check_for_interrupt: // In OP_Goto
  pOp = &aOp[pOp->p2 -1] // p2レジスタの1つ前にプログラムカウンタを合わせている
  // .. 割り込みの検査など
  break;

Halt

いろいろな処理を終えて最後にたどり着く命令で終了を意味している。 vdbe_returnにジャンプする事でバイトコード実行を終了している。 同じプリペアドステートメント(バイトコード)を複数回実行できるようにするためにHalt 以降に初期化命令が書かれている。 2回目以降はHaltの続きから実行される。

case OP_Halt:
  // プログラムカウンタ・確保リソース解放処理など
  goto vdbe_return;
  // ...
} // close switch

// ...
vdbe_return:
  sqlite3VdbeLeave(p);
  return rc;

ループを担う命令(OpenRead, Rewind, Next)

SQLの処理はレコード分繰り返して処理されている。 これはカーソル(下位のデータ構造(BTree)へのイテレータ)を利用して実現される。 下の3命令で実行されている。

命令 意味
OpenRead カーソルの確保
Rewind カーソルの初期化
Next カーソルを進めてプログラムカウンタをループ先頭に戻す

OpenRead

カーソルは実は2重構造になっていて。 VdbeCursor, BtCursorの両方ともBTree(within データベースファイル)へのカーソルを表しいている。 なぜ2重構造なのかわからなかったがVdbeCursorのメンバにBtCursorが存在する。 VdbeCursorisOrdered, isTable, isEphemeralなどカーソルのメタ情報も含んで保持していた。 BTreeはテーブル,インデックスがありえる。 テーブルの時はp4レジスタがP4_KEYINFOとなっている。

全体の流れはallocateCursorで確保してsqlite3BtreeCursorで設定している。

case OP_OpenRead:
case OP_OpenWrite: // 一緒に実装されてる
  p2 = pOp->p2; iDb = pOp->p3; // p3レジスタはバックエンドDB Indexを指定している
  pDb = &db->aDb[iDb]; // バックエンド中 iDb番のDBを取得している
  pX = pDb->pBt;       // バックエンドDBに対応したB*Tree 構造体
  // ... (pKeyInfo の設定など)

  // pCur をpOp->p1番(スタックの様にメモリ領域(p->aMem)の末尾p1番目)に確保する
  //   フィールド数(カラム数): nFieldのレコードサイズ; データベース: iDb
  pCur = allocateCursor(p, pOp->p1, nField, iDb, 1);

  // 初期化
  pCur->nullRow = 1; pCur->isOrdered = 1; pCur->pgnoRoot = p2;
  // pCur->pCursor をp2番のB*Treeに向けて設定
  rc = sqlite3BtreeCursor(pX, p2, wrFlag, pKeyInfo, pCur->pCursor);
  pCur->pKeyInfo = pKeyInfo; pCur->isTable = pOp->p4type != P4_KEYINFO;
  break;

Rewind

カーソルをBTreeの先頭に移動させる。 ループに使うイテレータはp1レジスタで指定する。 このカーソルは以前にOpenReadで確保されたものになる。 src/btree.c::sqlite3BtreeFirstが実際にBTree先頭にカーソルを持ってきくる。

case OP_Rewind:
  pC = p->apCsr[pOp->p1];
  res = 1;
  pC->seekOp = OP_Rewind;
  if( isSorter(pC) ){ //
  } else {
    pCrsr = pC->pCursor;
    rc = sqlite3BtreeFirst(pCrsr, &res);
    pC->nullRow = (u8)res;
  }
  if( res ) goto jump_to_p2;
  break;

だいたい以下の様にBTreeのleaf-nodeに辿り着いている。 だいたい以下の様に呼び出されていた。 デバッガでb btreePageFromDbPageを試せば読める。

sqlite3BtreeFirst():
  moveToRoot():
    getAndInitPage():
      # DbPageを取得してBtreePageを取得
      # そのアドレスはCusor->apPage[pCur->iPage]に格納
      # pCur->iPage はカーソル作成時に-1になりページallocate毎に増える
  moveToLeftmost:
    moveToChild:
      getAndInitPage:
        sqlite3PagerAcquire:# (in pager.c)
          # この中でos.c経由でディスクからPageを取得したりしている。
          btreePageFromDbPage:
            # btree探索に使える形に変換したりしてる

参考: How does SQLite work? Part 1: pages!

Next

Nextによりループ先頭に戻る。ループ用イテレータはp1で指定する。 実際にはカーソルの指す要素が最終か判断してp2行にジャンプしている。 ループを実現するためにp2にはRewindの次の行が指定されている。

case OP_Next:
  pC = p->apCsr[pOp->p1];
  res = pOp->p3;
  VdbeBranchTaken(res==0,2);
  rc = pOp->p4.xAdvance(pC->pCursor, &res);
  if( res==0 ){
    p->aCounter[pOp->p5]++; // カウンタを増やしてループ数を上げている
    sqlite3_search_count++;
    goto jump_to_p2_and_check_for_interrupt; // jmp 命令に行く
  }
  break;

RestulRow

sqlite3_stepは行毎にバイトコード実行が中断されカラム情報などを受け取る事が出来る。 これはResultRow命令でプログラムカウンタの値などを永続化してからsqlite3VdbeExecを脱出することで実現している。

case OP_ResultRow:
  // ...
  p->pc = (int)(pOp - aOp) + 1;
  rc = SQLITE_ROW;
  goto vdbe_return;

Vdbeのプログラムカウンタ(p->pc)に変更が加わるのはこの中断時になる。 SELECT文は上記の様にResultRowが中断しつつ全レコード分繰り返している。

データ処理命令(Column)

テーブルBTreeから値を外部に公開できる様にするなどの命令が必要になる。

Column

読みきれてないがp1カーソルのp2番カラムの値をp3メモリに格納する。

sqlite3BtreeDataFetch -> fetchPayloadが現在のカーソルの向き先レコードの実際のアドレスを返している。 sqlite3VdbeMemFromBtree -> vdbeMemFromBtreeResizeがキー・レコード情報をBtreeからメモリ領域へコピーする。

pDest = &aMem[pOp->p2];
// pC->aRow に
if( pC->nullRow ){
  if( pCrsr==0 ){
    pC->payloadSize = pC->szRow = avail = pReg->n;
    pC->aRow = (u8*)pReg->z;
  }
} else {
  if (pC->isTable == 0) {
    VVA_ONLY(rc =) sqlite3BtreeKeySize(pCrsr, &payloadSize64);
    pC->aRow = sqlite3BtreeKeyFetch(pCrsr, &avail);
    pC->payloadSize = (u32)payloadSize64;
  } else {
    VVA_ONLY(rc =) sqlite3BtreeDataSize(pCrsr, &pC->payloadSize);
    pC->aRow = sqlite3BtreeDataFetch(pCrsr, &avail);
  }
}
// p2 のオフセットを操作する
// ...
// 今のレコードのp2番目のカラムをpDestに格納する
rc = sqlite3VdbeMemFromBtree(pCrsr, aOffset[p2], len, !pC->isTable, pDest);

少し複雑なSELECT文

簡単なSELECTがわかったので次にINNER JOINを確認する。 新しい命令について確認する。

sqlite> explain SELECT * FROM test_rec INNER JOIN test ON (test_rec.id = test.id);
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     22    0                    00
1     OpenRead       1     2     0     1              00
2     OpenRead       0     3     0     2              00
3     OpenRead       2     4     0     k(2,nil,nil)   02
4     Rewind         1     18    0                    00
5       Column         1     0     1                    00
6       IsNull         1     17    0                    00
7       Affinity       1     1     0     D              00
8       SeekGE         2     17    1     1              00
9         IdxGT          2     17    1     1              00
10        IdxRowid       2     2     0                    00
11        Seek           0     2     0                    00
12        Column         2     0     3                    00
13        Column         0     1     4                    00
14        Column         1     0     5                    00
15        ResultRow      3     3     0                    00
16      Next           2     9     0                    00
17    Next           1     5     0                    01
18    Close          1     0     0                    00
19    Close          0     0     0                    00
20    Close          2     0     0                    00
21    Halt           0     0     0                    00
22    Transaction    0     0     4     0              01
23    TableLock      0     2     0     test           00
24    TableLock      0     3     0     test_rec       00
25    Goto           0     1     0                    00

カラムに含まれる値を操作する命令(Affinity, IsNull)

DBから取得された値に関する操作の命令が新たに出てきた。

Affinity

型変換してる。p4レジスタに入っている文字列の各文字が型を表現している。 またp4レジスタの文字列長がp2の値が入っていて、文字列末尾には\0が入ってる。 メモリ上でp1オフセットに適用される。

zAffinity = pOp->p4.z;
pIn1 = &aMem[pOp->p1];
while( (cAff = * (zAffinity++))!=0 ){
  applyAffinity(pIn1, cAff, encoding);
  pIn1++;
}
break;

IsNull

モリ領域(aMem)のp1番目に確保された値がNullか判断している。 Nullであればp2レジスタで指定される行にジャンプする。

pIn1 = &aMem[pOp->p1];
VdbeBranchTaken( (pIn1->flags & MEM_Null)!=0, 2);
if( (pIn1->flags & MEM_Null)!=0 ){
  goto jump_to_p2;
}
break;

複雑なカーソル操作(SeekGE, IdxGT, IdxRowid, Seek)

SeekGE,IdxGT,IdxRowid,Seekについて調べる事でJOINがどの様に実現されるか確認する。

SeekGE

<=条件で検索をかけている。他の条件(<,>=,>)の命令も同じ場所で処理される。 構成は確認用コード, カーソルの移動, 境界条件に合わせてカーソル位置を微調整の3段階で行われている。 カーソルの移動はsqlite3BtreeMovetoUnpackedを用いて実施される。 2種類のカーソルで共通で使うため渡す引数に応じて挙動が変わるため呼び出し側ではpC->isTableを使って分岐している。

OP_SeekLT:
OP_SeekLE:
OP_SeekGE:
OP_SeekGT:
  // どの条件で検索をかけているか確認
  // ....

  // カーソルの種類(isTable or not)により検索条件を切り替えている
  pC = p->apCsr[pOp->p1];
  if (pC->isTable) { // テーブルだと行数を渡す
    // メモリ領域のp3番目にSqliteの整数型として格納されている。
    iKey = sqlite3VdbeIntValue(&aMem[pOp->p3]);
    sqlite3BtreeMovetoUnpacked(pC->pCursor, 0, (u64)iKey, 0, &res)
  } else {
    // テーブルではないのでフィルードを表現した UnpackedRecord
    nField = pOp->p4.i;
    r.pKeyInfo = pC->pKeyInfo;
    r.nField = (u16)nField;
    r.aMem = &aMem[pOp->p3];
    sqlite3BtreeMovetoUnpacked(pC->pCursor, &r, 0, 0, &res)
  }
  // Cursor移動後にLT, LE, GE, GTに合わせて微調整している
  if( oc>=OP_SeekGE ){  assert( oc==OP_SeekGE || oc==OP_SeekGT );
    if( res<0 || (res==0 && oc==OP_SeekGT) ){
      res = 0;
      rc = sqlite3BtreeNext(pC->uc.pCursor, &res);
      if( rc!=SQLITE_OK ) goto abort_due_to_error;
    }else{
      res = 0;
    }
  }else{
    assert( oc==OP_SeekLT || oc==OP_SeekLE );
    if( res>0 || (res==0 && oc==OP_SeekLT) ){
      res = 0;
      rc = sqlite3BtreePrevious(pC->uc.pCursor, &res);
      if( rc!=SQLITE_OK ) goto abort_due_to_error;
    }else{
      res = sqlite3BtreeEof(pC->uc.pCursor);
    }
  }

IdxGT

p1カーソルのインデックス値をレジスタ位置p4に位置するUnpackedRecordp3番目の値以上となればp2行へジャンプする。 カーソルのインデックスを扱う関数は結果の比較情報を最後の引数resに格納しており これにより比較条件に合わせて挙動を変更している。

OP_IdxGE:
OP_IdxGT:
OP_IdxLE:
OP_IdxLT:
   pC = pOp->p1;
   r.nField = (u16)pOp->p4.i
   res = 0;
   sqlite3VdbeIdxKeyCompare(db, pC, &r, &res)
   // GE, GT, LE, LT に応じて resの値を操作
   if (res > 0) {
     goto jmp_to_p2;
   }

IdxRowid

p2レジスタにp1カーソルのインデックスを格納する。 抜粋コードに書かれているようにMEM_Int型として格納される。 またsqlite3VdbeCursorRestoreが呼ばれる必要がある通りCursorが実際に移動する処理は必要がない場合は遅延されて効率化されていた。

  1. out2Preleaseを使ってp2レジスタを確保
  2. sqlite3VdbeCursorRestore()で予約されているカーソル移動を完了させる
  3. sqlite3VdbeIdxRowid()でインデックスを取得している
OP_IdxRowid:
  pOut = out2Prerelease(p, pOp);
  pC = p->apCsr[pOp->p1];
  rc = sqlite3VdbeCursorRestore(pC);
  rc = sqlite3VdbeIdxRowid(db, pCrsr, &rowid);
  pOut->u.i = rowid;
  pOut->flags = MEM_Int;

Seek

p1カーソルに対してSeek処理を予約している。 メモリ領域のp2番目の値を異動先インデックスとして指定している。 これによって次のReadでカーソルが対象レコードに移動する(移動に伴うI/Oなどが遅延される)。

OP_Seek:
   pC = apCsr[pOp->p1]
   pC->movetoTarget = sqlite3VdbeIntValue(&aMem[pOp->p2]);
   pC->deferredMoveto = 1;