Search results matching tags 'Undocumented' and 'Seeks'

SQL Server, Seeks, and Binary Search

Paul White — Mon, 08 Aug 2011 20:10:27 GMT

The following table summarizes the results from my last two blog entries, showing the CPU time used when performing 5 million clustered index seeks:

In test 1, making the clustered index unique improved performance by around 40%. In test 2, making the same change reduced performance by around 70% (on 64-bit systems – more on that later). As a reminder, both tests use nested loops to join a single-column BIGINT table of numbers to itself:

In test 1, the table contains numbers from 1 to 5 million inclusive; for test 2, the table contains the even numbers from 2 to 10 million (still 5 million rows). In case you were wondering, the test 2 results are the same if we populate the table with odd numbers from 1 to 9,999,999 instead of even numbers. How can we explain these results?

Performing an Index Seek

Perhaps we need to look a bit deeper into how SQL Server performs an index seek. Most people know that SQL Server indexes are a B+ tree, so let’s work through an example of locating the row containing the value 1 million, when the table contains values from 1 to 5 million, with a unique clustered index.

Index seeks start at the index root page, which we can find in a number of ways (e.g. sys.system_internals_allocation_units). I happened to use DBCC IND to determine that the root of the index was page 117482 in file 1 (in Denali, we can use a new DMF: sys.dm_db_database_page_allocations). Anyway, whichever way you find it, we can use DBCC PAGE to look at the contents of the root page:

The col1 (key) column shows the lowest key value that can possibly be present in the lower-level page specified by Child Page Id. We can see that the lowest possible key value on page 117485 is 906305, and the next lowest key value possible is 1132881 on page 117486. So, if a row containing the value 1 million exists, the next page to look at is 117485:

We are now at level 1 of the index, and have to scroll down the output a bit further to see that the next page to look at is 119580. This page is at the leaf level of the index, and we find our target value at position 399:

Binary Search

When performing an index seek, SQL Server obviously doesn’t run DBCC PAGE and scroll down the output window to find the next page to look at like we just did. You may know that SQL Server can use binary search to locate index entries, but it’s worth taking a closer look at the index pages to see how this works in practice:

The slot array contains a series of two-byte offsets pointing to the index records. The index records are not necessarily stored in any particular order on the page; only the slot array entries are guaranteed to be in sorted order. Note that the sorted slot array entries do not contain the index keys themselves, just offsets.

Performance

When SQL Server uses binary search to locate an index entry, it starts by checking the middle element of the slot array (shown in red in the example above). It then follows that offset pointer to the index record, and compares the value it finds there with the sought value. Assuming the value is not the one we are looking for, the sorted nature of the slot array allows SQL Server to narrow the search range in half after this first comparison.

If the red index record happens to contain a value higher than the sought value, we know the value we are looking for is in that half of the slot array that sorts lower than the red entry. This process of cutting the search space in half continues until we find the record we are looking for, or until it becomes clear that the value does not exist.

The average and worst case performance of binary search is very close to log₂N comparisons to find the item of interest in a sorted list of N items. For the 476 index entries found in our test example index structure at the leaf level, that means at most 9 comparison operations. That compares well to a linear search of the sorted slot array, which might require as many as 476 comparisons if we are unlucky, 238 on average.

None of this offers any particular insight into why a binary search into a unique indexes containing only even (or odd!) numbers should be so slow. One of the advantages of binary search is that it expects to perform around the same amount of work, regardless of the distribution of the values in the index. Luckily, binary search is not the only game in town.

Linear Interpolation

As efficient as binary search is in the general case, in some cases we can do better.

When searching for the value 1 million, we know from level 1 of the index that the lowest key value that can appear on the leaf level page we are interested in is 999,601. We also know that the lowest key value on the next page is 1,000,077. From the header information on our target page, we also know there are 476 entries in the slot array on that page. Given these facts, we can make an immediate guess at which slot the value 1,000,000 ought to appear in:

expected slot = (1000077 - 999601) / 476 * (1000000 - 999601) = 399

This simple calculation takes us immediately to slot 399. As we saw earlier, slot 399 does indeed contain the value 1,000,000:

Naturally, the quality of the linear interpolation guess depends on how evenly distributed the values are within the page. To a lesser extent, it also depends on how closely the minimum key value information at level 1 of the index matches reality. In both tests shown in earlier blog entries, the values are precisely evenly distributed and the level 1 index key information is spot on.

Performance

Linear interpolation has the potential to be more efficient even than binary search, finding the target value in one comparison in this example, compared to nine comparisons for binary search. Even where the data is not perfectly distributed, there is scope for linear interpolation to be superior, simply by applying the technique repeatedly on successively narrower ranges.

A reasonable practical compromise might be to try linear interpolation two or three times, before falling back to linear or binary search on the remaining range. The advantage of linear interpolation may not seem much, but consider that SQL Server makes these comparisons for every index seek operation – when doing many millions of seeks, the difference can soon add up. It is probably not coincidence that the OLTP TPC benchmark tests perform a very great number of singleton index seeks.

Linear Regression

A natural extension to the idea of linear interpolation is to apply a linear regression (line of best fit) instead:

In the diagram, the blue dotted line represents a linear interpolation based on the values of the smallest and highest values only. The black line is obtained by a linear regression of all the data values, and results in a much better fit.

Since every straight line can be represented by a formula of the form y = mx + b, we can completely specify it by recording the values of the ‘m’ (slope) and ‘b’ (y-axis intercept) parameters. The R² value gives an idea of how good a fit the linear regression line is to the data. In the present context, the ‘y’ value represents the indexed value, and the ‘x’ value is the slot position where that value can be found. It’s easy to see that once we have a linear regression line, we can estimate the slot position for a particular sought index value by solving x = (y – b) / m.

To use linear regression in a database, we might imagine storing the ‘b’ and ‘m’ parameter values somewhere (perhaps in a compact format in the page header), and deciding whether to apply the technique based on the R² value.

What Does SQL Server Do?

All this is fine in theory, but does SQL Server really ever use anything except binary search? To see, I ran tests with a debugger attached to the SQL Server process, and stepped through the calls made while the seek test queries were running. The call stack below was obtained when running 64-bit SQL Server:

By contrast, the following call stack comes from 32-bit SQL Server:

Interestingly, SQL Server follows the same code paths (at least at the call stack level, which is the best we can do without source code) regardless of whether the index is defined as unique or not, and for all the numeric data types I tested (INT, BIGINT, REAL, FLOAT, DECIMAL with a zero scale).

The performance problem on x64 servers appears to be most pronounced when the key values have a small fixed gap between them. As we have seen, performance is very much worse on x64 servers compared with x86 versions when the table contains just even or odd numbers (i.e. with a gap of 1 between index entries). If we change the test to multiply the original entries by a factor of ten (to produce a sequence of 10, 20, 30, 40…) the performance penalty all but disappears, and the x64 unique index test is around 30% faster than the non-unique test.

Conclusions and Further Reading

From the evidence available, my best guess is that 64-bit SQL Server does use linear interpolation and/or linear regression instead of binary search under suitable conditions, but that the implementation has edge-case poor performance where the index keys are separated by a small fixed offset. It seems that we can achieve best performance by using a unique index where possible, and ensuring that keys are, as far as practicable, sequential and contiguous.

B-tree Indexes, Interpolation Search, and Skew – Microsoft Research
Interpolation Search – a log log N Search (PDF)

email: SQLkiwi@gmail.com
twitter: @SQL_Kiwi

A Tale of Two Index Hints

Paul White — Wed, 22 Sep 2010 21:44:00 GMT

If you look up Table Hints in Books Online, you’ll find the following statement:

If a clustered index exists, INDEX(0) forces a clustered index scan and INDEX(1) forces a clustered index scan or seek.
If no clustered index exists, INDEX(0) forces a table scan and INDEX(1) is interpreted as an error.

The interesting thing there is that both hints can result in a scan. If that is the case, you might wonder if there is any effective difference between the two. This blog entry explores that question, and highlights an optimizer quirk that can result in a much less efficient query plan when using INDEX(0). I’ll also cover some stuff about ordering guarantees.

Test Environment

As usual, we need to create a test table:

USE     tempdb;
SET     NOCOUNT ON;
GO
IF      OBJECT_ID(N'Test.Orders', N'U')
        IS NOT NULL
        DROP TABLE Test.Orders;
GO
IF      SCHEMA_ID(N'Test')
        IS NOT NULL
        DROP SCHEMA Test;
GO
CREATE  SCHEMA Test

        CREATE  TABLE Orders
                (
                order_id    INTEGER NOT NULL,
                product_id  INTEGER NOT NULL,
                quantity    INTEGER NOT NULL,
                padding     CHAR(980) NOT NULL DEFAULT (SPACE(0)),
                
                CONSTRAINT  [PK Test.Orders order_id]
                PRIMARY KEY CLUSTERED (order_id ASC)
                );
GO
CREATE  NONCLUSTERED INDEX  [IX Test.Orders quantity]
ON      Test.Orders (quantity ASC)
        INCLUDE (padding);
GO
DECLARE @Counter    INTEGER = 1,
        @RowCount   INTEGER = 64 * 8;
        
WHILE   @Counter <= @RowCount
BEGIN
        INSERT  Test.Orders
                (order_id, product_id, quantity)
        VALUES  (
                @RowCount - @Counter,
                @RowCount - @Counter,
                @RowCount - @Counter
                );
                
        SET     @Counter += 1;
END;
GO

The test table has 512 rows, padded so that eight rows fit on each 8KB data page. The table is clustered on the order_id column, and there is a nonclustered index on the quantity column, with the padding column INCLUDEd to again ensure that eight rows fit on each nonclustered index page.

The script also deliberately generates a very high level of logical fragmentation, which we can see with the following query:

SELECT  SI.name,
        IPS.index_type_desc,
        IPS.avg_fragmentation_in_percent,
        IPS.fragment_count,
        IPS.page_count
FROM    sys.dm_db_index_physical_stats
        (
        DB_ID(),
        OBJECT_ID(N'Test.Orders', N'U'),
        DEFAULT,
        DEFAULT,
        DEFAULT
        ) IPS
JOIN    sys.indexes SI
        ON  SI.[object_id] = IPS.[object_id]
        AND SI.index_id = IPS.index_id
ORDER   BY
        IPS.index_id;
GO

The reason for the fragmentation will become apparent later on. These are the results I saw on my machine:

Background Information on Scans

A scan of a table or index processes every row, whereas a seek returns one or more rows from one or more ranges of the index.

Scan Strategies

When the SQL Server optimizer produces a plan containing a scan of an index or clustered table, the Storage Engine may be able to choose from two different strategies: scanning the pages in logical order, or the order in which they were allocated. In the first case, it follows the doubly-linked list at the leaf level of the index. In the second case, it can use the Index Allocation Map (IAM) pages to drive the scan.

A scan of a heap always uses the IAM pages of course (there is no clustered index to provide a logical page order), but this post is concerned mainly with indexes and clustered tables, so I won’t talk much more about heaps.

The advantage of an IAM-driven scan is that pages will tend to be read in physical order on the disk, which generally results in sequential I/O, and promotes effective read-ahead. How efficient scanning the pages in logical order is depends on the level of logical fragmentation: if fragmentation is high, the scan will tend to result in a high proportion of random I/Os, and read-ahead may be much less effective.

The downside to the IAM-driven scan is that it is not guaranteed to return results in logical key order (in fact it usually won’t), and there is an extra start-up cost in accessing the IAM pages, and planning the scan.

IAM-driven scans

The Storage Engine may choose an IAM-driven scan if:

The index contains 64 or more pages (giving the method a chance to recover the start-up cost);
The optimizer indicates that an ordered scan is not required for correct results; and
Either the data cannot change during the scan, or the query indicates that incorrect results are acceptable.

Hopefully the first point makes sense on it’s own. The second point refers to a flag that the optimizer can set on a scanning iterator in a query plan. This flag shows up as an “Ordered:True” or “Ordered:False” property of the iterator. When set to true, it indicates that the Storage Engine must perform a scan in logical key order for the plan to produce correct results. When set to false, it means that the order does not matter. In the latter case, the Storage Engine has the choice of performing either type of scan. The query plan does not show which type of scan was chosen.

The third point comes in two parts, but both relate to the fact that an IAM-driven scan does not take the locks necessary to prevent other concurrent operations from changing the data in the table, or moving the pages around (perhaps as the result of a page split).

The simplest way to satisfy the first part (to ensure that the data cannot be changed or moved) is to take a shared table lock. The second part (acceptable incorrect results) refers to transaction isolation level. If the scan runs at an effective isolation level of READ UNCOMMITTED (either explicitly or through the use of a NOLOCK hint) we are effectively saying that we don’t care about reading consistent data. More than that, we imply that we are happy to read the same data twice, or not at all.

The Reason for the Fragmentation

Our test table has been created with a high level of fragmentation. This allows us to see whether the Storage Engine used an IAM-driven scan or not. If the results come back in logical key order, we can be sure (in these specific examples) that the scan was performed by following the doubly-linked list at the leaf level of the index. If the results come back in allocation order, they will look very different, and we can infer that an IAM-driven scan was performed.

Important: Please don’t take any of that to mean that you can rely on query results to come back in a particular order in more general cases. The very simple tests shown here are carefully crafted to encourage the ordering behaviour I have just described, but there are no guarantees. Never rely on plan details to provide ordering – always use an ORDER BY clause if you require ordered results.

Scanning Examples

Let’s look first at two simple queries that return all columns and all rows from our test table:

-- Query 1
SELECT  T.*
FROM    Test.Orders T;
 
-- Query 2
SELECT  T.*
FROM    Test.Orders T 
ORDER   BY 
        T.order_id ASC;

Both queries produce very similar execution plans, but the first specifies “Ordered:False” while the second specifies “Ordered:True”. The second example avoids an expensive explicit Sort iterator by requiring the Storage Engine to return rows from the scan in logical key order (the clustered index is on order_id, remember).

Both queries return records ordered by the clustering key; Query 1 because the Storage Engine cannot perform an IAM-driven scan (we haven’t met all the conditions); and Query 2 because an ordered scan was requested by the optimizer.

Query 1 is not guaranteed to return records in that order, but Query 2 (almost) is. In case you are wondering what might cause Query 1 to return records in a different order, consider the effect of a parallel plan, or Enterprise Edition’s Advanced Scan feature. For anyone that follows that second link, I should mention that Advanced Scan is only possible when the Ordered flag is set to False.

An IAM-driven Scan

Query 1 above meets two of the conditions for an IAM-driven scan: the index contains at least 64 pages, and the optimizer did not specify Ordered:True. We can meet the third condition by adding a WITH (TABLOCK) hint:

SELECT  T.*
FROM    Test.Orders T WITH (TABLOCK);

We receive the following result set:

Each group of eight records (each 8KB page) comes back ordered by the clustering key, but the overall order of pages is in the order the pages were written. This is the result of an IAM-driven scan: pages in allocation order, records within the pages in clustered key order. As you may have guessed, neither of these two observed orderings can be relied on either – I mention them for pure geek interest value.

Adding the TABLOCK hint to Query 2 does not result in an IAM-driven scan, because the optimizer continues to specify Ordered:True on the scan (to avoid the sort that would be necessary to honour the ORDER BY clause).

For Query 2, the optimizer does still consider a plan with an unordered scan followed by a sort, but rejects it as being more expensive than an ordered scan. For very large tables, the optimizer may calculate that an IAM-driven scan might save more time than would be consumed by the extra sort, and a plan featuring the unordered scan + sort would be chosen. This is a heuristic optimization: the optimizer knows nothing about the actual fragmentation level of an index (though it does know how many pages it occupies).

Index Hints

Let’s now run the Query 1 test again, this time specifying INDEX(0) or INDEX(1) hints, as well as choosing to specify TABLOCK or not:

SELECT  T.* FROM Test.Orders T WITH (INDEX(0));
SELECT  T.* FROM Test.Orders T WITH (INDEX(1));
SELECT  T.* FROM Test.Orders T WITH (INDEX(0), TABLOCK);
SELECT  T.* FROM Test.Orders T WITH (INDEX(1), TABLOCK);

In all cases, the results are the same: if we specify TABLOCK, we meet the conditions for an IAM-driven scan, and the records comes back in physical order. If we omit TABLOCK, we happen to get results in clustered-key order – but we know that is just coincidental. All four query plans look exactly the same as the simple clustered index scans shown earlier, and all feature “Ordered:False”.

Let’s try the same thing with the ORDER BY clause (Query 2):

SELECT  T.* FROM Test.Orders T WITH (INDEX(0)) ORDER BY T.order_id;
SELECT  T.* FROM Test.Orders T WITH (INDEX(0), TABLOCK) ORDER BY T.order_id;
SELECT  T.* FROM Test.Orders T WITH (INDEX(1)) ORDER BY T.order_id;
SELECT  T.* FROM Test.Orders T WITH (INDEX(1), TABLOCK) ORDER BY T.order_id;

All four queries produce the same results, in the same order, and are guaranteed to do so thanks to the ORDER BY clause. The execution plans are rather different, however:

Both INDEX(1) plans produce the plan shown on the left, with the scan showing “Ordered:True”, and a cost of 0.05.
Both INDEX(0) plans produce the plan shown on the right, with the scan showing “Ordered:False”, and a cost of 0.07.

Optimizer Bug, Limitation, or “By Design”?

It seems that INDEX(0) forces “Ordered:False” on the scan. As a consequence, we get an explicit Sort iterator when the ORDER BY clause is present. Why should INDEX(0) force an unordered scan?

One can imagine a line of reasoning that says we would normally specify INDEX(0) only on a heap table, where an ordered scan is not possible. The flaw in this argument is that INDEX(1) does not enable us to force a scan of a clustered table – it will result in a seek if at all possible.

INDEX(0) and Ordered:True

Nevertheless, it is possible to produce “Ordered:True” when INDEX(0) is specified, in an INSERT, UPDATE or DELETE query. Let’s look at three alternative formulations of a trivial UPDATE query on our test table:

All three plans feature the “Ordered:True” flag, but the one with INDEX(0) includes a sort on order_id. That sort is probably redundant, since the Clustered Index Scan (with “Ordered:True”) ought to be guaranteed to produce rows in that same order. Not only will that sort slow down your query, it will require a memory grant, and might even spill to tempdb.

A Data Modification Optimization

When performing our UPDATE query, the optimizer takes into account the effect of ordering. If rows arrive at the update iterator in clustered index order, the pattern of updates will likely result in sequential I/O. If rows are in a different order, the updates will likely cause random I/O as the index is updated row by row.

Often, the optimizer may choose to pre-sort the records on the clustered index key to optimize for sequential I/O. On other occasions, it may decide that the cost of the sort would exceed the savings made – this is seen when the number of rows to be updated is very small, and the rows can be located most efficiently from a nonclustered index.

When the rows are sourced from the clustered index, the optimizer always adds the “Ordered:True” flag to maximize the chances for sequential I/O, regardless of the estimated number of rows. This explains how the Clustered Index Scan above manages to acquire the “Ordered:True” flag when INDEX(0) was specified. It seems that the optimizer misses the fact that by adding the ordering flag, the sort is now redundant.

Final Thoughts

Although I have concentrated very much on clustered indexes in this entry, I want to stress that the two scanning strategies apply to both clustered and non-clustered indexes. I created a nonclustered index on the test table so you can verify for yourself that IAM-driven scans are possible with nonclustered indexes, and the rules are exactly the same.

It is also not necessary to specify TABLOCK explicitly to get an IAM-driven scan: if the index in question happens to have row and page locks disabled (using ALTER INDEX (…) SET ALLOW_ROW_LOCKS = OFF, ALLOW_PAGE_LOCKS = OFF) the Storage Engine will recognise that a table lock has to be taken. Other circumstances like the database being read-only will also meet the underlying requirement that the data cannot change during the scan.

Beware of using NOLOCK when the other conditions for an IAM-driven scan are met. Not only might you read data that has not been committed yet, you can also read committed data twice, or not at all. Your query might also fail completely with the dreaded error: “Could not continue scan with NOLOCK due to data movement”.

Finally, watch out for unnecessary sorts in plans that use the INDEX(0) table hint – consider using INDEX(1) instead, or rewriting the query to avoid the hint altogether.

Paul White
Email: SQLkiwi@gmail.com
Twitter: @SQL_Kiwi