Before we begin our journey in SQL Indexing it is important to understand how a SQL Server stores its data.

Database FileGroups and Files

A MS SQL database uses a .mdf file as the primary data file, a number of .ldf files as transaction logs, and optionally a number of .ndf files as secondary data files. These data files (.mdf and .ndf) are organized to FileGroups, for management and allocation purposes.

By default, the first group that is automatically created is called the “Primary File Group”. Each .mdf and .ndf files that are created, automatically belong to that group.

Note that the system tables and the primary data file of a database, always belong to the “Primary File Group”. The Secondary data files may be assigned to a user file group by using the FILEGROUP keyword in the CREATE or ALTER DATABASE statement.

Pages and extents

The fundamental storage unit in SQL server is the “page”. A page is always 8KB and it is allocated at the primary and secondary data files. Note that I/O operations are performed at the page level.

SQL server has to efficiently manage these pages. For that purpose it groups 8 contiguous pages in a unit called the “extent”. Note that log files are not divided into pages, as it just consists of a series of log entries.

Extent Types

Extents are subdivided in mixed and uniform extents. A uniform extent contains pages from a single object, while a mixed extent contains pages from various objects. You see, an extent can contain up to 8 pages, thus a mixed type extent can contain up to 8 different page object owners.

Pages from a new table or index are usually allocated to a mixed extent. However, SQL server will allocate a new index to a uniform extent, as long as it has enough rows to generate 8 pages.

A table or index will switch to use uniform extents, for subsequent allocations, when it grows up to a point that uses 8 pages.

Page Types

Similarly to extents, pages are subdivided into categories: data pages, index pages, large object pages and other pages.

Data pages can store all data values except for those which identified as large types, such as text, xml, varchar(max), etc. These are stored in the “large object pages”.

As SQL server data rows cannot span to multiple data pages, large types are stored to a different page. This page type is called the “large object page”. Data values identified as large types, stored in the large object pages, are referred back to the original data page by using reference pointers, as shown in the picture below.

Some data types like varchar and varbinary, while can grow large, may be stored in the original data or index page. This can happen if the row size does not exceed the 8KB page limit. SQL server can dynamically move back and forth such columns, between data page and large object page according to the row size limit.

The “Index pages” store index entries. These entries include the index keys and some additional information used by SQL server to locate the data and manage the index process.

The “Other pages” are special pages that are used by SQL server to store configuration information, like index application map, bulk changes map, etc.

Data Page Structure

A data page consists of the 96-byte page header, the data rows and the data row offsets. The page header is quite important as it stores essential information about the page. This information includes the page number, the page type, the amount of page’s free space, pointers to the previous and next pages (in case the pages are linked together) and the allocation unit ID of the page object owner.

The “row offsets table” contains a 2-byte information about each row in the table. Consisting of the row number and the row offset byte address in the page. As the first element in a page is always the 96-byte header, the first row in the page is always at byte offset 96.

For example, when a page has 3 rows, which are 30 byte long (including overhead), the second row will be at offset 96+30=126 and the third at 126+30=156.

Non-clustered indexes and data page relationship

The row offset information is particularly important in the case of non-clustered indexes, because such indexes may store a pointer to the data rows in their leaf-level index pages. This pointer is called row ID (RID) and includes information about the file ID, the page ID and the row ID.

Each time a non-clustered index refers to a row by RID, it is going to ask for a row number, at a specific page (ID) in a specific file (ID). At this point SQL server is going to refer to the row offset table to retrieve the desired row by using the byte offset of the desired row.

Thanks to the offset table, a row can change position in a page without the need to change the RID in a non-clustered index. For example, you delete the ROW0. In such case the SQL server may move ROW2 to ROW0 to keep the contiguous of free space. The ID of ROW2 would remain the same, while the byte offset would change from 156 to 96 to reflect the row movement to the different slot in the data page.

Indexes and index page performance

Indexes are stored in index pages, separately from data pages. This is helpful because indexes can be allocated to different FileGroups, and even stored to different physical HDDs, to improve performance.

As I/O operations perform at the page level, it is important for an index to allocate as many rows as possible per index page. To achieve this you need to consider the index column type and the number of columns in a composite index. For that reason it is best to use narrow index keys like INT instead of larger ones. Also, consider splitting large composite keys to smaller chunks, whenever possible, to accommodate more rows in an index page.

Index page splitting can cause index page fragmentation resulting in reduced performance. Thus it is important to consider index defragmentation. Data page splitting can also affect index performance, particularly in non-clustered indexes, because of the bookmarking at the leaf level of the index.

Consider the following example. You want to retrieve column A, B, C and D from Table T1 and you have a non-clustered index on column B. While fetching the data, SQL server is looking at your index and decides to use it, to filter the returning data. For each matching row in the index, SQL has to jump back to the data page to retrieve column A, C and D. If there is a page split on the data pages, SQL has to do one more jump to the next page to successfully retrieve all rows.