Schedule

Date	Topic	Slides	Notes	Video
Jan 17, 2018	Course Introduction and History of Database Systems 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) Assignment Released: SQL String Functions
Jan 22, 2018	In-Memory Databases S. Harizopoulos, et al., OLTP Through the Looking Glass, and What We Found There, in SIGMOD, 2008 H. Garcia-Molina, et al., Main Memory Database Systems: An Overview, in IEEE Trans. on Knowl. and Data Eng., 1992 (Optional) D.J. DeWitt, et al., Implementation Techniques for Main Memory Database Systems, in SIGMOD, 1984 (Optional)
Jan 24, 2018	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)
Jan 29, 2018	Optimistic Concurrency Control (OCC) S. Tu, et al., Speedy Transactions in Multicore In-Memory Databases, in SOSP, 2013 X. Yu, et al., TicToc: Time-Traveling Optimistic Concurrency Control, in SIGMOD, 2016 (Optional) X. Yu, et al., Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores, in VLDB, 2014 (Optional) Assignment Due: SQL String Functions
Jan 31, 2018	Multi-Version Concurrency Control (Part I) Y. Wu, et al., An Empirical Evaluation of In-Memory Multi-Version Concurrency Control, in VLDB, 2017 A. Adya, et al., Generalized Isolation Level Definitions, in ICDE, 2000 (Optional) Assignment Released: Concurrent Index
Feb 05, 2018	Multi-Version Concurrency Control (Part II) H. Lim, et al., Cicada: Dependably Fast Multi-Core In-Memory Transactions, in SIGMOD, 2017 D.R.K. Ports, et al., Serializable Snapshot Isolation in PostgreSQL, in VLDB, 2012 (Optional) P.-A. Larson, et al., High-Performance Concurrency Control Mechanisms for Main-Memory Databases, in VLDB, 2011 (Optional) T. Neumann, et al., Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems, in SIGMOD, 2015 (Optional)
Feb 07, 2018	Index Locking & Latching G. Graefe, A Survey of B-Tree Locking Techniques, in TODS, 2010 J. Faleiro, et al., Latch-free Synchronization in Database Systems: Silver Bullet or Fool's Gold?, in CIDR, 2017 (Optional) S.K. Cha, et al., Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems, in VLDB, 2001 (Optional)
Feb 12, 2018	OLTP Indexes (Part I) J. Levandoski, et al., The Bw-Tree: A B-tree for New Hardware, in ICDE, 2013 Ticki, Skip Lists: Done Right, in [BLOG], 2016 (Optional) W. Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, in CACM, 1990 (Optional) W. Pugh, Concurrent Maintenance of Skip Lists, in University of Maryland Tech Report, 1990 (Optional) T. Kissinger, et al., KISS-Tree: smart latch-free in-memory indexing on modern architectures, in DaMoN, 2012 (Optional)
Feb 14, 2018	OLTP Indexes (Part II) V. Leis, et al., The ART of Practical Synchronization, in DaMoN, 2016 V. Leis, et al., The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases, in ICDE, 2013 (Optional) Z. Wang, et al., Building A Bw-Tree Takes More Than Just Buzz Words, in SIGMOD, 2018 (Optional) (Downloadable only from CMU!)
Feb 19, 2018	Storage Models, Data Layout, & System Catalogs J. Arulraj, et al., Bridging the Archipelago Between Row-Stores and Column-Stores for Hybrid Workloads, in SIGMOD, 2016 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, in SIGMOD, 2008 (Optional)
Feb 21, 2018	Database Compression C. Binnig, et al., Dictionary-based Order-preserving String Compression for Main Memory Column Stores, in SIGMOD, 2009 V. Raman, et al., How to Wring a Table Dry: Entropy Compression of Relations and Querying of Compressed Relations, in VLDB, 2006 (Optional) D. Abadi, et al., Integrating Compression and Execution in Column-Oriented Database Systems, in SIGMOD, 2006 (Optional) H. Zhang, et al., Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes, in SIGMOD, 2016 (Optional)
Feb 26, 2018	Logging Protocols W. Zheng, et al., Fast Databases with Fast Durability and Recovery Through Multicore Parallelism, in OSDI, 2014 R. Johnson, et al., Aether: A Scalable Approach to Logging, in VLDB, 2010 (Optional) T.J. Lehman, et al., A Recovery Algorithm for a High-performance Memory-resident Database System, in SIGMOD, 1987 (Optional) N. Malviya, et al., Rethinking Main Memory OLTP Recovery, in ICDE, 2014 (Optional) J. Lee, et al., Differential Logging: A Commutative and Associative Logging Scheme for Highly Parallel Main Memory Database, in ICDE, 2001 (Optional)
Feb 28, 2018	Checkpointing Protocols T. Cao, et al., Fast Checkpoint Recovery Algorithms for Frequently Consistent Applications, in SIGMOD, 2011 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)
Mar 05, 2018	Networking 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) Assignment Released: Final Project		—
Mar 07, 2018	Mid-term Exam	—	—	—
Mar 12, 2018	Spring Break — No Class Assignment Due: Concurrent Index
Mar 14, 2018	Spring Break — No Class
Mar 19, 2018	Student Project Proposals	—	—	—
Mar 21, 2018	Optimizer Implementation (Part I) Yongwen Xu, Efficiency in the Columbia Database Query Optimizer (pages 1-35), in Portland State University, 1998 S. Chaudhuri, An Overview of Query Optimization in Relational Systems, in PODS, 1998 (Optional) G. Graefe, et al., The Volcano Optimizer Generator: Extensibility and Efficient Search, in ICDE, 1993 (Optional) G.M. Lohman, Grammar-like Functional Rules for Representing Query Optimization Alternatives, in SIGMOD, 1988 (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)		—
Mar 26, 2018	Optimizer Implementation (Part II) J. Chen, et al., The MemSQL Query Optimizer, in VLDB, 2017 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)		—
Mar 28, 2018	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)		—
Apr 02, 2018	Execution & 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) P. Boncz, et al., MonetDB/X100: Hyper-Pipelining Query Execution, in CIDR, 2005 (Optional)		—
Apr 04, 2018	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)		—
Apr 09, 2018	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 11, 2018	Student Project Meetings — No Class
Apr 16, 2018	Student Project Updates	—	—	—
Apr 18, 2018	Vectorized Execution (Part I) O. Polychroniou, et al., Rethinking SIMD Vectorization for In-Memory Databases, in SIGMOD, 2015 J. Sompolski, et al., Vectorization vs. Compilation in Query Execution, in DaMoN, 2011 (Optional) T. Thomas Willhalm, et al., SIMD-scan: Ultra Fast In-memory Table Scan using On-chip Vector Processing Units, in VLDB, 2009 (Optional)		—
Apr 23, 2018	Vectorized Execution (Part II) P. Menon, et al., Relaxed Operator Fusion for In-Memory Databases: Making Compilation, Vectorization, and Prefetching Work Together At Last, in VLDB, 2017 Y. Li, et al., BitWeaving: Fast Scans for Main Memory Data Processing, in SIGMOD, 2013 (Optional) Z. Feng, et al., ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout, in SIGMOD, 2015 (Optional) H. Lang, et al., Data Blocks: Hybrid OLTP and OLAP on Compressed Storage using both Vectorization and Compilation, in SIGMOD, 2016 (Optional)		—
Apr 25, 2018	Larger-than-Memory Databases J. DeBrabant, et al., Anti-Caching: A New Approach to Database Management System Architecture, in VLDB, 2013 F. Funke, et al., Compacting Transactional Data in Hybrid OLTP&OLAP Databases, in VLDB, 2012 (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 30, 2018	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) V. Leis, et al., Exploiting Hardware Transactional Memory in Main-Memory Databases, in ICDE, 2014 (Optional)		—
May 02, 2018	Guest Speaker: Ashish Motivala, Snowflake Computing		—

Trigger Warning: The material presented in this lecture uses explicit language and discusses certain situations in database management systems that may be triggering to some students.