CS631 : Implementation techniques in DBMS

Autumn 2024


Previous years: Autumn 2023, Autumn 2022, Autumn 2021, Autumn 2020, Autumn 2019, Spring 2019 and many earlier years; older offerings are linked from earlier years.
Sample exam papers will be provided in moodle.
Instructor: S. Sudarshan
Teaching Assistants: Sunanda Somwase
TA Office Hours: TBD
Faculty Office hours: Sudarshan: To be fixed

Lecture schedule Slot 3: Mon 1030-1125, Tue 1135-1230, Thu 830-925

Course Websites: In addition to this static Web page, we will also be using Moodle for assignment submissions, and Piazza for discussions. More information on Piazza sign up to be provided.
Textbook Database System Concepts, Silberschatz, Korth and Sudarshan, 7th edition, McGraw Hill.

Other reading material will be made available periodically
Book Slides, Errata, solutions to selected exercises and other resources are available at: https://db-book.com

Course contents We will be covering Implementation techniques including Storage and indexing, query processing, and transaction processing (Chapters 12-19), Database System Architectures (Chapter 20) and Parallel and Distributed Storage, Query Processing and Transaction Processing (Chapters 21-23).

We may also cover several research papers during the course.

As in the other recent offerings, we will have an increased focus on Big Data, starting with using Big Data systems, and then diving into their internals. You will also set up PostgreSQL, and learn how to make small changes to it as part of the course assignments.

The infrastructure for your course project will be your choice of PostgreSQL or any of the open source big data systems. If you wish to do it on any other infrastructure, you can discuss it with me.

Evaluation scheme Details are linked from Moodle.

Audit Requirements: Must attend all classes and take all exams. No need to do homeworks/assignments/projects.


Project Information
  1. PostgreSQL project topic suggestions (under construction, will add more ideas) Information about Projects TBA

PostgreSQL Resources Click Here (Instruction on creating patch files for submitting your project)

Schedule of Lectures (tentative)

Topic No. Date TopicNotes
1 July 29 Introduction/Overview
2 July 30, Aug 1, Aug 5 Chapter 12 and 13: Physical Storage Systems and Data Storage Structures Assignment: Download and compile PostgreSQL, and open in Eclipse, using instructions provided here
Physical Storage in PostgreSQL, Look inside above link for information on file layout, database page layout, and free space map (and lots more details src/backend/storage/freespace/README). And how PostgreSQL stores oversized attributes using the TOAST technique
3 Aug 6, 8, 12, 13 Chapter 14: Indexing Index access method interface in PostgreSQL (read only if you want to create new index types)
4 Aug 19, 20, 22 Chapter 15: Query Processing .
TBD Extra class: Overview of PostgreSQL internals -1 PostgreSQL resources, in particular see Tom Lane's talk
5 Aug 26, 27, 29 Chapter 16: Query Optimization Statistics in PostgreSQL, and examples of row estimation in PostgreSQL in particular see how PostgreSQL special cases most common values (MCVs).
Assignments on query plans in PostgreSQL
TBD Extra class: Overview of PostgreSQL internals -2, Debugging in Eclipse ..
6 Sep 2, 3, 5 Chapter 17 Transactions .
7 Sep 9, 10, 12 Chapter 18: Concurrency Control .
Sep 14 - 22 No Class (Midsem Exam) .
8 Sep 23, 24, 26 Chapter 19: Recovery .
9 Sep 30, Oct 1, 3 Chapter 10: Big Data
10 Oct 7, 8, 10 Chapter 20: Database Architecture
11 Oct 14, 15, 17 Parallel and Distributed Storage .
12 Oct 21, 22, 24 Parallel and Distributed Query Processing
13 Oct 28, 29, Nov 4, 5 Parallel and Distributed Transaction Processing .
14 Nov 8 RAFT: In search of an Understandable Consensus Algorithm, Diego Ongarro and John Ousterhout, USENIX ATC 2014 .