Specialized Course "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 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, 10:00 - 12:00, 024, Building E1.4
Exercises: Wednesday, 14:00 - 16:00, 024, Building E1.4

Slides:

Lecture 1: Introduction.[view]
Lecture 2: Textbook Query Optimization.[view]
Lecture 3: Textbook Query Optimization (ii). Join Ordering.[view]
Lecture 4: Join Ordering (ii).[view]
Lecture 5: Join Ordering (iii).[view]
Lecture 6: Join Ordering (iv).[view]
Lecture 7: Join Ordering (v).[view]
Lecture 8: Join Ordering (vi).[view]
Lecture 9: Join Ordering (vii).[view]
Lecture 10: Join Ordering (vii).[view]
Lecture 11: Join Ordering (viii).[view]
Lecture 12: Join Ordering (ix). Accessing the data.[view]
Lecture 13: Accessing the data (ii).[view]
Lecture 14: Accessing the data (iii).[view]
Lecture 15: Accessing the data (iv).[view]
Lecture 16: Accessing the data (v).[view]
Lecture 17: Accessing the data (vi).[view]
References [view]

Exercises:

Exercise 1, due 2009-04-28[view]
Exercise 2, due 2009-05-06[view]
Exercise 3, due 2009-05-13[view]
Exercise 4, due 2009-05-20[view]
Exercise 5, due 2009-05-27[view]
Exercise 6, due 2009-06-03[view]
Exercise 7, due 2009-06-10[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.

Tools:

The tinydb package can be used as a runtime system.
The TPC-D data set can be used as larger test set.

Exam:

Date: 2009-06-22/23/24 Duration: 20 min Room: 433 Building E1.4

	2009-06-22	2009-06-23	2009-06-24
10:00	Erdal Kuzey	Christina Teflioudi
10:25	Xiaoqi Cao	Yagiz Kargin
10:50	Baris Oztop	Kondreddi Sarath Kumar
11:15	Schuh Stefan	Maik Freis
11:40	Sergej Isak-Geidel	Timm Meiser
12:05	Erik Falk	Aleksandra Pochron
14:00	Ioannis Giannopoulos		Shaik Ajaz Basha
14:25	Sathess Thirunavukkarasu		Stefan Richter
14:50	Jörg Schad		Mohamed Yahya
15:15	Stefan Heinz		Oliver Dejon
15:40	Florian Groß		Thomas Gard
16:05	Dogan Karaoglan		David Philippi
16:30	Ilona Komor		Christian Fechner

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)