Step 4: Execution Plan Selection

At this point in the query optimization process, the optimizer has examined the entire query and estimated the costs of all possible indexes to be used and of the various query-processing strategies. It now needs to choose which plan to pass on to SQL Server for execution.

For a single table query, choosing the best query plan involves choosing the index and query processing strategy that results in the fewest number of logical I/Os performed to process the query on that table.

For a multitable query, choosing the best plan involves not only determining the cheapest index and query processing strategy for each table individually, but also determining the best index strategy in conjunction with the optimal join strategy that results in the lowest estimated I/O time, as discussed in the previous section on join selection.

Additionally, if any ORDER BY , GROUP BY , or DISTINCT clauses are present, the optimizer chooses the most efficient method to process them.

For all its options, the overriding factor in selecting a plan is total I/O. The optimizer is committed to selecting a query plan that results in the least amount of I/O processing. After the plan is selected, it's passed to the SQL Server for execution.

NOTE

As you have seen in examples throughout this chapter, you can examine the query plan chosen by the optimizer with the graphical execution plan feature of Query Analyzer. You can also display a text representation of the execution plan by enabling the SHOWPLAN_TEXT option or the STATISTICS PROFILE option in a user session. How to interpret the output from these tools is covered in the next chapter, "Query Analysis," along with a discussion of other tools available for examining the query plan selection process.

You also have the capability to influence or override the query plan selection process using the methods discussed later in this chapter in the section, "Managing the Optimizer."

The optimizer can choose from many possible execution plans, especially when a large number of tables are involved in the query ”and an even greater number of permutations of join strategies and index usage is possible. The number of permutations grows exponentially as the number of tables involved in the query grows. To manage the number of permutations without spending all its time optimizing queries rather than running them, the query optimizer might go through multiple optimization passes before choosing the execution plan to run. Each pass considers a larger set of the possible plans. On each pass, it keeps track of the best plan thus far and uses a cost estimate to reduce the search in succeeding passes .

Initally, SQL Server tries to determine if only one viable plan for a query exists. For simple queries, this can save the optimizer a lot of work. An example of a trivial query plan is a single table SELECT statement with a SARG on a unique key. Another example is an INSERT statement using a VALUES clause ”there is only one way to insert this record. For both of these examples, the query plans are fairly obvious plans that are typically very inexpensive, so the optimizer generates the plan without trying to find something better. If the optimizer tried to consider every possible plan, the optimization cost could actually exceed the query processing time, outweighing any benefit provided by well-optimized queries.

If a trivial plan is not available, SQL Server will begin a more thorough optimization process. To avoid just running through all the possibilities that would cause the optimization process to take a long time, the optimization is broken up into phases. After each phase, SQL Server applies a set of rules to evaluate the cost of any resulting plan. If according to these rules, the plan is cheap enough, it chooses and submits that plan for execution. If according to the rules, no plan is still cheap enough, the optimizer continues on to the next phase, with its own set of rules to apply. In the vast majority of cases, SQL Server finds a good plan in the preliminary phases.

If the optimizer has gone through all the preliminary optimization phases and still hasn't found, according to the rules, what is considered to be a cheap plan, it determines the cost of the best plan it has thus far. If the cost of the best plan found is still above a particular threshold, and the system has more than one CPU available to SQL Server, the optimizer enters its full optimization phase that considers using parallel query processing strategies. You can configure this threshold using the cost threshold for parallelism configuration option. If the cost of the best plan found so far is still below the parallelism threshold, the full optimization phase continues using a brute-force method to find a serial plan, checking every possible combination of indexes and processing strategies.

Eventually, an execution plan is determined to be the most efficient. After this is determined, the execution plan is passed on to the SQL Server query processor to be executed.