CMU15721.md

CMU 15-721 course paperlink

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)

In-memory Database

• 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)

OLTP Index(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)

OLTP Index(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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

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)

Server-side Logic Execution

• K. Ramachandra, et al., Froid: Optimization of Imperative Programs in a Relational Database, in VLDB, 2017
• C. Duta, et al., Compiling PL/SQL Away, in CIDR, 2020 (Optional)

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)