Query Optimization

for RuBoard

When you submit a query to SQL Server, it begins by optimizing your query for execution. Using the statistics and indexes at its disposal, the SQL Server query optimizer develops an execution plan that it believes is the most efficient way to service your query. This optimization is cost-based, with plans that cost less in terms of estimated execution time winning out over those that cost more. The costing process leans heavily toward reducing I/O operations because they are the typical bottleneck when accessing large amounts of data.

As illustrated by Figure 17-1, query plan development consists of several phases or steps:

  1. Identify trivial plans.

  2. Simplify plan.

  3. Load statistics.

  4. Evaluate plans based on cost.

  5. Optimize for parallelism.

  6. Output plan.

Figure 17-1. The query optimization process.

graphics/17fig01.gif

Let's discuss each of these in more depth.

Trivial Plan Optimization

Because query plans can be expensive to evaluate, SQL Server includes a special optimization for creating plans for queries that really only have one possible plan anyway. A SELECT against a table with a single unique covering index is one example. An INSERT statement with a VALUES clause is another. SQL Server uses built-in heuristics to identify candidates for trivial plans. If a query plan can be trivialized without giving up performance, it saves the optimizer from having to evaluate all the possible plans for the query.

Simplification

If the trivial plan optimizer is unable to find a plan for the query, the optimizer simplifies the query through syntactic transformations by doing things like folding constants, converting HAVING to WHERE when possible, translating != @parm to < @parm OR >@parm, and so forth. These optimizations do not require examining cost, index, or statistics info , but they can result in a more efficient query plan being developed.

Statistics Loading

Once the plan has been simplified, the optimizer loads index and column statistics as well as other support info so that cost-based plan generation can begin. This means that it accesses sysindexes and other system tables and loads up the pertinent info for the tables involved in the query.

Cost-based Optimization

Cost-based optimization is divided into a series of phases that allow plans to be generated in pieces. Because of the number of options available to SQL Server for optimizing a plan, the optimizer tries simpler plan optimizations first in order to minimize the time spent formulating a plan. Each successive phase tries transformations of the query that are more costly that the previous one, but that hopefully yield a more efficient plan. This process is repeated until a plan that meets the optimizer's threshold for cost is reached.

The preliminary phases of cost-based optimization are the most basic. The optimizer is designed so that the vast majority of plans can be formulated during the preliminary cost-based optimization phases. This keeps the cost of generating plans relatively low and ensures that the more advanced phases of optimization are reserved for advanced queries.

Each time an execution plan is generated, SQL Server examines it to see whether the plan is sufficiently cheap to execute based on an internal threshold. If the plan is sufficiently cheap, the optimizer outputs it. If not, it keeps looking.

The preliminary phases usually find simple plans involving nested loops for tables with just one usable index. These simpler plans can resolve a good number of queries fairly well, so the optimizer is designed to generate them in a wide variety of circumstances.

Every optimization phase consists of applying a set of rules to transform the query into a resolvable series of steps. When the optimizer believes that the cost of executing these steps would be sufficiently cheap, it emits the plan to be executed.

Full Optimization

If, during the preliminary phases, the optimizer doesn't find a suitable plan, it puts the query through a full optimization phase. It's during this phase that a parallel plan can be developed. It bases the decision to do this on whether the cost threshold for parallelism has been reached. This threshold refers to the number of seconds required to execute the plan in a serial (nonparallel) fashion on a specific hardware configuration. If SQL Server is running on an SMP machine and the optimizer estimates that executing the serial version of a plan would exceed the cost threshold, it builds a parallel plan for the query. The optimizer assumes that the query is sufficiently long or complex to benefit from being run in parallel. It believes that the overall gains in performance from executing the plan in parallel will offset the expense of initializing, synchronizing, and terminating the parallel plan. Even though the plan may end up running serially because of other factors on the server, if conditions are right, the optimizer still targets a parallel plan. Sometimes a parallel plan is chosen even though the query's cost ends up being less than the cost threshold because the decision regarding whether to use a parallel plan is based on the optimizer's estimate of query time before the full optimization process has completed.

Selectivity Estimation

To correctly determine the relative cost of a query plan, the optimizer needs to be able to precisely estimate the number of rows returned by the query. As I mentioned earlier, this is known as selectivity, and it's crucial for the optimizer to be able to accurately estimate it.

Selectivity estimates come from comparing query criteria with the statistics for the index key or column they reference. Selectivity tells us to expect a single row for a given key value, or 10,000 rows for a different one. It gives us an idea of how many rows correspond to the key or column value for which we're searching. This, in turn , helps us determine the type of approach that would be the most efficient for accessing those rows. Obviously, you take a different approach to access one row than you would for 10,000.

If the optimizer discovers that you don't have index or column statistics for a column in the query's filter criteria, it may automatically create column-level statistics for the column if you have the AUTO_CREATE_STATISITCS database option enabled. You'll incur the cost of creating the statistics the first time around, but subsequent queries should be sped up by the new statistics.

Optimizing Search Arguments

A SARG, or search argument, is a clause in a query that the optimizer can potentially use in conjunction with an index to limit the results returned by the query. The optimizer attempts to identify SARGs in a query's criteria so that it can determine the best indexes to use to service the query. SARGs have the form

 Column op Constant/Variable 

(the terms can be reversed ) where Column is a table column; op is one of the following operators: =, >=, <=, >, <, <>, !=, !>, !<, BETWEEN, and LIKE (some LIKE clauses can be translated to SARGs; some can't); and Constant/Variable is a constant value, variable reference, or one of a handful of functions.

Even though some of these operators do not lend themselves to becoming SARGs, the optimizer can translate them into expressions that do. For example, consider the query in Listing 17-9:

Listing 17-9 The optimizer can translate != to something SARG-able.
 SELECT * FROM authors WHERE au_lname != 'Greene' 

Is the WHERE clause SARG-able? Yes. Look at the translation that occurs in this excerpt from the query plan:

 SEEK:([authors].[au_lname] < 'Greene' OR [authors].[au_lname] > 'Greene') 

The optimizer is smart enough to know that x != @parm is the same as x < @parm OR x > @parm, and translates it accordingly . Because the two branches of the OR clause can be executed in parallel and merged, this affords the use of an index to service the WHERE.

How about this one (Listing 17-10):

Listing 17-10 LIKE expressions can also be SARG-able.
 SELECT * FROM authors WHERE au_lname LIKE 'Gr%' 

Is it SARG-able? Yes. Once again, the optimizer translates the WHERE clause criteria to something it finds more palatable:

 SEEK:([authors].[au_lname] >= 'GQ_' AND [authors].[au_lname] < 'GS') 

Here's another (Listing 17-11):

Listing 17-11 The optimizer can translate !> to something more usable.
 SELECT * FROM authors WHERE au_lname !> 'Greene' 

Can the optimizer use an index to satisfy the query? Yes it can. Here's an excerpt from the plan:

 SEEK:([authors].[au_lname] <= 'Greene') 

Here's one more query (Listing 17-12):

Listing 17-12 The optimizer can use expressions involving !<.
 SELECT * FROM authors WHERE au_lname !< 'Greene' 

And here's its plan:

 SEEK:([authors].[au_lname] >= 'Greene') 

See the pattern? The optimizer attempts to translate seemingly un-SARG-able expressions into ones it can deal with more easily.

SARGs can be joined together with AND to form compound clauses. The rule of thumb for identifying SARGs is that a clause can be a useful search argument if the optimizer can detect that it's a comparison between an index key value and a constant or variable. A clause that compares two columns or one that compares two expressions is not a SARG clause. A common beginner's error is to involve a column in an expression when comparing it with a constant or variable. For the most part, this prevents the clause from being a SARG because the optimizer doesn't know what the expression actually evaluates toit's not known until runtime. The trick, then, is to isolate the column in these types of expressions so that it's not modified or encapsulated in any way. Use commonsense algebra to put the modifiers in the clause on the value/constant side of the expression and leave the column itself unmodified.

Join Order and Type Selection

In addition to choosing indexes and identifying SARGs, the optimizer also selects a join order and picks a join strategy. The selection of indexes and join strategy go hand-in-hand: Indexes influence the types of join strategies that are viable , and the join strategy influences the types of indexes the optimizer needs to produce an efficient plan.

SQL Server supports three types of joins:

  1. Nested loopWorks well with a smaller outer table and an index on the inner table.

  2. MergeWorks well when both inputs are sorted on the joining column (the optimizer can sort one of the inputs if necessary).

  3. HashPerforms well in situations in which there are no usable indexes. Usually, creating an index (so that a different join strategy can be chosen) will provide better performance.

The optimizer determines the join strategy to use to service a query. It evaluates the cost of each strategy and selects the one it thinks will cost the least. It reserves the right to reorder tables in the FROM clause if doing so will improve the performance of the query. You can always tell whether this has happened by inspecting the execution plan. The order of the tables in the execution plan is the order the optimizer thought would perform best.

You can override the optimizer's ability to determine join order using the OPTION (FORCE ORDER) clause for a query and using the SET FORCEPLAN ON session option. Each of these forces the optimizer to join tables in the order specified by the FROM clause.

Note that forcing join order may have the side effect of also forcing a particular join strategy. For example, consider the query in Listing 17-13:

Listing 17-13 Right outer joins often result in table reordering by the optimizer.
 SELECT o.OrderId, p.ProductId FROM [Order Details] o RIGHT JOIN Products p ON (o.ProductId=p.ProductId) 

Here's its execution plan (Listing 17-14):

Listing 17-14 The optimizer switches the order of the Order Details and Products tables.
 StmtText --------------------------------------------------------------------------- SELECT o.OrderId, p.ProductId FROM [Order Details] o RIGHT JOIN Products p ON (o.ProductId=p.ProductId)   --  Nested Loops  (Left Outer Join, OUTER REFERENCES:(p.ProductID))        --Index Scan(OBJECT:(Northwind.dbo.Products.SuppliersProducts AS p))        --Index Seek(OBJECT:(Northwind.dbo.[Order Details].ProductID AS o),           SEEK:(o.ProductID=p.ProductID) ORDERED FORWARD) 

Notice that it uses a nested loop join and that it reorders the tables (Products is listed first in the plan, even though Order Details is listed first in the FROM clause). Now let's force the join order using the FORCE ORDER query hint (Listing 17-15):

Listing 17-15 You can force the join order using the FORCE ORDER hint.
 SELECT o.OrderId, p.ProductId FROM [Order Details] o RIGHT JOIN Products p ON (o.ProductId=p.ProductId) OPTION(FORCE ORDER) 

Look what happens to the query plan (Listing 17-16):

Listing 17-16 Forcing the join order sometimes changes the join strategy.
 StmtText --------------------------------------------------------------------------- SELECT o.OrderId, p.ProductId FROM [Order Details] o RIGHT JOIN Products p ON (o.ProductId=p.ProductId) OPTION(FORCE ORDER)   --  Merge   Join  (Right Outer Join, MANY-TO-MANY MERGE:(o.ProductID)=     (p.ProductID), RESIDUAL:(o.ProductID=p.ProductID))        --Index Scan(OBJECT:(Northwind.dbo.[Order Details].           ProductsOrder_Details AS o), ORDERED FORWARD)        --Clustered Index Scan(OBJECT:(Northwind.dbo.Products.           PK_Products AS p), ORDERED FORWARD) 

Because it can't reorder the tables, the optimizer switches to a merge join strategy. This is less efficient than letting the optimizer order the tables as it sees fit and join the tables using a nested loop.

Nested Loop Joins

Nested loop joins consist of a loop within a loop. A nested loop join designates one table in the join as the outer loop and the other as the inner loop. For each iteration of the outer loop, the entire inner loop is traversed. This works fine for small to medium- sized tables, but as the loops grow larger, this strategy becomes increasingly inefficient. The general process is as follows :

  1. Find a row in the first table.

  2. Use values from that row to find a row in the second table.

  3. Repeat the process until there are no more rows in the first table that match the search criteria.

The optimizer evaluates at least four join combinations even if those combinations are not specified in the join predicate. It balances the cost of evaluating additional combinations with the need to keep down the overall cost of the producing the query plan.

Nested loop joins perform much better than merge joins and hash joins when working with small to medium-sized amounts of data. The query optimizer uses nested loop joins if the outer input is quite small and the inner input is indexed and quite large. It orders the tables so that the smaller input is the outer table and requires a useful index on the inner table. The optimizer always uses the nested loop strategy with theta (nonequality) joins.

Merge Joins

Merge joins perform much more efficiently with large data sets than nested loop joins. Both tables must be sorted on the merge column in order for the join to work. The optimizer usually chooses a merge join when working with large data sets that are already sorted on the join columns. The optimizer can use index trees to provide the sorted inputs and can also leverage the sort operations of GROUP BY, CUBE, and ORDER BYthe sorting only needs to occur once. If an input is not already sorted, the optimizer may opt to first sort it so that a merge join can be performed if it thinks a merge join is more efficient than a nested loop join. This happens very rarely and is denoted by the SORT operator in the query plan.

A merge join entails the following five steps:

  1. Get the first input values from each table.

  2. Compare them.

  3. If the values are equal, return the rows.

  4. If the values are not equal, toss the lower value and use the next input value from that table for the next comparison.

  5. Repeat the process until all the rows from one of the tables have been processed .

The optimizer only makes one pass per table. The operation terminates after all the input values from one of the tables have been evaluated. Any values remaining in the other table are not processed.

The optimizer can perform a merge join operation for every type of relational join operation except CROSS JOIN and FULL JOIN. Merge operations can also be used to UNION tables together (because they must be sorted to eliminate duplicates).

Hash Joins

Hash joins are also more efficient with large data sets than nested loop joins. Additionally, they work well with tables that are not sorted on the join columns. The optimizer typically opts for a hash join when dealing with large inputs, and no index exists to join them or an index exists but is unusable.

SQL Server performs hash joins by hashing the rows from the smaller of the two tables (designated the "build" table) and inserting them into a hash table, then processing the larger table (the "probe" table) a row at a time and scanning the hash table for matches. Because the smaller of the two tables supplies the values in the hash table, the table size is kept to a minimum, and because hashed values rather than real values are used, comparisons can be made between the tables very quickly.

Hash joins are a variation on the concept of hashed indexes that have been available in a handful of advanced DBMS products for several years . With hashed indexes, the hash table is stored permanentlyit is the index. Data is hashed into slots that have the same hashing value. If the index has a unique contiguous key, what is known as a minimal perfect hashing function exists: Every value hashes to its own slot and there are no gaps between slots in the index. If the index is unique but noncontiguous, the next best thinga perfect hashing function can exist in which every value hashes to its own slot, but there are potentially gaps between them.

If the build and probe inputs are chosen incorrectly (for example, because of inaccurate density estimates), the optimizer reverses them dynamically using a process called role reversal.

Hash join operations can service every type of relational join (including UNION and DIFFERENCE operations) except CROSS JOINs. Hashing can also be used to group data and remove duplicates (for example, with vector aggregatesSUM(Quantity) GROUP BY ProductId). When it uses hashing in this fashion, the optimizer uses the same table for both the build and probe roles.

When join inputs are large and of a similar size, a hash join performs comparably with a merge join. When join inputs are large, but differ significantly in size, a hash join will usually outperform a merge join by a fair margin.

Subqueries and Join Alternatives

A subquery is a query nested within a larger one. Typically, a subquery supplies values for predicate operators such as IN, ANY, and EXISTS, or a single value for a derived column or variable assignment. Subqueries can be used in lots of places, including a query's WHERE and HAVING clauses.

Understand that joins are not inherently better than subqueries. Often the optimizer will normalize a subquery into a join, but this doesn't mean that the subquery was an inefficient coding choice.

When attempting to rework a query to avoid the performance overhead of joins, remember that you can use table variables and temporary tables to store work data for further processing. For extremely complex queries, this may be the best alternative because it affords you complete control over the optimization process. You can break the query into several steps and can control what executes when.

For simple to moderately complex queries, derived tables provide a similar benefit in that they allow you to serialize the order of query processing to some extent. Derived tables work like parentheses in expression evaluation (and are, in fact, delimited with parentheses)they establish an order of events. When you demote part of a complex SELECT to a derived table, against which you then apply the remainder of the SELECT, you're in effect saying, Do this first, then hand its results to the outer SELECT. This ability alonethe capability to serialize the processing of the querygives you some of the power of a stored procedure in terms of query evaluation without the complexities or code maintenance.

Logical and Physical Operators

Physical operators describe what SQL Server is doing to execute the query. Logical operators describe the relational operation used to process the statement. They correspond to the operations in your code that caused particular physical operators to be used. Oftentimes a logical operator maps to multiple physical operators. Because execution plans consist of physical operations, this means that all execution plan steps will have physical operators, but not all will have logical ones.

Each step in an execution plan corresponds to a physical operator: Execution plans consist of a series of physical operators. Query Analyzer's graphical execution plan displays these operations in the title area of its yellow pop-up hint windows . If a step has a logical operator in addition to the physical operator, it will also be displayed in the title area of the window to the right of the physical operator, separated by a slash. For the textual show plan, the PhysicalOp column stores the physical operator, whereas the LogicalOp column stores the logical operator for a step.

This is best understood by way of example. Consider the query in Listing 17-17:

Listing 17-17 This query requests a relational inner join.
 SELECT * FROM Orders o JOIN [Order Details] d ON (o.OrderID = d.OrderID) 

The optimizer chooses a merge join for it, although the query itself obviously doesn't ask for one. Relationally, the query is performing an inner join between the two tables. Here's an excerpt from its textual show plan (Listing 17-18):

Listing 17-18 The logical operation is INNER JOIN; the physical one is MERGE JOIN.
 PhysicalOp           LogicalOp            Argument -------------------- -------------------- ------------------------------ Merge Join           Inner Join           MERGE:([o].[OrderID])=([d].[Or Clustered Index Scan Clustered Index Scan OBJECT:([Northwind].[dbo].[Ord Clustered Index Scan Clustered Index Scan OBJECT:([Northwind].[dbo].[Ord 

Notice that the PhysicalOp column lists MERGE JOIN as the operator. This is what happens behind the scenes to service the operation spelled out in the LogicalOp column: INNER JOIN. An inner join is what we requested via our query. The server chose a MERGE JOIN as the physical operator to carry out our request.

Besides deciding which index to use and which join strategy to apply, the optimizer has additional decisions to make regarding other types of operations. A few of them are presented in the following pages:

DISTINCT

When the optimizer encounters DISTINCT or UNION in a query, it must remove duplicates from the inputs before returning a result set. It has a couple of options here. It can sort the data to remove duplicates, or it can hash it. The optimizer may service the DISTINCT or UNION logical operation using a hash or sort physical operator. (Stream Aggregatethe same physical operator often used for GROUP BY queriesis also a popular choice here.)

GROUP BY

The optimizer can service GROUP BY queries using plain sorts or by hashing. Again, the physical operator may be HASH or SORT, but the logical operator remains AGGREGATE OR something similar. Also, STREAM AGGREGATE is a popular choice for GROUP BY operations.

Because the optimizer may choose to perform a HASH operation to group the data, the result set may not come back in sorted order. You can't rely on GROUP BY to sort data automatically. If you want the result set sorted, include an ORDER BY clause.

ORDER BY

Even with ORDER BY, the optimizer has a decision to make. Assuming no clustered index exists that has already sorted the data, the optimizer has to come up with a way to return the result set in the requested order. It can sort the data, as we'd naturally expect, or it can traverse the leaf level of an appropriately keyed nonclustered index. Whether it does this depends on a number of factors. The biggest one is selectivity: How many rows will be returned by the query? Equally relevant is index covering: Can the nonclustered index cover the query? If the number of rows is relatively low, it may be cheaper to use the nonclustered index than to sort the entire table. Likewise, if the index can cover the query, you've got the next best thing to having a second clustered index, and the optimizer will likely use it.

Spooling

The Spooling operator in a query plan indicates that the optimizer is saving the results from an intermediate query in a table for further processing. With a lazy spool, the worktable is populated as needed. With an eager spool, the table is populated in one step. The optimizer favors lazy spools over eager spools because of the possibility that it may be able to avoid having to fill the worktable completely based on logic deeper in the query plan. There are cases when eager spools are necessaryfor example, to protect against the Halloween problembut, generally , the optimizer prefers lazy spools because of their reduced overhead.

Table 17-3. The Optimizer's Physical Operators
PhysicalOp Meaning
ASSERT Indicates a subquery is being used in a situation in which it is only allowed to return one row (use SELECT TOP 1 in the subquery to eliminate the Assert).
BOOKMARK Indicates that the RID or clustered index key stored in a LOOKUP nonclustered index is being used to look up data in the underlying table or clustered index.
CONSTANT SCAN Indicates that the optimizer knows in advance that a condition will never be true.
CURSOR Indicates operations with server-side cursors .
OPERATIONS FILTER Indicates that data is being reduced (probably using WHERE clause criteria) before being passed on.
JOINS A nested loop, merge, or hash join is occurring.
SCAN Indicates a sequential search of the leaf-level nodes of an index.
SEEK Indicates a binary (nonsequential) search of an index B-tree.
SORT Indicates data is being sorted before being passed to the next step.
SPOOL Indicates that the optimizer is saving the results from an intermediate query plan step in a worktable for further processing.
STREAM AGGREGATE Indicates vector aggregation or grouping is occurring.

Spool operations can be performed on tables as well as indexes. The optimizer uses a rowcount spool when all it needs to know is whether a row exists.

Table 17-3 lists the physical operators the SQL Server optimizer uses and their meanings.

for RuBoard


The Guru[ap]s Guide to SQL Server[tm] Stored Procedures, XML, and HTML
The Guru[ap]s Guide to SQL Server[tm] Stored Procedures, XML, and HTML
ISBN: 201700468
EAN: N/A
Year: 2005
Pages: 223

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net