CS 6422 Database System Implementation - Fall 2025

2025 FallにCS 6422: Database System Implementationを履修した。プロジェクトを通してDatabaseの内部実装を勉強するコース。主なテーマはstorage management、 indexing、 query execution。実装はC++。内容としてはCIOSやHPCAとオーパーラップする部分も多く、理解を深めるのにも良かったと思う。プロジェクトはC++の簡単な使い方から始まり、buffer manager, B+tree, volcano operator の実装など。てっきりQuery engine の実装がメインかと思いきや、そちらは最後のプロジェクトのみであった。

プロジェクトと並行して小テスト、中間テスト、期末テストが行われた。期末テストは特に難しくて、思っていたより低い点数に着地してしまった。使ったテキストブックはDatabase System Conceptsで、備考録としてクラスで取り上げられた論文のリンクも貼っておく。

• Codd, E. F. (1970). A Relational Model of Data for Large Shared Data Banks. Communications of the ACM, 13(6), 377–387. Available at: https://www.seas.upenn.edu/~zives/03f/cis550/codd.pdf
• Stonebraker, M., Pavlo, A. (2024). What Goes Around Comes Around… And Around… SIGMOD Record, 21–37. Association for Computing Machinery. Available at: https://db.cs.cmu.edu/papers/2024/whatgoesaround-sigmodrec2024.pdf
• Stonebraker, M. (1981). Operating system support for database management. Communications of the ACM, 24(7), 412–418. https://dl.acm.org/doi/10.1145/358699.358703
• Neumann, T.; Freitag, M. (2020). Umbra: A Disk-Based System with In-Memory Performance — https://db.in.tum.de/~freitag/papers/p29-neumann-cidr20.pdf.
• Levandoski, J. J.; Lomet, D. B.; Sengupta, S. (2013). The Bw-Tree: A B-tree for New Hardware Platforms — https://15721.courses.cs.cmu.edu/spring2016/papers/bwtree-icde2013.pdf.
• Guttman, A. (1984). R-trees: A Dynamic Index Structure for Spatial Searching — https://doi.org/10.1145/602259.602266. (ACM Digital Library)
• Kraska, T.; Beutel, A.; Chi, E. H.; Dean, J.; Polyzotis, N. (2018). The Case for Learned Index Structures — https://doi.org/10.1145/3183713.3196909. (ACM Digital Library)
• DeWitt, D.; Gray, J. (1992). Query Processing in Parallel Relational Database Systems — https://www.cs.cmu.edu/~15721-f24/papers/Parallel_Database_Systems.pdf
• Graefe, G. (1990). Encapsulation of Parallelism in the Volcano Query Processing System — https://cs-people.bu.edu/mathan/reading-groups/papers-classics/encapsulation-volcano.pdf
• Neumann, T. (2011). Efficiently Compiling Efficient Query Plans for Modern Hardware — https://www.vldb.org/pvldb/vol4/p539-neumann.pdf
• Boncz, P. A.; Zukowski, M. (2012). Vectorwise: Beyond Column Stores — http://sites.computer.org/debull/A12mar/vectorwise.pdf
• Stonebraker, M.; Abadi, D. J.; et al. (2005). C-Store: A Column-oriented DBMS — https://web.stanford.edu/class/cs345d-01/rl/cstore.pdf

仕事で触るデータベースだけど、内部の実装を理解することで、実践的な知識が深まったと思う ( データベース内部の最適化など)。個人的にはlearned indexが実用レベルになって、indexの管理から開放される未来に期待したい。 クラスの負荷という意味では軽い方だったと思う。実践的なDB内部実装の理解を深めたい+そこまで労力をかけたくないという人にはおすすめできるクラスかもしれない。2026 SpringはCS 7295: GPU Hardware and Softwareを履修予定。卒業までいよいよ残りわずか。学生ライフを満喫せねば。