Random Prefetching
In my last post, I explained the importance of asynchronous I/O and described how SQL Server uses sequential read ahead to boost the performance of scans. In this post, I'll discuss how SQL Server uses random prefetching. Let's begin with a simple example of a query plan that performs many random I/Os. As in my prior post, all of the examples in this post use a 1GB scale factor TPC-H database. The following query returns the number of line items associated with each order placed on March 15, 1998:
SELECT O_ORDERKEY, COUNT(*)
FROM ORDERS JOIN LINEITEM ON O_ORDERKEY = L_ORDERKEY
WHERE O_ORDERDATE = '1998-03-15'
GROUP BY O_ORDERKEY
|--Compute Scalar(DEFINE:([Expr1008]=CONVERT_IMPLICIT(int,[Expr1012],0)))
|--Stream Aggregate(GROUP BY:([ORDERS].[O_ORDERKEY]) DEFINE:([Expr1012]=Count(*)))
|--Nested Loops(Inner Join, OUTER REFERENCES:([ORDERS].[O_ORDERKEY], [Expr1011]) OPTIMIZED WITH UNORDERED PREFETCH)
|--Clustered Index Seek(OBJECT:([ORDERS].[O_ORDERDATE_CLUIDX]), SEEK:([ORDERS].[O_ORDERDATE]='1998-03-15') ORDERED FORWARD)
|--Index Seek(OBJECT:([LINEITEM].[L_ORDERKEY_IDX]), SEEK:([LINEITEM].[L_ORDERKEY]=[ORDERS].[O_ORDERKEY]) ORDERED FORWARD)
This query plan uses an index nested loops join. The clustered index seek on the ORDERS table returns the 661 orders that were placed on March 15, 1998. For each of these 661 orders, SQL Server performs an index seek on the LINEITEM table to lookup the records associated with this order. Each of these index seeks potentially represents a series of random I/Os to navigate from the root of the B-tree index to the leaf page(s) where the records for that order are stored. To minimize the cost of these I/Os, SQL Server enhances the nested loops join with prefetching. (Notice the WITH UNORDERED PREFETCH keywords associated with the nested loops join.) The prefetching mechanism peers ahead in the clustered index seek on the ORDERS table and issues asynchronous I/Os for the pages that will ultimately be needed by the index seek on the LINEITEM table. As in the sequential read ahead scenario, we can see the prefetching in action by checking the output of SET STATISTICS IO ON. Look at the read-ahead reads for the LINEITEM table:
Table 'LINEITEM'. Scan count 661, logical reads 5165, physical reads 2, read-ahead reads 5000, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'ORDERS'. Scan count 1, logical reads 15, physical reads 2, read-ahead reads 19, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
You may have noticed that the prefetch in this example was UNORDERED. Indeed, there are two types of prefetch: UNORDERED and ORDERED. Although a nested loops join ordinarily preserves the order of the rows from its outer input (in this case the ORDERS table), a nested loops join WITH UNORDERED PREFETCH does not preserve order. Instead, the rows are returned in the order that the asynchronous I/Os complete. However, if the order of the rows is important, SQL Server can use a nested loops join WITH ORDERED PREFETCH. For example, observe what happens to the plan if we add an ORDER BY clause to the above query:
SELECT O_ORDERKEY, COUNT(*)
FROM ORDERS JOIN LINEITEM ON O_ORDERKEY = L_ORDERKEY
WHERE O_ORDERDATE = '1998-03-15'
GROUP BY O_ORDERKEY
ORDER BY O_ORDERKEY
|--Compute Scalar(DEFINE:([Expr1008]=CONVERT_IMPLICIT(int,[Expr1012],0)))
|--Stream Aggregate(GROUP BY:([ORDERS].[O_ORDERKEY]) DEFINE:([Expr1012]=Count(*)))
|--Nested Loops(Inner Join, OUTER REFERENCES:([ORDERS].[O_ORDERKEY], [Expr1011]) WITH ORDERED PREFETCH)
|--Sort(ORDER BY:([ORDERS].[O_ORDERKEY] ASC))
| |--Clustered Index Seek(OBJECT:([ORDERS].[O_ORDERDATE_CLUIDX]), SEEK:([ORDERS].[O_ORDERDATE]='1998-03-15 00:00:00.000') ORDERED FORWARD)
|--Index Seek(OBJECT:([LINEITEM].[L_ORDERKEY_IDX]), SEEK:([LINEITEM].[L_ORDERKEY]=[ORDERS].[O_ORDERKEY]) ORDERED FORWARD)
Notice that SQL Server chooses to push the sort below the nested loops join. For this sort to satisfy the ORDER BY clause, the nested loops join must preserve the order of the rows that it returns. Thus, this time SQL Server uses a nested loops join WITH ORDERED PREFETCH.
SQL Server can also use random prefetching to speed up bookmark lookups and certain update and delete statements. For instance, consider the following two statements:
SELECT *
FROM LINEITEM
WHERE L_ORDERKEY BETWEEN 5000000 AND 5001000
|--Nested Loops(Inner Join, OUTER REFERENCES:([Uniq1002], [LINEITEM].[L_SHIPDATE], [Expr1004]) OPTIMIZED WITH UNORDERED PREFETCH)
|--Index Seek(OBJECT:([LINEITEM].[L_ORDERKEY_IDX]), SEEK:([LINEITEM].[L_ORDERKEY] >= (5000000) AND [LINEITEM].[L_ORDERKEY] <= (5001000)) ORDERED FORWARD)
|--Clustered Index Seek(OBJECT:([LINEITEM].[L_SHIPDATE_CLUIDX]), SEEK:([LINEITEM].[L_SHIPDATE]=[LINEITEM].[L_SHIPDATE] AND [Uniq1002]=[Uniq1002]) LOOKUP ORDERED FORWARD)
UPDATE LINEITEM
SET L_DISCOUNT = 0.1
WHERE L_ORDERKEY BETWEEN 5000000 AND 5001000
|--Clustered Index Update(OBJECT:([LINEITEM].[L_SHIPDATE_CLUIDX]), SET:([LINEITEM].[L_DISCOUNT] = RaiseIfNull([ConstExpr1010])) WITH UNORDERED PREFETCH)
|--Compute Scalar(DEFINE:([ConstExpr1010]=CONVERT_IMPLICIT(money,[@1],0)))
|--Top(ROWCOUNT est 0)
|--Index Seek(OBJECT:([LINEITEM].[L_ORDERKEY_IDX]), SEEK:([LINEITEM].[L_ORDERKEY] >= [@2] AND [LINEITEM].[L_ORDERKEY] <= [@3]) ORDERED FORWARD)
Both plans use a non-clustered index on the LINEITEM table to identify rows that match the L_ORDERKEY predicate. In the case of the SELECT statement, SQL Server performs a bookmark lookup - recall that a bookmark lookup is just a special case of a nested loops join - to fetch the columns of the LINEITEM table that are not covered by the non-clustered index. In the case of the UPDATE statement, SQL Server needs to locate the correct page and row in the clustered index and update the L_DISCOUNT column. The resulting I/O sequence is the same as the bookmark lookup. In both cases, to minimize the cost of the I/Os, SQL Server adds prefetching to the plan. Just as in the original example above, the prefetch mechanism peers ahead in the non-clustered index seek on the LINEITEM table and issues asynchronous I/Os for the pages of the clustered index that will be needed.
For systems with many hard drives, random prefetching can dramatically improve performance. However, prefetching can adversely affect concurrency as I explained in this post.
Comments
- Anonymous
March 18, 2009
In my past two posts, I explained how SQL Server may add a sort to the outer side of a nested loops join