Schedule | CMU 15-799 :: Special Topics in Databases: Query Optimization (Spring 2025)

Last Updated: Mar 12, 2025

Date	Topic	Slides	Notes	Video
Jan 13	Lecture #01 》Intro to Query Optimization Slides: Video: Readings: EQOP Book (Chapter 1) An Overview of Query Optimization in Relational Systems (S. Chaudhuri, PODS 1998) (Optional)		—
Jan 15	Lecture #02 》IBM System R Slides: Notes: Video: Readings: Access Path Selection in a Relational Database Management System (P.G. Selinger et al., SIGMOD 1979)
Jan 20	Martin Luther King Day — No Class
Jan 22	Lecture #03 》IBM Starburst Slides: Notes: Video: Readings: Extensible Query Processing in Starburst (L.M. Haas et al., SIGMOD Record 1989) EQOP Book (Chapter 3.1) (Optional) Grammar-like Functional Rules for Representing Query Optimization Alternatives (G. Lohman, SIGMOD Record 1988) (Optional) Extensible/Rule Based Query Rewrite Optimization in Starburst (H. Pirahesh et al., SIGMOD Record 1992) (Optional) Implementing an Interpreter for Functional Rules in a Query Optimizer (M.K Lee et al., VLDB 1988) (Optional) Query Optimization in the IBM DB2 Family (P. Gassner et al., IEEE Data Engineering Bulletin 1993) (Optional) Project: Project #1
Jan 27	Lecture #04 》Volcano Slides: Notes: Video: Readings: The Volcano Optimizer Generator: Extensibility and Efficient Search (G. Graefe et al., ICDE 1993) Volcano - An Extensible and Parallel Query Evaluation System (G. Graefe et al., ICDE 1994) (Optional) The EXODUS Optimizer Generator (G. Graefe et al., SIGMOD 1987) (Optional)
Jan 29	Lecture #05 》Cascades Slides: Notes: Video: Readings: EQOP Book (Chapter 2) The Cascades Framework for Query Optimization (G. Graefe, IEEE Data Engineering Bulletin 1995) (Optional)
Feb 03	Lecture #06 》Transformations Slides: Notes: Video: Readings: EQOP Book (Chapter 4.1-4.4, 4.6) Prairie: A Rule Specification Framework for Query Optimizers (D. Das, ICDE 1995) (Optional)
Feb 05	Lecture #07 》Join Ordering: Bottom-Up Slides: Notes: Video: Readings: Adaptive Optimization of Very Large Join Queries (T. Neumann et al., SIGMOD 2018) Dynamic Programming Strikes Back (G. Moerkotte et al., SIGMOD 2008) (Optional) DPconv: Super-Polynomially Faster Join Ordering (M. Stoian et al., SIGMOD 2025) (Optional)
Feb 10	Lecture #08 》Join Ordering: Top-Down Slides: Video: Readings: Optimal Top-Down Join Enumeration (D. DeHaan et al., SIGMOD 2007) Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs (P. Fender et al., VLDB 2013) (Optional) A New, Highly Efficient, and Easy To Implement Top-Down Join Enumeration Algorithm (P. Fender et al., VLDB 2011) (Optional) The Complexity of Transformation-Based Join Enumeration (A. Pellenkoft et al., VLDB 1997) (Optional)		—
Feb 12	Lecture #09 》Parallelization: Bottom-Up Slides: Video: Readings: Efficient Massively Parallel Join Optimization for Large Queries (R. Mancini et al., SIGMOD 2022) Parallelizing Query Optimization (W.S. Han et al., VLDB 2008) (Optional)		—
Feb 17	Lecture #10 》Parallelization: Top-Down Slides: Video: Readings: Parallelizing Extensible Query Optimizers (F.M. Waas et al., SIGMOD 2008) Project: Project #2		—
Feb 19	Lecture #11 》Unnesting Queries Slides: Video: Readings: Improving Unnesting of Complex Queries (T. Neumann, BTW 2025) Unnesting Arbitrary Queries (T. Neumann et al., BTW 2015) (Optional) EQOP Book (Chapter 4.5) (Optional)		—
Feb 24	Lecture #12 》Cost Models: Statistics Slides: Video: Readings: EQOP Book (Chapter 5.1-5.3) Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates (M. Freitg et al., CIDR 2019) (Optional) Effective Use of Block-Level Sampling in Statistics Estimation (S. Chaudhuri et al., SIGMOD 2004) (Optional)		—
Feb 26	Lecture #13 》Cost Models: Cardinality Estimation Slides: Video: Readings: Query Optimization Through the Looking Glass, and What We Found Running the Join Order Benchmark (V. Leis et al., VLDB Journal 2017) EQOP Book (Chapter 5.4-5.5) (Optional) How Good are Query Optimizers, Really? (V. Leis et al., VLDB 2015) (Optional)		—
Mar 03	Spring Break — No Class
Mar 05	Spring Break — No Class
Mar 10	Student Project Proposals
Mar 12	Lecture #14 》Cost Models: More Cardinality Estimation Slides: Readings: Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server (K. Lee et al., VLDB 2023)		—	—
Mar 17	Lecture #15 》Cost Models: Learned Approaches Readings: Learned Cardinality Estimation: An In-depth Study (K. Kim et al., SIGMOD 2022) Learned Cardinality Estimation: A Design Space Exploration and A Comparative Evaluation (J. Sun et al., VLDB 2022) (Optional) Are We Ready For Learned Cardinality Estimation? (X. Wang et al., VLDB 2021) (Optional) Rethinking Learned Cost Models: Why Start from Scratch? (J. Yang et al., SIGMOD 2023) (Optional) An End-to-End Learning-based Cost Estimator (J. Sun et al., VLDB 2019) (Optional)	—	—	—
Mar 19	Lecture #16 》Parametric Query Optimization Readings: Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees (A. Dutt et al., SIGMOD 2017) Progressive Parametric Query Optimization (P. Bizarro et al., TKDE 2009) (Optional) Design and Analysis of Parametric Query Optimization Algorithms (S. Ganguly, VLDB 1998) (Optional) Leveraging Query Logs and Machine Query Optimization Learning for Parametric Query Optimization (K. Vaidya et al., VLDB 2022) (Optional)	—	—	—
Mar 24	Lecture #17 》Adaptivity: Feedback Readings: Plan Stitch: Harnessing the Best of Many Plans (B. Ding et al., VLDB 2018) LEO - DB2's LEarning Optimizer (M. Stillger et al., VLDB 2001) (Optional)	—	—	—
Mar 26	Lecture #18 》Adaptivity: Runtime Processing Readings: Adaptive Query Processing in the Looking Glass (S. Babu et al., CIDR 2015) Looking Ahead Makes Query Plans Robust (J. Zhu et al., VLDB 2017) (Optional)	—	—	—
Mar 31	Lecture #19 》User-Defined Function Optimizations Readings: Froid: Optimization of Imperative Programs in a Relational Database (K. Ramachandra et al., VLDB 2017) The Key to Effective UDF Optimization: Before Inlining, First Perform Outlining (S. Arch et al., VLDB 2024) (Optional) Dear User-Defined Functions, Inlining isn’t working out so great for us. Let’s try batching to make our relationship work. Sincerely, SQL (K. Franz et al., CIDR 2024) (Optional) Aggify: Lifting the Curse of Cursor Loops using Custom Aggregates (S. Gupta et al., SIGMOD 2020) (Optional) Compiling PL/SQL Away (C. Duta et al., CIDR 2020) (Optional) Procedural Extensions of SQL: Understanding Their Usage in the Wild (S. Gupta et al., VLDB 2021) (Optional) Functional-Style SQL UDFs With a Capital ‘F’ (C. Duta et al., SIGMOD 2020) (Optional)	—	—	—
Apr 02	Lecture #20 》Implementation: Apache Calcite Readings: Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources (E. Begoli et al., SIGMOD 2018)	—	—	—
Apr 07	Student Project Status Updates
Apr 09	Lecture #21 》Implementation: Orca Readings: Orca: A Modular Query Optimizer Architecture for Big Data (M.A. Soliman et al., SIGMOD 2014) Testing the Accuracy of Query Optimizers (Z. Gu et al., DBTest 2012) (Optional)	—	—	—
Apr 14	Lecture #22 》Implementation: MemSQL / SingleStore Readings: The MemSQL Query Optimizer (J. Chen et al., VLDB 2017)	—	—	—
Apr 16	Lecture #23 》Implementation: MongoDB Readings: First Past the Post: Evaluating Query Optimization in MongoDB (D. Tao et al., ADC 2024) ROME: Robust Query Optimization via Parallel Multi-Plan Execution (Z. Wei et al., SIGMOD 2024) (Optional)	—	—	—
Apr 21	Lecture #24 》Implementation: Microsoft Fabric Readings: Unified Query Optimization in the Fabric Data Warehouse (N. Bruno et al., SIGMOD 2024) Towards Query Optimizer as a Service (QOaaS) in a Unified LakeHouse Ecosystem: Can One QO Rule Them All? (R. Alotaibi et al., CIDR 2025) (Optional)	—	—	—
Apr 23	Final Exam

Schedule Last Updated: Mar 12, 2025