THE SQL Server Blog Spot on the Web

Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
in Search

Paul White: Page Free Space

A technical SQL Server blog from New Zealand. See also my articles on SQLperformance.com

Can a SELECT query cause page splits?

Books Online has this to say about page splits:

When a new row is added to a full index page, the Database Engine moves approximately half the rows to a new page to make room for the new row.  This reorganization is known as a page split.  A page split makes room for new records, but can take time to perform and is a resource intensive operation. Also, it can cause fragmentation that causes increased I/O operations.

Given that information, how can a SELECT statement be responsible for page splits?  Well, I suppose we could SELECT from a function that adds rows to a table variable as part of its internal implementation, but that would clearly be cheating, and no fun at all from a blogging point of view.

Tables & Sample Data

To demonstrate the effects I want to talk about today, I’m going to use a couple of tables with data from the sales data in the Adventure Works sample database.  There’s a full script at the end of this post for those of you that like to run these things for yourselves, but the data generally looks like this: (header table on the left; detail table on the right):

image

Both tables have a clustered index on the Sales Order ID column.  The query I’m going to run is this:

image

I have expressed the natural join predicate as (X >= Y) AND (X <= Y) instead of (X = Y) to prevent the optimizer choosing a hash or merge join (both of which require at least one equality predicate to perform an inner join).  The “+ 0” is there to prevent the optimizer from using an indexed nested loop join (that is, using a seek on the inner side of the join).  These tricks are necessary to generate a plan with an eager index spool on this small sample data set.

Checking for Splits

There are several ways to check for page splits while this query is running.  I’m going to use the new extended events UI in SQL Server 2012, which, by the way, I’m quite impressed with: it’s a lot like using Profiler inside SSMS and does away with all that tedious mucking about with CREATE EVENT SESSION statements and XQuery (there are also no improbability factors to compute).  Ok, so running the query above and looking for page splits via extended events, I get output like this:

image

These page splits are all caused by the Index Spool in the query plan.  This iterator builds a temporary b-tree index on the data produced by its sub-tree, and like any index insert operation, page splits will occur.  In fact this is a bit of a cheat, because these page splits aren’t really page splits at all – notice the sequential nature of the pages being ‘split’ (the page_id column), and its relationship with the new page.

Index Spool Internals

Having shown page splits that aren’t really page splits, let’s get to demonstrating an index spool that ‘really does’ split pages.  To do that, we need to know something about the way index spools build their temporary index.  You have probably noticed that most query plans that build permanent indexes involve a sort, which in turn requires a memory grant.

Index spools do not get a memory grant, and are not preceded by an explicit sort operator in query plans.  Given that indexes require sorting, how does an index spool manage to build a b-tree index structure at all?  The answer is that index spools just insert rows into an empty b-tree in the order they are received.  In general, the rows used for the index will not be received in sorted order, resulting in lots and lots of page splits in the temporary index b-tree.

The first run of the query did not suffer from this problem due to the clustered index on the header table, which tends to produce rows ordered by Sales Order ID – exactly the order of the index built by the index spool.  Let’s rebuild the header table clustered index to use the Customer ID column instead, and re-run the test.  The query plan looks exactly the same – the only difference is that the index spool is fed by a clustered index scan that is now extremely unlikely to produce rows in Sales Order ID sorted order:

image

The page splits reported by the extended events ‘trace’ are now very different:

image

Notice the same source page (page_id) being split over and over again as rows arrive in unsorted order.  There are now very many more page splits than before, and they are a lot more expensive because we are now not just allocating new empty pages at the end of the index – we have to shift half the rows and fix up all the page pointers.  In practice, this is the sort of splitting you are likely to see in tempdb with an index spool – rows are very unlikely to be in index order (else why would we need the spool at all?).  On that last point, consider the hoops I had to jump through to demonstrate a plan where the rows were in temporary index order – all that mess with “>= AND <=” and “+ 0”…

Note: You can distinguish between mid-page splits and the end-of-index ‘splits’ using the technique Jonathan Kehayias (blog | twitter) shows here (it won’t work for our current example because work table index builds are not logged).

Parallel Index Spools

The last thing I want to cover about index spools is how they behave in parallel plans.  You might have noticed the MAXOP 1 hint in the previous examples.  Let’s remove that now, add some wait type monitoring, and see how we go:

image

Don’t be fooled by the parallelism indicator on the index spool – the index building portion of its execution happens on a single thread.  One way to see this is to capture thread and task information using the page splitting event session, where the same task and thread ids are reported for every one of the hundreds of events:

image

The wait statistics provide additional confirmation:

image

Ignore the CXPACKET waits (they are perfectly normal) and look at the EXECSYNC waits.  This query ran at DOP 8 on my machine, so 7 parallel threads had to wait while a single thread built the temporary index.  The index build took 114ms, and 7 threads waiting simultaneously for that time gives 7 x 114 = 798ms.  That’s within one quantum (4ms) of the total recorded EXECSYNC wait time.  EXECSYNC is used for lots of different things – whenever synchronization of parallel workers needs to occur outside a Parallelism operator, so please don’t take away the idea that EXECSYNC = index spool.

© Paul White 2011

Twitter: @SQL_Kiwi
Email: SQLkiwi@gmail.com

Script:

-- Any AdventureWorks version should be fine
USE AdventureWorks2008R2
GO
-- Tables
CREATE TABLE #OrdHeader
(
    SalesOrderID        INTEGER NOT NULL,
    OrderDate           DATETIME NOT NULL,
    SalesOrderNumber    NVARCHAR(25) NOT NULL,
    CustomerID          INTEGER NOT NULL
)
GO
CREATE TABLE #OrdDetail
(
    SalesOrderID        INTEGER NOT NULL,
    OrderQty            SMALLINT NOT NULL,
    LineTotal           NUMERIC(38,6) NOT NULL
);
GO
-- Data
INSERT #OrdHeader
SELECT
    h.SalesOrderID,
    h.OrderDate,
    h.SalesOrderNumber,
    h.CustomerID
FROM Sales.SalesOrderHeader AS h
GO
INSERT #OrdDetail
SELECT
    d.SalesOrderID,
    d.OrderQty,
    d.LineTotal
FROM Sales.SalesOrderDetail AS d
GO
-- Clustered indexes
CREATE UNIQUE CLUSTERED INDEX cuq ON #OrdHeader (SalesOrderID) WITH (MAXDOP = 1)
CREATE CLUSTERED INDEX cuq ON #OrdDetail (SalesOrderID) WITH (MAXDOP = 1)
GO
-- Test query
SELECT
    d.OrderQty,
    h.SalesOrderNumber,
    h.OrderDate
FROM #OrdDetail AS d
JOIN #OrdHeader AS h ON
    d.SalesOrderID >= h.SalesOrderID + 0
    AND d.SalesOrderID <= h.SalesOrderID + 0
OPTION  (MAXDOP 1)
GO
-- Lose the ordering
CREATE CLUSTERED INDEX cuq ON #OrdHeader (CustomerID) 
WITH (DROP_EXISTING = ON, MAXDOP = 1)
GO
SELECT
    d.OrderQty,
    h.SalesOrderNumber,
    h.OrderDate
FROM #OrdDetail AS d
JOIN #OrdHeader AS h ON
    d.SalesOrderID >= h.SalesOrderID + 0
    AND d.SalesOrderID <= h.SalesOrderID + 0
OPTION  (MAXDOP 1)
GO
-- Parallelism
DBCC SQLPERF('sys.dm_os_wait_stats', 'CLEAR')
GO
SELECT
    d.OrderQty,
    h.SalesOrderNumber,
    h.OrderDate
FROM #OrdDetail AS d
JOIN #OrdHeader AS h ON
    d.SalesOrderID >= h.SalesOrderID + 0
    AND d.SalesOrderID <= h.SalesOrderID + 0
GO
SELECT
    ows.wait_type,
    ows.waiting_tasks_count,
    ows.wait_time_ms,
    ows.max_wait_time_ms,
    ows.signal_wait_time_ms
FROM sys.dm_os_wait_stats AS ows
WHERE
    ows.wait_type IN (N'CXPACKET', 'EXECSYNC')
GO
DROP TABLE 
    #OrdHeader, 
    #OrdDetail
GO
/*
-- Denali Extended Events Session Script (change the session_id filter!)
-- Try the UI :)
 
CREATE EVENT SESSION [Page Splits] ON SERVER 
ADD EVENT sqlserver.page_split
    (
    ACTION(sqlos.system_thread_id,sqlos.task_address,sqlserver.sql_text)
WHERE 
    ([package0].[equal_uint64]([sqlserver].[session_id],(60)))) 
ADD TARGET 
    package0.ring_buffer(SET max_memory=(65536))
WITH 
(
    MAX_MEMORY=4096 KB,
    EVENT_RETENTION_MODE=ALLOW_SINGLE_EVENT_LOSS,
    MAX_DISPATCH_LATENCY=30 SECONDS,
    MAX_EVENT_SIZE=0 KB,
    MEMORY_PARTITION_MODE=NONE,
    TRACK_CAUSALITY=OFF,
    STARTUP_STATE=OFF
)
*/
Published Tuesday, August 30, 2011 7:46 AM by Paul White

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

 

Thiago Dantas said:

Thanks for the article Paul. Really interesting material. Will surely check out XEvents on CTP3 now

August 29, 2011 2:22 PM
 

Fabiano Amorim said:

I was wondering if we could do something to force a sort to avoid these page splits on index spool. What do you think?

As always, very nice post. indeed, It's much better to use XE on CTP3 :-).

August 29, 2011 6:56 PM
 

Paul White said:

Hi Fabiano,

Yes we can often rewrite the query to achieve an explicit sort before the index spool by using unsupported tricks like a subquery with TOP (BIGINT.Max) ... ORDER BY <spool index columns>, but should we have to?

We could also manually edit the XML show plan and use a plan guide with a 'real' plan obtained by using that as a USE PLAN hint, but this is even more work and forces a plan shape that might not always be ideal.

The other main option is to remove the need for the spool by providing a better access path (e.g. by improving the indexes on the base tables), but this isn't always possible.

Paul

August 30, 2011 2:46 AM
 

Hiriyo said:

Hi Paul,

First of all I would like to thank you for sharing your knowledge and ideas to the Index based stuffs. I am regular reader of your Blogs. If possible could you please provide me a doc file for your all blogs related to Index performance posted after July 2010. I know its a laborious task but we all will definitely appreciate it.

Thanks again..

September 9, 2011 2:08 AM
 

Rob Volk said:

Jonathan has struck again and found a way to identify mid-page splits, if anyone's interested:

http://sqlskills.com/blogs/jonathan/post/Tracking-Problematic-Pages-Splits-in-SQL-Server-2012-Extended-Events-e28093-No-Really-This-Time!.aspx

December 15, 2011 12:06 PM
 

Paul White: Page Free Space said:

This is a post for T-SQL Tuesday #43 hosted by my good friend Rob Farley . The topic this month is Plan

June 11, 2013 5:00 AM

Leave a Comment

(required) 
(required) 
Submit
Powered by Community Server (Commercial Edition), by Telligent Systems
  Privacy Statement