CodeCrafters の Build Your Own SqLite コースに Ruby で取り組んだ。(完成品のコードはこちら)

実装時に、公式ドキュメントであるDatabase File Formatを読み、SQLiteのデータベースの構造(各ページがどのようなバイト配列になっているか等)を色々調べる必要があった。この際に調べたことをメモる。

Step1. Print page size (-> 今回は 4096 bytes)

SQLiteのDBファイルの最初の100byteは、ヘッダーである。
ヘッダーの中の、Offset=16~17の2bytesに、pagesizeが収納されている。
👉 今回見ているsample.dbのページサイズは、4096 bytesだった。

Step2. Print number of tables

SQLiteのDBファイルは、ページ(今回だと4096bytes)が並んでいる。ページの中身は以下の通り。

DBファイルの中の１ページ目は、sqlite_schemaテーブル(ref)のルートノードに相当する。
sqlite_schemaテーブルの各レコードは、そのDB内に入っている１テーブルに相当する。よって、このテーブル内のレコード数を求めれば良い。

(なお、１ページ目の最初の100bytesはファイルヘッダーなので、１ページ目のみ他のページよりも100bytesほど使用可能容量が少ない。)

SQLiteには、2種類のtreeがある。

table B-tree
index B-tree

各node=pageのoffset=1の1byteを見ることで、それが(table-btree/index-btree, interior-node/leaf-node) のどれに当たるかを知ることができる。

hexdummp -C sample.db (-Cオプションにより、1byteずつのbig endianとして解釈)により、今回のDBファイルを見てみると、、

これにより、１ページ目は、0x0d = 13 = leaf table b-tree pageであるので、sqlite_schemaテーブルのデータは、１ページ目に収まっていることがわかる。

よって、このページ内のレコードの数 = セルの数(leafであるため)なので、このページの offset=3~4の値を見れば良い。実際の実装はこちら

Step3: Print table names

ページ１に乗っかっているsqlite_schemaテーブルの中のレコードの一覧を取得すれば良い。
今Stepでは、sqlite_schemaテーブルの中のレコード数が少ないため、ページ1に全てのレコードが乗っかった。従って、

leaf page内でレコードたちを読む。-> 今Stepで実装
interior pageのポインターより、その子のpageを辿っていく -> Step8で実装

table B-tree leaf page は以下のように構成される。

よって、やることとしては以下。実際の実装はこちら。

header内のoffset 3-4を読んで、cell数=record数を知る。
records(array)を初期し、headerの直後であるoffset=8から、#cell回、以下を繰り返す。
- 2bytesのcell pointerを読む。
- そのoffset=に飛ぶ。これはcellの先頭である。
- payload sizeを示すvarintを一回読む。
- rowidを示すvarintを一回読む。
- col_to_serial_type(hashmap)を初期化し、カラムの個数回以下を繰り返す。
  - varintを読みこむ。それぞれが、各カラムの値の型とバイト長を示す。
  - これをcol_to_serial_type[col]に保存する。
- record(hashmap)を初期化し、カラムの個数回以下を繰り返す。
  - col_to_serial_type[col]に入っているcol_to_serial_typeを元に、カラムの値を求める。
  - これをrecord[col]に代入する。
- records(array)にrecordをappendする。

Step4: Count rows in a table

これは簡単。Step3で、TableBTreeTraverser#cnt_recordsを実装したのでこれを以下の順に使うだけ。実装はこちら

sqlite_schemaの中のテーブル一覧の中で該当するテーブルのレコードに注目し、root page indexを得る。
そのページインデックスを引数に、TableBTreeTraverser#cnt_recordsを走らせる。これで、テーブル内のレコード数が得られる。

Step5: Read data from a single column

これも簡単。Step3で、TableBTreeTraverser#get_recordsを実装したのでこれを以下の順に使うだけ。実装はこちら

sqlite_schemaの中のテーブル一覧の中で該当するテーブルのレコードに注目し、root page indexを得る。
そのページインデックスを引数に、TableBTreeTraverser#cnt_recordsを走らせる。これでテーブル内のレコードの配列が得られる。
このレコードの配列を、SELECTで指定されたカラムの値にmappingしてやる。

Step6: Read data from multiple columns

これはStep5の最後でmappingのロジックを変えるだけ。

そのページインデックスを引数に、TableBTreeTraverser#cnt_recordsを走らせる。これでテーブル内のレコードの配列が得られる。
このレコードの配列を、SELECTで指定されたカラムの値にmappingしてやる。

このmapping先を複数カラムにする。

Step7: Filter data with a WHERE clause

そのページインデックスを引数に、TableBTreeTraverser#cnt_recordsを走らせる。これでテーブル内のレコードの配列が得られる。

これに、WHERE clauseの条件を満たすレコードのみの集合を取り出すようフィルタリングする。

Step8: Retrieve data using a full-table scan

Step3では、sqlite_schemaテーブルの中のレコード数が少ないため、ページ1に全てのレコードが乗っかった。従って、

leaf page内でレコードたちを読む。-> 今Stepで実装

interior pageのポインターより、その子のpageを辿っていく -> Step8で実装

interior pageには、その子であるページのインデックスを持つポインタが複数含まれている。
これを元にleaf pageまで辿っていくロジックを実装すれば良い。

interior pageの構成は以下。

実装はこちら。

Step9: Retrieve data using an index

WHERE clause で indexが貼られたカラムをフィルタリングするクエリが投げられる。
よって、index treeを使ってスキャンするレコードを絞ることが求められた。

具体的なステップは以下。

インデックスツリーをtraverseし、WHERE clauseで指定された条件を満たすrowidの配列を求める。実装
テーブルツリーをtraverseし、rowidの配列に含まれるrowidに相当するレコードのみを取り出す。実装

なお、index treeの leaf が持っている rowidとは、元のテーブルにおけるPrimary Keyのことである。
テーブルツリーは、primary keyによりノードがソートされているので、2のツリーのtraverseも高速にできる。

Ref.