Data Modification and Performance

Now that you have a better understanding of the storage structures in SQL Server, it's time to take a look at how SQL Server maintains and manages those structures when data modifications are taking place in the database.

Inserting Data

When you add a data row to a heap table, SQL Server adds the row to the heap wherever space is available. SQL Server uses the IAM and PFS pages to identify whether any pages with free space are available in the extents already allocated to the table. If no free pages are found, SQL Server uses the information from the GAM and SGAM pages to locate a free extent and allocate it to the table. With a clustered index on the table, the new data row is inserted to the appropriate location on the appropriate data page relative to the clustered index sort order. If there is no more room on the destination page, SQL Server needs to link a new page in the chain to make room available and add the row. This is called a page split.

In addition to modifying the affected data pages when adding rows, all nonclustered indexes need to be updated to add a pointer to the new record. If a page split occurs, this incurs even more overhead as the clustered index needs to be updated to store the pointer for the new page added to the table. Fortunately, because the clustered key is used as the bookmark in nonclustered indexes when a table is clustered, even though the page and row IDs have changed, the bookmarks for rows moved by a page split do not have to be updated as long as the clustered key remains the same.

Page Splits

When a page split occurs, SQL Server looks for an available page to link into the page chain. It first tries to find an available page in the same extent as the pages it will be linked to. If no free pages exist in the same extent, it looks at the IAM to determine whether there are any free pages in any other extents already allocated to the table or index. If no free pages are found, a new extent is allocated to the table.

When a new page is found, the original page is split. Approximately half the rows are moved to the new page, and the rest remain on the original page (see Figure 33.22). Whether the new page goes before or after the original page when the split is made depends on the amount of data to be moved. In an effort to minimize logging, SQL Server moves the smaller rows to the new page. If the smaller rows are at the beginning of the page, SQL Server places the new page before the original page and moves the smaller rows to it. If the larger rows are at the beginning of the page, SQL Server keeps them on the original page and moves the smaller rows to the new page after the original page.

Figure 33.22. Page splitting due to inserts .

Figure 33.22 illustrates page splitting due to inserts.

After determining where the new row goes between the existing rows and whether the new page is to be added before or after the original page, SQL Server has to move rows to the new page. The simplified algorithm for determining the split point is as follows :

1. Place the first row (with the lowest clustered key value) at the beginning of the first page.

2. Place the last row (with the highest clustered key value) on the second page.

3. Place the row with the next lowest clustered key value on the first page after the existing row(s).

4. Place the next-to-last row (with the second highest clustered key value) on the second page.

5. Continue alternating back and forth until the space between the two pages is balanced or one of the pages is full.

There are situations where a double split can occur. If the new row has to go between two existing rows on a page, but the new row is too large to fit on either page with any of the existing rows, a new page is added after the original. The new row is added to the new page, a second new page is added after that, and the remaining original rows are inserted into the second new page. An example of a double split is shown in Figure 33.23.

Figure 33.23. Double page split due to large row insert.

NOTE

Although page splits are expensive when they occur, they do generate free space in the split pages for future inserts into those pages. Page splits also help keep the index tree balanced as rows are added to the table. However, if you monitor the system with Performance Monitor and are seeing hundreds of page splits per second, you might want to consider rebuilding the clustered index on the table and applying a lower fill factor to provide more free space in the existing pages (see DBCC DBREINDEX earlier in this chapter). This can help improve system performance until eventually the pages fill up and start splitting again. For this reason, some shops supporting high-volume OLTP environments with a lot of insert activity rebuild the indexes with a lower fill factor on a daily basis.

Deleting Rows

What happens when rows are deleted from a table? How, and when, does SQL Server reclaim the space when data is removed from a table?

Deleting Rows from a Heap

In a heap table, SQL Server does not automatically compress the space on a page when a row is removed ”that is, the rows are not all moved up to the beginning of the page to keep all free space at the end, as SQL Server did in versions prior to 7.0. To optimize performance, SQL Server holds off on compacting the rows until the page needs contiguous space for storing a new row. You can see this with a simple example using DBCC PAGE . First create a heap table and add some rows to it. Then get the first page of the table:

 create table heaptable (a char(4))  go insert heaptable values ('row1') insert heaptable values ('row2') insert heaptable values ('row3') go exec sp_SSU_showindexpages heaptable go tablename    id          indid  indexname    root       first      firstiam ------------ ----------- ------ ------------ ---------- ---------- ---------- heaptable     1957582012      0 heaptable    1:251      1:251      1:252 go 

Now examine the row with DBCC PAGE . The following displays just the DATA and offset table section of DBCC PAGE :

 DBCC PAGE (pubs, 1, 251, 1)  go DATA: ----- Slot 0, Offset 0x60 ------------------- Record Type = PRIMARY_RECORD Record Attributes =  NULL_BITMAP 1A8CC060:  00080010  31776f72    000001           ....row1... Slot 1, Offset 0x6b ------------------- Record Type = PRIMARY_RECORD Record Attributes =  NULL_BITMAP 1A8CC06B:  00080010  32776f72    000001           ....row2... Slot 2, Offset 0x76 ------------------- Record Type = PRIMARY_RECORD Record Attributes =  NULL_BITMAP 1A8CC076:  00080010  33776f72    000001           ....row3... OFFSET TABLE: ------------- Row - Offset 2 (0x2) - 118 (0x76) 1 (0x1) - 107 (0x6b) 0 (0x0) - 96 (0x60) 

As you can see at this point, all three rows are contiguous on the page. Take note of the offset of row 3 ( Slot 2, Offset 0x76 ). Now, delete row 2 and look at the page again:

 delete heaptable where a = 'row2'  go dbcc page (pubs, 1, 251, 1) go DATA: ----- Slot 0, Offset 0x60 ------------------- Record Type = PRIMARY_RECORD Record Attributes =  NULL_BITMAP 1A8CC060:  00080010  31776f72    000001           ....row1... Slot 2, Offset 0x76 ------------------- Record Type = PRIMARY_RECORD Record Attributes =  NULL_BITMAP 1A8CC076:  00080010  33776f72    000001           ....row3... OFFSET TABLE: ------------- Row - Offset 2 (0x2) - 118 (0x76) 1 (0x1) - 0 (0x0) 0 (0x0) - 96 (0x60) 

You can see that row 2 no longer exists in the page, but row 3 remained where it was ( Slot 2, Offset 0x76 ). The offset for row 2 (Slot 1) has been set to 0 to indicate there is no row in that slot currently.

Deleting Rows from an Index

Because the data pages of a clustered table are actually the leaf pages of the clustered index, the behavior of data row deletes on a clustered table is the same as row deletions from an index page.

When rows are deleted from the leaf level of an index, they are not actually deleted but marked as ghost records. Keeping the row as a ghost record makes it easier for SQL Server to perform key-range locking (key-range locking is discussed in Chapter 38, "Locking and Performance"). If ghost records were not used, SQL Server would have to lock the entire range surrounding the deleted record. With the ghost record still present and visible internally to SQL Server (it is not visible in query result sets), SQL Server can use the ghost record as an endpoint for the key-range lock to prevent "phantom" records with the same key value from being inserted, while allowing inserts of other values to proceed.

Ghost records do not stay around forever, though. SQL Server has a special internal housekeeping process that periodically examines the leaf level of B-trees for ghost records and removes them. This is the same thread that performs the auto-shrink process for databases.

If you add a clustered index to the heap table in the previous example and then delete a row, you can see the ghost record with DBCC PAGE , as shown in Listing 33.6.

Listing 33.6 Viewing a Ghost Record for a Delete from a Clustered Table

 create clustered index CI_heaptable on heaptable (a) go /* get the new page information sp_SSU_showindexpages heaptable go tablename    id          indid  indexname    root       first      firstiam ------------ ----------- ------ ------------ ---------- ---------- ---------- heaptable     1957582012      1 CI_heaptable 1:256      1:254      1:255 begin tran delete heaptable where a = 'row1' /* do not commit the transaction before running DBCC PAGE ** or the ghost record by get cleaned up by the housekeeper ** process first */ dbcc page (pubs, 1, 254, 1) go DATA: ----- Slot 0, Offset 0x60 ------------------- Record Type = GHOST_DATA_RECORD Record Attributes =  NULL_BITMAP 1A8DC060:  0008001c  31776f72    000001           ....row1... Slot 1, Offset 0x6b ------------------- Record Type = PRIMARY_RECORD Record Attributes =  NULL_BITMAP 1A8DC06B:  00080010  33776f72    000001           ....row3... OFFSET TABLE: ------------- Row - Offset 1 (0x1) - 107 (0x6b) 0 (0x0) - 96 (0x60) 

You can see in Listing 33.6 that row1 now has a record type of GHOST_DATA_RECORD . After the transaction is committed, the row can be removed by the housekeeper process. To see the total number of ghost records in a table, you can turn on trace flag 2514 and run DBCC CHECKTABLE , as in the following example:

 DBCC TRACEON(2514)  DBCC CHECKTABLE (heaptable) go DBCC execution completed. If DBCC printed error messages, contact your  system administrator. DBCC results for 'heaptable'. There are 1 rows in 1 pages for object 'heaptable'. Ghost Record count = 1 DBCC execution completed. If DBCC printed error messages, contact your  system administrator. 

Whenever you delete a row, all nonclustered indexes need to be updated to remove the pointers to the deleted row. Nonleaf index rows are not ghosted when deleted. Like heap tables, however, the space is not compressed on the nonleaf index page until needed.

Reclaiming Space

Only when the last row is deleted from a data page is the page deallocated from the table. The only exception is if it is the last page remaining ”all tables have to have at least one page allocated, even if it's empty. When a deletion of an index row leaves only one row remaining on the page, the remaining row is moved to a neighboring page, and the now empty index page is deallocated.

If the page to be deallocated is the last remaining used page in a uniform extent allocated to the table, the extent is deallocated from the table as well.

Updating Rows

Versions of SQL Server prior to 7.0 supported deferred updates. With deferred updates, the rows to be modified were copied to the transaction log as no-op records. The records were then rescanned in the log and the changes applied back to the actual table. This was a log- intensive and expensive type of update.

SQL Server 2000 does not perform deferred updates. Due to the way SQL Server now maintains clustered indexes, all updates can be done directly without using the transaction log as a holding area.

However, there are two types of direct updates that SQL Server can perform:

• In-place updates

• Not-in-place updates

In-Place Updates

In SQL Server 2000, in-place updates are performed as often as possible to minimize the overhead of an update. An in-place update means that the row is modified where it is on the page and only the affected bytes are changed. In versions of SQL Server prior to 7.0, in-place updates were almost the exception rather than the norm.

When an in-place update is performed, in addition to the reduced overhead in the table itself, only a single modify record is written to the log. However, if the table has a trigger on it or is marked for replication, the update is still done in place but is recorded in the log as a delete followed by an insert (this provides the before-and-after image for the trigger that is referenced in the inserted and deleted tables).

In-place updates are performed whenever a heap is being updated or when a clustered table is updated, but the clustered key itself is not changed. You can get an in-place update if the clustered key changes but the row does not have to move ”that is, the sorting of the rows wouldn't change.

Not-In-Place Updates

If the change to a clustered key prevents an in-place update from being performed, or if the modification to a row increases its size such that it can no longer fit on its current page, the update will be performed as a delete followed by an insert ”this is referred to as a not-in-place update.

When performing an update that affects multiple index keys, SQL Server keeps a list of the rows that need to be updated in memory, if it's small enough; otherwise , it is stored in tempdb . SQL Server then sorts the list by index key and type of operation (delete or insert). This list of operations, called the input stream, consists of both the old and new values for every column in the affected rows as well as the unique row identifier for each row.

SQL Server then examines the input stream to determine whether any of the updates conflict or would generate duplicate key values while processing (if they were to generate a duplicate key after processing, the update cannot proceed), and rearranges the operations in the input stream in a manner to prevent any intermediate violations of the unique key.

For example, consider the following update to a table with a unique key on a sequential primary key:

 update table1 set pkey = pkey + 1 

Even though all values would still be unique when the update finished, if the update were performed internally one row at a time in sequential order, it would generate duplicates during the intermediate processing as the pkey value was incremented and matched the next pkey value. SQL Server would rearrange and rework the updates in the input stream to process them in a manner that would avoid the duplicates and then process them a row at a time. If possible, deletes and inserts on the same key value in the input stream are collapsed into a single update. In some cases, you might still get some rows that can be updated in place.

Forward Pointers

As mentioned earlier, when page splits on a clustered table occur, the nonclustered indexes do not need to be updated to reflect the new location of the rows because the bookmark to the row is the clustered index key rather than the row pointer. When an update operation on a heap table causes rows to move, the row pointers in the nonclustered index would need to be updated to reflect the new location or the rows. This could be expensive if there were a larger number of nonclustered indexes on the heap.

SQL Server 2000 addresses this performance issue through the use of forward pointers. When a row in a heap moves, it leaves a forward pointer in the original location of the row. The forward pointer avoids having to update the nonclustered index pointer to the row. When SQL Server is searching for the row via the nonclustered index, the index pointer directs it to the original location where the forward pointer redirects it to the new row location.

A row never has more than one forward pointer. If the row moves again from its forwarded location, the forward pointer stored at the original row location is updated to the row's new location. There is never a forward pointer that points to another forward pointer. If the row ever shrinks enough to fit back into its original location, the forward pointer is removed, and the row is put back where it originated.

When a forward pointer is created, it remains unless the row moves back to its original location. The only other circumstance that results in forward pointers being deleted is when the entire database is shrunk. When a database file is shrunk and the data reorganized, all bookmarks are reassigned because the rows are moved to new pages.

To view the forward pointers for a table, you can enable trace flag 2509 . When you run DBCC CHECKTABLE , it displays the number of forwarded records in the table.