News

Final Grades

Written on 17.08.23 by Immanuel Haffner

Dear all,

we have decided on your final course grades.  The course grade is determined to a large degree by your presentation. Your peer summaries and your participation in the Q&A were considered mostly when we had to decide between two grades. You can inspect your grade in your Personal… Read more

Dear all,

we have decided on your final course grades.  The course grade is determined to a large degree by your presentation. Your peer summaries and your participation in the Q&A were considered mostly when we had to decide between two grades. You can inspect your grade in your Personal Status page. Should you not find your grade on this page, please contact me immediately.

We provide you the opportunity to get feedback on your presentation. This feedback can clarify our decision for your grade and may provide useful suggestions for improvement that can aid you when preparing your next presentation. This service is optional. If you want to get feedback, please contact your assigned advisor to schedule a meeting. The meeting should take 5-10 minutes. IMPORTANT: To set expectations right, let me clearly say that this is NOT an opportunity for you to negotiate a better grade.

Thanks for this nice seminar. I hope you learned something and became even more passionate about database systems and query optimization than you were already ;)

Kind regards,

Immanuel

Final Talks Attendance is Mandatory

Written on 02.08.23 (last change on 02.08.23) by Immanuel Haffner

Dear all,

To rectify any misunderstandings: attendance at all final talks is mandatory to acquire the seminar certificate.

Best,

Immanuel 

Final Talks and Presentation Guideline

Written on 21.07.23 by Immanuel Haffner

Dear all,

we will have the final talks on Monday, August 7th, and Wednesday, August 9th. More precisely, we will have four blocks of talks in total, with one block before lunch break and one block after lunch break on each day.

Schedule

The exact times are as follows:

Dear all,

we will have the final talks on Monday, August 7th, and Wednesday, August 9th. More precisely, we will have four blocks of talks in total, with one block before lunch break and one block after lunch break on each day.

Schedule

The exact times are as follows:

  • Monday, August 7

    • Block Foundational: 11am - 1pm
    • Block Bottom-Up: 2pm - 4pm
  • Wednesday, August 9
    • Block Top-Down: 9:30am - 11:30am
    • Block Heuristic Algorithms: 12:30pm - 2pm

If you haven't scheduled a meeting with your advisor yet, please do so ASAP. The meeting with your advisor is mandatory. If you do not have this meeting with your advisor, we will lower your grade by one level.

 

Presentation Guideline

Your talk must be 23-25 minutes in length. The technical deep dive afterwards, where you discuss an important proof or go over some code, must take 7-10 minutes. Overall, your presentation will take 30-35 minutes. Afterwards, we will have 5 minutes for questions and discussion with the audience (Q&A). You may (and should) prepare backup slides of anything that you were not able to cover in your talk because of a lack of time but which might come up during the Q&A. Please include references to related work(s) and use the alphabetic style for references. They should look like this: [Sel+89; OL90; Van98; VM96; MN06] where Sel+89 is Selinger et al.'s work from 1989 and OL90 is Ono & Lohman's work from 1990. Have the bibliography appear after your final / concluding slide. Our seminar room 3.06 (where we held our peer group meetings) is very bright and we do not have shutters on the windows to the north. Slides with black / dark background don't work well in this room, please avoid them and prefer high contrast with black / dark text on white background. Also make sure to prepare slides for the beamer's 4:3 aspect ratio.

Please contact me immediately if something is unclear.

 

Looking forward to great talks!

Kind regards,

Immanuel

Find Timeslots for the Final Talks

Written on 11.07.23 by Immanuel Haffner

Dear all,

please fill in this poll to schedule the final talks. I plan to have 3 presentations of 25+10 minutes each in a 2h block. We will then distribute four 2h blocks over the week. Optimally, we would need two days with one block before and one block after lunch. Let's see how the poll… Read more

Dear all,

please fill in this poll to schedule the final talks. I plan to have 3 presentations of 25+10 minutes each in a 2h block. We will then distribute four 2h blocks over the week. Optimally, we would need two days with one block before and one block after lunch. Let's see how the poll goes.

Regards,

Immanuel

Supervisor Assignment & Meeting

Written on 11.07.23 by Immanuel Haffner

Dear all,

here is the assignment of students to supervisors:

  • Joris Nix: 5, 7, 8
  • Marcel Maltry: 1, 9, 10
  • Immanuel Haffner: 2, 3, 6, 11, 12

Please get in contact with your advisor soon to schedule a meeting. You can reach us by mail via the Team page.

The meeting with your advisor… Read more

Dear all,

here is the assignment of students to supervisors:

  • Joris Nix: 5, 7, 8
  • Marcel Maltry: 1, 9, 10
  • Immanuel Haffner: 2, 3, 6, 11, 12

Please get in contact with your advisor soon to schedule a meeting. You can reach us by mail via the Team page.

The meeting with your advisor should happen this month, so that you have time to incorporate your supervisor's feedback into your presentation. Make sure to come prepared! Prepare your slides, have a clear agenda for your presentation, and prepare your 10 minutes "deep dive" (e.g. code or proof).

I will send around a poll to schedule the final presentations shortly.

Regards,

Immanuel

Second Peer Group Meeting

Written on 26.06.23 by Immanuel Haffner

Dear all,

our second peer group meeting will be held on Thursday, June 29, at 3:15 pm in E1.1 room 3.06.

For the two students who are unable to attend: if you can't make it to the meeting, I expect you to get in contact with your peers on your own -- by video call, for example -- and catch… Read more

Dear all,

our second peer group meeting will be held on Thursday, June 29, at 3:15 pm in E1.1 room 3.06.

For the two students who are unable to attend: if you can't make it to the meeting, I expect you to get in contact with your peers on your own -- by video call, for example -- and catch up.

Sorry for sending you this information so late.

Regards,

Immanuel

Summaries Available in CMS

Written on 25.06.23 by Immanuel Haffner

Dear all,

your peer summaries are now available in the CMS in the Materials section. Make sure to read your peers' summaries carefully before our second peer group meeting.

I am sending you these lines from my flight back from SIGMOD in Seattle while watching the sunrise from the air plane. I… Read more

Dear all,

your peer summaries are now available in the CMS in the Materials section. Make sure to read your peers' summaries carefully before our second peer group meeting.

I am sending you these lines from my flight back from SIGMOD in Seattle while watching the sunrise from the air plane. I can say that the internet up here is much better than in any DB train :D

Kind regards,

Immanuel

Find a Timeslot for the Second Peer Group Meeting

Written on 05.06.23 (last change on 05.06.23) by Immanuel Haffner

Dear all,

we need to schedule the second peer group meeting. Please fill in this poll.

Best,

Immanuel

Peer Paper Summary Deadline POSTPONED

Written on 03.06.23 by Immanuel Haffner

Dear all,

I have postponed the submission deadline for your peer paper summaries to June 18th, 23:59. Please make sure to not miss this deadline! You can submit your paper summaries via CMS on your personal status page. Please file one separate submission per paper. (Do not submit a single document… Read more

Dear all,

I have postponed the submission deadline for your peer paper summaries to June 18th, 23:59. Please make sure to not miss this deadline! You can submit your paper summaries via CMS on your personal status page. Please file one separate submission per paper. (Do not submit a single document summarizing both peer papers.)

After the submission deadline, your paper summaries will be made accessible on the CMS within this course so your peers can access your summaries. Your summary should be 1-2 pages. If you can manage to summarize the paper in one page, that is perfectly fine. Please also add remarks where you feel the paper is lacking detail, experimental results are unexpected, claims are not properly supported by proofs or experiments, or anything else that you feel needs to be discussed. Also, if you have a hard time understanding a particular section of a paper, please write that down and let your peer know. There is no shame in not understanding (parts of) a paper -- its often the authors' fault ;) Your opinion will greatly aid your peers in preparing an excellent presentation and better manage where to invest more time.

Overall, I suggest that you put in the effort to writing those summaries that you expect from your peers ;)

Regarding Peer Group D: You must write a summary on your peer's paper as well as on your own paper. This means you will be writing two peer summaries, like everyone else.

All the best,

Immanuel

First Peer Group Meeting

Written on 28.05.23 by Immanuel Haffner

Dear all,

Our first peer group meeting will be held on Thursday, June 1st, at 3:15 pm. Make sure to come prepared: you must have read your assigned paper and are expected to give your peers a brief, roughly 5 minutes, overview of the paper. Afterwards, you will discuss how your papers are related,… Read more

Dear all,

Our first peer group meeting will be held on Thursday, June 1st, at 3:15 pm. Make sure to come prepared: you must have read your assigned paper and are expected to give your peers a brief, roughly 5 minutes, overview of the paper. Afterwards, you will discuss how your papers are related, how they overlap in content, and how you will be able to build upon each other's presentations.

We meet in seminar room 3.06 in E1.1 (as usual).

See you on Thursday.

Regards, Immanuel 

LSF Registration Deadline

Written on 24.05.23 by Immanuel Haffner

Dear all,

Please make sure to register for this seminar in LSF by June 2nd.

Regards, Immanuel 

Find Timeslot for the First Peer Group Meeting

Written on 24.05.23 by Immanuel Haffner

Dear all,

please fill in this poll so we can find a date for our first peer group meeting. You can find the peer groups on the Paper Assignment page.

For the first peer group meeting, you must have read your own paper and give a brief (~5 minutes) overview of the paper to your peers. After each… Read more

Dear all,

please fill in this poll so we can find a date for our first peer group meeting. You can find the peer groups on the Paper Assignment page.

For the first peer group meeting, you must have read your own paper and give a brief (~5 minutes) overview of the paper to your peers. After each peer group member introduced their paper, you spend ~15 minutes on identifying overlapping content and how your assigned papers are related. Think about how you will be able to build on each others presentations to avoid repeating material.

Looking forward to seeing you next week ;)

Regards, Immanuel

Paper Assignment Done

Written on 13.05.23 by Immanuel Haffner

Dear students,

the paper assignment is finished and can be found at Information → Paper Assignment. I can happily say that everyone was assigned their first or second preference; no third preference had to be assigned.

I only received 11 paper preferences. Currently, paper #4 by Cluet &… Read more

Dear students,

the paper assignment is finished and can be found at Information → Paper Assignment. I can happily say that everyone was assigned their first or second preference; no third preference had to be assigned.

I only received 11 paper preferences. Currently, paper #4 by Cluet & Moerkotte is not assigned.

Regards,

Immanuel

Paper Preferences Deadline TODAY

Written on 11.05.23 by Immanuel Haffner

Dear all,

please be aware that the deadline for the paper preferences submission is TODAY. To submit your preferences follow the instructions in the calendar entry. I will do my best to have your papers assigned to you by tomorrow afternoon.

(If you sent me a mail to my CMS mail address and the… Read more

Dear all,

please be aware that the deadline for the paper preferences submission is TODAY. To submit your preferences follow the instructions in the calendar entry. I will do my best to have your papers assigned to you by tomorrow afternoon.

(If you sent me a mail to my CMS mail address and the mail didn't bounce, you can assume that I received it.)

Best,

Immanuel

Kick-Off Meeting on May 4th, 3pm

Written on 26.04.23 by Immanuel Haffner

Dear students,

we will hold our kick-off meeting on Thursday, May 4th, at 3pm in E1.1, room 3.06.  Be aware that we will start at 3pm sharp (s.t.)!

See you around. Regards,

Immanuel

Schedule our Kick-Off Meeting

Written on 21.04.23 (last change on 21.04.23) by Immanuel Haffner

Dear students,

I am very pleased to welcome you to our seminar on query optimization.  We have to quickly find a date for our kick-off meeting. Please use the following link to our poll with available dates for a kick-off meeting. Please select all the dates you have time for.

Link to poll: Read more

Dear students,

I am very pleased to welcome you to our seminar on query optimization.  We have to quickly find a date for our kick-off meeting. Please use the following link to our poll with available dates for a kick-off meeting. Please select all the dates you have time for.

Link to poll: https://nuudel.digitalcourage.de/XDAyjjIGgL1eLx5t

Please fill in the poll as soon as you can.  This poll is for the kick-off meeting only.  For future meetings, we will do another poll.

Thanks & kind regards,

Immanuel

Show all

Query Optimization: Past to Present

Block Seminar

 

Overview

In the Database Systems core lecture we taught you about query optimization. In particular, you learned to compute optimal join orders under some cost model using dynamic programming.  In this seminar, we will take a much closer look at query optimization. We will learn that there are different optimization goals, and hence cost models, and that for some cost models the optimization problem is NP-hard. We will learn about an algebraic cost model Cout that is a generalization of cost models for which the optimization problem is actually NP-hard. We will discuss different algorithms to compute join orders, including various bottom-up and top-down dynamic programming algorithms. We will also be looking at specialized algorithms that take the topology of the query graph into account to compute optimal join orders for particular kinds of queries in polynomial time. Sometimes, computing an optimal solution is not possible within a given time budget or simply not required.  Therefore, we will also discuss algorithms for computing suboptimal join orders.  Finally, we take a look at a recent work that tackles join order optimization as a graph search problem.

Preliminaries

To succeed in this seminar, you must have passed our core lecture Database Systems. The knowledge that you acquired in this lecture enables you to comprehend and professionally present your assigned paper(s).

Schedule

  • Every student is assigned one to two papers to present at the end of the term1. The presentation is expected to take 20 minutes to present the contents of the paper plus around 10 minutes of an in-depth discussion of the algorithm presented in the paper2. The presentation makes 80% of your final seminar grade.
  • We form "peer groups" of 2-3 students.
  • Every student must write a summary of each of their peer's papers. Summaries must be 1-2 pages, DIN A4, 11pt; not less, not more. These summaries must be submitted during the lecture period. Summaries are graded and make 20% of your final seminar grade. Writing the summaries is mandatory to pass the seminar. The summaries are made accessible to all other students of the seminar and aid your peers in preparing their presentation.
  • Students must submit a draft of their slides 4 weeks prior to their presentation. The final version of the slides must be submitted 2 weeks before the presentation. Students must present a draft of their presentation to their supervisor prior to their talk.
  • We will have three mandatory meetings during the lecture period:
  1. the kick-off meeting, where we provide an overview of the papers,
  2. a meeting to get to know your peers and by which you must have read the paper assigned to you,
  3. a meeting after you have submitted your peer reviews, where you can interact with your peers to resolve open questions.

1 We only assign two papers to a student where the papers are closely related and overlapping in content. When you achieved an understanding of either paper, you understand the other as well. Two papers does not mean twice as much work! You will still give a single presentation of 20 minutes.

2 Most papers discussed in this seminar propose a new algorithm for join ordering. Almost all of them have been implemented in mutable.  You are expected to give an in-depth discussion of the algorithm along the implementation in mutable. For the few papers that do not propose an algorithm we expect an in-depth discussion of the theory presented in the paper, e.g. complexity analysis. 

 

Papers

Below follows the list of papers that we will discuss in this seminar. The list is ordered by publication date. This is not necessarily the order in which you will present the papers.

  • Selinger et al. - Access Path Selection in a Relational Database Management System (1979)
  • Ibaraki, Kameda - On the Optimal Nesting Order for Computing N-Relational Joins (1984) / Krishnamurthy, Boral, Zaniolo - Optimization of Nonrecursive Queries (1986)
  • Ono, Lohman - Measuring the Complexity of Join Enumeration in Query Optimization (1990)
  • Cluet, Moerkotte - On the Complexity of Generating Optimal Left-Deep Processing Trees with Cross Products (1995)
  • Vance, Maier - Rapid Bushy Join-order Optimization with Cartesian Products (1996)
  • Steinbrunn, Moerkotte, Kemper - Heuristic and Randomized Optimization for the Join Ordering Problem (1997)
  • Moerkotte, Neumann - Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products (2006)
  • DeHaan, Tompa - Optimal Top-Down Join Enumeration (2007)
  • Neumann - Query Simplification: Graceful Degradation for Join-Order Optimization (2009)
  • Fender, Moerkotte - A New, Highly Efficient, and Easy to Implement Top-Down Join Enumeration Algorithm (2011)
  • Neumann, Radke - Adaptive Optimization of Very Large Join Queries (2018)
  • Haffner, Dittrich - Efficiently Computing Join Orders with Heuristic Search (2023)
Optional Papers
  • Chaudhuri et al. - Optimizing Queries with Materialized Views (1995)
  • Fender, Moerkotte - Reassessing Top-Down Join Enumeration (2011)

All papers are available in our "Semesterapparat", that is provided by the Math & Informatics library. The papers can be accessed from within the University Intranet.

Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators.