Database Query Optimization
May 2010
Warsaw University of Technology

Semester: Summer 2010 (May 4 - May 21)
Course/Sect#: CSE 4411 (York)
Time: 4-7PM (May 4-7 and 17-20)
Location: Audytorium Centralne
Web page:
Instructor: Jarek Gryz
Office: 317
Office Hours: 3-4PM
and by appointment
Ph#: TBA
e-mail: [my first name]

Books / Reading

Required Textbook / Reading

Database Management Systems.
Third Edition, 2003.
Raghu Ramakrishnan and Johannes Gehrke
WCB/McGraw Hill.
ISBN: 0-07-232206-3

Additional slides

The Course

Course Objectives and Content

In this course, we go "under the hood" to learn how a relational database management system is built. Students will learn the issues involved in designing efficient database systems, and the strategies, data-structures, and algorithms used in the implementation of such systems.

The course is designed in three parts: the physical database, query processing and query optimization. Specific contents include the following.

I. The Physical Database
  • file organizations
  • indexes
    • tree-structured indexing
    • hash-based indexes
  • external sorting
II. Query Processing
  • evaluation of relational operators
    • selection
    • projection
    • joins (the many ways)
    • set operations
    • aggregate operations
  • physical database design and tuning
III. Query Optimization
  • rewrite optimization
    • semantic query optimization
    • magic sets
    • the COUNT bug
    • ...
  • cost optimization
    • cost model
    • selectivity estimation
    • ...
  • new paradigms in query optimization

Grading Criteria / Course Requirements

Final Exam 100% May 21