OMSCS C++

CS 6422: Database System Implementation

OMSCS 7 つ目の授業に関する記録

OMSCS 2025 Fall (秋学期) では Database System Implementation を受講した。データベースを実装しつつ、内部構成に関して学ぶことができる授業であった。

Overall

この講義は、データベースを実際に構築していきながらデータベースの仕組みを学ぶコースであった。 キャンパスでのみオフラインで存在していたコースだが、2025年 Spring からオンラインでも開設されたコースとなっている。もともと口頭試験などあったらしく、オンラインで開設するにあたり、調整はあったようである。新しい授業であったので色々と整っていない可能性があったが、データベースのトピックに関して興味を持っていた。また受講された方の情報を見るとそのような心配はなく、内容としても評価が悪くなったので受講を決断した。 業務でデータベースを使っておりそれなりに知っているつもりであったが、実装レベルでの学びは非常に貴重であった。

CS 6422: Database System Implementation

Content

講義に関しては最初にストレージエンジンの話から始まり、インデックス、クエリ実行までが範囲あった。課題に関してはプログラミング課題は四つであった。 この授業の評価は、50 % が試験で、27.5 % がプログラミング課題、22.5 % が小テストであった。試験の比重が高い構成であったため、試験勉強に苦労した。 プログラミング課題に関しては、隠されたテストケースなどはなく、明示されたテストがパスできれば点数が加算されるため、比較的進めやすかった。 授業の中でいくつか論文を紹介され、試験問題にもなっていたが、十分に時間を費やすことはできなかった。興味深い内容が多かったため、時間をかけて読み進めたい。

Assignment

  • Assignment 1
    初回の課題は、CSV ファイルの読み書きを中心として C++ の基礎を中心とした課題であった。合わせて、ファイルベースのデータ管理の問題点などを学び、講義の導入でもあった。 ファイルの操作の並列処理にも対応するため、C++ における lock_guard になどを活用し、Thread Safe な実装の基礎を実践した。

  • Assignment 2
    ファイルベースから RDBMS の登場を学んだ後、ストレージエンジンを中心とした実践として Buffer Manager の実装を行った。ストレージエンジンとしては、可変長なデータの格納を実現するため、Slotted Page で実装されている。ページと呼ばれる単位でデータが扱われるが、Slotted Page ではページの先頭行にヘッダーが構成されており、実際のデータ格納位置を示すため柔軟性が特徴である。 また、Buffer Manager では、ディスクに対してデータの読み取り、書き込みを担う。ディスクへのアクセスがパフォーマンスのネックになることから、一時的にデータをメモリに保持しておくキャッシュの実装も行った。FIFO (First In First Out)、LRU (Least Recently Used) を組み合わせた、2Q ポリシーによってキャッシュを管理した。こちらも同時実行性のため、読み込みのための共有ロックと書き込みの場合の占有ロックの実装が必要であった。。

  • Assignment 3
    効率的なデータの格納として B+ Tree を学んだ後、実際に B+ Tree を実装した。Root, Inner node, Leaf node を実装し、ノードサイズまでデータを格納した場合には、適切にスプリットする必要があった。ノードの実装には、C++ のテンプレートを活用している。また、Leaf node 間はリンクし、レンジクエリにも対応する必要があった。

  • Assignment 4
    最後はクエリの実行パートについて学び、 iterator モデルであり、それぞれの処理を Operator として実装するエリ実行部分がテーマの課題であった。クエリテキストを入力としてパースし、内部表現に変換した。その後、Operator クラスから継承した具体的な操作 (Select, Scan など) を組み合わせて処理を行った。

Exam

試験に関しては 2 回行われた。A4 1 枚を Cheet Sheet として持ち込み可能であったので、まとめて参照した。問題の形式は 4 択の選択問題であったが、C++ での実装に関する内容や論文からの出題も多かった。

  • Midterm Exam
  • Final Exam

Paper

授業で紹介された論文は以下である。

Code

講義では概念や実装の説明があったが、実際のソースコードに関しては以下で公開されている。講義が進むにつれて、BuzzDB と呼ばれるデータベースがより高度にバージョンアップされている。

https://github.com/jarulraj/buzzdb/tree/main

(ちなみに、ジョージア工科大学のマスコットキャラクターが Buzz というハチであるため、よく Buzz なんとかを見かけることがある。wikipedia にもページが存在していた。)

https://en.wikipedia.org/wiki/Buzz_(mascot)

各バージョンの変化に関しては、以下にメモとしてまとめた。

BuzzDB バージョン履歴

  • V1

    • Tuple, BuzzDB class の実装

  • V2

    • File input の追加

  • V3

    • 実行時間計測の追加

  • V4

    • Field class の追加

  • V5

    • Fieldtype における String の追加
    • Field の Destructor で Tuple の Destructor が呼ばれてる

  • V6

    • Smart pointer の導入
    • String の constructor で std::copy から strcpy に変化

  • V7

    • Field の data が data_s などで異なっていたが、data に統一された
    • std::memcpy(data.get(), &i, data_length); → int 型の値 i を char[] のバッファ (data) にコピー。つまり、i のバイナリ表現を data に格納している
    • 異なる型（int, float, string など）を一つのクラスで扱いたい

  • V8

    • Page class の導入
    • Page class 内で tuple の vector である tuples が定義
    • V7 までは、tuple の vector である table が buzzdb で定義されていた
    • Ifstream

  • V9

    • Field, tuple にそれぞれ serialize logic を実装
      • Page に write は健在
    • Field, tuple, Page に deserialize
    • Static method によって、page 作成しなくても deserialize を呼べる
      • static std::unique_ptr<Page> deserialize

  • V10

    • deleteTuple の導入
    • deleteTuple -> tuples.erase を読んでる

  • V11

    • Slotted page の導入
    • Slot* slot_array = reinterpret_cast<Slot*>(page_data.get()); がコンストラクタと addtuple にある
    • deleteTuple が slot の書き換えのみ
    • Write と deserialize が page_data.get()
    • Deserialize は page 全体

  • V12

    • Database file の作成が追加されている
    • BuzzDB class extendDatabaseFile
    • Deserialize は page id に基づいて実施
    • Slotted page に flush の追加

  • V13

    • Index の作成
    • Buzzdb scanTableToBuildIndex
    • なぜ istringstream なのか
      • const char* tuple_data = page_buffer + slot_array[slot_itr].offset;
      • std::istringstream iss(tuple_data);

  • V14

    • StorageManager の実装
    • Page の追加の extend が SM 側へ

  • V15

    • BufferManager の導入
    • PageList が lruList でどの page id があるか記録
    • pageMap が page の実態？
      • typename PageList::iterator

  • V16

    • Policy class の導入

  • V17

    • TwoQPolicy の導入
    • L470, 475 で LRU.push_front から LRU.push_back に変更？
    • Module 5

  • V18

    • TwoQPolicy のテスト
    • Module 5

  • V23

    • Point, Rectangle, Timestamp, Vector 型を追加

  • V24

    • HashIndex class あり
    • unordered_map で実装
    • Module 7

  • V25

    • Hash index を独自実装
    • std::vector<std::optional<HashEntry>> hashTable;
    • hashFunction は単純な mod
    • Linear probing
    • Exists によるソフトデリート
    • Module 7

  • V26

    • Position の追加
    • Module 7

  • V27

    • Quadratic probing の実装
    • Module 7

  • V28

    • Buzzdb における processPageRange, parallelProcessPages の実装
    • scanTableToBuildIndex -> parallelProcessPages -> processPageRange
    • parallelProcessPages
      • 割り当てられた page を対象に thread が processPageRange を実行
    • processPageRange
      • 対象区間の tuple data を iss で読み取って index.insertOrUpdate を実行
    • Module 8

  • V29

    • Mutex の vector を導入
    • MUTEX_PER_SLOT の実装
    • Capacity サイズの hashTable を作成
    • Capacity 分の mutex を作成
    • insertOrUpdate, getValue で mutex を利用し lock
    • Module 8

  • V30

    • shared_mutex の導入
    • insertOrUpdate は unique_lock で排他ロック
    • getValue は shared_lock で共有ロック
    • Module 8

  • V31

    • Rangequery あり
    • Index に method
    • Scan が生じるため非効率
    • Module 9

  • V32

    • B+tree の導入
    • B+tree は template
    • Lambda function によるバイナリーサーチ
    • Module 9

  • V33

    • Key と value を異なる vector に保存
    • Module 9

  • V34

    • scanTableToBuildIndex, selectGroupBySum が実装されたか
    • Hard coded query
    • Module 11

  • V35

    • Operator class の導入
      • explicit コンストラクタは暗黙の型変換を禁止する
    • UnaryOperator, BinaryOperator
      • ScanOperator の導入
      • Open でも row を読んでいるが、print もしていないので、何か飛ばしていたりしないか
    • Module 11

  • V36

    • Predicator class の導入
    • Module 11

  • V37

    • OperandType { DIRECT, INDIRECT }; の導入
    • Operand class
    • Module 11

  • V38

    • Select operator の導入
      • SelectOperator は UnaryOperator を継承した具象クラス
      • UnaryOperator は Operator を継承した抽象クラス
      • Operator 抽象基底クラス
    • Module 11

  • V39

    • IPredicate class の導入
      • SimplePredicate, ComplexPredicate の実現
    • Executequery で greaterThanTwo と lessThanSix の AND
    • Module 12

  • V40

    • HashAggregationOperator の導入
      • group_keys は大きな while なので、いったん固定
      • 以下で key に対して、vector を付与で、値は 0
        std::vector<Field> aggr_values(aggr_funcs.size(), Field(0));
        hash_table[group_keys] = aggr_values;
      • 3 つ目の引数 *tuple[aggr_funcs[i].attr_index] で現在の tuple の値を加えている
    • Module 12

  • V41?

    • Module 13?

  • V42

    • Create Index operator
    • Open で hash_index.insertOrUpdate を呼び出している
    • Module 12

  • V43

    • parseQuery の実装
    • emplace の違い:
      • push_back や insert は「既に作られたオブジェクト」をコピー／ムーブして格納
      • emplace はコンテナ内部でオブジェクトをその場で構築する
    • Module 13

  • V44

    • queryCompilation の実装
    • Pointer を変換して、integerField に入れて、Field の int にしている

Reflection

試験に関してもう少しうまくやれたかという後悔もあるが、全体としては自分の興味のある領域に合致するような授業であったと思う。特にデータベースに関しては、今まで業務で使ってきたため馴染みはあったが、実際のコードベースでその実装だったり工夫だったりを学ぶことができたのは非常に大きい。また論文に関しても、Codd をはじめとする有名なデータベースに関する論文に触れる機会があり、この先のそのデータベースデータに関する業務にも役立つ内容だったと思う。

Licensed under CC BY-NC-SA 4.0
© 2024 - 2025 Example Person
Hugo で構築されています。
テーマ Stack は Jimmy によって設計されています。