March 24, 2009 at 11:29 am
Hello,
I'm trying to improve the performance of an existing stored procedure. The stored procedure selects from a few tables using inner joins. There is one mandatory parameter (Surname) and three optional (GivenName, PhoneNumber, Address). All tables have over 100,000 records. I've been running a number of tests and am confused on a couple of results.
I started with a very simple query:
SELECT
M.Surname,
M.GivenName
FROM
Member AS M
WHERE
M.Surname LIKE 'sm%'
There is a clustered index on the key (not shown). There is also a non-clustered index on the Surname column and one on the GivenName column. When I view the actual execution plan, it shows a hash match (inner join) with a cost of 57%, and index seek on Surname with a cost of 1% and an index scan on GivenName with a cost of 42%. The total execution time is ~124ms.
I'm confused why an index scan is used on GivenName since it's only included in the output. Now take a look a the next query:
SELECT
M.Surname,
M.GivenName,
M.MiddleName
FROM
Member AS M
WHERE
M.Surname LIKE 'sm%'
The only thing I changed was adding the MiddleName column to the output (which doesn't have an index). I viewed the execution plan and found it was changed to a bookmark lookup with a cost of 100% and then an index seek on Surname with a cost of 0%. The execution time went down from ~124ms to ~46ms.
I find this very confusing. I've always tried to follow the best practises, in this case, only include the columns you need in the output and add indexes to columns that are used often in a where clause (the GivenName isn't used in the example above, but is an optional parameter in my final stored procedure). In this case, adding an extra column to the output that does not have an index actually improves the performance of the query (removing the index on the GivenName does the same, but this is not an option).
Can someone please help me understand why this execution plan was chosen for the first query? Is there anything else I can do to optimize this?
Note: I realize we're talking about milliseconds in this example, but I'm just trying to get a handle on how indexes are used.
March 24, 2009 at 1:35 pm
This is one of those things where it really depends.
In general, the SQL optimizer does what it thinks will work the best based on the data that it has available to it. Obviously in your first query, the optimizer felt that it would be best to hash join the two indexes together and join them based on the clustering key (which is present in both non-clustered indexes implicitly). In the second, it did not see that need and it obviously ended up doing a bookmark lookup to get the middle name and givenname columns.
The first thing that comes to my mind is that your statistics are not up to date. I would try updating the indexes on the Member table with a fullscan, that way you can guarantee that everything is as up to date as humanly possible. This seems the most likely culprit in my eyes, since both cases will certainly have to do a lookup of some sort. Try updating the statistics on that table and post the results.
Update statistics member with fullscan
March 24, 2009 at 2:27 pm
Thanks for your response Mike.
Try updating the statistics on that table and post the results.
Update statistics member with fullscan
I tried this and ran it again. The execution plan remains unchanged. There is no noticeable difference in execution time.
...the optimizer felt that it would be best to hash join the two indexes together and join them based on the clustering key (which is present in both non-clustered indexes implicitly).
To test this, I removed the clustered index. I tried again, but there was no difference; the hash join with an index seek and an index scan are still used.
Let me expand a little bit more on my original post. The hash match and two indexes are used on this table if a) all of the output columns have indexes, and b) not all of the output columns are included in the where clause. For example, if I add an index for the MiddleName and replace the GivenName column with it in the first query, I will get the same results. If I add a column to the output that does not have an index, the bookmark lookup and single index seek will be used (second query). If I remove the index from the GivenName column and run the first query again, it will use a bookmark lookup and index seek. If I include the GivenName column in the where clause, it will use a hash match and two index seeks (where there is an index on GivenName).
The only one I can't seem to figure out is the first one where it uses the hash match and two indexes (seek and scan).
March 24, 2009 at 2:43 pm
I have another example that demonstrates this issue. Take the following query:
SELECT
M.Surname,
M.GivenName,
A.StreetName
FROM
Member AS M
INNER JOIN MemberAddress AS A ON M.MemberID = A.MemberID
WHERE
M.Surname LIKE 'sm%'
There is an index on the MemberID column in both the Member and MemberAddress tables, as well as an index on the MemberAddress StreetName column.
Now, not only is there a hash match, index seek and index scan for the Member table, but there is also a hash match for the join with an index scan used on the MemberAddress MemberID index.
If I add a non-indexed column from the MemberAddress table in the output list (or remove the index from the StreetName column), it will change the hash match to a nested loop and the index scan to a clustered index seek, and the total execution time is improved.
This is the same scenario as my first example. I just don't understand why it's doing the hash match and index scan in these examples.
March 24, 2009 at 2:53 pm
You may want to check on the IO's for these queries to get a better feel for the sorts of reads SQL is doing under the covers (set statistics io on).
It is possible that somehow doing the hash joins is lowering the reads for these tables, though it certainly seems unlikely. In all cases, something is not quite being used right.
Obviously depending on the space you have available to you, what all other indexes exist on these tables, etc...your best option is to have an index on the Member table that has all three Surname, GivenName and MiddleName (in taht order) and maybe even include the MemberID (if that is not the clustering key) for queries that join on that as well. Obviously a covering index in this case should be optimal for pretty much every single query you have added here though I understand that if you already have 20 indexes on the table and inserts/updates are starting to take longer already that this may not be the best idea.
It is still baffling that the optimizer somehow sees joining to the second index as the best solution here, but there must be some underlying reason for it and hopefully the statistics io will help show you that. But if you can add a covering index, I would bet money that will be you best solution regardless.
March 24, 2009 at 3:03 pm
One thing I also just realized is that you are doing all of this to try to improve performance of a stored procedure. Could you include the whole stored procedure text to go along with this?
The reason I ask for this is because there is a chance that you are a victim of procedure caching, such that this is using an older plan that is no longer valid. If the procedure does some dynamic sql or has a bunch of case statements that use similar but different queries it is possible that you will want to force a recompile of this procedure so that with each execution it figures out the optimal plan, or possible within the procedure split it out to call separate procedures that will use the correct plan each time around.
I would still recommend creating a covering index and one that includes as many of these columns as possible so that it can be useful in many circumstances, but it is possible that this is just a caching issue.
Run the following to clean some of that out.
dbcc freeproccache
dbcc dropcleanbuffers
I do not recommend running this on your production environment since it will clear out things you do not want it to, but if you have a test environment definitely try this out so you can see if this is a caching problem.
March 25, 2009 at 9:40 am
Mike, thanks for all of your help. You'll see below that we're on the right track!
You may want to check on the IO's for these queries to get a better feel for the sorts of reads SQL is doing under the covers (set statistics io on).
I set statistics io on, executed DBCC DROPCLEANBUFFERS and ran the first query. Here are the results: Table 'Member'. Scan count 2, logical reads 570, physical reads 10, read-ahead reads 509.
I ran it again without executing DBCC DROPCLEANBUFFERS. Here are the results: Table 'Member'. Scan count 2, logical reads 570, physical reads 0, read-ahead reads 0.
I did the same for the second query (the one that uses the bookmark lookup and index seek). Here are the results after executing DBCC DROPCLEANBUFFERS: Table 'Member'. Scan count 1, logical reads 3091, physical reads 59, read-ahead reads 75.
Here are the results after running it a second time without executing DBCC DROPCLEANBUFFERS: Table 'Member'. Scan count 1, logical reads 2286, physical reads 0, read-ahead reads 0.
When executing the queries after running DBCC DROPCLEANBUFFERS, the first query is now faster than the second query. The first query executes in ~209ms, the second executes in ~640ms. I guess this explains why it chose the execution plan that it did; there are less reads, which has a big impact when the page cache is clear (please correct me if I'm wrong).
I've been dropping and adding indexes, so I figured the fragmentation shouldn't be too bad. I ran DBCC SHOWCONTIG on all indexes on the Member table just to make sure. As expected, it was very good.
But if you can add a covering index, I would bet money that will be you best solution regardless.
For testing purposes, I removed my non-clustered indexes and added a new covering index on Surname and GivenName (I did not include MiddleName, as I do not want to include it in my query). I ran the first query again and got some pretty good results. First, the execution plan is a simple select and index seek (better than any of the others). Next, the execution time after clearing the cache went down from ~209ms to ~71. With the data cached, it went from ~124ms to ~27ms. These are the best results I've seen so far. As far as IO, here are the results with no cache: Table 'Member'. Scan count 1, logical reads 7, physical reads 1, read-ahead reads 6.
Here are the results when the data is cached: Table 'Member'. Scan count 1, logical reads 7, physical reads 0, read-ahead reads 0.
FYI, this database is only written to once a day (daily import), but this query is used probably over 100 times per day. An increase in the duration of the import is acceptable if the performance of this query is improved. This definitely appears to be the way to go for this particular scenario.
...there is a chance that you are a victim of procedure caching, such that this is using an older plan that is no longer valid.
For testing, I am actually just running a query; I have not updated the stored procedure yet. I had cleared the cache before my testing anyway, just to make sure.
Could you include the whole stored procedure text to go along with this?
I would like to completely rewrite the stored procedure from the bottom up. I didn't write the original stored procedure, and there are some confusing parts there that I have to look into (e.i there appears to be unnecessary conditions and joins). If you still feel it would be beneficial, I can send you a message offline about it.
So, I'm now going to try to optimize the join! I've learned quite a bit so far, so hopefully I'll be able to tackle this one on my own. I'll update this thread on my progress.
Thanks again Mike. You've been a great help.
March 25, 2009 at 11:55 am
Glad to help. Good luck with the rest of it and definitely post back after you have your final solution in place.
March 25, 2009 at 1:18 pm
How many ways can you skin a cat? I've been testing the join with a number of different index combinations and I haven't found a clear cut winner. I have too many test results to post here.
First, I am using the following query: SELECT
M.Surname,
M.GivenName,
A.StreetNumber,
A.StreetName
FROM
Member AS M
INNER JOIN MemberAddress AS A ON M.MemberID = A.MemberID
WHERE
M.Surname LIKE 'sm%'
I added Member.MemberID to the covering index I created (the order is Surname, GivenName, MemberID). I already had a clustered index for MemberID in the MemberAddress table. So I've run tests with a composite index on StreetNumber and StreetName, with individual indexes on StreetNumber and StreetName, with a clustered index on all and a non-clustered index on all. I've also tried changing the order on the Member covering index. There are some clearcut losers, but no clearcut winners.
To make sure I'm moving in the right direction, what indexes would you use on the MemberAddress table? What would you expect the execution plan to be (e.g. hash match with two index seeks)?
I know I could probably just go with one of the better performing index combinations, but I'd really love to understand this better.
March 25, 2009 at 1:51 pm
Given the code you have here (I am copying it in for my own reference)
SELECT
M.Surname,
M.GivenName,
A.StreetNumber,
A.StreetName
FROM
Member AS M
INNER JOIN MemberAddress AS A ON M.MemberID = A.MemberID
WHERE
M.Surname LIKE 'sm%'
if you wanted to get the best read performance for these two tables I would imagine the best bet would be to have...
Clustered Index on Member(MemberID)
Non-clusterd index on Member(Surname, GivenName) --which will implicitly include the clustering key
and then for MemberAddress, the idea index here would include
MemberAddress(MemberID, StreetNumber, StreetName) .
Having this index will give the optimizer the ability to not even have to think about bookmark lookups since the data will all be present on that index, and the key that will be used to get data from that index (memberid) will be the leftmost field.
To me this seems like the ideal scenario for this particular query.
March 25, 2009 at 1:55 pm
Since I got them, I might as well post some of my test results:
Clustered Index on MemberID, index on StreetNumber, index on StreetName
Execution Plan: select, nested loop, index seek on covering index on Member, clustered index seek on clustered index on MemberAddress.
Without Cache
Execution time: ~734ms
IO stats:
Table 'MemberAddress'. Scan count 724, logical reads 3645, physical reads 32, read-ahead reads 210.
Table 'Member'. Scan count 1, logical reads 7, physical reads 2, read-ahead reads 6.
With Cache
Execution time: ~128ms
IO stats:
Table 'MemberAddress'. Scan count 724, logical reads 2839, physical reads 0, read-ahead reads 0.
Table 'Member'. Scan count 1, logical reads 7, physical reads 0, read-ahead reads 0.
Clustered Index on MemberID, composite index on StreetNumber and StreetName
Exectuion Plan: select, hash match, index seek on covering index on Member, index scan on composite index on MemberAddress.
Without Cache
Execution time: ~281ms
IO stats:
Table 'MemberAddress'. Scan count 1, logical reads 787, physical reads 1, read-ahead reads 787.
Table 'Member'. Scan count 1, logical reads 7, physical reads 2, read-ahead reads 6.
With Cache
Execution time: ~209ms
IO stats:
Table 'MemberAddress'. Scan count 1, logical reads 787, physical reads 0, read-ahead reads 0.
Table 'Member'. Scan count 1, logical reads 7, physical reads 0, read-ahead reads 0.
Clustered Index on MemberID, StreetNumber and StreetName
Exectuion Plan: select, nested loops, index seek on covering index on Member, clustered index seek on clustered index on MemberAddress.
Without Cache
Execution time: ~787ms
IO stats:
Table 'MemberAddress'. Scan count 724, logical reads 3839, physical reads 21, read-ahead reads 231.
Table 'Member'. Scan count 1, logical reads 7, physical reads 2, read-ahead reads 6.
With Cache
Execution time: ~112ms
IO stats:
Table 'MemberAddress'. Scan count 724, logical reads 2782, physical reads 0, read-ahead reads 0.
Table 'Member'. Scan count 1, logical reads 7, physical reads 0, read-ahead reads 0.
Non-clustered Index on MemberID, StreetNumber and StreetName
Exectuion Plan: select, merge join, index scan on covering index on Member, sort and then index seek on non-clustered index on MemberAddress.
Without Cache
Execution time: ~418ms
IO stats:
Table 'Worktable'. Scan count 1666, logical reads 2614, physical reads 0, read-ahead reads 0.
Table 'Member'. Scan count 1, logical reads 7, physical reads 2, read-ahead reads 6.
Table 'MemberAddress'. Scan count 1, logical reads 842, physical reads 2, read-ahead reads 846.
With Cache
Execution time: ~162ms
IO stats:
Table 'Worktable'. Scan count 1666, logical reads 2614, physical reads 0, read-ahead reads 0.
Table 'Member'. Scan count 1, logical reads 7, physical reads 0, read-ahead reads 0.
Table 'MemberAddress'. Scan count 1, logical reads 842, physical reads 0, read-ahead reads 0.
March 25, 2009 at 1:57 pm
Thanks Mike. I'll try out your suggestion tomorrow and will get back to you.
April 1, 2009 at 12:10 pm
Mike (3/25/2009)
Given the code you have here (I am copying it in for my own reference)
SELECTM.Surname,
M.GivenName,
A.StreetNumber,
A.StreetName
FROM
Member AS M
INNER JOIN MemberAddress AS A ON M.MemberID = A.MemberID
WHERE
M.Surname LIKE 'sm%'
if you wanted to get the best read performance for these two tables I would imagine the best bet would be to have...
Clustered Index on Member(MemberID)
Non-clusterd index on Member(Surname, GivenName) --which will implicitly include the clustering key
and then for MemberAddress, the idea index here would include
MemberAddress(MemberID, StreetNumber, StreetName) .
Having this index will give the optimizer the ability to not even have to think about bookmark lookups since the data will all be present on that index, and the key that will be used to get data from that index (memberid) will be the leftmost field.
To me this seems like the ideal scenario for this particular query.
You're absolutely right. Based on my test results, this gave the best overall results (both cached and non-cached). In the end I was able to improve the performance of the stored procedure from 7+ minutes for a search on 'sm%' down to about 200ms. 'sm%' returns more results than any other search (based on a two character minimum). When something else is used (e.g. 'mc%'), it is common for the results to be below 100ms.
The main things that helped were having the correct indexes and ensuring that those indexes were being used. Reviewing the execution plan after making changes made it very easy to detect and correct any issues where indexes were not being used in an optimal way.
To further improve things, I have also decided to use a table which contains all of the data that I require in the search. This data gets updated after every import (once per day). Now "select distinct" is no longer required, there are fewer records and there are no joins. Even without indexes this is fast. However, having the correct indexes on this table allows any query to return results instantly (30ms or less for just about any query).
Obviously, I am very happy with the results. Mike, thank you so much for your help. My understand of indexes and how they are used has greatly increased since I started this exercise. Working on the last 70% of the query took minutes after I had a solid grasp on indexes and their usage.
April 1, 2009 at 12:16 pm
Glad to hear it all worked out and was beneficial for you. Always a good feeling to see those queries drop from minutes to under a second, isn't it?
April 1, 2009 at 12:50 pm
Mike (4/1/2009)
Glad to hear it all worked out and was beneficial for you. Always a good feeling to see those queries drop from minutes to under a second, isn't it?
For sure! But the best part is knowing what's going on. I feel much more confident about how to deal with similar issues that may arise in the future.
Thanks again!
Viewing 15 posts - 1 through 14 (of 14 total)
You must be logged in to reply to this topic. Login to reply