SQL Server insertion performance

Question

Let's suppose I have the following table with a clustered index on a column (say, a)

CREATE TABLE Tmp
(
    a int,
    constraint pk_a primary key clustered (a)
)

Then, let's assume that I have two sets of a very large number of rows to insert to the table.

• 1st set) values are sequentially increasing (i.e., {0,1,2,3,4,5,6,7,8,9,..., 999999997, 999999998, 99999999})
• 2nd set) values are sequentially decreasing (i.e., {99999999,999999998,999999997, ..., 3,2,1,0}

do you think there would be performance difference between inserting values in the first set and the second set? If so, why?

thanks

Answer 1

SQL Server will generally try and sort large inserts into clustered index order prior to insert anyway.

If the source for the insert is a table variable however then it will not take account of the cardinality unless the statement is recompiled after the table variable is populated. Without this it will assume the insert will only be one row.

The below script demonstrates three possible scenarios.

1. The insert source is already exactly in correct order.
2. The insert source is exactly in reversed order.
3. The insert source is exactly in reversed order but OPTION (RECOMPILE) is used so SQL Server compiles a plan suited for inserting 1,000,000 rows.

Execution Plans

The third one has a sort operator to get the inserted values into clustered index order first.

/*Create three separate identical tables*/
CREATE TABLE Tmp1(a int primary key clustered (a))
CREATE TABLE Tmp2(a int primary key clustered (a))
CREATE TABLE Tmp3(a int primary key clustered (a))

DBCC FREEPROCCACHE;

GO

DECLARE @Source TABLE (N INT PRIMARY KEY (N ASC))

INSERT INTO @Source
SELECT TOP (1000000) ROW_NUMBER() OVER (ORDER BY (SELECT 0)) 
FROM sys.all_columns c1, sys.all_columns c2, sys.all_columns c3

SET STATISTICS TIME ON;

PRINT 'Tmp1'
INSERT INTO Tmp1
SELECT TOP (1000000) N
FROM @Source
ORDER BY N

PRINT 'Tmp2'
INSERT INTO Tmp2
SELECT  TOP (1000000) 1000000 - N
FROM @Source
ORDER BY N

PRINT 'Tmp3'
INSERT INTO Tmp3
SELECT 1000000 - N
FROM @Source
ORDER BY N
OPTION (RECOMPILE)

SET STATISTICS TIME OFF;

Verify Results and clean up

SELECT object_name(object_id) AS name, 
       page_count, 
       avg_fragmentation_in_percent, 
       fragment_count, 
       avg_fragment_size_in_pages
FROM 
sys.dm_db_index_physical_stats(db_id(), object_id('Tmp1'), 1, NULL, 'DETAILED') 
WHERE  index_level = 0 
UNION ALL 
SELECT object_name(object_id) AS name, 
       page_count, 
       avg_fragmentation_in_percent, 
       fragment_count, 
       avg_fragment_size_in_pages
FROM 
sys.dm_db_index_physical_stats(db_id(), object_id('Tmp2'), 1, NULL, 'DETAILED') 
WHERE  index_level = 0 
UNION ALL 
SELECT object_name(object_id) AS name, 
       page_count, 
       avg_fragmentation_in_percent, 
       fragment_count, 
       avg_fragment_size_in_pages
FROM 
sys.dm_db_index_physical_stats(db_id(), object_id('Tmp3'), 1, NULL, 'DETAILED') 
WHERE  index_level = 0 

DROP TABLE Tmp1, Tmp2, Tmp3

STATISTICS TIME ON results

+------+----------+--------------+
|      | CPU Time | Elapsed Time |
+------+----------+--------------+
| Tmp1 | 6718 ms  | 6775 ms      |
| Tmp2 | 7469 ms  | 7240 ms      |
| Tmp3 | 7813 ms  | 9318 ms      |
+------+----------+--------------+

Fragmentation Results

+------+------------+------------------------------+----------------+----------------------------+
| name | page_count | avg_fragmentation_in_percent | fragment_count | avg_fragment_size_in_pages |
+------+------------+------------------------------+----------------+----------------------------+
| Tmp1 |       3345 | 0.448430493                  |             17 | 196.7647059                |
| Tmp2 |       3345 | 99.97010463                  |           3345 | 1                          |
| Tmp3 |       3345 | 0.418535127                  |             16 | 209.0625                   |
+------+------------+------------------------------+----------------+----------------------------+

Conclusion

In this case all three of them ended up using exactly the same number of pages. However Tmp2 is 99.97% fragmented compared with only 0.4% for the other two. The insert to Tmp3 took the longest as this required an additional sort step first but this one time cost needs to be set against the benefit to future scans against the table of minimal fragmentation.

The reason why Tmp2 is so heavily fragmented can be seen from the below query

WITH T AS
(
SELECT TOP 3000 file_id, page_id, a
FROM Tmp2
CROSS APPLY sys.fn_PhysLocCracker(%%physloc%%)
ORDER BY a
)
SELECT file_id, page_id, MIN(a), MAX(a)
FROM T 
group by file_id, page_id
ORDER BY MIN(a)

With zero logical fragmentation the page with the next highest key value would be the next highest page in the file but the pages are exactly in the opposite order of what they are supposed to be.

+---------+---------+--------+--------+
| file_id | page_id | Min(a) | Max(a) |
+---------+---------+--------+--------+
|       1 |   26827 |      0 |    143 |
|       1 |   26826 |    144 |    442 |
|       1 |   26825 |    443 |    741 |
|       1 |   26824 |    742 |   1040 |
|       1 |   26823 |   1041 |   1339 |
|       1 |   26822 |   1340 |   1638 |
|       1 |   26821 |   1639 |   1937 |
|       1 |   26820 |   1938 |   2236 |
|       1 |   26819 |   2237 |   2535 |
|       1 |   26818 |   2536 |   2834 |
|       1 |   26817 |   2835 |   2999 |
+---------+---------+--------+--------+

The rows arrived in descending order so for example values 2834 to 2536 were put into page 26818 then a new page was allocated for 2535 but this was page 26819 rather than page 26817.

One possible reason why the insert to Tmp2 took longer than Tmp1 is because as the rows are being inserted in exactly reverse order on the page every insert to Tmp2 means the slot array on the page needs to be rewritten with all previous entries moved up to make room for the new arrival.

Answer 2

It has to do with allocating pages sequentially as is done for a clustered index. With the first they would naturally cluster together. But in the second, I think you would have to keep moving the page locations to have them sequentially ascending. However, I really only understand SQL server at a conceptual level, so you'd have to test.

Answer 3

To answer this question, you only need to look up what effect clustering has on data and the manner in which it is logically ordered. By clustering ascending, higher numbers get added on to the end of the table; inserts will be very fast. When inserting in reverse, it will be inserted in between two other records (read up on page splitting); this will result in slower inserts. This actually has other negative effects as well (read up on fill factor).