There\u2019s also some additional background material available for more enthusiastic students:<\/p>\n
- \n
- Introduction to Indexes<\/a><\/li>\n
- Introduction to Indexes: Part 2 \u2013 The clustered index<\/a><\/li>\n
- Introduction to Indexes: Part 3 \u2013 The nonclustered index<\/a><\/li>\n
- Index Internals<\/a> (Video)<\/li>\n
- The Clustered Index Debate<\/a> (Video)<\/li>\n
- Index Selectivity and Column Order<\/a><\/li>\n<\/ul>\n
Right, now that the admin has been handled, let’s get straight into things. Nothing like starting at the deep end\u2026<\/p>\n
Most people would rightly associate indexes with where clause predicates and joins, after all, the main usage of an index is to reduce the rows in consideration for a query as fast as possible. However there\u2019s another portion of your queries that indexes can, if appropriately designed, help with \u2013 grouping and sorting.<\/p>\n
Sorting is an extremely expensive operation, especially on large numbers of rows. For the academics in the audience, the algorithmic complexity of sorting is above linear, the time to sort a set of data increases faster than the number of items in the list. The common sorting algorithms<\/a> have an average time complexity of O(n log n). It\u2019s better than O(n2<\/sup>), but it can still hurt at the higher row counts.<\/p>\n
![\"O(n^2)\"](\"https:\/\/www.sqlinthewild.co.za\/wp-content\/uploads\/2011\/11\/On2_thumb.png\" "\\"O(n^2)\\"")
<\/a>\u00a0![\"O(n](\"https:\/\/www.sqlinthewild.co.za\/wp-content\/uploads\/2011\/11\/Onlogn_thumb.png\" "\\"O(n")
<\/a><\/p>\nO(n2<\/sup>) on the left, O(n log n) on the right (Thanks to QuickMath<\/a>)<\/p>\n
Right, the non-academics can wake up now.<\/p>\n
The other reason that sorting hurts is that it needs a memory grant to do the sort. If there\u2019s a shortage of memory the query could have to wait a while for the memory to be granted and, if the optimiser mis-estimates the number of rows to be sorted, the memory grant could be insufficient and the sort would have to spill into TempDB. You don\u2019t want that happening.<\/p>\n
Finally, sort is a blocking operator in the execution plan (all rows must have been fetched from the source before any output can be returned), and so the client won\u2019t start seeing rows returned until the entire sort has been completed. This can make the query feel like it takes longer than it really does.<\/p>\n
Grouping and aggregation are much the same. To aggregate one set of values based on another set of values, SQL has to get all the like values of the grouping columns together so that it can do the aggregation. That sounds suspiciously like a sort doesn\u2019t it?<\/p>\n
SQL doesn\u2019t always sort to do aggregations, but the alternative \u2013 hash tables \u2013 isn\u2019t exactly free (homework exercise \u2013 read up on hash tables)<\/p>\n
So for both sorting and grouping, the query processor\u2019s job would be a lot easier if there was some way that it could get the data ordered by the sorting or grouping columns without having to do the work of actually sorting. Sounds impossible? No.<\/p>\n
<\/p>\n
Enter indexes. The b-tree structure of an index makes it great for quickly finding matching rows, but today we\u2019re more interested in the leaf-level of the index than the upper levels. The leaf level of an index is logically ordered by the index key (not physically ordered, let\u2019s stop that myth right here please).<\/p>\n
The leaf level of an index is logically ordered by the index key columns. So, if the index leaf level is read, it can return the data in the order of the index key. If that order is what the query processor needs in order to process a sort or grouping, then there\u2019s no need for an expensive sort to be done, the underlying order can be leveraged.<\/p>\n
Now, before someone misquotes me and goes off crying out that data is always returned in the order of the index used, no it is not. If there\u2019s no order by on a query, there\u2019s no guarantee of order regardless of indexes. However if there is an order by, the query optimiser and query processor may be able to utilise the underlying index order and avoid the cost of actually sorting the data.<\/p>\n
Ok, enough theory for now, let\u2019s look at some practical examples. We\u2019ll use AdventureWorks here and I\u2019m going to use the TransactionHistoryArchive table (in the Product schema)<\/p>\n
Firstly a simple (and silly) example:<\/p>\n
SELECT ProductID, TransactionDate, ActualCost\r\n FROM Production.TransactionHistoryArchive\r\n ORDER BY ActualCost<\/pre>\n
This one\u2019s not very realistic, but it\u2019s a nice simple one to start with. Give me all the rows in the table ordered by the ActualCost column. There\u2019s no filter here so many would say that indexes can\u2019t help here, and it\u2019s true that an index can\u2019t help with finding rows (because all are required), but it can help.<\/p>\n
![\"SortExample1\"](\"https:\/\/www.sqlinthewild.co.za\/wp-content\/uploads\/2011\/11\/SortExample1_thumb.png\" "\\"SortExample1\\"")
<\/a><\/p>\nTable ‘TransactionHistoryArchive’. Scan count 1, logical reads 1419, physical reads 0.<\/p>\n
SQL Server Execution Times:
\nCPU time = 421 ms,\u00a0 elapsed time = 4855 ms.<\/p><\/blockquote>\n421ms of CPU time, with an estimated cost of 93% for the sort. Let\u2019s see if we can make this any better.<\/p>\n
If I create an index on ActualCost, that gives SQL the option of scanning the index (scan, because there\u2019s no seek predicate) to retrieve the data in the order of the ActualCost column. I\u2019m going to have to make it a covering index, as there is no way at all that SQL will willingly do key lookups for every single row of the table.<\/p>\n
CREATE NONCLUSTERED INDEX idx_TransactionHistoryArchive_ACtualCost\r\n ON Production.TransactionHistoryArchive (ActualCost)\r\n INCLUDE (ProductID, TransactionDate)<\/pre>\n
Let\u2019s see how that\u2019s changed the query\u2019s execution.<\/p>\n
![\"SortExample2\"](\"https:\/\/www.sqlinthewild.co.za\/wp-content\/uploads\/2011\/11\/SortExample2_thumb.png\" "\\"SortExample2\\"")
<\/a><\/p>\nTable ‘TransactionHistoryArchive’. Scan count 1, logical reads 682, physical reads 0.<\/p>\n
SQL Server Execution Times:
\nCPU time = 47 ms,\u00a0 elapsed time = 4073 ms.<\/p><\/blockquote>\nThe reads have dropped slightly, because we\u2019re now scanning a nonclustered index which is smaller than the clustered index, but that\u2019s not the main point here. The CPU usage has dropped by around a factor of 8. 421ms down to 47ms. If this was a critical query that ran several times a minute then this change could make a nice improvement to throughput and overall CPU usage.<\/p>\n
That was a silly example, let\u2019s try for something a little more complex:<\/p>\n
SELECT\u00a0 ProductID ,\r\nTransactionDate ,\r\nTransactionType ,\r\nQuantity ,\r\nActualCost\r\nFROM Production.TransactionHistoryArchive\r\nWHERE TransactionType = 'S'\r\nAND ReferenceOrderID = 51739\r\nORDER BY TransactionDate<\/pre>\n
If we look at the execution plan, there\u2019s already an index in use. There\u2019s an index on ReferenceOrderID, but it\u2019s clearly not as good as it could be.<\/p>\n
![\"SortExample3\"](\"https:\/\/www.sqlinthewild.co.za\/wp-content\/uploads\/2011\/11\/SortExample3_thumb.png\" "\\"SortExample3\\"")
<\/a><\/p>\nTable ‘TransactionHistoryArchive’. Scan count 1, logical reads 222, physical reads 0.<\/p>\n
SQL Server Execution Times:
\nCPU time = 0 ms,\u00a0 elapsed time = 1 ms.<\/p><\/blockquote>\nWell, it\u2019s not exactly taking ages on the CPU (it’s a tiny resultset), but this can still be better than it is. The key lookup is there because the existing index is only on two columns \u2013 ReferenceOrderID and ReferenceOrderLineID. I can\u2019t modify that index for this query without potentially breaking some other query\u2019s use of it, so I\u2019ll create a new index.<\/p>\n
CREATE NONCLUSTERED INDEX idx_TransactionTypeReferenceOrderID\r\nON Production.TransactionHistoryArchive (TransactionType, ReferenceOrderID)\r\nINCLUDE (ProductID, TransactionDate, Quantity, ActualCost)<\/pre>\n
Why TransactionType first? Come back on Friday and I\u2019ll be discussing that.<\/p>\n
Plan\u2019s now much simpler, the key lookup has gone, and now the sort is the majority of the cost<\/p>\n
![\"SortExample4\"](\"https:\/\/www.sqlinthewild.co.za\/wp-content\/uploads\/2011\/11\/SortExample4_thumb.png\" "\\"SortExample4\\"")
<\/a><\/p>\nThe key to getting rid of that sort is to understand that a multi-column index is sorted by the entire key. So, if we have an index on Col1, Col2, then for rows where Col1 has the same value, those rows are listed within the index ordered by Col2. In other words, if we read the leaf level of that index it would look like this:<\/p>\n
Col1 Col2\r\nA 1\r\nA 3\r\nA 8\r\nB 4\r\nB 8\r\nB 9\r\nB 14\r\nC 0\r\n\\C 1<\/pre>\n
And so on and so on. Hence, if I filtered that by Col1 = B, the resulting rows could be returned ordered by Col2 with no additional work.<\/p>\n
So in the above case, if I add the sort column (TransactionDate) as a key column in the index (it\u2019s currently an Include column), then once the filter on TransactionType and ReferenceOrderID is done, the qualifying rows can be read in order of TransactionDate.<\/p>\n
Let\u2019s drop the index we created and create one with TransactionDate as an additional key column.<\/p>\n
CREATE NONCLUSTERED INDEX idx_TransactionTypeReferenceOrderID\r\nON Production.TransactionHistoryArchive (TransactionType, ReferenceOrderID, TransactionDate)\r\nINCLUDE (ProductID, Quantity, ActualCost)<\/pre>\n
![\"SortExample5\"](\"https:\/\/www.sqlinthewild.co.za\/wp-content\/uploads\/2011\/11\/SortExample5_thumb.png\" "\\"SortExample5\\"")
<\/a><\/p>\nSuccess, the sort has gone!<\/p>\n
One last example, then we\u2019ll take a brief look at group by before finishing up for the day.<\/p>\n
SELECT\u00a0 ProductID ,\r\nTransactionDate ,\r\nTransactionType ,\r\nQuantity ,\r\nActualCost\r\nFROM Production.TransactionHistoryArchive\r\nWHERE ActualCost > 2500\r\nORDER BY TransactionDate<\/pre>\n
Can I use the same technique here to remove the need for a sort?<\/p>\n
Let’s look at that simplistic index that I described earlier and see how the inequality would play out.<\/p>\n
Col1 Col2\r\nA 1\r\nA 3\r\nA 8\r\nB 4\r\nB 8\r\nB 9\r\nB 14\r\nC 0\r\nC 1<\/pre>\n
If I filter that for Col1 > ‘A’, are the resultant rows ordered by Col2?<\/p>\n
No, because the filter on Col1 is an inequality, a filter that returns multiple different values of Col1, the results aren’t ordered by the second column and hence we can’t\u00a0 use an index here to both support the filter and the order.<\/p>\n
Given this one, we could create an index to support the filter and have SQL sort the rows that qualified or we could create an index to support the order by and have SQL scan that and filter out rows that don’t match.<\/p>\n
In general, the first option is the one that will be best in the majority of cases. The primary use of an index is to locate rows and filter resultsets. There are cases where the alternative may be appropriate, if the vast majority of the rows in the table qualify for the filter then it may be more optimal to support the sort and let SQL scan and filter. Definitely not the usual case though.<\/p>\n
That about wraps up sorts, now for a quick look at group by.<\/p>\n
As mentioned earlier, SQL has two ways to process grouping, it can do what is called a Stream Aggregate or it can use a hash table and do a Hash Aggregate. Stream Aggregate requires that the resultset be sorted in the order of the grouping columns. Well, given that fact and that we’ve spend a lot of time showing how to use indexes to support a sort, this should be quick and easy.<\/p>\n
Let’s dive straight into some examples, because the theory is the same as for the sort described earlier<\/p>\n
SELECT ProductID, SUM(ActualCost) AS TotalCostPerProduct\r\nFROM Production.TransactionHistoryArchive\r\nGROUP BY ProductID<\/pre>\n
This currently executes as a hash aggregate.<\/p>\n
![\"Grouping1\"](\"https:\/\/www.sqlinthewild.co.za\/wp-content\/uploads\/2011\/11\/Grouping1_thumb.png\" "\\"Grouping1\\"")
<\/a><\/p>\nTable ‘Worktable’. Scan count 0, logical reads 0, physical reads 0, read-ahead reads 0.<\/p>\n
Table ‘TransactionHistoryArchive’. Scan count 1, logical reads 1419, physical reads 0.<\/p>\n
SQL Server Execution Times:<\/p>\n
CPU time = 47 ms,\u00a0 elapsed time = 46 ms.<\/p><\/blockquote>\n
If we want a stream aggregate, then we need to get the rows entering the aggregation ordered by ProductID. SQL is not going to willingly sort the entire resultset (the hash aggregate is cheaper), so the only way we’re going to get a stream aggregate (other than with a hint) is by adding an index so that the data can be read from the index already ordered. There’s no filter here so it’s a straightforward index<\/p>\n
CREATE NONCLUSTERED INDEX idx_TransactionHistoryArchive_ProductID\r\nON Production.TransactionHistoryArchive (ProductID)\r\nINCLUDE (ActualCost)<\/pre>\n
![\"Grouping2\"](\"https:\/\/www.sqlinthewild.co.za\/wp-content\/uploads\/2011\/11\/Grouping2_thumb.png\" "\\"Grouping2\\"")
<\/a><\/p>\nTable ‘TransactionHistoryArchive’. Scan count 1, logical reads 482, physical reads 0.<\/p>\n
SQL Server Execution Times:<\/p>\n
CPU time = 31 ms,\u00a0 elapsed time = 34 ms.<\/p><\/blockquote>\n
Not a massive improvement, but the principle is there.<\/p>\n
Now, for homework, take these two queries and see firstly if it is possible to create an index to support both the filter and the group by and, if so, identify what that index is.<\/p>\n
Question 1<\/strong><\/p>\n
SELECT\u00a0 ReferenceOrderID\r\nProductID ,\r\nSUM(Quantity) AS TotalQuantity ,\r\nSUM(ActualCost) AS TotalCost\r\nFROM Production.TransactionHistoryArchive\r\nWHERE TransactionType = 'S'\r\n GROUP BY ReferenceOrderID, ProductID<\/pre>\n
![\"Homework1\"](\"https:\/\/www.sqlinthewild.co.za\/wp-content\/uploads\/2011\/11\/Homework1_thumb.png\" "\\"Homework1\\"")
<\/a><\/p>\nQuestion 2<\/strong><\/p>\n
SELECT ReferenceOrderID ,MIN(ActualCost)|\r\nFROM Production.TransactionHistoryArchive AS tha\r\nWHERE TransactionDate > '2004-01-01'\r\nGROUP BY ReferenceOrderID<\/pre>\n
- Introduction to Indexes: Part 2 \u2013 The clustered index<\/a><\/li>\n
![\"Homework2\"](\"https:\/\/www.sqlinthewild.co.za\/wp-content\/uploads\/2011\/11\/Homework2_thumb.png\" "\\"Homework2\\"")
<\/a><\/p>\n