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.