· OR logic in the WHERE clause In this pattern, the condition on each side of the OR operator in the WHERE or JOIN clause evaluates different tables. This can be resolved by use of a UNION operator instead of the OR operator in the WHERE or JOIN clause.
· Aggregations in intermediate results sets This pattern has joins on aggregated data sets, which can result in poor performance. This can be resolved by placing the aggregated intermediate result sets in temporary tables.
· A large number of very complex joins This pattern has a large number of joins, especially joins on ranges, which can result in poor performance because of progressively degrading estimates of cardinality. This can be resolved by breaking down the query and using temporary tables.
· A CASE clause in the WHERE or JOIN clause This pattern has CASE operators in the WHERE or JOIN clauses, which cause poor estimates of cardinality. This can be resolved by breaking down the cases into separate queries and using the Transact-SQL IF statement to direct the flow for the conditions.
· WHERE a.col1 = @val1 OR a.col1 = @val2 … This pattern is just another way of writing WHERE col1 IN (@val1, @val2 …). Testing this pattern did not produce poor query plans. However, note that each value in parentheses requires SQL Server to navigate from the top of an index B tree to the bottom, increasing the number of logical reads by the depth of the index multiplied by the number of values in parentheses.
The key to this pattern is that the same column is being evaluated by both sides of the OR operator. In the example, this column is col1. If an index exists with col1 as its first column, a seek operation on this index can satisfy each condition. If the index is small and does not cover the query, you might get a scan. The same guidelines apply to covering indexes with this pattern as apply to other queries.
· WHERE a.col1 = @val1 OR a.col2 = @val2 … In this query pattern, two columns in the same table are evaluated by the two sides of the OR operator. If two indexes exist on this table—one with col1 as its leading column and the other with col2 as its leading column—then SQL Server will run a scan if the tables are small. However, when the data set gets large enough, SQL Server will use an index union to retrieve the rows. (See Figure 1.) When SQL Server is able to use this index union, this query pattern is not a problem.
Figure 1: In this query plan, the pattern of WHERE a.col1 = @val1 OR a.col2 = @val2 is used on a large table. The query plan used involves an index union to retrieve the rows meeting either requirement. The Stream Aggregate operator eliminates any duplicates. The Key Lookup operator is required after elimination of duplicates to retrieve columns in rows where ManagerID = 10, but the columns are not included in the forTest index.
· WHERE a.col1 = @val1 OR a.col2 IN (SELECT col2 FROM tab2) By analyzing this pattern, you can see that SQL Server rewrote the IN clause and performed a join to tab2, as expected. Different indexes are used to retrieve the rows that fit either condition, and the results are sorted to eliminate duplicates at the end. (See Figure 2.) This is an efficient plan; applying the techniques discussed in this paper does not result in a better query plan.
Figure 2: This plan uses a variation of the pattern WHERE a.col1 = @val1 OR a.col2 IN (SELECT col2 FROM tab2). The retrieval from the dbo.Employee table (which would be ‘a’ in the pattern) is performed with two seeks. The smallest table is scanned because there is no filter in the IN clause. The plan produced is not problematic.
· WHERE a.col1 = @val1 OR b.col2 = @val2 The pattern represented by this query predicate is problematic. Breaking down the query into two steps produces a significantly “cheaper” plan. Note that in this pattern, there are two tables involved; on each side of the OR operator is a condition that applies to different tables. This problematic condition is detailed, from setup to execution, in Appendix A: Example of a Problematic Use of OR.
Following is the example query described in Appendix A, which causes a problematic query plan.
/*
The first script uses local variables to set up the range
and uses the OR logic in the WHERE clause
*/
DECLARE @minEmp INT
DECLARE @maxEmp INT
SET @minEmp = 100
SET @maxEmp = 200
SELECT e.* FROM dbo.Employee e
LEFT JOIN Adventureworks.Person.Contact c ON e.EmployeeId = c.ContactID
WHERE EmployeeId BETWEEN @minEmp and @maxEmp
OR c.EmailAddress IN ('sabria0@adventure-works.com', 'teresa0@adventure-works.com', 'shaun0@adventure-works.com')
Table 1. Indexes for Adventureworks.Person.Contact
An index exists on Adventureworks.Person.Contact (EmailAddress) that should be able to retrieve the three email addresses requested in the query. The primary key on dbo.Employee in the example tables is on EmployeeId, and the supporting index is clustered. SQL Server should be able to retrieve the results from the two tables with two inexpensive index seeks. However, executing the query results in an execution plan in which SQL Server scans the clustered index on both tables involved in the join. (See Figure 4.)
Figure 4: In this query pattern, SQL Server scans the clustered index on both tables involved in the join.
When STATISTCS IO and STATISTCS TIME are set to ON, as they are in the example in Appendix A, the query plan results in the following output.
The result is a total of 7,532 page reads and 94 milliseconds of CPU time. This may not be noticeable in a small system in which the plan is not executed frequently. However, as tables grow in size or as a query grows in complexity, this type of query can become a drain on the system because both the number of page reads and the CPU time will increase as the data size increases.
To reduce the cost, you can break down the query into separate queries that SQL Server can interpret more easily; you can rewrite the query, breaking the WHERE clause predicates into conditions that apply to the tables individually.
For a simple query such as that in the example, it is easy to see that the end result set is a union of results that meet the condition of a.EmployeeId between 100 and 200 and the rows that have the three email addresses you are searching for, as shown below.
Though functionally equivalent to the original query, SQL Server now handles this query differently. In this query plan, a UNION is used instead of an OR condition. By using the UNION, SQL Server is able to perform seeks on all indexes, reducing the overall query cost. (See Figure 5.)
Figure 5: In this query plan, a UNION is used instead of an OR condition. By using the UNION, SQL Server is able to perform seeks on all indexes, and the overall query cost has been reduced dramatically.
Although it required a little more typing, using the UNION in place of the OR reduced the number of page reads to 26 and the CPU time to less than one millisecond.
1. Copy the setup queries from Appendix C into a query window, and execute them.
2. Copy Query 1 and Query 2 from Appendix D into separate query windows pointing to the database you used when you ran the setup in Appendix C.
3. In each window from step 2, run SET STATISTICS IO ON and SET STATISTICS TIME ON.
4. Click Include Actual Execution Plan at the top of the page.
Figure 6: As joins are made between aggregated intermediate result sets, the "Estimated Number of Rows" diverges farther from the "Actual Number of Rows," as you can see in the tool tip that appears in the execution plan.
Figure 7: SQL Server underestimates the number of rows at this stage in the execution plan, leading to the decision to use a nested loop join strategy for the next left outer Join.
Figure 8: A wider view of the part of the query plan shows that the table scan (at the bottom) will be performed 334 times rather than the one time that the estimated number of rows would indicate. This type of underestimation with a nested loop join can cause the query cost to skyrocket.
Figure 9: This plan breaks down the query by using a temporary table, SQL Server is able to compute statistics on the intermediate result set.
Table 2. Improvement on the demo data by breaking the query into two queries and using a temp table
· A query with a large number of very complex joins With each subsequent join, the original data set becomes farther removed from the initial data set, and more factors are introduced into the estimation of cardinality. Data anomalies within a single table can cause a skewed cost estimate that is then multiplied across every subsequent join.
In queries with large numbers of joins, it might be better to break down the query into multiple queries, bringing intermediate result sets into temporary tables. You can then perform subsequent operations or joins on the intermediate sets in temporary tables.
· A CASE clause in the WHERE or JOIN clause This case refers specifically to a clause such as WHERE col1 = CASE @val1 WHEN 1 THEN ‘val1’ WHEN 2 THEN ‘val2’ WHEN 3 THEN col1. Such clauses create situations in which the number of rows is difficult, if not impossible, to estimate. Any time the number of rows can be badly misestimated, a poor query plan can result.
Instead of trying to include such logic in a query, use the Transact-SQL conditional statements IF and ELSE IF to break the conditions into multiple statements that can cover the different possible values for @val1. Breaking down the query in this way leads to a more accurate estimation of results.
1. Ensure that the Adventureworks demo database is installed on SQL Server.
2. Run the following script to set up the other tables that are needed.
· SET STATISTICS IO (Transact-SQL) http://msdn.microsoft.com/en-us/library/ms184361.aspx?lc=1033
· SET STATISTICS TIME (Transact-SQL) http://msdn.microsoft.com/en-us/library/ms190287.aspx
· Table and Index Organization http://msdn.microsoft.com/en-us/library/ms189051.aspx
· DBCC SHOW_STATISTICS (Transact-SQL) http://msdn.microsoft.com/en-us/library/ms174384.aspx
· Query Tuning Recommendations http://msdn.microsoft.com/en-us/library/ms188722.aspx
· Nested Loop Joins http://msdn.microsoft.com/en-us/library/ms191318(v=SQL.105).aspx
I've run modified examples of your queries using the employee table, and on my server the first/worst had a cost of 10. The union was 8. But wrapping the union up in sp_ExecuteSQL went down to 0.02! Can you explain why this is so much better when used this way?
Regards
Dave
Dave, can you give me the repro on it. I want to be sure I get your modifications so I'm looking at the same thing. I'll see if I can answer it back when I can do that.
Great article. I work with tables which contain data originally culled from a hierarchical model database. As a result, some of our joins involve several tables and gargantuan intermediate results. To make things worse, a lot of the select conditions are based not just on selecting records with certain values but also selecting records based on calculations and decisions derived from data in other records. I have often thought about trying to break some of these down into more simple queries and storing intermediate results in temp tables. What has always stopped me, however, was concerns that breaking them up would mean that the optimizer would have to deal with some of the hierarchies in more than one query and would lose any ability to reuse results or choose traversal techniques which are ideal to all the ways the data is used in the query. At this point, however, I've pretty much decided that it likely couldn't do a much worse job than it already is given that the queries have so many tables, clauses, decisions, UDFs, etc. that one would have a hard time even describing what the query does. Your article has inspired me to experiment with this approach and see if I can find some improvements. If nothing else, the code will become much more readable, but that won't likely draw much praise if performance degrades. If I start by trying to identify examples of the patterns you have described, however, that may give me a significant boost over simple seat-of-the-pants. experimentation.
Thanks again.
- Les
Hi Steve,
We recently noticed another case where the "optimizer" does not do it's job properly. It was a simple join between two tables with filter on each of these tables.
Here is the query:
SELECT DL.demand_seq_no, DL.coord_x, DL.coord_y, DW.orig_route_pos
FROM demloc DL FULL JOIN dem_workload DW
ON DL.demgrp_seqno = DW.demgrp_seqno AND
DL.merged_ver_seqno = DW.merged_ver_seqno AND
DL.sector_seqno = DW.sector_seqno AND
DL.demand_seq_no = DW.demand_seq_no
WHERE (DL.demgrp_seqno = 6099 OR DW.demgrp_seqno = 6099) AND
(DL.merged_ver_seqno = -2 OR DW.merged_ver_seqno = -2) AND
DW.workloadver_seqno IS NULL
It took 12 seconds to execute (return 0 rows) and involved two clustered index full scan.
I then rewrote this query like this:
SELECT d.demand_seq_no, d.coord_x, d.coord_y, dw.orig_route_pos
FROM (SELECT demand_seq_no, coord_x, coord_y, demgrp_seqno, merged_ver_seqno, sector_seqno
FROM demloc
WHERE demgrp_seqno = 6099 AND merged_ver_seqno = -2) d
FULL JOIN
(SELECT demgrp_seqno, merged_ver_seqno, sector_seqno, demand_seq_no, orig_route_pos
FROM dem_workload
WHERE demgrp_seqno = 6099 AND merged_ver_seqno = -2 AND workloadver_seqno IS NULL) dw
ON d.demgrp_seqno = dw.demgrp_seqno AND
d.merged_ver_seqno = dw.merged_ver_seqno AND
d.sector_seqno = dw.sector_seqno AND
d.demand_seq_no = dw.demand_seq_no;
It took less than a second to execute and used index seek on the proper indexes (with seek predicates).
I was really surprised that this simple query was not porperly treated by SQL Server but I realized a little bit later that it was also the case with Oracle! :(
Best regards.
Carl
Hi Howard,
I recently found a case were I had to rewrite the query beacause the "Optimizer" was not treating it the proper way.
Here is the initial query :
FROM demloc DL
FULL JOIN dem_workload DW
ON
DL.demgrp_seqno = DW.demgrp_seqno AND
WHERE
(DL.demgrp_seqno = 6099 OR DW.demgrp_seqno = 6099) AND
It took approx. 6 to 12 seconde to execute, return 0 rows and did two clustered index full scan! :(.
I than reworte the query like this:
And now it execute in less than a second, still return 0 rows and use the proper (expected) non clustered index (with seek predicates).
I was very surprised that a simple query like this was not treated properly but I later found that Oracle avec the same problem... :(
Best regards,
Very good article for SQL Server Perfomance!
Hey Carl,
Looks to me like the use of the OR is confusing the optimiser so it's not able to do a seek on the index. Once you change it to an AND operator then it works as expected, perhaps also your clustered index is made up of both the demgrp_seqno and merged_ver_seqno columns as well.
Without the benefit of data couldn't you re-write the query as per the below and get the same result? Syntax is a bit simplier.
DL.demand_seq_no = DW.demand_seq_no AND
DW.demgrp_seqno = 6099 AND
DW.merged_ver_seqno = -2
DL.demgrp_seqno = 6099 AND
DL.merged_ver_seqno = -2 AND
Hi Marty,
We won't have the same result since we do a full outer join and rows within DW (dem_workload) that match value 6099 for demgrp_seqno and -2 for merged_seqno won't be return unless these rows exists in table DL (demloc).
Rigth?