SQLiteエンジンを自作時にDBファイル構造を調べたのでメモる

CodeCrafters の [Build Your Own SqLite](https://app.codecrafters.io/courses/sqlite?track=ruby) コースに Ruby で取り組んだ。(完成品のコードは[こちら](https://github.com/kudojp/codecrafters-sqlite-ruby
))

実装時に、公式ドキュメントである[Database File Format](https://www.sqlite.org/fileformat.html#storage_of_the_sql_database_schema)を読み、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)が並んでいる。ページの中身は以下の通り。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/534442/34cb4112-6918-bd46-c05e-5af4824b7e02.png)


DBファイルの中の１ページ目は、`sqlite_schema`テーブル([ref](https://www.sqlite.org/schematab.html))のルートノードに相当する。
`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) のどれに当たるかを知ることができる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/534442/7c7288b7-eb20-d9a0-4fee-59f8777ce929.png)

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/534442/b7b91e12-aa88-e085-b0c1-72674192a66d.png)

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


よって、このページ内のレコードの数 = セルの数(leafであるため)なので、このページの offset=3~4の値を見れば良い。実際の実装は[こちら](https://github.com/kudojp/codecrafters-sqlite-ruby/blob/d48ee3ebdecec30622bacbdf188f78d4fb40ed1a/app/database_file_scanner.rb#L65-L67)


## Step3: Print table names

ページ１に乗っかっているsqlite_schemaテーブルの中のレコードの一覧を取得すれば良い。
今Stepでは、sqlite_schemaテーブルの中のレコード数が少ないため、ページ1に全てのレコードが乗っかった。従って、
- leaf page内でレコードたちを読む。-> 今Stepで実装
- interior pageのポインターより、その子のpageを辿っていく -> Step8で実装

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/534442/1e7097ba-fb7d-0bf0-1248-e6963743e2fa.png)

よって、やることとしては以下。実際の実装は[こちら](https://github.com/kudojp/codecrafters-sqlite-ruby/blob/7b34ab284a75462ff47cf41b3e1c051f1a952142/app/database_file_scanner/table_b_tree_traverser.rb#L62-L107)。

- 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`を実装したのでこれを以下の順に使うだけ。実装は[こちら](https://github.com/kudojp/codecrafters-sqlite-ruby/blob/7b34ab284a75462ff47cf41b3e1c051f1a952142/app/database_file_scanner.rb#L22-L27)

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

## Step5: Read data from a single column

これも簡単。Step3で、`TableBTreeTraverser#get_records`を実装したのでこれを以下の順に使うだけ。実装は[こちら](https://github.com/kudojp/codecrafters-sqlite-ruby/blob/7b34ab284a75462ff47cf41b3e1c051f1a952142/app/database_file_scanner.rb#L29-L35)

- 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の構成は以下。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/534442/998fa1e4-d8f8-b987-bccf-7b0ffe6d59b5.png)


実装は[こちら](https://github.com/kudojp/codecrafters-sqlite-ruby/blob/e384423636c42f172adb258dc0687bbf840a9def/app/database_file_scanner/table_b_tree_traverser.rb#L65-L68)。


## Step9: Retrieve data using an index

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

具体的なステップは以下。
1. インデックスツリーをtraverseし、WHERE clauseで指定された条件を満たすrowidの配列を求める。[実装](https://github.com/kudojp/codecrafters-sqlite-ruby/blob/c30f34861e07493902cf66cc4effefd721b383f3/app/database_file_scanner/index_b_tree_traverser.rb#L19-L160)
2. テーブルツリーをtraverseし、rowidの配列に含まれるrowidに相当するレコードのみを取り出す。[実装](https://github.com/kudojp/codecrafters-sqlite-ruby/blob/c30f34861e07493902cf66cc4effefd721b383f3/app/database_file_scanner.rb#L41-L61)


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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/534442/e7f470a6-c9c9-8f33-de0e-099b22e0d98f.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/534442/122f2ae4-bbd1-5ee7-c0f4-6283f0b6bbc1.png)



## Ref.

https://www.sqlite.org/fileformat.html

https://fly.io/blog/sqlite-internals-btree/