Query Optimization
Content:
Query optimization is addressed shortly in Database Systems, this lecture looks at a broader topic of optimization techniques. It concentrates on the central issues like join ordering and access path selections, but gives an overview of the whole query processing machinery. The main goals of the lecture are twofold: First, to learn different optimization techniques, which are also relevant in other areas. And second, to get an understanding how queries are processed and why queries are fast or slow.
Slides:
- Chapter 1: Introduction
- Chapter 2: Textbook Query Optimization
- Chapter 3: Join Ordering
- Chapter 4: Accessing the Data
- Chapter 5: Physical Properties
Exercise session:
- Session 1: Introduction, Algebra, Textbook Optimization
- Session 2: Physical Optimization
- Session 3: Selectivity Estimation
- Session 4: Join Ordering Problem
- Session 5: GOO, IKKBZ
- Session 6: MVP, DP
- Session 7: DP, Simplification
- Session 8: Randomized Algorithms
- Session 10: Metaheuristics
- Session 11: Order-Preserving Joins, Combinatorics
- Session 12: Yao
- Session 13: Yao, Cheung, Bitvector, Histograms
- Session 14: Repetition
Assignments:
You can work on exercises in teams of two students. Specify names of both participants when submitting
- Exercise 1: Due Oktober 30
- Exercise 2: Due November 6
- Exercise 3: Due November 13
- Exercise 4: Due November 20
- Exercise 5: Due November 27
- Exercise 6: Due December 4
- Exercise 7: Due December 11
- Exercise 8: Due December 18
- Exercise 9: Due January 8
- Exercise 10: Due January 15
- Exercise 11: Due January 22
- Exercise 12: Due January 29
patched TinyDB
patched TinyDB with Parser
patch (apply by running 'patch -p 1 -i <path to patch file>' in the project root directory)
Literature:
- J.D. Ullman. Database and Knowledge Base Systems. Computer Science Press, 1989.
- T. Özsu and J. Blakeley. Modern Database Systems. Addison Wesley, 1995.
- H. Garcia-Molina and J.D. Ullman and J. Widom. Database System Implementation. Prentice Hall, 1999.
- P. Gassner, G. Lohman, and K. Schiefer. Query optimization in the IBM DB2 family. IEEE Data Engineering Bulletin, 16:4 18, Dec. 1993.
- S. Chaudhuri. An Overview of Query Optimization in Relational Systems. PODS, 1998
- G. Moerkotte. Building Query Compilers. (draft)