Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I have a SQL statement that inserts rows into a table with a clustered index on the column TRACKING_NUMBER.

E.G.:

INSERT INTO TABL_NAME (TRACKING_NUMBER, COLB, COLC) 
SELECT TRACKING_NUMBER, COL_B, COL_C 
FROM STAGING_TABLE

My question is - does it help to use an ORDER BY clause in the SELECT statement for the clustered index column, or would any gain acheived be negated by the extra sort required for the ORDER BY clause?

share|improve this question
    
Hey Gary, welcome to DBA.SE! Are you talking about SQL Server? If so, what version? –  Nick Chammas Oct 28 '11 at 15:13

3 Answers 3

As the other answers already indicate SQL Server may or may not explicitly ensure that the rows are sorted in clustered index order prior to the insert.

This is dependant upon whether or not the clustered index operator in the plan has the DMLRequestSort property set (which in turn depends upon the estimated number of rows that are inserted).

If you find that SQL Server is underestimating this for whatever reason you might benefit from adding an explicit ORDER BY to the SELECT query to minimize page splits and ensuing fragmentation from the INSERT operation

Example:

use tempdb;

GO

CREATE TABLE T(N INT PRIMARY KEY,Filler char(2000))

CREATE TABLE T2(N INT PRIMARY KEY,Filler char(2000))

GO

DECLARE @T TABLE (U UNIQUEIDENTIFIER PRIMARY KEY DEFAULT NEWID(),N int)

INSERT INTO @T(N)
SELECT number 
FROM master..spt_values
WHERE type = 'P' AND number BETWEEN 0 AND 499

/*Estimated row count wrong as inserting from table variable*/
INSERT INTO T(N)
SELECT T1.N*1000 + T2.N
FROM @T T1, @T T2

/*Same operation using explicit sort*/    
INSERT INTO T2(N)
SELECT T1.N*1000 + T2.N
FROM @T T1, @T T2
ORDER BY T1.N*1000 + T2.N


SELECT avg_fragmentation_in_percent,
       fragment_count,
       page_count,
       avg_page_space_used_in_percent,
       record_count
FROM   sys.dm_db_index_physical_stats(2, OBJECT_ID('T'), NULL, NULL, 'DETAILED')
;  


SELECT avg_fragmentation_in_percent,
       fragment_count,
       page_count,
       avg_page_space_used_in_percent,
       record_count
FROM   sys.dm_db_index_physical_stats(2, OBJECT_ID('T2'), NULL, NULL, 'DETAILED')
;  

Shows that T is massively fragmented

avg_fragmentation_in_percent fragment_count       page_count           avg_page_space_used_in_percent record_count
---------------------------- -------------------- -------------------- ------------------------------ --------------------
99.3116118225536             92535                92535                67.1668272794663               250000
99.5                         200                  200                  74.2868173956017               92535
0                            1                    1                    32.0978502594514               200

But for T2 fragmentation is minimal

avg_fragmentation_in_percent fragment_count       page_count           avg_page_space_used_in_percent record_count
---------------------------- -------------------- -------------------- ------------------------------ --------------------
0.376                        262                  62500                99.456387447492                250000
2.1551724137931              232                  232                  43.2438349394613               62500
0                            1                    1                    37.2374598468001               232

Conversely sometimes you might want to force SQL Server to underestimate the row count when you know the data is already pre-sorted and wish to avoid an unnecessary sort. One notable example is when inserting a large number of rows into a table with a newsequentialid clustered index key. In versions of SQL Server prior to Denali SQL Server adds an unnecessary and potentially expensive sort operation. This can be avoided by

DECLARE @var INT =2147483647

INSERT INTO Foo
SELECT TOP (@var) *
FROM Bar

SQL Server will then estimate that 100 rows will be inserted irrespective of the size of Bar which is below the threshold at which a sort is added to the plan. However as pointed out in the comments below this does mean that the insert will unfortunately not be able to take advantage of minimal logging.

share|improve this answer
    
Thank you - your post brings up some important considerations. Much appreciated. –  Gary Oct 28 '11 at 19:35
    
@MartinSmith - Assume you're using table variables to ensure the optimiser uses an inaccurate row estimate? For completeness, might be worth adding something to your answer pointing this out. –  Mark Storey-Smith Oct 28 '11 at 22:44
    
@MarkStorey-Smith - Yes. A TOP (@variable) would have the same effect in making the estimate wrong. I do have the following code comment in my answer /*Estimated row count wrong as inserting from table variable*/ –  Martin Smith Oct 28 '11 at 22:47
    
Apologies, code blindness after a long day :) –  Mark Storey-Smith Oct 28 '11 at 23:54
1  
@SQLkiwi - So would that mean that trying to avoid the sort in the newsequentialid case would also mean that the operation could not be minimally logged? –  Martin Smith Nov 13 '11 at 23:20

It the optimiser decides it would be more efficient to sort the data prior to insert, it will do so somewhere upstream of the insert operator. If you introduce a sort as part of your query, the optimiser should realise that the data is already sorted and omit doing so again. Note the execution plan chosen may vary from run to run depending on the number of rows inserted from your staging table.

If you can capture execution plans of the process with and without the explicit sort, attach them to your question for comment.

Edit: 2011-10-28 17:00

@Gonsalu's answer appears to show that a sort operation always occurs, this is not the case. Demo scripts required!

As the scripts were getting quite large, I've moved them to Gist. For ease of experimentation, the scripts use SQLCMD mode. Tests run on 2K5SP3, dual core, 8GB.

The insert tests cover three scenarios:

  1. Staging data clustered index in same order as target.
  2. Staging data clustered index in reverse order.
  3. Staging data clustered by col2 which contains a random INT.

First run, inserting 25 rows.

1st run, 25 rows

All three execution plans are the same, no sort occurs anywhere in the plan and the clustered index scan is "ordered=false".

Second run, inserting 26 rows.

2nd run, 26 rows

This time the plans differ.

  • The first shows the clustered index scan as ordered=false. No sort has occurred as the source data is appropriately sorted.
  • In the second the clustered index scan as ordered=true, backward. So we don't have a sort operation but the need for the data to be sorted is recognised by the optimiser and it scans in reverse order.
  • The third shows a sort operator.

So, there is a tipping point where the optimiser deems a sort to be necessary. As @MartinSmith shows, this appears to be based on the estimated rows to be inserted. On my test rig 25 doesn't require a sort, 26 does (2K5SP3, dual core, 8GB)

The SQLCMD script includes variables that allow the size of the rows in the table to change (altering the page density) and the number of rows in dbo.MyTable before the additional inserts. From my testing, neither has any effect on the tipping point.

If any readers are so inclined, please run the scripts and add your tipping point as a comment. Interested to hear if it varies across test rigs and/or versions.

Edit: 2011-10-28 20:15

Repeated tests on same rig but with 2K8R2. This time the tipping point is 251 rows. Again, varying the page density and existing row counts has no effect.

share|improve this answer
    
Thanks very much for the detailed follow up. I will run some tests and look at the execution plan. –  Gary Oct 28 '11 at 19:34
    
So in short, when you have enough rows that it matters (>1K) SQL Server will sort for you anyway. Correct? –  Nick Chammas Oct 28 '11 at 20:24
1  
Much less than that! 26 rows in 2005, 251 rows in 2008. But, as @MartinSmith points out, you may want to sort deliberately if the execution plan shows a poor estimate. –  Mark Storey-Smith Oct 28 '11 at 20:33
    
@MarkStorey-Smith - I get 250 vs 251 as the cut off point as well on 2008. The one exception I've found is if the clustered index key is an identity column then 819 vs 820 seems to be the cut off point for some reason. –  Martin Smith Oct 28 '11 at 21:55
    
@MartinSmith - I tried the same (assuming you made the target an identity and set identity_insert on?) and it stayed at 251. Different plan though, with the sort pushed to the last operator for test 2 and 3. –  Mark Storey-Smith Oct 28 '11 at 22:20

The ORDER BY clause in the SELECT statement is redundant.

It is redundant because the rows that will be inserted, if they need to be sorted, are sorted anyway.

Let us create a test case.

CREATE TABLE #Test (
    id INTEGER NOT NULL
);

CREATE UNIQUE CLUSTERED INDEX CL_Test_ID ON #Test (id);

CREATE TABLE #Sequence (
    number INTEGER NOT NULL
);

INSERT INTO #Sequence
SELECT number FROM master..spt_values WHERE name IS NULL;

Let's enable the text display of the actual query plans, so we can see what tasks are carried out by the query processor.

SET STATISTICS PROFILE ON;
GO

Now, let's INSERT 2K rows into the table without an ORDER BY clause.

INSERT INTO #Test
SELECT number
  FROM #Sequence

The actual execution plan for this query is the following.

INSERT INTO #Test  SELECT number    FROM #Sequence
  |--Clustered Index Insert(OBJECT:([tempdb].[dbo].[#Test]), SET:([tempdb].[dbo].[#Test].[id] = [tempdb].[dbo].[#Sequence].[number]))
       |--Top(ROWCOUNT est 0)
            |--Sort(ORDER BY:([tempdb].[dbo].[#Sequence].[number] ASC))
                 |--Table Scan(OBJECT:([tempdb].[dbo].[#Sequence]))

As you can see, there's a Sort operator before the actual INSERT occurs.

Now, let's clear the table, and INSERT 2k rows into the table with the ORDER BY clause.

TRUNCATE TABLE #Test;
GO

INSERT INTO #Test
SELECT number
  FROM #Sequence
 ORDER BY number

The actual execution plan for this query is the following.

INSERT INTO #Test  SELECT number    FROM #Sequence   ORDER BY number
  |--Clustered Index Insert(OBJECT:([tempdb].[dbo].[#Test]), SET:([tempdb].[dbo].[#Test].[id] = [tempdb].[dbo].[#Sequence].[number]))
       |--Top(ROWCOUNT est 0)
            |--Sort(ORDER BY:([tempdb].[dbo].[#Sequence].[number] ASC))
                 |--Table Scan(OBJECT:([tempdb].[dbo].[#Sequence]))

Note that it's the same execution plan that was used for the INSERT statement without the ORDER BY clause.

Now, the Sort operation is not always required, as Mark Smith has shown in another answer (if the number of rows to be inserted is low), but the ORDER BY clause is still redundant in that case, because even with an explicit ORDER BY, no Sort operation is generated by the query processor.

You can optimize an INSERT statement into a table with a clustered index, by using a minimally-logged INSERT, but that's out of scope for this question.

Updated 2011-11-02: As Mark Smith has shown, INSERTs into a table with a clustered index might not always require to be sorted -- the ORDER BY clause is also redundant in that case, though.

share|improve this answer
    
Excellent demonstration. Could this behavior change depending on the size of the insert (per Mark's answer)? –  Nick Chammas Oct 28 '11 at 15:16
5  
@Nick - Yes. It depends on whether the insert iterator in the plan has the DMLRequestSort property set (which is dependant on estimated row count) –  Martin Smith Oct 28 '11 at 16:29
    
@Martin How does one check which properties are set? –  Gonsalu Oct 28 '11 at 16:40
2  
@Gonsalu - Have a look at the "Actual Execution Plan" in Management Studio, select the clustered index insert then hit F4 or right click and select "Properties". It also appears in the XML of course. –  Martin Smith Oct 28 '11 at 16:43
    
@MartinSmith Thanks! –  Gonsalu Oct 28 '11 at 16:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.