Query Optimisation

Working with our airline example database, and the following assumptions:

size of People = 100,000
size of Reservations = 1,000,000
size of Flights = 1,000
size of Airports = 100
20% of all flights happen on a Friday
5% of all flights go to Miami
50% of all Friday Miami flights cost less than $1000
NO indexes have been created

We will ask "who flew to Miami on a Friday, and paid less than $1000":

        SELECT p.name
        FROM airports a, flights f, reservations r, people p
        WHERE r.paid<1000
          AND r.day='F'
          AND a.name='Miami'
          AND a.code=f.dest
          AND f.number=r.flight
          AND r.passenger=p.id

The first three conditions are filters accepting only the records we are interestde in; the last three conditions are effectively the natural join conditions, telling us how to combine entries from individual tables.

First, we look at the Canonical Query Tree which represents the way a non-optimising database system might attack the question. I have been unable to find a good way to draw a tree in HTML, so I'll represent it as a sequence of steps instead:

Join airports with flights (where a.code=f.dest), call the resultant table T1.
Join T1 with reservations (where r.flight=f.number), call the resultant table T2.
Join T2 with people (where r.passenger=p.id), call the resultant table T3.
Filter T3 with (r.paid<1000) and (r.day='F') and (a.name='Miami'), call the resultant table T4.
Project T4 keeping only p.name, call the resultant table T5.
T5 is the answer.

Now we work out how long each step takes, and how much data they produce, remembering that we are not using any indexes.

Joining unindexed tables requires nested searches through them both; number of disc operations = size-of-one time size-of-other. time is 100,000 ops. Each flight record is only successfully joined with one airport record, so #T1 = #flights = 1,000.
Same as above, #T1=1,000, #reservations=1,000,000, so time is 1,000,000,000 ops. Each reservation matches only one flight, so #T2 = #reservations = 1,000,000.
Same as above, #T2=1,000,000, #people=100,000, so time is 100,000,000,000 ops. Each reservation only successfully matches one person, so #T3 = #T2 = 1,000,000.
Each of the 1,000,000 incoming records must be scanned, taking time 1,000,000 ops. only 50%×5%×20% = 0.5% will survive the filtering, so #T4 = 5,000.
Each of the 5,000 records must be individually processed to remove the unwanted information, taking a time of 5,000 ops and delivering a final answer with 5,000 records describing people who flew to Miami on a Friday for less than $1,000.

The total time is about 100,000,000,000 disc operations. Ignoring the (perfectly real) possibility of reading multiple records at the same time, and assuming 11mS per access, that comes to 1,100,000,000 seconds or 35 years.

We know that Select operations can move through the query tree, so long as they don't try to use information before it becomes available. Project operations can also be moved, but that does not usually produce much of an improvement. Moving Selects down the tree is usually good because Select operations discard some (usually most) incoming records, so the sizes of intermediate tables can be significantly reduced. Let's try it:

The condition (a.name='Miami') can be applied before step 1, giving us a new step 0.5: filter Airports with the condition (a.name='Miami'). Each airport entry gets scanned once, so the time is only 100 ops, and only one record survives the filtering. The resultant table (with just 1 record) is called A1.
Now step 1 becomes join A1 with flights, time is 1,000 ops, resultant table called T1 only has 50 entries because only 5% of flights are to Miami.
The conditions (r.paid<1000) and (r.day='F') can move all the way down the tree, and be applied as a step 1.5: filter reservations with those conditions, taking time = #reservations = 1,000,000 ops, but producing a table of size 50%×20%×#reservations = 100,000 entries. call this table R1
Now step 2 would involve joining T1 with R1, time is #T1×#R1 = 5,000,000 ops; the result T2 has 5,000 entries because only 5% of the reservations in R1 will match with a Miami flight.
Now step 3 still takes time #T2 × #people, but #T2 has been reduced to 5,000 entries and #people is still 100,000 entries, so the time for step 3 is 500,000,000 ops.

Step 3 was the most time-consuming step, so we'll stop the reanalysis here; by moving the selects, we have got things working 200 times faster, which is a huge improvement, but the query will still take 2 months.

The lesson is that indexes are really important. Optimisation does a lot of good, but without indexes the situation is often hopeless. If we had indexes on each of the natural join attributes of each of the tables, the time taken to perform a join would be proportional to the size of the result, not to the product of the sizes of the inputs, so step 3 would be down to (some small constant times) 5,000 ops. That is what would make everything possible.

Remember also that there is also the possibility of joining the tables in a different order. We could not sensibly have started by joining reservations with airports, becasue there is no direct connection between those two tables, but our first join could have been between people and reservations, and that could have made a big difference to the timing. For each viable ordering of the Joins, move all Selects as far down the tree as possible, work out the timings and pick the best.