Fragmentation occurs when data is modified in a table. When you insert or update data in a table (via INSERT or UPDATE), the table's corresponding clustered indexes and the affected nonclustered indexes are modified. This can cause an index leaf page split if the modification to an index can't be accommodated in the same page. A new leaf page will then be added that contains part of the original page and maintains the logical order of the rows in the index key. Although the new leaf page maintains the logical order of the data rows in the original page, this new page usually won't be physically adjacent to the original page on the disk. Or, put a slightly different way, the logical key order of the index doesn't match the physical order within the file.

For example, suppose an index has nine key values (or index rows) and the average size of the index rows allows a maximum of four index rows in a leaf page. As explained in Chapter 4, the 8KB leaf pages are connected to the previous and next leaf pages to maintain the logical order of the index. Figure 8-1 illustrates the layout of the leaf pages for the index.

Figure 8.1. Leaf pages layout

Since the index key values in the leaf pages are always sorted, a new index row with a key value of 25 has to occupy a place between the existing key values 20 and 30. Because the leaf page containing these existing index key values is full with the four index rows, the new index row will cause the corresponding leaf page to split. A new leaf page will be assigned to the index, and part of the first leaf page will be moved to this new leaf page so that the new index key can be inserted in the correct logical order. The links between the index pages will also be updated so that the pages are logically connected in the order of the index. As shown in Figure 8-2, the new leaf page, even though linked to the other pages in the correct logical order, can be physically out of order.

Figure 8.2. Out-of-order leaf pages

The pages are grouped together in bigger units called extents, which can contain eight pages. SQL Server uses an extent as a physical unit of allocation on the disk. Ideally, the physical order of the extents containing the leaf pages of an index should be the same as the logical order of the index. This reduces the number of switches required between extents when retrieving a range of index rows. However, page splits can physically disorder the pages within the extents, and they can also physically disorder the extents themselves. For example, suppose the first two leaf pages of the index are in extent 1, and say the third leaf page is in extent 2. If extent 2 contains free space, then the new leaf page allocated to the index because of the page split will be in extent 2, as shown in Figure 8-3.

Figure 8.3. Out-of-order leaf pages distributed across extents

With the leaf pages distributed between two extents, ideally you expect to read a range of index rows with a maximum of one switch between the two extents. However, the disorganization of pages between the extents can cause more than one extent switch while retrieving a range of index rows. For example, to retrieve a range of index rows between 25 and 90, you will need three extent switches between the two extents, as follows:

This type of fragmentation is called external fragmentation. External fragmentation is always undesirable.

Fragmentation can also happen within an index page. If an INSERT or UPDATE operation creates a page split, then free space will be left behind in the original leaf page. Free space can also be caused by a DELETE operation. The net effect is to reduce the number of rows included in a leaf page. For example, in Figure 8-3, the page split caused by the INSERT operation has created an empty space within the first leaf page. This is known as internal fragmentation.

For a highly transactional database, it is desirable to deliberately leave some free space within your leaf pages so that you can add new rows, or change the size of existing rows, without causing a page split. In Figure 8-3, the free space within the first leaf page allows an index key value of 26 to be added to the leaf page without causing a page split.

SQL Server 2008 exposes the leaf pages and other data through a dynamic management view called sys.dm_db_index_physical_stats. It stores both the index size and the fragmentation. I'll cover it in more detail in the next section. The DMV is much easier to work with than DBCC SHOWCONTIG.

Let's now take a look at the mechanics of fragmentation.

Page Split by an UPDATE Statement

To show what happens when a page split is caused by an UPDATE statement, I'll use a constructed table for an example. This small test table will have a clustered index, which orders the rows within one leaf (or data) page as follows (you'll find this code in create_t1.sql in the code download):

IF(SELECT OBJECT_ID('t1')) IS NOT NULL
  DROP TABLE t1
GO

CREATE TABLE t1(c1 INT, c2 CHAR(999), c3 VARCHAR(10))
INSERT INTO t1 VALUES(100, 'c2', '')
INSERT INTO t1 VALUES(200, 'c2', '')
INSERT INTO t1 VALUES(300, 'c2', '')
INSERT INTO t1 VALUES(400, 'c2', '')
INSERT INTO t1 VALUES(500, 'c2', '')
INSERT INTO t1 VALUES(600, 'c2', '')
INSERT INTO t1 VALUES(700, 'c2', '')
INSERT INTO t1 VALUES(800, 'c2', '')

CREATE CLUSTERED INDEX i1 ON t1(c1)

The average size of a row in the clustered index leaf page (excluding internal overhead) is not just the sum of the average size of the clustered index columns; it's the sum of the average size of all the columns in the table, since the leaf page of the clustered index and the data page of the table are the same. Therefore, the average size of a row in the clustered index is as follows:

= (Average size of [c1]) + (Average size of [c2]) + (Average size of [c3]) bytes

= (Size of INT) + (Size of CHAR(999)) + (Average size of data in [c3]) bytes

= 4 + 999 + 0 = 1,003 bytes

The maximum size of a row in SQL Server is 8,060 bytes. Therefore, if the internal overhead is not very high, all eight rows can be accommodated in a single 8KB page.

To determine the number of leaf pages assigned to the i1 clustered index, execute the SELECT statement against sys.dm_db_index_physical_stats:

SELECT  s.avg_fragmentation_in_percent
       ,s.fragment_count
       ,s.page_count
       ,s.avg_page_space_used_in_percent
       ,s.record_count
       ,avg_record_size_in_bytes
FROM    sys.dm_db_index_physical_stats(DB_ID('AdventureWorks2008'),
                                       OBJECT_ID(N'dbo.t1'), NULL, NULL,
                                       'Sampled') AS s

You can see the results of this query in Figure 8-4.

Figure 8.4. Physical layout of index i1

From the page_count column in this output, you can see that the number of pages assigned to the clustered index is 1. You can also see the average space used, 100, in the avg_page_space_used_in_percent column. From this you can infer that the page has no free space left to expand the content of c3, which is of type VARCHAR(10) and is currently empty.

Note

I'll analyze more of the information provided by sys.dm_db_index_physical_stats in the "Analyzing the Amount of Fragmentation" section later in this chapter.

Therefore, if you attempt to expand the content of column c3 for one of the rows as follows, it should cause a page split:

UPDATE  t1
SET     c3 = 'Add data'
WHERE   c1 = 200

Selecting the data from sys.dm_db_index_physical_stats results in the information in Figure 8-5.

Figure 8.5. i1 index after a data update

From the output in Figure 8-5, you can see that SQL Server has added a new page to the index. On a page split, SQL Server generally moves half the total number of rows in the original page to the new page. Therefore, the rows in the two pages are distributed as shown in Figure 8-6.

Figure 8.6. Page split caused by an UPDATE statement

From the preceding tables, you can see that the page split caused by the UPDATE statement results in an internal fragmentation of data in the leaf pages. If the new leaf page can't be written physically next to the original leaf page, there will be external fragmentation as well. For a large table with a high amount of fragmentation, a larger number of leaf pages will be required to hold all the index rows.

To confirm the resultant distribution of rows shown in the previous pages, you can add three trailing rows to the first leaf page and four trailing rows to the second page (t1_insert.sql in the download):

INSERT INTO t1 VALUES(410, 'c2', '')
INSERT INTO t1 VALUES(420, 'c2', '')
INSERT INTO t1 VALUES(430, 'c2', '')
INSERT INTO t1 VALUES(900, 'c2', '')
INSERT INTO t1 VALUES(1000, 'c2', '')
INSERT INTO t1 VALUES(1100, 'c2', '')
INSERT INTO t1 VALUES(1200, 'c2', '')

These seven new rows are accommodated in the existing two leaf pages without causing a page split. You can confirm this by querying sys.dm_db_index_physical_stats again (Figure 8-7).

Figure 8.7. Pages after the addition of more rows

Page Split by an INSERT Statement

To understand how a page split can be caused by an INSERT statement, create the same test table (create_t1.sql) as you did previously, with the eight initial rows and the clustered index. Since the single index leaf page is completely filled, any attempt to add an intermediate row as follows should cause a page split in the leaf page:

INSERT INTO t1 VALUES(110, 'c2', '')

You can verify this by examining the output of sys.dm_db_index_physical_stats (Figure 8-8).

Figure 8.8. Pages after insert

As explained previously, half the rows from the original leaf page are moved to the new page. Once space is cleared in the original leaf page, the new row is added in the appropriate order to the original leaf page. Be aware that a row is associated with only one page; it cannot span multiple pages. Figure 8-9 shows the resultant distribution of rows in the two pages

Figure 8.9. Page split caused by an INSERT statement

From the previous index pages, you can see that the page split caused by the INSERT statement spreads the rows sparsely across the leaf pages, causing internal fragmentation. It often causes external fragmentation also, since the new leaf page may not be physically adjacent to the original page. For a large table with a high amount of fragmentation, the page splits caused by the INSERT statement will require a larger number of leaf pages to accommodate all the index rows.

To verify the row distribution shown in the index pages, you can run t1_insert.sql again, adding three more rows to the first page and four more rows to the second page:

INSERT INTO t1 VALUES(120, 'c2', '')
INSERT INTO t1 VALUES(130, 'c2', '')
INSERT INTO t1 VALUES(140, 'c2', '')
INSERT INTO t1 VALUES(900, 'c2', '')
INSERT INTO t1 VALUES(1000, 'c2', '')
INSERT INTO t1 VALUES(1100, 'c2', '')
INSERT INTO t1 VALUES(1200, 'c2', '')

The result is the same as for the previous example: these seven new rows can be accommodated in the two existing leaf pages without causing any page split. Note that in the first page, new rows are added in between the other rows in the page. This won't cause a page split, since free space is available in the page.

What about when you have to add rows to the trailing end of an index? In this case, even if a new page is required, it won't split any existing page. For example, adding a new row with c1 equal to 1,300 will require a new page, but it won't cause a page split since the row isn't added in an intermediate position. Therefore, if new rows are added in the order of the clustered index, then the index rows will be always added at the trailing end of the index, preventing the page splits otherwise caused by the INSERT statements.

Fragmentation caused by page splits hurts data-retrieval performance, as you will see next.

Both internal and external fragmentations adversely affect data-retrieval performance. External fragmentation causes a noncontiguous sequence of index pages on the disk, with new leaf pages far from the original leaf pages, and their physical ordering different from their logical ordering. Consequently, a range scan on an index will need more switches between the corresponding extents than ideally required, as explained earlier in the chapter. Also, a range scan on an index will be unable to benefit from read-ahead operations performed on the disk. If the pages are arranged contiguously, then a read-ahead operation can read pages in advance without much head movement.

For better performance, it is preferable to use sequential I/O, since this can read a whole extent (eight 8KB pages together) in a single disk I/O operation. By contrast, a noncontiguous layout of pages requires nonsequential or random I/O operations to retrieve the index pages from the disk, and a random I/O operation can read only 8KB of data in a single disk operation (this may be acceptable, however, if you are retrieving only one row).

In the case of internal fragmentation, rows are distributed sparsely across a large number of pages, increasing the number of disk I/O operations required to read the index pages into memory and increasing the number of logical reads required to retrieve multiple index rows from memory. As mentioned earlier, even though it increases the cost of data retrieval, a little internal fragmentation can be beneficial, because it allows you to perform INSERT and UPDATE queries without causing page splits. For queries that don't have to traverse a series of pages to retrieve the data, fragmentation can have minimal impact.

To understand how fragmentation affects the cost of a query, create a test table with a clustered index, and insert a highly fragmented data set in the table. Since an INSERT operation in between an ordered data set can cause a page split, you can easily create the fragmented data set by adding rows in the following order (create_t1_fragmented.sql in the code download):

IF (SELECT  OBJECT_ID('t1')
   ) IS NOT NULL
    DROP TABLE t1
GO
CREATE TABLE t1
    (c1 INT
    ,c2 INT
    ,c3 INT
    ,c4 CHAR(2000))
CREATE CLUSTERED INDEX i1 ON t1 (c1) ;
WITH    Nums
          AS (SELECT    1 AS n
              UNION ALL
              SELECT    n + 1
              FROM      Nums
              WHERE     n < 21
             )
    INSERT  INTO t1 (c1, c2, c3, c4)
            SELECT  n
                   ,n
                   ,n
                   ,'a'
            FROM    Nums ;
WITH    Nums
          AS (SELECT    1 AS n
              UNION ALL
              SELECT    n + 1
              FROM      Nums
              WHERE     n < 21
             )
    INSERT  INTO t1 (c1, c2, c3, c4)
            SELECT  41 - n
                   ,n
                   ,n
                   ,'a'
            FROM    Nums

To determine the number of logical reads required to retrieve a small result set and a large result set from this fragmented table, execute the two SELECT statements with STATISTICS IO and TIME set to ON (statistics.sql in the download):

SELECT * FROM t1 WHERE c1 BETWEEN 21 AND 25 --Reads 6 rows
SELECT * FROM t1 WHERE c1 BETWEEN 1 AND 40  --Reads all rows

The number of logical reads performed by the individual queries is, respectively, as follows:

Table 't1'. Scan count 1, logical reads 6
CPU time = 0 ms,  elapsed time = 28 ms.
Table 't1'. Scan count 1, logical reads 15
CPU time = 0 ms,  elapsed time = 260 ms.

To evaluate how the fragmented data set affects the number of logical reads, rearrange the index leaf pages physically by rebuilding the clustered index:

ALTER INDEX i1 ON dbo.t1 REBUILD

With the index leaf pages rearranged in the proper order, rerun statistics.sql. The number of logical reads required by the preceding two SELECT statements reduces to 5 and 13, respectively:

Table 't1'. Scan count 1, logical reads 5
CPU time = 0 ms,  elapsed time = 30 ms.
Table 't1'. Scan count 1, logical reads 13
CPU time = 0 ms,  elapsed time = 219 ms.

Notice, though, that the execution time wasn't radically reduced, because dropping a single page from the read just isn't likely to increase speed much. The cost overhead because of fragmentation usually increases in line with the number of rows retrieved, because this involves reading a greater number of out-of-order pages. For point queries (queries retrieving only one row), fragmentation doesn't usually matter, since the row is retrieved from one leaf page only, but this isn't always the case. Because of the internal structure of the index, fragmentation may increase the cost of even a point query. For instance, the following SELECT statement (singlestat.sql in the download) performs two logical reads with the leaf pages rearranged properly, but it requires three logical reads on the fragmented data set. To see this in action, run create_t1_fragmented.sql again. Now run this query with STATISTICS IO and TIME enabled:

SELECT * FROM t1 WHERE c1 = 10 --Read 1 row

The resulting message in the query window for this script is as follows:

Table 't1'. Scan count 1, logical reads 3
CPU time = 0 ms,  elapsed time = 0 ms.

Once more, rebuild the index using this script:

ALTER INDEX i1 ON dbo.t1 REBUILD

Running the earlier SELECT statement again results in the following output:

Table 't1'. Scan count 1, logical reads 2
CPU time = 0 ms,  elapsed time = 0 ms.

Remember, this test is on a very small scale, but the number of reads was decreased by a third. Imagine what reducing a third of the number of reads against a table with millions of rows could accomplish.

You can analyze the fragmentation ratio of an index by using the sys.dm_db_index_physical_stats dynamic management function. For a table with a clustered index, the fragmentation of the clustered index is congruous with the fragmentation of the data pages, since the leaf pages of the clustered index and data pages are the same. sys.dm_db_index_physical_stats also indicates the amount of fragmentation in a heap table (or a table with no clustered index). Since a heap table doesn't require any row ordering, the logical order of the pages isn't relevant for the heap table.

The output of sys.dm_db_index_physical_stats shows information on the pages and extents of an index (or a table). A row is returned for each level of the B-tree in the index. A single row for each allocation unit in a heap is returned. As explained earlier, in SQL Server, eight contiguous 8KB pages are grouped together in an extent that is 64KB in size. For very small tables (much less than 64KB), the pages in an extent can belong to more than one index or table—these are called mixed extents. If there are too many small tables in the database, mixed extents help SQL Server conserve disk space.

As a table (or an index) grows and requests more than eight pages, SQL Server creates an extent dedicated to the table (or index) and assigns the pages from this extent. Such an extent is called a uniform extent, and it serves up to eight page requests for the same table (or index). Uniform extents help SQL Server lay out the pages of a table (or an index) contiguously. They also reduce the number of page creation requests by an eighth, since a set of eight pages is created in the form of an extent.

To analyze the fragmentation of an index, let's re-create the table with the fragmented data set used in the "Fragmentation Overhead" section (create_t1_fragmented.sql). You can obtain the fragmentation detail of the clustered index (Figure 8-10) by executing the query against the sys.dm_db_index_physical_stats dynamic view used earlier:

SELECT  s.avg_fragmentation_in_percent
       ,s.fragment_count
       ,s.page_count
       ,s.avg_page_space_used_in_percent
       ,s.record_count
       ,avg_record_size_in_bytes
FROM    sys.dm_db_index_physical_stats(DB_ID('AdventureWorks2008'),
                                       OBJECT_ID(N'dbo.t1'), NULL, NULL,
                                       'Sampled') AS s

Figure 8.10. Fragmented statistics

The dynamic management function sys.dm_db_index_physical_stats scans the pages of an index to return the data. You can control the level of the scan, which affects the speed and the accuracy of the scan. To quickly check the fragmentation of an index, use the Limited option. You can obtain an increased accuracy with only a moderate decrease in speed by using the Sample option, as in the previous example, which scans 1 percent of the pages. For the most accuracy, use the Detailed scan, which hits all the pages in an index. If the index has fewer than 10,000 pages and you select the Sample mode, then the Detailed mode is used instead. This means that despite the choice made in the earlier query, the Detailed scan mode was used.

By defining the different parameters, you can get fragmentation information on different sets of data. By removing the OBJECT_ID function in the earlier query and supplying a NULL value, the query would return information on all indexes within the database. You can also specify the index you want information on or even the partition with a partitioned index.

The output from sys.dm_db_index_physical_stats includes 21 different columns. I selected the basic set of columns used to determine the fragmentation and size of an index. This output represents the following:

Running sys.dm_db_index_physical_stats with a Detailed scan will return multiple rows for a given index. That is, multiple rows are displayed if that index spans more than one level. Multiple levels exist in an index when that index spans more than a single page. To see what this looks like and to observe some of the other columns of data present in the dynamic management function, run the query this way:

SELECT  s.*
FROM    sys.dm_db_index_physical_stats(DB_ID('AdventureWorks2008'),
                                       OBJECT_ID(N'dbo.t1'), NULL, NULL,
                                       'Detailed') AS s

To make the data readable, I've broken down the resulting data table into three pieces in a single graphic; see Figure 8-11.

Figure 8.11. Detailed scan of fragmented index

As you can see, two rows were returned, representing the leaf level of the index (index_level = 0) and representing the first level of the B-tree (index_level = 1), which is the second row. You can see the additional information offered by sys.dm_db_index_physical_stats that can provide more detailed analysis of your indexes. For example, you can see the minimum and maximum record sizes, as well as the index depth (the number of levels in the B-tree) and how many records are on each level. A lot of this information will be less useful for basic fragmentation analysis, which is why I chose to limit the number of columns in the samples as well as use the Sampled scan mode.

Analyzing the Fragmentation of a Small Table

Don't be overly concerned with the output of sys.dm_db_index_physical_stats for small tables. For a small table or index with fewer than eight pages, SQL Server uses mixed extents for the pages. For example, if a table (SmallTable1 or its clustered index) contains only two pages, then SQL Server allocates the two pages from a mixed extent instead of dedicating an extent to the table. The mixed extent may contain pages of other small tables/indexes also, as shown in Figure 8-12.

Figure 8.12. Mixed extent

The distribution of pages across multiple mixed extents may lead you to believe that there is a high amount of external fragmentation in the table or the index, when in fact this is by design in SQL Server and is therefore perfectly acceptable.

To understand how the fragmentation information of a small table or index may look, create a small table with a clustered index (create_small_t1_fragmented.sql in the download):

IF(SELECT OBJECT_ID('t1')) IS NOT NULL
  DROP TABLE t1
GO
CREATE TABLE t1(c1 INT, c2 INT, c3 INT, c4 CHAR(2000))
DECLARE @n INT
SET @n = 1
WHILE @n <= 28
BEGIN
  INSERT INTO t1 VALUES(@n, @n, @n, 'a')
  SET @n = @n + 1
END
CREATE CLUSTERED INDEX i1 ON t1(c1)

In the preceding table, with each INT taking 4 bytes, the average row size is 2,012 (= 4 + 4 + 4 + 2,000) bytes. Therefore, a default 8KB page can contain up to four rows. After all 28 rows are added to the table, a clustered index is created to physically arrange the rows and reduce fragmentation to a minimum. With the minimum internal fragmentation, seven (= 28 / 4) pages are required for the clustered index (or the base table). Since the number of pages is not more than eight, SQL Server uses pages from mixed extents for the clustered index (or the base table). If the mixed extents used for the clustered index are not side by side, then the output of sys.dm_db_index_physical_stats may express a high amount of external fragmentation. But as a SQL user, you can't reduce the resultant external fragmentation. Figure 8-13 shows the output of sys.dm_db_index_physical_stats.

Figure 8.13. Fragmentation of a small clustered index

From the output of sys.dm_db_index_physical_stats, you can analyze the fragmentation of the small clustered index (or the table) as follows:

• avg_fragmentation_in_percent: Although this index may cross to multiple extents, the fragmentation shown here is not an indication of external fragmentation because this index is being stored on mixed extents.

• avg_page_space_used_in_percent: This shows that all or most of the data is stored well within the seven pages displayed in the page_count field. This eliminates the possibility of logical fragmentation.

• fragment_count: This shows that the data is fragmented and stored on more than one extent, but since it's less than eight pages long, SQL Server doesn't have much choice about where it stores the data.

In spite of the preceding misleading values, a small table (or index) with fewer than eight pages is simply unlikely to benefit from efforts to remove the fragmentation because it will be stored on mixed extents.

Once you determine that fragmentation in an index (or a table) needs to be dealt with, you need to decide which defragmentation technique to use. The factors affecting this decision, and the different techniques, are explained in the following section.

You can resolve fragmentation in an index by rearranging the index rows and pages so that their physical and logical orders match. To reduce external fragmentation, you can physically reorder the leaf pages of the index to follow the logical order of the index. You achieve this through the following techniques:

CREATE UNIQUE CLUSTERED INDEX pkcl ON t1(c1)
  WITH (DROP_EXISTING = ON)

Executing the ALTER INDEX REBUILD Statement

ALTER INDEX REBUILD rebuilds an index in one atomic step, just like CREATE INDEX with the DROP_EXISTING clause. Since ALTER INDEX REBUILD also rebuilds the index physically, it allows SQL Server to assign fresh pages to reduce both internal and external fragmentation to a minimum. But unlike CREATE INDEX with the DROP_EXISTING clause, it allows an index (supporting either the PRIMARY KEY or UNIQUE constraint) to be rebuilt dynamically without dropping and re-creating the constraints.

To understand the use of ALTER INDEX REBUILD to defragment an index, consider the fragmented table used in the "Fragmentation Overhead" and "Analyzing the Amount of Fragmentation" sections (create_t1_fragmented.sql). This table is repeated here:

IF (SELECT  OBJECT_ID('t1')
   ) IS NOT NULL
    DROP TABLE t1
GO
CREATE TABLE t1
    (c1 INT
    ,c2 INT
    ,c3 INT
    ,c4 CHAR(2000))
CREATE CLUSTERED INDEX i1 ON t1 (c1) ;

WITH    Nums
          AS (SELECT    1 AS n
              UNION ALL
              SELECT    n + 1
              FROM      Nums
              WHERE     n < 21
             )
    INSERT  INTO t1 (c1, c2, c3, c4)
            SELECT  n
                   ,n
                   ,n
                   ,'a'
            FROM    Nums ;
WITH    Nums
          AS (SELECT    1 AS n
              UNION ALL
              SELECT    n + 1
              FROM      Nums
              WHERE     n < 21
             )
    INSERT  INTO t1 (c1, c2, c3, c4)
            SELECT  41 - n
                   ,n
                   ,n
                   ,'a'
            FROM    Nums

If you take a look at the current fragmentation, you can see that it is both internally and externally fragmented (Figure 8-14).

Figure 8.14. Internal and external fragmentation

You can defragment the clustered index (or the table) by using the ALTER INDEX REBUILD statement:

ALTER INDEX i1 ON dbo.t1 REBUILD

Figure 8-15 shows the resultant output of the standard SELECT statement against sys.dm_db_index_physical_stats.

Figure 8.15. Fragmentation resolved by ALTER INDEX REBUILD

Compare the preceding results of the query in Figure 8-15 with that from the earlier results in Figure 8-14. You can see that both internal and external fragmentation have been reduced efficiently. Here's an analysis of the output:

• Internal fragmentation: The table has 42 rows with an average row size (2,019.38 bytes) that allows a maximum of four rows per page. If the rows are highly defragmented to reduce the internal fragmentation to a minimum, then there should be 11 data pages in the table (or leaf pages in the clustered index). You can observe the following in the preceding output:

  • Number of leaf (or data) pages = page_count = 11

  • Amount of defragmentation in a page = avg_page_space_used_in_percent = 95.33 percent

• External fragmentation: A minimum of two extents is required to hold the 11 pages. For a minimum of external fragmentation, there should not be any gap between the two extents, and all pages should be physically arranged in the logical order of the index. The preceding output illustrates the number of out-of-order pages = avg_fragmentation_in_percent = 27.27 percent. Although this may not be a perfect level of fragmentation, being greater than 20 percent, this is adequate considering the size of the index.

As shown previously, the ALTER INDEX REBUILD technique effectively reduces fragmentation. You can also use it to rebuild all the indexes of a table in one statement:

ALTER INDEX ALL ON dbo.t1

Although this is the most effective defragmentation technique, it does have some overhead and limitations:

• Blocking: Similar to the previous two index-rebuilding techniques, ALTER INDEX REBUILD introduces blocking in the system. It blocks all other queries trying to access the table (or any index on the table). It can also be blocked by those queries.

• Transaction rollback: Since ALTER INDEX REBUILD is fully atomic in action, if it is stopped before completion, then all the defragmentation actions performed up to that time are lost. You can run ALTER INDEX REBUILD using the ONLINE keyword, which will reduce the locking mechanisms, but it will increase the time involved in rebuilding the index.

Executing the ALTER INDEX REORGANIZE Statement

ALTER INDEX REORGANIZE reduces the fragmentation of an index without rebuilding the index. It reduces external fragmentation by rearranging the existing leaf pages of the index in the logical order of the index key. It compacts the rows within the pages, reducing internal fragmentation, and discards the resultant empty pages. This technique doesn't use any new pages for defragmentation.

To avoid the blocking overhead associated with ALTER INDEX REBUILD, this technique uses a nonatomic online approach. As it proceeds through its steps, it requests a small number of locks for a short period. Once each step is done, it releases the locks and proceeds to the next step. While trying to access a page, if it finds that the page is being used, it skips that page and never returns to the page again. This allows other queries to run on the table along with the ALTER INDEX REORGANIZE operation. Also, if this operation is stopped intermediately, then all the defragmentation steps performed up to then are preserved.

Since ALTER INDEX REORGANIZE doesn't use any new pages to reorder the index and it skips the locked pages, the amount of defragmentation provided by this approach is usually less than that of ALTER INDEX REBUILD. To observe the relative effectiveness of ALTER INDEX REORGANIZE compared to ALTER INDEX REBUILD, rebuild the test table (create_t1_fragmented.sql) used in the previous section on ALTER INDEX REBUILD.

Now, to reduce the fragmentation of the clustered index, use ALTER INDEX REORGANIZE as follows:

ALTER INDEX i1 ON dbo.t1 REORGANIZE

Figure 8-16 shows the resultant output from sys.dm_db_index_physical_stats.

Figure 8.16. Results of ALTER INDEX REORGANIZE

From the output, you can see that ALTER INDEX REORGANIZE doesn't reduce fragmentation as effectively as ALTER INDEX REBUILD, as shown in the previous section. For a highly fragmented index, the ALTER INDEX REORGANIZE operation can take much longer than rebuilding the index. Also, if an index spans multiple files, ALTER INDEX REORGANIZE doesn't migrate pages between the files. However, the main benefit of using ALTER INDEX REORGANIZE is that it allows other queries to access the table (or the indexes) simultaneously.

Table 8-1 summarizes the characteristics of these four defragmentation techniques.

Table 8.1. Characteristics of Four Defragmentation Techniques

Characteristics/Issues	Drop and Create Index	Create Index with DROP_EXISTING	ALTER INDEX REBUILD	ALTER INDEX REORGANIZE
Rebuild nonclustered indexes on clustered index fragmentation	Twice	No	No	No
Missing indexes	Yes	No	No	No
Defragment index with constraints	Highly complex	Moderately complex	Easy	Easy
Defragment multiple indexes together	No	No	Yes	Yes
Concurrency with others	Low	Low	Medium, depending on concurrent user activity	High
Intermediate cancellation	Dangerous with no transaction	Progress lost	Progress lost	Progress preserved
Degree of defragmentation	High	High	High	Moderate to low
Apply new fill factor	Yes	Yes	Yes	No
Statistics are updated	Yes	Yes	Yes	No

You can also reduce internal fragmentation by compressing more rows within a page, reducing free spaces within the pages. The maximum amount of compression that can be done within the leaf pages of an index is controlled by the fill factor, as you will see next.

When dealing with very large databases and the indexes associated, it may become necessary to split the tables and the indexes up across servers and/or disks using partitioning. Indexes on partitions can also become fragmented as the data within the partition changes. When dealing with a portioned index, you will need to determine whether you want to either REORGANIZE or REBUILD one, some, or all partitions as part of the ALTER INDEX command. Partitioned indexes cannot be rebuilt online. Keep in mind that doing anything that affects all partitions is likely to be a very costly operation.

One of the new features of SQL Server 2008 is data compression. If compression is specified on an index, even on a partitioned index, you must be sure to set the compression while performing the ALTER INDEX operation to what it was before; if you don't, it will be lost, and you'll have to rebuild the index again. This is especially important for nonclustered indexes, which will not inherit the compression setting from the table.

The internal fragmentation of an index is reduced by compressing more rows per leaf page in an index. Compressing more rows within a leaf page reduces the total number of pages required for the index and in turn decreases disk I/O and the logical reads required to retrieve a range of index rows. On the other hand, if the index key values are highly transactional, then having fully compressed index pages will cause page splits. Therefore, for a transactional table, a good balance between maximizing the number of rows in a page and avoiding page splits is required.

SQL Server allows you to control the amount of free space within the leaf pages of the index by using the fill factor. If you know that there will be enough INSERT queries on the table or UPDATE queries on the index key columns, then you can pre-add free space to the index leaf page using the fill factor to minimize page splits. If the table is read-only, you can create the index with a high fill factor to reduce the number of index pages.

The default fill factor is 0, which means the leaf pages are packed to 100 percent, although some free space is left in the branch nodes of the B-tree structure. The fill factor for an index is applied only when the index is created. As keys are inserted and updated, the density of rows in the index eventually stabilizes within a narrow range. As you saw in the previous chapter's sections on page splits caused by UPDATE and INSERT, when a page split occurs, generally half the original page is moved to a new page, which happens irrespective of the fill factor used during the index creation.

To understand the significance of the fill factor, let's use a small test table (create_t1_fill.sql in the download) with 24 rows:

IF (SELECT  OBJECT_ID('t1')
 ) IS NOT NULL
  DROP TABLE t1
GO

CREATE TABLE t1 (c1 INT, c2 CHAR(999)) ;
WITH    Nums
          AS (SELECT    1 AS n
              UNION ALL
              SELECT    n + 1
              FROM      Nums
              WHERE     n < 24
             )
    INSERT  INTO t1 (c1, c2)
            SELECT  n * 100
                   ,'a'
            FROM    Nums

Compress the maximum number of rows in the leaf (or data) page by creating a clustered index with the default fill factor:

CREATE CLUSTERED INDEX i1 ON t1(c1)

Since the average row size is 1,010 bytes, a clustered index leaf page (or table data page) can contain a maximum of eight rows. Therefore, at least three leaf pages are required for the 24 rows. You can confirm this in the sys.dm_db_index_physical_stats output shown in Figure 8-17.

Figure 8.17. Fill factor set to default value of 0

Note that avg_page_space_used_in_percent is 100 percent, since the default fill factor allows the maximum number of rows to be compressed in a page. Since a page cannot contain a part row to fill the page fully, avg_page_space_used_in_percent will be often a little less than 100 percent, even with the default fill factor.

To prevent page splits caused by INSERT and UPDATE operations, create some free space within the leaf (or data) pages by re-creating the clustered index with a fill factor as follows:

ALTER INDEX i1 ON dbo.t1 REBUILD
    WITH (
         FILLFACTOR=
         75)

Because each page has a total space for eight rows, a fill factor of 75 percent will allow six rows per page. Thus, for 24 rows, the number of leaf pages should increase to four, as in the sys.dm_db_index_physical_stats output shown in Figure 8-18.

Figure 8.18. Fill factor set to 75

Note that avg_page_space_used_in_percent is about 75 percent, as set by the fill factor. This allows two more rows to be inserted in each page without causing a page split. You can confirm this by adding two rows to the first set of six rows (c1 = 100 – 600, contained in the first page):

INSERT INTO t1 VALUES(110, 'a') --25th row
INSERT INTO t1 VALUES(120, 'a') --26th row

Figure 8-19 shows the current fragmentation.

Figure 8.19. Fragmentation after new records

From the output, you can see that the addition of the two rows has not added any pages to the index. Accordingly, avg_page_space_used_in_percent increased from 74.99 percent to 81.25 percent. With the addition of two rows to the set of the first six rows, the first page should be completely full (eight rows). Any further addition of rows within the range of the first eight rows should cause a page split and thereby increase the number of index pages to five:

INSERT INTO t1 VALUES(130, 'a') --27th row

Now sys.dm_db_index_physical_stats displays the difference in Figure 8-20.

Figure 8.20. Number of pages goes up

Note that even though the fill factor for the index is 75 percent, Avg. Page Density (full) has decreased to 67.49 percent, which can be computed as follows:

From the preceding example, you can see that the fill factor is applied when the index is created. But later, as the data is modified, it has no significance. Irrespective of the fill factor, whenever a page splits, the rows of the original page are distributed between two pages, and avg_page_space_used_in_percent settles accordingly. Therefore, if you use a nondefault fill factor, you should ensure that the fill factor is reapplied regularly to maintain its effect.

You can reapply a fill factor by re-creating the index or by using ALTER INDEX REORGANIZE or ALTER INDEX REBUILD, as was shown. ALTER INDEX REORGANIZE takes the fill factor specified during the index creation into account. ALTER INDEX REBUILD also takes the original fill factor into account, but it allows a new fill factor to be specified, if required.

Without periodic maintenance of the fill factor, for both default and nondefault fill factor settings, avg_page_space_used_in_percent for an index (or a table) eventually settles within a narrow range. Therefore, in most cases, without manual maintenance of the fill factor, the default fill factor is generally good enough.

You should also consider one final aspect when deciding upon the fill factor. Even for a heavy OLTP application, the number of database reads typically outnumbers writes by a factor of 5 to 10. Specifying a fill factor other than the default can degrade read performance by an amount inversely proportional to the fill factor setting, since it spreads keys over a wider area. Before setting the fill factor at a database-wide level, use Performance Monitor to compare the SQL Server:Buffer ManagerPage reads/sec counter to the SQL Server:Buffer ManagerPage writes/sec counter, and use the fill factor option only if writes are a substantial fraction of reads (greater than 30 percent).

In a database with a great deal of transactions, tables and indexes become fragmented over time. Thus, to improve performance, you should check the fragmentation of the tables and indexes regularly, and you should defragment the ones with a high amount of fragmentation. You can do this analysis for a database by following these steps:

A sample SQL stored procedure (IndexDefrag.sql in the download) is included here for easy reference. It performs the following actions:

Here's how to analyze and resolve database fragmentation (store this where appropriate on your system; we have a designated database for enterprise-level scripts):

CREATE PROCEDURE IndexDefrag
AS

DECLARE @DBName NVARCHAR(255)
    ,@TableName NVARCHAR(255)
    ,@SchemaName NVARCHAR(255)
    ,@IndexName NVARCHAR(255)
    ,@PctFrag DECIMAL

DECLARE @Defrag NVARCHAR(MAX)

IF EXISTS (SELECT * FROM sys.objects WHERE OBJECT_ID = OBJECT_ID(N'#Frag'))
    DROP TABLE #Frag

CREATE TABLE #Frag
(DBName NVARCHAR(255)
,TableName NVARCHAR(255)
,SchemaName NVARCHAR(255)
,IndexName NVARCHAR(255)
,AvgFragment DECIMAL)

EXEC sp_msforeachdb 'INSERT INTO #Frag (
    DBName,
    TableName,
    SchemaName,
    IndexName,
    AvgFragment
) SELECT  ''?'' AS DBName
       ,t.Name AS TableName
       ,sc.Name AS SchemaName
       ,i.name AS IndexName
       ,s.avg_fragmentation_in_percent
FROM    ?.sys.dm_db_index_physical_stats(DB_ID(''?''), NULL, NULL,
                                       NULL, ''Sampled'') AS s
        JOIN ?.sys.indexes i
        ON s.Object_Id = i.Object_id
           AND s.Index_id = i.Index_id
        JOIN ?.sys.tables t
        ON i.Object_id = t.Object_Id
        JOIN ?.sys.schemas sc
        ON t.schema_id = sc.SCHEMA_ID

WHERE s.avg_fragmentation_in_percent > 20
AND t.TYPE = ''U''
AND s.page_count > 8
ORDER BY TableName,IndexName'

DECLARE cList CURSOR
FOR SELECT * FROM #Frag

OPEN cList
FETCH NEXT FROM cList
INTO @DBName, @TableName,@SchemaName,@IndexName,@PctFrag
WHILE @@FETCH_STATUS = 0
BEGIN
    IF @PctFrag BETWEEN 20.0 AND 40.0
    BEGIN
        SET @Defrag = N'ALTER INDEX ' + @IndexName + ' ON ' + @DBName + '.' +
 @SchemaName + '.' + @TableName + ' REORGANIZE'
        EXEC sp_executesql @Defrag
        PRINT 'Reorganize index: ' + @DBName + '.' + @SchemaName + '.' + @TableName
+'.' + @IndexName
    END
    ELSE IF @PctFrag > 40.0
    BEGIN
        SET @Defrag = N'ALTER INDEX ' + @IndexName + ' ON ' + @DBName + '.' +
@SchemaName + '.' + @TableName + ' REBUILD'
        EXEC sp_executesql @Defrag
        PRINT 'Rebuild index: '+ @DBName + '.' + @SchemaName + '.' + @TableName +'.'
 + @IndexName
    END

    FETCH NEXT FROM cList
    INTO @DBName, @TableName,@SchemaName,@IndexName,@PctFrag

END
CLOSE cList
DEALLOCATE cList

DROP TABLE #Frag
GO

To automate the fragmentation analysis process, you can create a SQL Server job from SQL Server Enterprise Manager by following these simple steps:

The SQL job will automatically analyze and defragment the fragmentation of each database every Sunday at 1 a.m. Figure 8-25 shows the corresponding output of the FragmentationOutput.txt file.

Figure 8.25. FragmentationOutput.txt file output

The output shows that the job analyzed the fragmentation of the database and identified a series of indexes for defragmentation, specifically for reorganization. Subsequently, it defragments the index. The stored procedure defragmented only the database object that was highly fragmented. Thus, the next run of the SQL job generally won't identify these same indexes for defragmentation.

As you learned in this chapter, in a highly transactional database page splits caused by INSERT and UPDATE statements fragment the tables and indexes, increasing the cost of data retrieval. You can avoid these page splits by maintaining free spaces within the pages using the fill factor. Since the fill factor is applied only during index creation, you should reapply it at regular intervals to maintain its effectiveness. You can determine the amount of fragmentation in an index (or a table) using sys.dm_db_physical_stats. Upon determining a high amount of fragmentation, you can use either ALTER INDEX REBUILD or ALTER INDEX REORGANIZE, depending on the required amount of defragmentation and database concurrency.

Defragmentation rearranges the data so that its physical order on the disk matches its logical order in the table/index, thus improving the performance of queries. However, unless the optimizer decides upon an effective execution plan for the query, query performance even after defragmentation can remain poor. Therefore, it is important to have the optimizer use efficient techniques to generate cost-effective execution plans.

In the next chapter, I will delve deeply into execution plan generation and the techniques the optimizer uses to decide upon an effective execution plan.