SQLiteバイトコードを追う

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に対するイテレータ(繰り返しの抽象化)
メモリ: 処理が進むにあたり一時的にデータを格納する領域レコード情報・比較に使うためのインデックス値などが格納される

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

調べるにあたりデバッグオプションを有効にしておくと何かと便利なので初めにデバッグオプションを有効にしてビルドする。 ./configureのac_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
----  -------------  ----  ----  ----  -------------  --  -------------
   Init           0     9     0                    00  Start at 9
   OpenRead       0     2     0     1              00  root=2 iDb=0; test
   Explain        0     0     0     SCAN TABLE test  00
   Rewind         0     7     0                    00
     Column         0     0     1                    00  r[1]=test.id
     ResultRow      1     1     0                    00  output=r[1]
   Next           0     4     0                    01
   Close          0     0     0                    00
   Halt           0     0     0                    00
   Transaction    0     0     4     0              01  usesStmtJournal=0
  TableLock      0     2     0     test           00  iDb=0 root=2 write=0
  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文を通してレコード毎の処理がどの様に実現されているかを確認する。

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

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

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

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() 関数によってテーブルロックを獲得している。

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

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

TableLockは*p2テーブルのロックしている。 Transactionとかとの役回りの違いがまだ分かっていない。

Goto

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

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	カーソルを進めてプログラムカウンタをループ先頭に戻す

カーソルは実は2重構造になっていて。 VdbeCursor, BtCursor の両方ともBTree(within データベースファイル)へのカーソルを表しいている。なぜ2重構造なのかわからなかったがVdbeCursorのメンバにBtCursorが存在する。 VdbeCursorはisOrdered, 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!

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
----  -------------  ----  ----  ----  -------------  --  -------------
   Init           0     22    0                    00
   OpenRead       1     2     0     1              00
   OpenRead       0     3     0     2              00
   OpenRead       2     4     0     k(2,nil,nil)   02
   Rewind         1     18    0                    00
     Column         1     0     1                    00
     IsNull         1     17    0                    00
     Affinity       1     1     0     D              00
     SeekGE         2     17    1     1              00
       IdxGT          2     17    1     1              00
      IdxRowid       2     2     0                    00
      Seek           0     2     0                    00
      Column         2     0     3                    00
      Column         0     1     4                    00
      Column         1     0     5                    00
      ResultRow      3     3     0                    00
    Next           2     9     0                    00
  Next           1     5     0                    01
  Close          1     0     0                    00
  Close          0     0     0                    00
  Close          2     0     0                    00
  Halt           0     0     0                    00
  Transaction    0     0     4     0              01
  TableLock      0     2     0     test           00
  TableLock      0     3     0     test_rec       00
  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に位置するUnpackedRecordのp3番目の値以上となればp22行へジャンプする。カーソルのインデックスを扱う関数は結果の比較情報を最後の引数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が実際に移動する処理は必要がない場合は遅延されて効率化されていた。

out2Preleaseを使ってp2レジスタを確保
sqlite3VdbeCursorRestore()で予約されているカーソル移動を完了させる
sqlite3VdbeIdxRowid()でインデックスを取得している

Seek

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

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

鱒身(Masu_mi)のブログ

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