Schedule

Date	Topic	Slides	Video
Jan 17, 2017	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)
Jan 19, 2017	In-Memory Databases H. Garcia-Molina, et al., Main Memory Database Systems: An Overview, in IEEE Trans. on Knowl. and Data Eng., 1992 S. Harizopoulos, et al., OLTP Through the Looking Glass, and What We Found There, in SIGMOD, 2008 (Optional) Assignment Released: EXTRACT Function
Jan 24, 2017	Concurrency Control Challenges X. Yu, et al., Staring into the Abyss: An Evaluation of Concurrency Control with One Thousand Cores, in VLDB, 2014
Jan 26, 2017	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)
Jan 31, 2017	Multi-Version Concurrency Control (MVCC) Y. Wu, et al., The Paper Title is Private - Ask Andy, in VLDB, 2017 (Downloadable only from CMU!) 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) Assignment Due: EXTRACT Function Assignment Released: Concurrent Index
Feb 02, 2017	Index Locking & Latching G. Graefe, A Survey of B-Tree Locking Techniques, in TODS, 2010 S.K. Cha, et al., Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems, in VLDB, 2001 (Optional)
Feb 07, 2017	Latch-free OLTP Indexes (Part I) Ticki, Skip Lists: Done Right, in [BLOG], 2016 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)
Feb 09, 2017	Latch-free OLTP Indexes (Part II) J. Levandoski, et al., The Bw-Tree: A B-tree for New Hardware, in ICDE, 2013 V. Leis, et al., The ART of Practical Synchronization, in DaMoN, 2016 (Optional) T. Kissinger, et al., KISS-Tree: smart latch-free in-memory indexing on modern architectures, in DaMoN, 2012 (Optional)
Feb 14, 2017	OLAP Indexes P.-A. Larson, et al., SQL Server Column Store Indexes, in SIGMOD, 2011 C.Y. Chan, et al., Bitmap Index Design and Evaluation, in SIGMOD, 1998 (Optional) L. Sidirourgos, et al., Column Imprints: A Secondary Index Structure, in SIGMOD, 2013 (Optional) J. Rao, et al., Cache Conscious Indexing for Decision-Support in Main Memory, in VLDB, 1999 (Optional)
Feb 16, 2017	Storage Models & Data Layout 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, 2017	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 23, 2017	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, 2017	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 02, 2017	Optimizer Implementation (Part I) G. Graefe, et al., The Volcano Optimizer Generator: Extensibility and Efficient Search, in ICDE, 1993 G.M. Lohman, Grammar-like Functional Rules for Representing Query Optimization Alternatives, in SIGMOD, 1988 (Optional) R. Avnur, et al., Eddies: Continuously Adaptive Query Processing, in SIGMOD, 2000 (Optional) G. Moerkotte, et al., Dynamic Programming Strikes Back, in SIGMOD, 2008 (Optional)
Mar 07, 2017	Optimizer Implementation (Part II) M.A. Soliman, et al., Orca: A Modular Query Optimizer Architecture for Big Data, in SIGMOD, 2014 G. Graefe, The Cascades Framework for Query Optimization, in IEEE Data Engineering Bulletin, 1995 (Optional) R. Sen, et al., Query Optimization Time: The New Bottleneck in Real-time Analytics, in IMDM, 2015 (Optional) L.D. Shapiro, et al., Exploiting Upper and Lower Bounds In Top-Down Query Optimization, in IDEAS, 2001 (Optional) Assignment Released: Final Project
Mar 09, 2017	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) Assignment Due: Concurrent Index Assignment Released: Extra Credit
Mar 14, 2017	Spring Break — No Class	—	—
Mar 16, 2017	Spring Break — No Class	—	—
Mar 21, 2017	Student Project Proposals	—	—
Mar 23, 2017	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)
Mar 28, 2017	Parallel Join Algorithms (Hashing) S. Blanas, et al., Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs, in SIGMOD, 2011 C. Balkesen, et al., Main-Memory Hash Joins on Multi-Core CPUs: Tuning to the Underlying Hardware, in ICDE, 2013 (Optional)
Mar 30, 2017	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 04, 2017	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) C. Freedman, et al., Compilation in the Microsoft SQL Server Hekaton Engine, in IEEE Data Eng. Bull., 2011 (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)
Apr 06, 2017	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 11, 2017	Vectorized Execution (Part II) Y. Li, et al., BitWeaving: Fast Scans for Main Memory Data Processing, in SIGMOD, 2013 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 13, 2017	Student Project Meetings — No Class	—	—
Apr 18, 2017	Student Project Updates	—	—
Apr 20, 2017	Carnival — No Class	—	—
Apr 25, 2017	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 27, 2017	Non-Volatile Memory Database Systems J. Arulraj, et al., Let's Talk About Storage & Recovery Methods for Non-Volatile Memory Database Systems, in SIGMOD, 2015 J. Arulraj, et al., Write-Behind Logging, in VLDB, 2016 (Optional) H. Kimura, FOEDUS: OLTP Engine for a Thousand Cores and NVRAM, in SIGMOD, 2015 (Optional) I. Oukid, et al., SOFORT: A Hybrid SCM-DRAM Storage Engine for Fast Data Recovery, in DaMoN, 2014 (Optional)
May 02, 2017	Final Review Guest Speaker: Marcel Kornacker (Cloudera Impala)		—
May 04, 2017	Final Exam	—	—

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.