Expert SQL Server Transactions and Locking: Concurrency Internals for SQL Server Practitioners

By Dmitri Korotkevitch

Master SQL Server’s Concurrency Model so you can implement high-throughput systems that deliver transactional consistency to your application customers. This book explains how to troubleshoot and address blocking problems and deadlocks, and write code and design database schemas to minimize concurrency issues in the systems you develop.
SQL Server’s Concurrency Model is one of the least understood parts of the SQL Server Database Engine. Almost every SQL Server system experiences hard-to-explain concurrency and blocking issues, and it can be extremely confusing to solve those issues without a base of knowledge in the internals of the Engine. While confusing from the outside, the SQL Server Concurrency Model is based on several well-defined principles that are covered in this book.
Understanding the internals surrounding SQL Server’s Concurrency Model helps you build high-throughput systems in multi-user environments. This book guides you through the Concurrency Model and elaborates how SQL Server supports transactional consistency in the databases. The book covers all versions of SQL Server, including Microsoft Azure SQL Database, and it includes coverage of new technologies such as In-Memory OLTP and Columnstore Indexes.

What You'll Learn

• Know how transaction isolation levels affect locking behavior and concurrency
  
• Troubleshoot and address blocking issues and deadlocks
  
• Provide required data consistency while minimizing concurrency issues
  
• Design efficient transaction strategies that lead to scalable code
  
• Reduce concurrency problems through good schema design
  
• Understand concurrency models for In-Memory OLTP and Columnstore Indexes
  
• Reduce blocking during index maintenance, batch data load, and similar tasks
  

Who This Book Is For
SQL Server developers, database administrators, and application architects who are developing highly-concurrent applications. The book is for anyone interested in the technical aspects of creating and troubleshooting high-throughput systems that respond swiftly to user requests.

• Language: English
• Publisher: Apress
• Release date: Oct 8, 2018
• ISBN: 9781484239575

Book preview

© Dmitri Korotkevitch 2018

Dmitri KorotkevitchExpert SQL Server Transactions and Lockinghttps://doi.org/10.1007/978-1-4842-3957-5_1

1. Data Storage and Access Methods

Dmitri Korotkevitch¹ 

(1)

Land O Lakes, Florida, USA

It is impossible to grasp the SQL Server concurrency model without understanding how SQL Server stores and accesses the data. This knowledge helps you to comprehend various aspects of locking behavior in the system, and it is also essential when troubleshooting concurrency issues.

Nowadays, SQL Server and Microsoft Azure SQL Databases support three different technologies that dictate how data is stored and manipulated in the system. The classic Storage Engine implements row-based storage. This technology persists the data in disk-based tables, combining all columns from a table together into data rows. The data rows, in turn, reside on 8 KB data pages, each of which may have one or multiple rows.

Starting with SQL Server 2012, you can store data in a columnar format using columnstore indexes. SQL Server splits the data into row groups of up to 1,048,576 rows each. The data in the row group is combined and stored on a per-column rather than a per-row basis. This format is optimized for reporting and analytics queries.

Finally, the In-Memory OLTP Engine, introduced in SQL Server 2014, allows you to define memory-optimized tables, which keep all data entirely in memory. The data rows in memory are linked to the data row chains through the memory pointers. This technology is optimized for heavy OLTP workload.

We will discuss locking behavior in In-Memory OLTP and columnstore indexes later in the book, after we cover the concurrency model of the classic Storage Engine. This knowledge is a cornerstone of understanding how SQL Server behaves in a multi-user environment.

The goal of this chapter is to give a high-level overview of row-based storage in SQL Server. It will explain how SQL Server stores the data in disk-based tables, illustrate the structure of B-Tree indexes, and demonstrate how SQL Server accesses data from them.

You should not consider this chapter as a deep dive into the SQL Server Storage Engine. It should provide, however, enough information to discuss the concurrency model in SQL Server.

Anatomy of a Table

The internal structure of a disk-based table is rather complex and consists of multiple elements and internal objects, as shown in Figure 1-1.

../images/463519_1_En_1_Chapter/463519_1_En_1_Fig1_HTML.jpg

Figure 1-1

Internal structure of a table

The data in the tables is stored either completely unsorted (those tables are called heap tables or heaps) or sorted according to the value of a clustered index key when a table has such an index defined.

In addition to a single clustered index, every table may have a set of nonclustered indexes. These indexes are separate data structures that store a copy of the data from a table sorted according to index key column(s). For example, if a column was included in three nonclustered indexes, SQL Server would store that data four times—once in a clustered index or heap and in each of the three nonclustered indexes.

You can create either 250 or 999 nonclustered indexes per table, depending on SQL Server version. However, it is clearly not a good idea to create a lot of them due to the overhead they introduce. In addition to storage overhead, SQL Server needs to insert or delete data from each nonclustered index during data modifications. Moreover, the update operation requires SQL Server to modify data in every index in which updated columns were present.

Internally, each index (and heap) consists of one or multiple partitions. Every partition, in a nutshell, is an internal data structure (index or heap) independent from other partitions in the object. SQL Server allows the use of a different partition strategy for every index in the table; however, in most cases, all indexes are partitioned in the same way and aligned with each other.

Note

Every table/index in SQL Server is partitioned. Non-partitioned tables are treated as single-partition tables/indexes internally.

As I already mentioned, the actual data is stored in data rows on 8 KB data pages with 8,060 bytes available to users. The pages that store users’ data may belong to three different categories called allocation units based on the type of data they store.

IN_ROW_DATA allocation unit pages store the main data row objects, which consist of internal attributes and the data from fixed-length columns, such as int, datetime, float, and others. The in-row part of a data row must fit on a single data page and, therefore, cannot exceed 8,060 bytes. The data from variable-length columns, such as (n)varchar(max), (n)varbinary(max), xml, and others, may also be stored in-row in the main row object when it fits into this limit.

In cases when variable-length data does not fit in-row, SQL Server stores it off-row on different data pages, referencing them through in-row pointers. Variable-length data that exceeds 8,000 bytes is stored on LOB_DATA allocation unit data pages (LOB stands for large objects). Otherwise, the data is stored in ROW_OVERFLOW_DATA allocation unit pages.

Let’s look at an example and create a table that contains several fixed- and variable-length columns and insert one row there, as shown in Listing 1-1.

create table dbo.DataRows

(

    ID int not null,

    ADate datetime not null,

    VarCol1 varchar(max),

    VarCol2 varchar(5000),

    VarCol3 varchar(5000)

);

insert into dbo.DataRows(ID, ADate, VarCol1, VarCol2, VarCol3)

values

(

    1

    ,'1974-08-22'

    ,replicate(convert(varchar(max),'A'),32000)

    ,replicate(convert(varchar(max),'B'),5000)

    ,replicate(convert(varchar(max),'C'),5000)

);

Listing 1-1

Data row storage: Creating the test table

The data from fixed-length columns (ID, ADate) will be stored in-row on an IN_ROW_DATA allocation unit page. The data from VarCol1 column is 32,000 bytes and will be stored on LOB_DATA data pages.

The VarCol2 and VarCol3 columns have 5,000 bytes of data each. SQL Server would keep one of them in-row (it would fit into the 8,060-byte limit) and place the other one on the single ROW_OVERFLOW_DATA page.

Note

Off-row column pointers use 16 or 24 bytes in-row, which counts toward the 8,060 maximum row size. In practice, this may limit the number of columns you can have in a table.

Figure 1-2 illustrates this state.

../images/463519_1_En_1_Chapter/463519_1_En_1_Fig2_HTML.jpg

Figure 1-2

Data row storage: Data pages after the first INSERT

The sys.dm_db_index_physical_stats data management function is usually used to analyze index fragmentation. It also displays the information about data pages on a per–allocation unit basis.

Listing 1-2 shows the query that returns the information about the dbo.DataRows table.

select

    index_id, partition_number, alloc_unit_type_desc

    ,page_count, record_count, min_record_size_in_bytes

    ,max_record_size_in_bytes, avg_record_size_in_bytes

from

    sys.dm_db_index_physical_stats

    (

        db_id()

        ,object_id(N'dbo.DataRows')

        ,0  /* IndexId = 0 -> Table Heap */

        ,NULL /* All Partitions */

        ,'DETAILED'

    );

Listing 1-2

Data row storage: Analyzing the table using sys.dm_db_index_physical_stats DMO

Figure 1-3 illustrates the output of the code. As expected, the table has one IN_ROW_DATA, one ROW_OVERFLOW_DATA, and four LOB_DATA pages. The IN_ROW data page has about 2,900 free bytes available.

../images/463519_1_En_1_Chapter/463519_1_En_1_Fig3_HTML.jpg

Figure 1-3

Data row storage: sys.dm_db_index_physical_stats output after the first INSERT

Let’s insert another row using the code from Listing 1-3.

insert into dbo.DataRows(ID, ADate, VarCol1, VarCol2, VarCol3)

values(2,'2006-09-29','DDDDD','EEEEE','FFFFF');

Listing 1-3

Data row storage: Inserting the second row

All three variable-length columns store five-character strings, and, therefore, the row would fit on the already-allocated IN_ROW_DATA page. Figure 1-4 illustrates data pages at this phase.

../images/463519_1_En_1_Chapter/463519_1_En_1_Fig4_HTML.jpg

Figure 1-4

Data row storage: Data pages after the second INSERT

You can confirm it by running the code from Listing 1-2 again. Figure 1-5 illustrates the output from the view.

../images/463519_1_En_1_Chapter/463519_1_En_1_Fig5_HTML.jpg

Figure 1-5

Data row storage: sys.dm_db_index_physical_stats output after the second INSERT

SQL Server logically groups eight pages into 64KB units called extents. There are two types of extents available: mixed extents store data that belongs to different objects, while uniform extents store the data for the same object.

By default, when a new object is created, SQL Server stores the first eight object pages in mixed extents. After that, all subsequent space allocation for that object is done with uniform extents.

Tip

Disabling mixed extents allocation may help to improve tempdb throughput in the system. In SQL Server prior to 2016, you can achieve that by enabling server-level trace flag T1118. This trace flag is not required in SQL Server 2016 and above, where tempdb does not use mixed extents anymore.

SQL Server uses a special kind of pages, called allocation maps, to track extent and page usage in database files. Index Allocation Maps (IAM) pages track extents that belong to an allocation unit on a per-partition basis. Those pages are, in a nutshell, bitmaps, where each bit indicates if the extent belongs to a specific allocation unit from the object partition.

Each IAM page covers about 64,000 extents, or almost 4 GB of data in a data file. For larger files, multiple IAM pages are linked together into IAM chains.

Note

There are many other types of allocation maps used for database management. You can read about them at https://docs.microsoft.com/en-us/sql/relational-databases/pages-and-extents-architecture-guide or in my Pro SQL Server Internals book.

Heap Tables

Heap tables are tables without a clustered index. The data in heap tables is unsorted. SQL Server does not guarantee, nor does it maintain, a sorting order of the data in heap tables.

When you insert data into heap tables, SQL Server tries to fill pages as much as possible, although it does not analyze the actual free space available on a page. It uses another type of allocation map page called Page Free Space (PFS) , which tracks the amount of free space available on the page. This tracking is imprecise, however. SQL Server uses three bits, which indicate if the page is empty, or if it is 1 to 50, 51 to 80, 81 to 95 or above 95 percent full. It is entirely possible that SQL Server would not store a new row on the page even when it has available space.

When you select data from the heap table, SQL Server uses IAM pages to find the pages and extents that belong to the table, processing them based on their order on the IAM pages rather than on the order in which the data was inserted. Figure 1-6 illustrates this point. This operation is shown as Table Scan in the execution plan.

../images/463519_1_En_1_Chapter/463519_1_En_1_Fig6_HTML.jpg

Figure 1-6

Selecting data from the heap table

When you update the row in the heap table, SQL Server tries to accommodate it on the same page. If there is no free space available, SQL Server moves the new version of the row to another page and replaces the old row with a special 16-byte row called a forwarding pointer. The new version of the row is called a forwarded row. Figure 1-7 illustrates this point.

../images/463519_1_En_1_Chapter/463519_1_En_1_Fig7_HTML.jpg

Figure 1-7

Forwarding pointers

There are two main reasons why forwarding pointers are used. First, they prevent updates of nonclustered index keys, which reference the row. We will talk about nonclustered indexes in more detail later in this chapter.

In addition, forwarding pointers help minimize the number of duplicated reads; that is, the situation when a single row is read multiple times during the table scan. Let’s look at Figure 1-7 as an example and assume that SQL Server scans the pages in left-to-right order. Let’s further assume that the row in page 3 was modified at the time when SQL Server reads page 4 (after page 3 has already been read). The new version of the row would be moved to page 5, which has yet to be processed. Without forwarding pointers, SQL Server would not know that the old version of the row had already been read, and it would read it again during the page 5 scan. With forwarding pointers, SQL Server skips the forwarded rows—they have a flag in their internal attributes indicating that condition.

Although forwarding pointers help minimize duplicated reads, they introduce additional read operations at the same time. SQL Server follows the forwarding pointers and reads the new versions of the rows at the time it encounters them. That behavior can introduce an excessive number of I/O operations when heap tables are frequently updated and have a large number of forwarded rows.

Note

You can analyze the number of forwarded rows in the table by checking the forwarded_record_count column in the sys.dm_db_index_physical_stats view.

When the size of the forwarded row is reduced by another update, and the data page with the forwarding pointer has enough space to accommodate the updated version of the row, SQL Server may move it back to its original data page and remove the forwarding pointer row. Nevertheless, the only reliable way to get rid of all forwarding pointers is by rebuilding the heap table. You can do that by using an ALTER TABLE REBUILD statement.

Heap tables can be useful in staging environments where you want to import a large amount of data into the system as quickly as possible. Inserting data into heap tables can often be faster than inserting it into tables with clustered indexes. Nevertheless, during a regular workload, tables with clustered indexes usually outperform heap tables as a result of heap tables’ suboptimal space control and extra I/O operations introduced by forwarding pointers.

Note

You can find the scripts that demonstrate forwarding pointers’ overhead and suboptimal space control in heap tables in this book’s companion materials.

Clustered Indexes and B-Trees

A clustered index dictates the physical order of the data in a table, which is sorted according to the clustered index key. The table can have only one clustered index defined.

Let’s assume that you want to create a clustered index on the heap table with the data. As a first step, which is shown in Figure 1-8, SQL Server creates another copy of the data and sorts it based on the value of the clustered key. The data pages are linked in a double-linked list, where every page contains pointers to the next and previous pages in the chain. This list is called the leaf level of the index , and it contains the actual table data.

../images/463519_1_En_1_Chapter/463519_1_En_1_Fig8_HTML.jpg

Figure 1-8

Clustered index structure: Leaf level

Note

The pages reference each other through page addresses, which consist of two values: file_id in the database and sequential number of the page in the file.

When the leaf level consists of multiple pages, SQL Server starts to build an intermediate level of the index, as shown in Figure 1-9.

../images/463519_1_En_1_Chapter/463519_1_En_1_Fig9_HTML.jpg

Figure 1-9

Clustered index structure: Intermediate levels

The intermediate level stores one row per each leaf-level page. It stores two pieces of information: the physical address and the minimum value of the index key from the page it references. The only exception is the very first row on the first page, where SQL Server stores NULL rather than the minimum index key value. With such optimization, SQL Server does not need to update non-leaf level rows when you insert the row with the lowest key value in the table.

The pages on the intermediate level are also linked in a double-linked list. SQL Server adds more and more intermediate levels until there is a level that includes just a single page. This level is called the root level, and it becomes the entry point to the index, as shown in Figure 1-10.

Note

This index structure is called a B-Tree Index , which stands for Balanced Tree.

../images/463519_1_En_1_Chapter/463519_1_En_1_Fig10_HTML.jpg

Figure 1-10

Clustered index structure: Root level

As you can see, the index always has one leaf level, one root level, and zero or more intermediate levels. The only exception is when the index data fits into a single page. In that case, SQL Server does not create the separate root-level page, and the index consists of just the single leaf-level page.

SQL Server always maintains the order of the data in the index, inserting new rows on the data pages to which they belong. In cases when a data page does not have enough free space, SQL Server allocates a new page and places the row there, adjusting pointers in the double-linked page list to maintain a logical sorting order in the index. This operation is called page split and leads to index fragmentation.

Figure 1-11 illustrates this condition. When Original Page does not have enough space to accommodate the new row, SQL Server performs a page split, moving about half of the data from Original Page to New Page, adjusting page pointers afterward.

../images/463519_1_En_1_Chapter/463519_1_En_1_Fig11_HTML.jpg

Figure 1-11

Leaf-level data pages after page split

A page split may also occur during data modifications. SQL Server does not use forwarding pointers with B-Tree indexes. Instead, when an update cannot be done in-place—for example, during data row increase—SQL Server performs a page split and moves updated and subsequent rows from the page to another page. Nevertheless, the index sorting order is maintained through the page pointers.

SQL Server may read the data from the index in three different ways. The first is an allocation order scan . SQL Server accesses the table data through IAM pages similar to how it does this with heap tables. This method, however, could introduce data consistency phenomena—with page splits, rows may be skipped or read more than once—and, therefore, allocation order scan is rarely used. We will discuss conditions that may lead to allocation order scans later in the book.

The second method is called an ordered scan . Let’s assume that we want to run the SELECT Name FROM dbo.Customers query. All data rows reside on the leaf level of the index, and SQL Server can scan it and return the rows to the client.

SQL Server starts with the root page of the index and reads the first row from there. That row references the intermediate page with the minimum key value from the table. SQL Server reads that page and repeats the process until it finds the first page on the leaf level. Then, SQL Server starts to read rows one by one, moving through the linked list of the pages until all rows have been read. Figure 1-12 illustrates this process.

../images/463519_1_En_1_Chapter/463519_1_En_1_Fig12_HTML.jpg

Figure 1-12

Ordered index scan

Both allocation order scan and ordered scan are represented as Index Scan operators in the execution plans.

Note

The server can navigate through indexes in both directions, forward and backward. However, SQL Server does not use parallelism during backward index scans.

The last index access method is called index seek . Let’s assume we want to run the following query: SELECT Name FROM dbo.Customers WHERE CustomerId BETWEEN 4 AND 7. Figure 1-13 illustrates how SQL Server may process it.

../images/463519_1_En_1_Chapter/463519_1_En_1_Fig13_HTML.jpg

Figure 1-13

Index seek

In order to read the range of rows from the table, SQL Server needs to find the row with the minimum value of the key from the range, which is 4. SQL Server starts with the root page, where the second row references the page with the minimum key value of 350. It is greater than the key value that we are looking for, and SQL Server reads the intermediate-level data page (1:170) referenced by the first row on the root page.

Similarly, the intermediate page leads SQL Server to the first leaf-level page (1:176). SQL Server reads that page, then it reads the rows with CustomerId equal to 4 and 5, and, finally, it reads the two remaining rows from the second page.

Technically speaking, there are two kinds of index seek operations. The first is called a point-lookup (or, sometimes, singleton lookup), where SQL Server seeks and returns a single row. You can think about the WHERE CustomerId = 2 predicate as an example.

The other type is called a range scan , and it requires SQL Server to find the lowest or highest value of the key and scan (either forward or backward) the set of rows until it reaches the end of scan range. The predicate WHERE CustomerId BETWEEN 4 AND 7 leads to the range scan. Both cases are shown as Index Seek operators in the execution plans.

As you can guess, index seek is more efficient than index scan because SQL Server processes just the subset of rows and data pages rather