CS 561

Data Systems Architectures

Syllabus

Class Projects

Announcements

Note: The class schedule is now finalized, however, monitor the website for any updates during the semester.

Class at a glance

Class: Tue/The 11:00am-12:15pm (CAS 228)
Instructor: Manos Athanassoulis

Lab: Fri 2:30-3:20pm (CDS 701)
Teaching Fellow: Teona Bagashvili

Office: CDS 928
Office Hours: Posted on Piazza

Discussion on Piazza / Grades on Gradescope
TF Office Hours: Posted on Piazza

Announcements

Semester starts on - stay tuned for updates.
See updates and announcements in Piazza.

Class Milestones - Important Dates

Keep in mind the Official Semester Dates.

Feb 1, submit project 0
Feb 15, submit project 1
Feb 22, submit your project proposal
February 24, last day to drop (without a "W")
- , meet with your assigned mentor (graded)
TBA, Student-led discussion
Mar 22, submit your mid-semester progress report
TBA, Student-led discussion
- , meet with your assigned mentor (graded)
April 3, last day to drop (with a "W")
TBA, Student-led discussion
May 3, final submission of project code and report

Class Schedule (tentative)

Here you can find the tentative schedule of the class (which might change as the semester progresses).

Class : Introduction to Data Systems and CS561

Readings

Slides

Class : Data Systems Architectures Essentials – Part 1

Readings

Slides
Architecture of a Database System, Foundations and Trends in Databases, 2007
The Design and Implementation of Modern Column-Oriented Database Systems, Foundations and Trends in Databases, 2012
Data Structures for Data-Intensive Applications: Tradeoffs and Design Guidelines, Foundations and Trends in Databases, 2023
Massively Parallel Databases and MapReduce Systems, Foundations and Trends in Databases, 2013
The Seattle Report on Database Research, SIGMOD Record, 2022
The Cambridge Report on Database Research, 2025

Class : Data Systems Architectures Essentials – Part 2

Readings

Slides
Architecture of a Database System, Foundations and Trends in Databases, 2007
The Design and Implementation of Modern Column-Oriented Database Systems, Foundations and Trends in Databases, 2012
Massively Parallel Databases and MapReduce Systems, Foundations and Trends in Databases, 2013
The Seattle Report on Database Research, SIGMOD Record, 2022

Class : LSM intro and Class Project Overview

Readings

Slides
Dissecting, Designing, and Optimizing LSM-based Data Stores, SIGMOD 2022
LSM-based Storage Techniques: A Survey, arXiv 2018

A: Storage Layouts

Class : Row-Stores vs. Column-Stores

Readings

Slides
Technical Question : Based on the paper, compare the performance of materialized views with the performance of column-stores. Briefly, explain the key reasons for the performance gap.
Column-Stores vs. Row-Stores: How Different Are They Really?, SIGMOD 2008 (Paper for TQ)
C-Store: A Column-oriented DBMS, VLDB 2005 [additiona link]

Class : Log-Structured Merge (LSM) Trees & Compaction & Deletes

Readings

Slides
Technical Question : What is the key design idea of Dostoevsky to address the limitations of existing merge policies? Explain how does this design affect the point lookups and range (short and long) lookups.
Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging, SIGMOD 2018 (Paper for TQ) [conf. present. video]
Dissecting, Designing, and Optimizing LSM-based Data Stores, SIGMOD 2022 [slides, conf. present. video]
Constructing and Analyzing the LSM Compaction Design Space, VLDB 2021
Monkey: Optimal Navigable Key-Value Store, SIGMOD 2020
Compactionary: A Dictionary for LSM Compactions, SIGMOD 2022 [DEMO]

Class : Scans in Key-Value Stores

Readings

Slides
Technical Question : How does TellStore-Log support fast get/put requests, versioning, and scans at the same time? In other words, describe the key design decisions of TellStore-Log that allows it to achieve fast get/put requests, versioning, and scans.
Fast Scans on Key-Value Stores, SIGMOD 2017 (Paper for TQ)
F2: Designing a Key-Value Store for Large Skewed Workloads

B. Indexing

Class : Introduction to Index Design

Readings

Slides
Technical Question : Given high cardinality and low cardinality attributes, which storage scheme (Bitmap-Level Storage, Component-Level Storage, Index-level Storage) would give better compression for each case? Justify your answer.
Bitmap Index Design and Evaluation, SIGMOD 1998 (Paper for TQ)
LSM-based Storage Techniques: A Survey, arXiv 2018
Modern B-Tree Techniques, Foundations and Trends in Databases 2011
Prefix B-trees, TODS 1977
Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing, VLDB 1998
Column imprints: a secondary index structure, SIGMOD 2013
Database Cracking, CIDR 2007

Class : Guest Lecture on SSD Design Elements: Teona Bagashvili

Readings

Slides
Technical Question : Estimate the latency of executing a zone finish command if the zone capacity is 8192 KiB, the page size is 16 KiB, the zone occupancy is 25%, and zone parallelism is 4. The SSD has finish granularity of 16 KiB, and a page write latency of 600 microseconds. How will latency change if finish granularity is 64 KiB?
Exploring I/O Management Performance in ZNS with ConfZNS++, SYSTOR 2024 (Paper for TQ)
ZNS: Avoiding the Block Interface Tax for Flash-based SSDs, USENIX 2021
Introduction to Flexible Data Placement: New Era of Optimized Data Management
A Brief History of Data Placement Technologies

Class : Robust and Learned Tuning

Readings

Slides
Technical Question : Based on the evidence presented in ENDURE, which of the two classic compaction policies (Tiering or Leveling) is more robust? Justify your answer.
ENDURE: A Robust Tuning Paradigm for LSM Trees, VLDB 2022 (Paper for TQ) [conf. present. video]
CliffGuard: A Principled Framework for Finding Robust Database Designs, SIGMOD 2015
Automatic Database Management System Tuning Through Large-scale Machine Learning, SIGMOD 2017

Class : Sortedness-Aware Indexing

Readings

Slides
Technical Question : In Fig 2b. QuIT is shown to have better sortedness-awareness. Yet, SWARE has an overall better memory utilization. Explain why
QuIT your B+ tree for Quick Insertion Tree, EDBT 2025 (Paper for TQ)
Indexing for Near-Sorted Data, ICDE 2023

Class : Adaptive Radix Trees

Readings

Slides
Technical Question : Suppose we have two trees: one ART and another B+trees. Compare their performance for point and range lookups. Further, if we implement prefix compression in the b+tree, would your answer change?
The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases, ICDE 2013

Class : Bitmap indexing

Readings

Slides
Technical Question : Based on UpBit paper, how does the granularity of fence pointers affect read and update latencies? Justify your answer
UpBit: Scalable In-Memory Updatable Bitmap Indexing, SIGMOD 2016 (Paper for TQ)
CUBIT: Concurrent Updatable Bitmap Indexing, VLDB Endowement 2024
RABIT: E!icient Range "eries with Bitmap Indexing, PACMMOD 2025

Class : Filters

Readings

Slides

C. Modern Hardware

Class : Modern hardware trends

Readings

Slides
Technical Question : What would be the speedup of the application with batchable reads and unbatchable writes, given that the workload has 60% reads and the SSD has a read concurrency of 8 and an asymmetry of 4. How would the speedup change if the asymmetry was 1?
A Parametric I/O Model for Modern Storage Devices, DaMon 2021 (Paper for TQ)
Data Management Over Flash Memory, SIGMOD 2011

Class : Relational Memory

Readings

Slides
Technical Question : TBD
Relational Fabric: Transparent Data Transformation, ICDE 2023
Relational Memory: Native In-Memory Accesses on Rows and Columns, EDBT 2023 (Paper for TQ)

Class : ACE Bufferpool

Readings

Slides
Technical Question : Consider you have three SSDs with the following asymmetry values: (i) α = 2.0, (ii) α = 4.0, (iii) α = 6.0. Your workload contains 50% writes with a predictive pattern. If all devices have the same concurrency values, which device will have the highest speedup after implementing ACE bufferpool and why? Also, will you use any prefetcher? Justify your answer.
ACEing the Bufferpool Management Paradigm for Modern Storage Devices, ICDE 2023 (Paper for TQ)
A Parametric I/O Model for Modern Storage Devices, DaMon 2021
Enhancing Data Systems Performance by Exploiting SSD Concurrency & Asymmetry, ICDE 2024 PhD Symposium
The Need for a New I/O Model, CIDR 2021

D. Student Talks

Class : Student Talk 1

Readings

Slides

Class : Student Talk 2

Readings

Slides

Class : Student Talk 3

Readings

Slides

Class : Student Talk 4

Readings

Slides

E. ML For Data Systems

Class : ML for Systems and Learned Query Evaluation

Readings

Slides
Technical Question : Given the query "SELECT SUM(revenue) FROM sales WHERE date BETWEEN '2023-01-01' AND '2023-01-31'" where date is an ordinal categorical attribute, explain how DBEst processes this query using its internal models. Specifically, what kind of model(s) must have been prebuilt? Justify your answer.
DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models, SIGMOD 2019
Automatic Database Management System Tuning Through Large-scale Machine Learning, SIGMOD 2017 [conf. present. video]
AB-tree: Index for Concurrent Random Sampling and Updates, VLDB 2022
Approximate Queries over Concurrent Updates, VLDB 2023 (demo of AB-tree)
Self-Driving Database Management Systems, CIDR 2017
Learning Multi-Dimensional Indexes, SIGMOD 2018 [conf. present. video]
The Case for Learned Index Structures, SIGMOD 2018 [conf. present. video]
ML-In-Databases: Assessment and Prognosis, IEEE Data Engineering Bulletin, 44(1), March 2021
Neo: A Learned Query Optimizer, VLDB 2019
SageDB: A Learned Database System, CIDR 2019
From Auto-tuning One Size Fits All to Self-designed and Learned Data-intensive Systems, SIGMOD 2019

Class : Learned Indexes

Readings

Slides
Technical Question : Discuss how learned bloom filter (with back up filter) would provide false positives, true positives, true negatives? What about false negatives?
The Case for Learned Index Structures, SIGMOD 2018 (Paper for TQ)
FITing-Tree: A Data-aware Index Structure, SIGMOD 2019
ALEX: An Updatable Adaptive Learned Index, SIGMOD 2020
Updatable Learned Index with Precise Positions, VLDB 2021
Benchmarking Learned Indexes, VLDB 2021
LSI: A Learned Secondary Index Structure, SIGMOD 2022

Class : Guest Lecture on Space Efficient Secondary Learned Indexes: Anwesha Saha

Readings

Technical Question : TBD
Slides
Exploring Wavelet Trees as Space-Efficient Physical-to-Sorted Mapping for Learned Indexes, AIDB 2025 (Paper for TQ)

Class : Exam

Click here for the exam guide

Project Presentation

Class : Project Presentations A

Project Presentation - I

Class : Project Presentations B

Project Presentation - II

Project Awards (by popular vote)

As a tradition for the class, the projects that attracted the most excitement among the class members are receiving awards by popular vote!

Class at a glance

Announcements

Class Milestones - Important Dates

Class Schedule (tentative)

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Introduction to Data Systems and CS561

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Data Systems Architectures Essentials – Part 1

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Data Systems Architectures Essentials – Part 2

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : LSM intro and Class Project Overview

Readings

A: Storage Layouts

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Row-Stores vs. Column-Stores

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Log-Structured Merge (LSM) Trees & Compaction & Deletes

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Scans in Key-Value Stores

Readings

B. Indexing

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Introduction to Index Design

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Guest Lecture on SSD Design Elements: Teona Bagashvili

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Robust and Learned Tuning

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Sortedness-Aware Indexing

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Adaptive Radix Trees

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Bitmap indexing

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Filters

Readings

C. Modern Hardware

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Modern hardware trends

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Relational Memory

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : ACE Bufferpool

Readings

D. Student Talks

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Student Talk 1

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Student Talk 2

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Student Talk 3

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Student Talk 4

Readings

E. ML For Data Systems

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : ML for Systems and Learned Query Evaluation

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Learned Indexes

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Guest Lecture on Space Efficient Secondary Learned Indexes: Anwesha Saha

Readings

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Exam

Project Presentation

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Project Presentations A

document.write("<a id=\"class" + (cday + 1) + "\"></a>"); Class document.write(cday + 1) : Project Presentations B

Project Awards (by popular vote)

Awards

Class : Introduction to Data Systems and CS561

Class : Data Systems Architectures Essentials – Part 1

Class : Data Systems Architectures Essentials – Part 2

Class : LSM intro and Class Project Overview

Class : Row-Stores vs. Column-Stores

Class : Log-Structured Merge (LSM) Trees & Compaction & Deletes

Class : Scans in Key-Value Stores

Class : Introduction to Index Design

Class : Guest Lecture on SSD Design Elements: Teona Bagashvili

Class : Robust and Learned Tuning

Class : Sortedness-Aware Indexing

Class : Adaptive Radix Trees

Class : Bitmap indexing

Class : Filters

Class : Modern hardware trends

Class : Relational Memory

Class : ACE Bufferpool

Class : Student Talk 1

Class : Student Talk 2

Class : Student Talk 3

Class : Student Talk 4

Class : ML for Systems and Learned Query Evaluation

Class : Learned Indexes

Class : Guest Lecture on Space Efficient Secondary Learned Indexes: Anwesha Saha

Class : Exam

Class : Project Presentations A

Class : Project Presentations B