Chapter 6. Deducing the Best Execution Plan

For Tyme ylost may nought recovered be.

Geoffrey Chaucer Troilus and Criseyde

Just as reducing a word problem to abstract mathematics is usually the hardest part of solving the problem, you will usually find that producing the query diagram is harder than deducing the best execution plan from the query diagram. Now that you know the hard part, how to translate a query into a query diagram, I demonstrate the easy part. There are several questions you need to answer to fully describe the optimum execution plan for a query:

• How do you reach each table in the execution plan, with a full table scan or one or more indexes, and which indexes do you use, if any?

• How do you join the tables in the execution plan?

• In what order do you join the tables in the execution plan?

Out of these three questions, I make a case that the only hard question, and the main point of the query diagram, is the question of join order. If you begin by finding the optimum join order, which is nearly decoupled from the other questions, you will find that answers to the other two questions are usually obvious. In the worst cases, you might need to try experiments to answer the other two questions, but these will require at most one or two experiments per table. If you did not have a systematic way to answer the join-order question, you would require potentially billions of experiments to find the best plan.