Page Splits 101
In SQL Server, a page split occurs on index pages when a row is required to be on a certain page (because of the index key), and there isn’t enough room on the page for it. This can be from either an insert operation, or an update operation. When this occurs, that page is split into two pages, with roughly half of the rows of that original page on each of the pages. The row is then put into the proper page. It is possible that a page split causes higher level leaf nodes to undergo page splits also. Furthermore, all of the page allocations and the data movement is logged in the transaction log.
Paul Randal has defined two different types of page splits. Paul calls the first type of page split a “good” page split, where the storage engine has to add a new page on the right hand side of the index’s leaf level. If you think of a table with an identity column, where the last page for the index for the identity column is too full to hold a new row, then adding a new row will allocate a new page so that the row can be inserted. Paul calls the second type of page split a “nasty” page split, which is when a row expands and the page doesn’t have enough space to hold the changed data, or if a new row needs to go on the page and there isn’t room for it.
In my book, the “good” page split isn’t really a page split, it’s just a new page allocation. However, this is deemed a page split in SQL Server, therefore this is the type of page split that we want to have happening.
Identity Columns
A recent SQLSkills newsletter has a discussion about a table that uses an integer identity column, and running out of values. Under normal usage (and the default unless otherwise specified) an identity column starts with the value of 1, and increments by 1. If you have enough rows where you exhaust the positive values, you need to do something so that your application will continue to work. Obviously, the best thing to do is to change this integer column into a bigint column. However, with over 2 billion rows in this table, a long maintenance window is needed to perform this conversion. What if you need to do something now, before this maintenance window? There are another 2+ billion negative values available for use in the integer data type, so we will use those.
In order to do this, the identity column needs to be changed. It can either be changed to start at the most negative value and increment by one, or start at -1 and be decremented by one. In other words, it can either be set to (-2147483648 , 1), or be set to (-1, -1).
Page Splits on Identity Columns
In considering which of these methods is preferred, we need to consider whether page splits impact these methods – especially nasty page splits. Furthermore, how will index maintenance affect each choice? So let’s think this through.
When there are negative values in this column, and the index is rebuilt, there will be a page with both negative and positive values in it. If the identity column is set to (-1, -1), there won’t be a gap (excluding the 0) in the values, and newly added rows will get a new page allocated – a good page split. If the identity column is set to (-2147483648 , 1), then there will be a full page with the records for the most recently used identity value, and with the values starting with 1 – a rather large gap.
When a new row is added, it will need to be added into the gap on this page, which will need to be split so that the new row can fit in before the value of 1. As more rows are added, the page with the value of 1 will again be used, and then need to be split again. As long as there are rows to be added, this cycle will continue. Therefore, considering the page splits, this choice seems to be a bad choice.
Well, that is my reasoning for how things will work. However, it’s best to test out your theory – especially if you are disagreeing with Paul. So, I will create a table with an identity column (set to 1, 1), and insert some rows. I will then change the identity column to the values to be tested, and add some more rows. I’ll throw in an index rebuild during this mix so that there will be a page with both the positive and negative values, and then insert more rows and see how this affects the page splits. With this in mind, the code to set up this test environment is as follows:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
USE master; IF DB_ID('PageSplits') IS NOT NULL DROP DATABASE PageSplits; GO CREATE DATABASE PageSplits; GO USE PageSplits; GO CREATE TABLE dbo.LotsaSplits ( RowID INTEGER IDENTITY (1 , 1) PRIMARY KEY CLUSTERED, Col01 CHAR(1000) ); GO -- put some positive numbers in there WITH Tens (N) AS (SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1), Hundreds(N) AS (SELECT 1 FROM Tens t1, Tens t2), Millions(N) AS (SELECT 1 FROM Hundreds t1, Hundreds t2, Hundreds t3), Tally (N) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM Millions) INSERT INTO dbo.LotsaSplits (Col01) SELECT TOP (995) CONVERT(CHAR(1000), N) FROM Tally; |
Reset the Identity Column
Next, the identity column needs to be reset to use the new seed / increment value – and this is where I ran into a problem with the test. While I can use DBCC CHECKIDENT to change the seed value, there is no way to change the increment value. Therefore, I can’t test my preferred method by changing the identity column to (-1, -1). However, I can simulate it by creating a table with the initial identity value at (-1, -1) and then using SET IDENTITY_INSERT to put in the positive values. Furthermore, I’ll need a second table to test the positive increment, so I’ll just create it with the most negative seed value and insert the positive values into it. The new code to setup the environment is:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
USE master; IF DB_ID('PageSplits') IS NOT NULL DROP DATABASE PageSplits; GO CREATE DATABASE PageSplits; GO USE PageSplits; GO -- since you can't change the increment, set it this way and use identity_insert to put positive values in there. CREATE TABLE dbo.LotsaSplits1 ( RowID INTEGER IDENTITY (-1 , -1) PRIMARY KEY CLUSTERED, Col01 CHAR(1000) ); GO CREATE TABLE dbo.LotsaSplits2 ( RowID INTEGER IDENTITY (-2147483648 , 1) PRIMARY KEY CLUSTERED, Col01 CHAR(1000) ); GO -- put some positive numbers in there SET IDENTITY_INSERT dbo.LotsaSplits1 ON; WITH Tens (N) AS (SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1), Hundreds(N) AS (SELECT 1 FROM Tens t1, Tens t2), Millions(N) AS (SELECT 1 FROM Hundreds t1, Hundreds t2, Hundreds t3), Tally (N) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM Millions) INSERT INTO dbo.LotsaSplits1 (RowID, Col01) SELECT TOP (995) N, CONVERT(CHAR(1000), N) FROM Tally; SET IDENTITY_INSERT dbo.LotsaSplits1 OFF; -- copy these into the other table SET IDENTITY_INSERT dbo.LotsaSplits2 ON; INSERT INTO dbo.LotsaSplits2 (RowID, Col01) SELECT RowID, Col01 FROM dbo.LotsaSplits1; SET IDENTITY_INSERT dbo.LotsaSplits2 OFF; GO |
The next part of this test is to create a page that has both positive and negative values in it. Since this test is to test out the second option, I’ll do this just for the second table. This code will insert a few rows, and then rebuild the index on this table. Finally it will show how the data on the page looks.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
-- reseed the identity value DBCC CHECKIDENT (LotsaSplits2, RESEED, -2147483648); GO -- Add some rows, and then rebuilt CI. This will have a page with a huge gap in the values. Where I think we will encounter a lot of page splits. INSERT INTO dbo.LotsaSplits2 (Col01) VALUES ('Filler1'), ('Filler2'); GO ALTER INDEX ALL ON dbo.LotsaSplits2 REBUILD; GO -- check tables for how they currently look: SELECT plc.page_id, COUNT(*) AS RowsOnPage, MIN(ls.RowID) AS MinRowID, MAX(ls.RowID) AS MaxRowID FROM dbo.LotsaSplits1 ls CROSS APPLY sys.fn_PhysLocCracker(%%physloc%%) plc GROUP BY plc.page_id ORDER BY MinRowID; SELECT plc.page_id, COUNT(*) AS RowsOnPage, MIN(ls.RowID) AS MinRowID, MAX(ls.RowID) AS MaxRowID FROM dbo.LotsaSplits2 ls CROSS APPLY sys.fn_PhysLocCracker(%%physloc%%) plc GROUP BY plc.page_id ORDER BY MinRowID; GO |
In this code, I use the undocumented virtual system column %%physloc%% to get the physical file/page/slot that a row is on, and then this binary value is cracked to return the actual file/page/slot. I then get the number of rows on this page, and the starting/ending values, and report by page. It can be seen that a page was created that will need to be split when more rows are inserted.
Checking for a page split
Continuing on, let’s add more rows to each table, and see how many page splits occurred. This will be performed for each table one at a time. This code and the results it produces is:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
-- now insert more rows into each table WITH Tens (N) AS (SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1), Hundreds(N) AS (SELECT 1 FROM Tens t1, Tens t2), Millions(N) AS (SELECT 1 FROM Hundreds t1, Hundreds t2, Hundreds t3), Tally (N) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM Millions) INSERT INTO dbo.LotsaSplits1 (Col01) SELECT TOP (995) CONVERT(CHAR(1000), N) FROM Tally; GO -- check for any page splits. SELECT [AllocUnitName] AS N'Index', (CASE [Context] WHEN N'LCX_INDEX_LEAF' THEN N'Nonclustered' WHEN N'LCX_CLUSTERED' THEN N'Clustered' ELSE N'Non-Leaf' END) AS [SplitType], COUNT (1) AS [SplitCount] FROM fn_dblog (NULL, NULL) WHERE [Operation] = N'LOP_DELETE_SPLIT' GROUP BY [AllocUnitName], [Context]; GO -- insert more rows into the other table. The one I expect to see splits happening in. WITH Tens (N) AS (SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1), Hundreds(N) AS (SELECT 1 FROM Tens t1, Tens t2), Millions(N) AS (SELECT 1 FROM Hundreds t1, Hundreds t2, Hundreds t3), Tally (N) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM Millions) INSERT INTO dbo.LotsaSplits2 (Col01) SELECT TOP (995) CONVERT(CHAR(1000), N) FROM Tally; GO -- check for any page splits. SELECT [AllocUnitName] AS N'Index', (CASE [Context] WHEN N'LCX_INDEX_LEAF' THEN N'Nonclustered' WHEN N'LCX_CLUSTERED' THEN N'Clustered' ELSE N'Non-Leaf' END) AS [SplitType], COUNT (1) AS [SplitCount] FROM fn_dblog (NULL, NULL) WHERE [Operation] = N'LOP_DELETE_SPLIT' GROUP BY [AllocUnitName], [Context]; GO |
Now this is unexpected – there is only one page split on the LotsaSplits2 table, where I was expecting many more. Let’s look at what data is on these pages for these tables:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
-- see how the data is distributed on the pages. SELECT plc.page_id, COUNT(*) AS RowsOnPage, MIN(ls.RowID) AS MinRowID, MAX(ls.RowID) AS MaxRowID FROM dbo.LotsaSplits1 ls CROSS APPLY sys.fn_PhysLocCracker(%%physloc%%) plc GROUP BY plc.page_id ORDER BY MinRowID; SELECT plc.page_id, COUNT(*) AS RowsOnPage, MIN(ls.RowID) AS MinRowID, MAX(ls.RowID) AS MaxRowID FROM dbo.LotsaSplits2 ls CROSS APPLY sys.fn_PhysLocCracker(%%physloc%%) plc GROUP BY plc.page_id ORDER BY MinRowID; |
The second result set (for the identity column set at (-2147483648 , 1) ) shows that the page split occurred at the value of 1. If we can get the page to split where it starts with 1, then inserted rows won’t go onto this page, thus meaning that additional page splits won’t occur. It seems like I really got lucky here. Since the page can hold 7 rows, I repeated this test several times with between 1 and 6 filler rows, and it always split at the value of 1. The page split algorithm seems to be smart enough to realize that this gap exists, and that there will be more page splits occurring unless there is a page that starts with that value of 1. In talking with Paul about this observed behavior, he replied to me:
You’ll get at most two nasty page splits. The Access Methods is smart enough on the second split to split at the +ve/-ve boundary and no more nasty page splits occur. Yes, it seems somewhat counter-intuitive until the observation about the smart page split.
So there we go – the page split algorithm is smart enough to look at the data and to try to prevent future page splits if possible. Very nice!
Did you notice earlier that LotsaSplits1 also showed a page split? My assumption is that since there is still a gap to hold a value of zero, that the page was used and was then split. I tested this by changing the setup code to use “N-1” instead, so that it will start with the value of zero. However, this still incurs a page split. Looking closely at Paul’s definition of a good page split, notice that he states that a good split is when adding a new page on the right hand side of the index’s leaf level. It so happens that we are adding to the left hand side. I still think that all that should be occurring is a new page allocation, yet these tests prove that internally SQL Server is performing a page split.
Hi,
I know I’m a little late to the party here, but it’s the most detailed article I could find on the subject.
The web is full of info on page splits (the normal page splits and the “nasty” page splits), however, there is one question for which I cannot find a definite answer.
Specifically : what happens if I build a DESC clusteded index with an auto-increment key ?
In that situation, we’ll always _prepend_ to the index, not append.
By your buddy’s definition, “a good split is when adding a new page on the right hand side of the index’s leaf level”, it is not a good split.
However, it’s not an insert in the middle either : we are always inserting on the left hand side.
But what about within the page itself ? Are record sorted within a page ? Does it matter ?
Say I have 10 records ( 1 through 10) that fit in a single Page (Page 0)
When I insert id 11, we’ll allocate a new page (Page 1) at the beginning of the index and put record 11 in it.
Will this record be at the beginning of the new page or at the end (if there is such a concept).
And what happens with we insert 12 in that page ?
When the two pages are full, what do they look like ?
Layout 1:
Page 1: 20-19-…-12-11 Page 2: 10-9-…-2-1
Layout 2:
Page 1: 11-12-…-19-20 Page 2: 1-2-…-9-10
Is it layout 1 or layout 2 (or maybe layout 3 where records have no order within a page anyway)
Bottom line : is there any performance penalty to doing that ?
NOTE : the reasoning for having a descending index was that newer records are typically more interesting and looked up more often than older record. And most request have a order by Id desc.
Reply
Hi Blaise,
I’m glad that you like the article.
A good page split is really when the storage engine has to add a new page to either the left or right hand side of index’s leaf level. In my example above, this was performed with the setting of the identity column. In your example, this is performed by having the index in a descending order. In either case, the new pages will be allocated on the left side.
Note that with either method, adding new pages to the left side will cause fragmented indexes.
As far as the order of the rows on the page: All of the rows that have to be on the page (due to the values in the columns in the index key) will be on that page. The slot array on that page will be maintained in the proper order for the rows that are on the page. However, the data for that row may or may not physically be in that order. See my posts Does a Clustered Index really physically store the rows in key order? and Automating DBCC PAGE – Part 3 (Is a Clustered Index physically sorted on disk?) for a more detailed explanation of how this works.
Reply
Messed up the page numbering. Should have been :
Layout 1:
Page 1: 20-19-…-12-11 Page 0: 10-9-…-2-1
Layout 2:
Page 1: 11-12-…-19-20 Page 0: 1-2-…-9-10
Reply
you should be able to use ALTER TABLE switch and a drop and rename to get the existing data into a table with the desired updated identity specification without any data movement.
Reply
Interesting idea. I’ll have to try this out.
Reply
As well as the effects of page splits there is also the issue of logical fragmentation. If the pages are allocated in ascending page order and the ids in descending numeric order you will end up with a perfectly fragmented index.
Reply