Specialized Course "Query Optimization"

Lecturer: Dr. Thomas Neumann

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 givens 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.

Prerequisites:

Students planning to attend the course should have some basic knowledge about information systems in general (successful participation in one of the courses Information Systems or Database Systems or Information Retrieval will be fine) and should be able to write simple programs in Java.

Organization:

• Lecture: Tuesday, 11:00 - 13:00, HS 024, Building E1.4
• Exercises: Wednesday, 14:00 - 16:00, HS 022, Building E1.4, Ralitsa Angelova
• Registration: Send a mail including your family name, first name and a matriculation number to Ralitsa Angelova

Slides:

• Lecture 1: Introduction. Textbook Query Optimization. [view]
• Lecture 2: Join ordering. [view]
• Lecture 3: Join Ordering (ii). Dynamic Programming. [view]
• Lecture 4: Join Ordering (iii). Transformative Approaches. [view]
• Lecture 5: Join Ordering (iv). Randomized Approaches. [view]
• Lecture 6: Join Ordering (v). Metaheuristics. Iterative Dynamic Programming. [view]
• Lecture 7: Accessing the Data. [view]
• Lecture 8: Accessing the Data (ii). Physical Storage. [view]
• Lecture 9: Accessing the Data (ii). Indices. [view]
• Lecture 10: Accessing the Data (iii). Indices. Counting Accesses. [view]
• Lecture 11: Accessing the Data (iv). Counting Accesses. [view]
• Lecture 12: Accessing the Data (iv). Counting Accesses. [view]
• Lecture 13: Physical Properties. [view]
• References. [view]

Exercises:

• Exercise 1, due 24.10.2006 [view]
• Dependent Join Example. [view]
• Exercise 2, due 31.10.2006 [view]
• Exercise 3, due 07.11.2006 [view]
• Exercise 4, due 14.11.2006 [view]
• Exercise 5, due 21.11.2006 [view]
• Exercise 6, due 28.11.2006 [view]
• Exercise 7, due 6.12.2006 [view]
• Exercise 8, due 13.12.2006 [view]
• Exercise 9, due 9.1.2007 [view]
• Exercise 10, due 16.1.2007 [view]
• Exercise 11, due 23.1.2007 [view]
• Exercise 12, due 30.1.2007 [view]
• Exercise 13, due 6.2.2007 [view]

Working on the exercises in a group is allowed. In this case submit one solution with all names on it. The groups can be of up to 3 people. The exercises have to be submitted in the beginning of each lecture or electronically per e-mail. However, all exercises have to be submitted with respect to the specified submission date. Late submissions will be discarded.

Exam:

Date: 2007-02-13/14 Duration: 20 min Room: 433 Building E1.4

Literature:

• J.D. Ullman. Database and Knowledge Base Systems. Computer Science Press, 1989.
• T. Özsu and J. Blakeley. Modern Database Systems. Addison Wesley, 1995.
• M. Jarke and J. Koch. Query optimization in database systems. ACM Computing Surveys, June 1984.
• P. Gassner, G. Lohman, and K. Schiefer. Query optimization in the IBM DB2 family. IEEE Data Engineering Bulletin, 16:4 18, Dec. 1993.

• Homepage MPI-INF
• About the Institute
• Departments:
  • Algorithms & Complexity
  • Computer Vision and Multimodal Computing
  • Computational Biology & Applied Algorithmics
  • Computer Graphics
  • Databases and Information Systems
    • People
    • Research
    • Offers
    • Teaching
    • News & Events
    • Publications
    • Software
    • Useful Links
  • Computational Genomics and Epidemiology
  • Ontologies
  • Automation of Logic
• News
• People
• Services
• Library
• Doctoral Research Program
• Max Planck Center