自作DBを始めたい人におすすめの本
この記事は、慶應理工アドベントカレンダー2021の20日目の記事です。
カレンダー全日埋まってすごい 🎉🎉
「Database Design and Implementation」という簡素なDBをスクラッチで作っていく本に取り組んだので、その読了エントリです。
こんな人におすすめ
MySQLやPostgreSQLを使った経験はあるが、DBの理論やその実装はあまり詳しくない人に特におすすめです。特に自作〇〇*1に興味がある人は間違いなく楽しめると思います。単純に本に紹介されている理論と実装に取り組むだけでもいいですのですが、豊富な拡張課題が用意されているので是非取り組むといいと思います。理論だけ紹介されて実装は全部自分で設計からやらないといけないので時間かかりますが... この本は英語で書かれていますが、わかりやすい説明だったので特に苦労しませんでした。
最終的にこんなクエリが実行できるようになります。
自作DB、こんなクエリが実行できるようになったぜー pic.twitter.com/q0tqyV8a4V
— サラダチキン (@salachike) 2021年8月26日
その他にもORDER BYとかGROUP BYとかデータを集約するクエリの実行や、インデックスを張ったりもできます！結構すごくないですか？
内容について
備忘録を兼ねてどんな内容を扱うのかまとめてみます。読んでてあんまり面白くないと思いますが、興味持ってくれると嬉しいです。 本のサンプルコードはJavaですが好きな言語で実装して大丈夫です。 ちなみに自分はC++で取り組みました。
Chap1--2: Introduction
データベースとは何なのかの説明。 モチベーションが否応なく?高まる...
Chap3: Disk and File Management
ディスクドライブの物理的な構成、アクセス高速化のための工夫 (Disk caches, Cylinders, and Disk Striping)、SSDなどについて説明と、ブロック単位のメモリ領域としてページという概念の説明があります。ディスク上にファイル単位でデータ全体を保存し、ブロック単位でデータの読み書きをおこなうFile Managerを実装します。
Chap4: Memory Management
ディスクアクセスはメモリアクセスに比べてめちゃくちゃ遅いので、In-Memoryでデータを管理して、必要に応じてディスクに書き込むようなDBの設計にしたい。そのためにDBのログをファイルに書き込むLog Managerと、ページの集合体であるBuffer Poolの管理をおこなうBuffer Managerを実装します。 Buffer Poolが全部使用されているときに、どのBufferをディスクに書き込んでから割り当て可能にするかを決定するアルゴリズムもいくつか紹介されます。好きなアルゴリズムを実装すると面白いと思います。
Chap5: Transaction Management
TransactionやACIDとかが題材ですが、理論も私には難しく何度も同じ箇所を読み返しました。Transactionのロールバックや、ログファイルを元にDBを整合性のある状態するRecovery Managerを実装します。また並行で動いている複数のTransactionにも対応できるように、共有・排他ロックをおこなうConcurrency Managerを実装します。
Chap6: Record Management
ファイルにレコードを保存するRecord Managerを実装します。レコードの先頭位置から、それぞれのフィールドのオフセット分を足した箇所に値を読み書きするようにします。
Chap7: Metadata Management
テーブルのレコードの構造(フィールドの長さと型 ( CHAR(8)とか )、オフセット)や、インデックスが張られたフィールド名などのメタデータを管理するMetadata Managerを実装します。
Chap8: Query Processing
select、project、productといった演算は関係代数的にはどういうことなのかが説明されてます。Iterativeにレコードを走査できるような処理を書きます。
Chap9: Parsing
クエリをパースする再帰下降パーサーを書きます。Nand2Tetrisのコンパイラの章で再帰下降パーサーを書いた経験が活きました...
Chap10: Planning
クエリをパースした結果から、実行計画を作るPlannerを実装します。パース結果のみだと実行計画は複数考えられる場合があるので、メタデータからブロックアクセス数などのコストを見積もりして、コストが低い実行計画を選ぶようにします。
Chap11: Interface
今までの機能をアプリケーションとして使えるようにします。
Chap12: Indexing
インデックスとしてB-Treeインデックスを実装します。インデックスを張ったフィールドがユニークな値が多い場合、ディスクアクセス数が少なくなりクエリの高速化が期待できます。 B-Treeの実装は難しかったので、もう一回復習したいところ。
Chap13: Materialization and Sorting
仮テーブルへの書き込み処理を実装します。 パイプライン化されたクエリの場合、中間の出力を一度仮のテーブルに書き込んだ方がブロックアクセス数がトータルで少なくなる場合があります。
以下のクエリを見てみましょう。
SELECT * FROM T1, T2 WHERE T1.FIELD= HOGE AND T2.FIELD = HUGA AND T1.ID = T2.ID;
ナイーブな実行計画だと、2つのテーブルT1とT2のレコードを2重ループで全探索していきます。これはレコード数の多いテーブルの場合非常に時間がかかります。ここで仮テーブルの出番です。テーブルT1で T1.FIELD = HOGE のレコードとテーブルT2で T2.FIELD = HUGA のレコードをそれぞれ別の仮テーブルに書き込みます。最後に2つの仮テーブルを全探索してT1.ID=T2.IDのレコードを出力します。このレコードを絞る方法の方がナイーブな実行計画よりブロックアクセス数が少なくなる可能性が高いです*2*3。
Chap14: Effective Buffer Utilization
複数のバッファーを使ってブロックアクセス数が少なくなるように、ORDER BYで使っていたマージソートを改造します。
Chap15: Query Optimization
複数の実行計画が考えられるクエリについてディスクアクセスがなるべく少なくなるようなヒューリスティックな実行計画の選択アルゴリズムの紹介とその実装をおこないます。
まとめ
DBというと凄腕エンジニアたちが叡智を結集して作っているようなイメージを持っていましたが、ひとつずつ理論と実装の対応を追っていけば普通の人間でも理解できることが分かって嬉しかったです。
今は「Operating System Concepts」というOSの有名な教科書を読んでいるので、それも読み終えたら書評を書きたいです。
*1:DB、OS、CPU、言語、コンテナ、TCP/IP プロトコルスタックetc
*2:T1.FILED = HOGEやT2.FIELD = HUGAでレコード数が絞られない場合、効果薄いです。
*3:例えばテーブルT1とT2で10000レコードずつあって、T1.FILED=HOGEとT2.FILED=HUGAのものが100個ずつあると仮定します。単純にコスト比較するとナイーブな実行計画は全探索で10000 * 10000 = 100000000、仮テーブルを使う場合 10000 (T1でT1.FIELD = HOGEのものを探す) + 10000 (T2でT2.FIELD = HUGAのものを探す) + 100*100 (仮テーブルの全探索) = 30000とかです。もちろん仮テーブルへの書き込みというオーバヘッドもあります。
