Page Splitting and Page Merging in Nonclustered Indexes
This appendix provides an overview of nonclustered index internal operations, such as page splitting and page merging.
Nonclustered Indexes Internal Maintenance
The In-Memory OLTP Engine has several internal operations to maintain the structure of nonclustered indexes. As you already know from Chapter 5, page consolidation rebuilds the nonclustered index page, consolidating all changes defined by the page delta records. It helps avoid the performance hit introduced by long delta record chains. The newly created page has the same PID in the mapping table and replaces the old page, which is marked for garbage collection.
Two other processes can create new index pages, page splitting and page merging. Both are complex actions and deserve detailed explanations of their internal implementation.
Page Splitting
Page splitting occurs when a page does not have enough free space to accommodate a new data row. Even though the process is similar to a B-Tree on-disk index page split, there is one conceptual difference. In B-Tree indexes, the page split moves the part of the data to the new data page, freeing up space on the original page. In Bw-Tree indexes, however, the pages are non-modifiable, and SQL Server replaces the old page with two new ones, splitting the data between them.
Let’s look at this situation in more detail. Figure B-1 shows the internal and leaf pages of the nonclustered index. Let’s assume that one of the sessions wants to insert a row with a key of value Bob.
Figure B-1. Page splitting: Initial state
When the delta record is created, SQL Server adjusts the delta records statistics on the index page and detects that there is no space on the page to accommodate the new index value once the delta records are consolidated. It triggers a page split process, which is done in two atomic steps.
In the first step, SQL Server creates two new leaf-level pages and splits the old page values between them. After that, it repoints the mapping table to the first newly created page and marks the old page and the delta records for garbage collection; Figure B-2 illustrates this state. At this state, there are no references to the second newly created leaf-level page from the internal pages. The first leaf-level page, however, maintains the link between pages (through the mapping table), and SQL Server is able to access and scan the second page if needed.
Figure B-2. Page splitting: First step
During the second step, SQL Server creates another internal page with key values that represent the new leaf-level page layout. When the new page is created, SQL Server switches the pointer in the mapping table and marks the old internal page for garbage collection. Figure B-3 illustrates this action.
Figure B-3. Page splitting: Second step
Eventually, the old data pages and delta records are deallocated by the garbage collection process.
Page Merging
Page merging occurs when a delete operation leaves an index page less than 10% from the maximum page size, which is 8KB now, or when an index page contains just a single row. During this operation, SQL Server merges the data from two adjacent index pages, replacing them with the new, combined, data page.
Assume that you have the page layout shown in Figure B-3, and you want to delete the index key value Bob, which means that all data rows with the name Bob have been already deleted. This leaves an index page with the single value Boris, which triggers page merging.
In the first step, SQL Server creates a delete delta record for Bob and another special kind of delta record called merge delta. Figure B-4 illustrates the layout after the first step.
Figure B-4. Page merging: First step
During the second step of page merging, SQL Server creates a new internal page that does not reference the leaf-level page that it is about to be merged. After that, SQL Server switches the mapping table to point to the newly created internal page and marks the old page for garbage collection. Figure B-5 illustrates this action.
Figure B-5. Page merging: Second step
Finally, SQL Server builds a new leaf-level page, copying the Boris value there. After the new page is created, it updates the mapping table and marks the old pages and delta records for garbage collection.
Figure B-6 shows the final data layout after page merging is completed.
Figure B-6. Page merging: Third ( final) step
You can get page consolidation, merging, and splitting statistics from the sys.dm_db_xtp_nonclustered_index_stats view.
Note You can read documentation about the sys.dm_db_xtp_nonclustered_index_stats view at https://msdn.microsoft.com/en-us/library/dn645468.aspx.
Summary
The In-Memory OLTP Engine uses several internal operations to maintain the structure of nonclustered indexes. Page consolidation rebuilds the index page, combining page data with the delta records. It helps avoid the performance impact introduced by long delta records chains.
Page splitting occurs when the index page does not have enough space to accommodate the new rows. In contrast to page splitting on-disk B-Tree indexes, which moves part of the data to the new page, Bw-Tree page splitting replaces the old data page with new pages that contain the data.
Page merging occurs when an index page is less than 10% of the maximum page size or when it has just a single row. SQL Server merges the data from adjacent data pages and replaces them with the new page with the merged data.