How to Solve the Tail Insert Problem

In the previous post, we talked about when you should use identity/sequence as a clustered index key and when it’s problematic.

In a nutshell, since traditionally we want our clustered index key to be narrow, static and ever-increasing, Identity is in many cases a very good choice. But since all inserts go to the last page of the index, if you load data from many sessions in parallel, they will interfere each other because each one has to acquire a latch on the page when inserting data into it. This problem is sometimes referred to as the tail insert problem.

Today, we will talk about the possible solutions for this situation. We will use the following table and see how each solution changes its creation script:

Transact-SQL

CREATE TABLE dbo.UserEntries_RegularWithIdentity ( Id BIGINT IDENTITY PRIMARY KEY CLUSTERED, UserId INT NOT NULL , CreatedDate DATETIME2 NOT NULL )

1

2

3

4

5

6

CREATE TABLE dbo.UserEntries_RegularWithIdentity

(

Id BIGINT IDENTITY PRIMARY KEY CLUSTERED,

UserId INT NOT NULL ,

CreatedDate DATETIME2 NOT NULL

)

Solution #1: Load to a Heap

Loading into a heap works different than into a clustered index. Instead of traversing the index tree and finding the relevant page for the insert, it uses the combination of the GAM, SGAM and PFS maps in order to find a page to insert the row to. When loading to a heap, a common problem is that the PFS, which is a shared data structure, become a hotspot. The way to solve the problem is just to add more data files to the database/filegroup, since each file (and each ~64MB of data to be exact) has a separate PFS map.

Transact-SQL

CREATE TABLE dbo.UserEntries_RegularWithIdentity ( Id BIGINT IDENTITY PRIMARY KEY NONCLUSTERED, UserId INT NOT NULL , CreatedDate DATETIME2 NOT NULL )

1

2

3

4

5

6

CREATE TABLE dbo.UserEntries_RegularWithIdentity

(

Id BIGINT IDENTITY PRIMARY KEY NONCLUSTERED,

UserId INT NOT NULL ,

CreatedDate DATETIME2 NOT NULL

)

Solution #2: Work with In-Memory OLTP

The In-Memory OLTP (aka Hekaton) engine uses lock-free data structures in order to not use latches. By doing so (and other super-cool stuff), inserting data from many threads in parallel can become much faster. The problem is that it’s pretty hard to work with In-Memory OLTP in SQL Server 2014. Migration is hard, you have to work with binary collati