| Jan 13, 2020 |
Course Introduction and History of Databases (No In-Class Lecture)
- M. Stonebraker, et al., What Goes Around Comes Around, in Readings in Database Systems, 4th Edition, 2006
(Optional)
- A. Pavlo, et al., What's New with NewSQL?, in SIGMOD Record (vol. 45, iss. 2), 2016
(Optional)
|
|
— |
|
| Jan 15, 2020 |
In-Memory Databases (No In-Class Lecture)
- X. Yu, et al., Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores, in VLDB, 2014
- S. Harizopoulos, et al., OLTP Through the Looking Glass, and What We Found There, in SIGMOD, 2008
(Optional)
- H. Garcia-Molina, et al., Main Memory Database Systems: An Overview, in IEEE Trans. on Knowl. and Data Eng., 1992
(Optional)
|
|
|
|
| Jan 20, 2020 |
Martin Luther King Day — No Class |
|
|
|
| Jan 22, 2020 |
Multi-Version Concurrency Control (Design Decisions)
- Y. Wu, et al., An Empirical Evaluation of In-Memory Multi-Version Concurrency Control, in VLDB, 2017
- D.R.K. Ports, et al., Serializable Snapshot Isolation in PostgreSQL, in VLDB, 2012
(Optional)
- Y. Huang, et al., Opportunities for Optimism in Contended Main-Memory Multicore Transactions, in VLDB, 2020
(Optional)
|
|
|
|
| Jan 27, 2020 |
Multi-Version Concurrency Control (Protocols)
- T. Neumann, et al., Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems, in SIGMOD, 2015
- H. Lim, et al., Cicada: Dependably Fast Multi-Core In-Memory Transactions, in SIGMOD, 2017
(Optional)
- P.-A. Larson, et al., High-Performance Concurrency Control Mechanisms for Main-Memory Databases, in VLDB, 2011
(Optional)
|
|
|
|
| Jan 29, 2020 |
Multi-Version Concurrency Control (Garbage Collection)
|
|
|
|
| Feb 03, 2020 |
OLTP Indexes (B+Tree Data Structures)
- Z. Wang, et al., Building A Bw-Tree Takes More Than Just Buzz Words, in SIGMOD, 2018
- S.K. Cha, et al., Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems, in VLDB, 2001
(Optional)
- G. Graefe, A Survey of B-Tree Locking Techniques, in TODS, 2010
(Optional)
- J. Levandoski, et al., The Bw-Tree: A B-tree for New Hardware, in ICDE, 2013
(Optional)
- J. Faleiro, et al., Latch-free Synchronization in Database Systems: Silver Bullet or Fool's Gold?, in CIDR, 2017
(Optional)
- T. Kissinger, et al., KISS-Tree: smart latch-free in-memory indexing on modern architectures, in DaMoN, 2012
(Optional)
|
|
|
|
| Feb 05, 2020 |
OLTP Indexes (Trie Data Structures)
- V. Alvarez, et al., A Comparison of Adaptive Radix Trees and Hash Tables, in ICDE, 2015
- V. Leis, et al., The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases, in ICDE, 2013
(Optional)
- V. Leis, et al., The ART of Practical Synchronization, in DaMoN, 2016
(Optional)
- R. Binna, et al., HOT: A Height Optimized Trie Index for Main-Memory Database Systems, in SIGMOD, 2018
(Optional)
|
|
— |
|
| Feb 10, 2020 |
Storage Models, Data Layout, & System Catalogs
- M. Athanassoulis, et al., Optimal Column Layout for Hybrid Workloads, in VLDB, 2019
- J. Arulraj, et al., Bridging the Archipelago Between Row-Stores and Column-Stores for Hybrid Workloads, in SIGMOD, 2016
(Optional)
- I. Alagiannis, et al., H2O: A Hands-free Adaptive Store, in SIGMOD, 2014
(Optional)
- M. Grund, et al., HYRISE: a main memory hybrid storage engine, in VLDB, 2010
(Optional)
- D. Abadi, et al., Column-Stores vs. Row-Stores: How Different Are They Really?, in SIGMOD, 2008
(Optional)
|
|
— |
|
| Feb 12, 2020 |
Database Compression
- D. Abadi, et al., Integrating Compression and Execution in Column-Oriented Database Systems, in SIGMOD, 2006
- C. Binnig, et al., Dictionary-based Order-preserving String Compression for Main Memory Column Stores, in SIGMOD, 2009
(Optional)
- I. Müller, et al., Adaptive String Dictionary Compression in In-Memory Column-Store Database Systems, in EDBT, 2014
(Optional)
- V. Raman, et al., How to Wring a Table Dry: Entropy Compression of Relations and Querying of Compressed Relations, in VLDB, 2006
(Optional)
- H. Zhang, et al., Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes, in SIGMOD, 2016
(Optional)
- C. Liu, et al., Mostly Order Preserving Dictionaries, in ICDE, 2019
(Optional)
|
|
— |
|
| Feb 17, 2020 |
Recovery Protocols
- P. Antonopoulos, et al., Constant Time Recovery in Azure SQL Database, in VLDB, 2019
- W. Zheng, et al., Fast Databases with Fast Durability and Recovery Through Multicore Parallelism, in OSDI, 2014
(Optional)
- A. Goel, et al., Fast Database Restarts at Facebook, in SIGMOD, 2014
(Optional)
- K. Ren, et al., Low-Overhead Asynchronous Checkpointing in Main-Memory Database Systems, in SIGMOD, 2016
(Optional)
- N. Malviya, et al., Rethinking Main Memory OLTP Recovery, in ICDE, 2014
(Optional)
|
|
— |
|
| Feb 19, 2020 |
Networking Protocols
- M. Raasveldt, et al., Don't Hold My Data Hostage: A Case for Client Protocol Redesign, in VLDB, 2017
- F. Li, et al., Accelerating Relational Databases by Leveraging Remote Memory and RDMA, in SIGMOD, 2016
(Optional)
- F. Binnig, et al., The End of Slow Networks: It's Time for a Redesign, in VLDB, 2016
(Optional)
|
|
— |
|
| Feb 24, 2020 |
Scheduling
- V. Leis, et al., Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age, in SIGMOD, 2014
- I. Psaroudakis, et al., Scaling Up Concurrent Main-Memory Column-Store Scans: Towards Adaptive NUMA-aware Data and Task Placement, in VLDB, 2015
(Optional)
- I. Psaroudakis, et al., Task Scheduling for Highly Concurrent Analytical and Transactional Main-Memory Workloads, in ADMS, 2013
(Optional)
- D. Porobic, et al., OLTP on Hardware Islands, in VLDB, 2012
(Optional)
|
|
— |
|
| Feb 26, 2020 |
Query Execution & Processing
- M. Kester, et al., Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?, in SIGMOD, 2017
- P. Boncz, et al., MonetDB/X100: Hyper-Pipelining Query Execution, in CIDR, 2005
(Optional)
- L. Shrinivas, et al., Materialization Strategies in the Vertica Analytic Database: Lessons Learned, in ICDE, 2013
(Optional)
- A. Mishra, et al., Accelerating Analytics with Dynamic In-Memory Expressions, in VLDB, 2016
(Optional)
|
|
— |
|
| Mar 02, 2020 |
Query Compilation
- T. Neumann, Efficiently Compiling Efficient Query Plans for Modern Hardware, in VLDB, 2011
- K. Krikellas, et al., Generating Code for Holistic Query Evaluation, in ICDE, 2010
(Optional)
- H. Pirk, et al., CPU and Cache Efficient Management of Memory-Resident Databases, in ICDE, 2013
(Optional)
- B. Raducanu, et al., Micro Adaptivity in Vectorwise, in SIGMOD, 2013
(Optional)
- A. Shaikhha, et al., How to Architect a Query Compiler, in SIGMOD, 2016
(Optional)
- A. Kohn, et al., Adaptive Execution of Compiled Queries, in ICDE, 2018
(Optional)
|
|
— |
|
| Mar 04, 2020 |
Vectorized Execution
- O. Polychroniou, et al., Rethinking SIMD Vectorization for In-Memory Databases, in SIGMOD, 2015
- T. Thomas Willhalm, et al., SIMD-scan: Ultra Fast In-memory Table Scan using On-chip Vector Processing Units, in VLDB, 2009
(Optional)
- Y. Li, et al., BitWeaving: Fast Scans for Main Memory Data Processing, in SIGMOD, 2013
(Optional)
Project Released: Extra Credit
|
|
— |
|
| Mar 09, 2020 |
Spring Break — No Class |
|
|
|
| Mar 11, 2020 |
Spring Break — No Class |
|
|
|
| Mar 16, 2020 |
University Closure — No Class |
|
|
|
| Mar 18, 2020 |
Student Project Proposals |
— |
— |
— |
| Mar 23, 2020 |
Vectorization vs. Compilation
- T. Kersten, et al., Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask, in VLDB, 2018
- P. Menon, et al., Relaxed Operator Fusion for In-Memory Databases: Making Compilation, Vectorization, and Prefetching Work Together At Last, in VLDB, 2017
(Optional)
- J. Sompolski, et al., Vectorization vs. Compilation in Query Execution, in DaMoN, 2011
(Optional)
- H. Lang, et al., Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation, in SIGMOD, 2016
(Optional)
|
|
— |
|
| Mar 25, 2020 |
Parallel Join Algorithms (Hashing)
- S. Schuh, et al., An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory, in SIGMOD, 2016
- S. Richter, et al., A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing, in VLDB, 2015
(Optional)
- S. Blanas, et al., Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs, in SIGMOD, 2011
(Optional)
- C. Balkesen, et al., Main-Memory Hash Joins on Multi-Core CPUs: Tuning to the Underlying Hardware, in ICDE, 2013
(Optional)
|
|
— |
|
| Mar 30, 2020 |
Parallel Join Algorithms (Sorting)
- C. Balkesen, et al., Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited, in VLDB, 2013
- C. Kim, et al., Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs, in VLDB, 2009
(Optional)
- G. Graefe, et al., Sort vs. Hash Revisited, in TKDE, 1994
(Optional)
- M.-C. Albutiu, et al., Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems, in VLDB, 2012
(Optional)
|
|
— |
|
| Apr 01, 2020 |
Optimizer Implementation (Overview)
- S. Chaudhuri, An Overview of Query Optimization in Relational Systems, in PODS, 1998
- G. Graefe, et al., The Volcano Optimizer Generator: Extensibility and Efficient Search, in ICDE, 1993
(Optional)
- G. Graefe, The Cascades Framework for Query Optimization, in IEEE Data Engineering Bulletin, 1995
(Optional)
- M.A. Soliman, et al., Orca: A Modular Query Optimizer Architecture for Big Data, in SIGMOD, 2014
(Optional)
- L.D. Shapiro, et al., Exploiting Upper and Lower Bounds In Top-Down Query Optimization, in IDEAS, 2001
(Optional)
|
|
— |
|
| Apr 06, 2020 |
Optimizer Implementation (Top-Down vs. Bottom-Up)
- Yongwen Xu, Efficiency in the Columbia Database Query Optimizer (pages 1-35), in Portland State University, 1998
- J. Chen, et al., The MemSQL Query Optimizer, in VLDB, 2017
(Optional)
- G. Moerkotte, et al., Dynamic Programming Strikes Back, in SIGMOD, 2008
(Optional)
- T. Neumann, et al., The Complete Story of Joins (in HyPer), in BTW, 2017
(Optional)
- E. Begoli, et al., Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources, in SIGMOD, 2018
(Optional)
|
|
— |
|
| Apr 08, 2020 |
Student Project Updates |
— |
— |
— |
| Apr 13, 2020 |
Optimizer Implementation (Alternative Approaches)
- B. Ding, et al., Plan Stitch: Harnessing the Best of Many Plans, in VLDB, 2018
- S. Babu, et al., Adaptive Query Processing in the Looking Glass, in CIDR, 2015
(Optional)
- J. Zhu, et al., Looking Ahead Makes Query Plans Robust, in VLDB, 2017
(Optional)
- R. Marcus, et al., Neo: A Learned Query Optimizer, in VLDB, 2019
(Optional)
- I. Trummer, et al., SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning, in SIGMOD, 2019
(Optional)
|
|
— |
|
| Apr 15, 2020 |
Cost Models
- V. Leis, et al., How Good are Query Optimizers, Really?, in VLDB, 2015
- M. Stillger, et al., LEO - DB2's LEarning Optimizer, in VLDB, 2001
(Optional)
- Z. Yang, et al., Deep Unsupervised Cardinality Estimation, in VLDB, 2019
(Optional)
- J. Sun, et al., An End-to-End Learning-based Cost Estimator, in VLDB, 2019
(Optional)
- D. Vengerov, et al., Join Size Estimation Subject to Filter Conditions, in VLDB, 2015
(Optional)
- Y. Chen, et al., Two-Level Sampling for Join Size Estimation, in SIGMOD, 2017
(Optional)
|
|
— |
|
| Apr 20, 2020 |
Larger-than-Memory Databases
- V. Leis, et al., LeanStore: In-Memory Data Management beyond Main Memory, in ICDE, 2018
- J. DeBrabant, et al., Anti-Caching: A New Approach to Database Management System Architecture, in VLDB, 2013
(Optional)
- R. Stoica, et al., Enabling Efficient OS Paging for Main-Memory OLTP Databases, in DaMoN, 2013
(Optional)
- G. Graefe, et al., In-Memory Performance for Big Data, in VLDB, 2014
(Optional)
- L. Ma, et al., Larger-than-memory Data Management on Modern Storage Hardware for In-memory OLTP Database Systems, in DaMoN, 2016
(Optional)
|
|
— |
|
| Apr 22, 2020 |
Server-side Logic Execution
|
|
— |
|
| Apr 27, 2020 |
Databases on New Hardware
- J. Arulraj, et al., Write-Behind Logging, in VLDB, 2016
- M. Owaida, et al., Centaur: A Framework for Hybrid CPU-FPGA Databases, in FCCM, 2017
(Optional)
- H. Kimura, FOEDUS: OLTP Engine for a Thousand Cores and NVRAM, in SIGMOD, 2015
(Optional)
- J. Power, et al., Toward GPUs Being Mainstream in Analytic Processing, in DaMoN, 2015
(Optional)
|
|
— |
|
| Apr 29, 2020 |
Guest Speaker: Ippokratis Pandis (PhD'07) (Amazon Redshift) (Only Available to CMU Students) |
— |
— |
— |
CMU 15-721