Query Optimization Overview
In this class we'll start a week's focus on query optimization. There
are two readings:
To successfully complete this reading, be ready to write a good
response and be prepared for a good in class discussion, I suggest the
following strategy:
- Read the overview first. It will help give you an idea of what to
focus on when reading Selinger et al. (especially since it has a
section on Selinger et al.) For the overview:
- For those of you who don't know what a group-by query is, a
group-by query is a query where you divide tuples into groups and
apply aggregate operators to each group. For example, you might look
through a relation about sailors and their ages, and count the
number of sailors who were each age.
- A "block" in a query is approximately equal to one
select from where block. A "nested query" is one that
consists of more than one block.
- For a basic definition of semi-join, check out
the
Wikipedia
article.
It's worth noting that this term has also been co-opted by a slightly
different one in the case of distributed databases, which is the
definition given in some books. You don't really need to know what it
means, but now you have a reference if you're curious.
- Feel free to skip/skim section 4.3 (Using semijoin like
techniques for optimizing multi-block queries)
- We'll be discussing Starburst (Section 6.1) and Volcano (Section
6.2) next; so if it's not totally clear, it'll make more sense
soon. Conversely, this is a good way to get a preview of what's up next.
- For Selinger et al:
- Don't worry about the details of the cost formulas, just get the
main idea
- Don't worry about the details of the join algorithms; we'll study
those a bit more when we study query execution methods. The
important thing to know is that there are several ways of performing a
join, and that some of them leave tuples sorted, and others leave the
tuples unsorted.
[504 home] [grading] [schedule][project] [Connect]
Rachel Pottinger
E-mail Address: ![rap [at] cs [dot] ubc [dot] ca](/~rap/address.jpg)
Office Location: ICICS 345
Phone: (604)822-0436
Fax:(604)822-5485
Postal/Courier address:
The Department of Computer Science
University of British Columbia
201-2366 Main Mall
Vancouver, B.C. V6T 1Z4
Canada