These keys are system-generated, and this TechNote deals with the question of how best to generate surrogate primary keys. The question of how to generate these keys is non-trivial because Sybase SQL Server's page-level locking causes the key generation algorithm to significantly affect overall SQL Server performance. This is especially true in an insert-intensive OLTP (online transaction processing) environment.
The different algorithms for key generation can be grouped into four general approaches:
1, 2, 3, 4, ...
1, 3, 4, 8, ...
15 March 1994, 21 March 1994, 1 April 1994, ...
Max Plus OnePerhaps the most apparent solution to surrogate primary key generation is to select the max from the data table and to add one to determine the next key value.
1> declare @next_key select @next_key =
1> insert into data_table (key_column, ...)However, this algorithm does have a serious problem. The transaction is not atomic. Two concurrent transactions could execute the select and obtain the same next key value before either one executes the insert. This algorithm could only be considered appropriate for a low-intensity environment.
Enhanced Max Plus OneThe first improvement to the "Max Plus One" algorithm is to include the holdlock keyword in the select statement.
1> declare @next_key select @next_key =
1> insert into data_table (key_column, ...)The SQL shown above will generate unique keys provided there is a clustered index on the key.
However, this algorithm frequently causes deadlocks in a highly concurrent environment. If two concurrent processes execute this code, both acquire shared locks on the last page. One then attempts to obtain the exclusive lock on the last page required by the insert statement and becomes blocked by the shared lock of the other process. The second process then tries to acquire the exclusive lock required by the insert statement and a deadlock results.
Even with the holdlock enhancement, the "Max Plus One" algorithm is suitable only in a low-intensity environment.
Next Key TableA more versatile approach is to introduce a separate table to store the next key value.
1> begin tranThe SQL is atomic and uniqueness is guaranteed. Notice that the update statement precedes the select statement. The update first acquires an exclusive lock on the table ensuring that no other processes can obtain a next key value from the table.
In the above example, the transaction includes both the generation of the key and the insert into the data table. The transaction is completely single-threaded. Consequently, there are no gaps in the sequences of key values inserted into the data table.
Identity PropertyThe identity property, as supplied in Sybase System 10, provides a series of sequential numbers to use as primary keys. The implementation and issues regarding gaps in the key sequence are described in your System 10 SQL Server documentation.
For a better understanding of the effects of the key generation scheme on concurrency, we must examine various indexing scenarios. These scenarios include the following:
No Index ConcurrencyIn the case where you have no index, the table acts as a heap and all inserts go to the last data page by default.
When more than one process tries to concurrently insert, the first process will block the second. The first process acquires an exclusive lock on the last data page of the table. The second tries to acquire an exclusive lock on this same page but is blocked until the first transaction has either been committed or rolled back.
This spot of contention is commonly referred to as a "hot spot."
Clustered Index ConcurrencyIf you create a clustered index on the surrogate primary key and there is still a similar concurrency situation. Because the series of key values generated is monotonic, all inserts are directed to the last page.
If the maximum key value is 100, the next key value generated is 101. An insert with a primary key value of 101 is directed to the last data page of the table, as is an insert of the row with a primary key of 102. Only one of the two processes is able to have the necessary exclusive lock on the page at any one time. Consequently in this case as well, concurrent inserts must wait for an exclusive lock.
Note that this situation applies for all algorithms that generate monotonic keys. When using the identity property, multiple processes can concurrently generate next key values without blocking each other. However, once two processes try to concurrently insert into the data table, they will block as described above.
Non-Clustered Index ConcurrencyIf you use a non-clustered index only on the surrogate primary key, the table acts as a heap. By default, all inserts go to the last data page. Consequently, there is still a troublesome hot spot and concurrent inserts must wait for an exclusive lock.
Clustered Index on Other Key ConcurrencyPerhaps the most frequently heard advice on the issue of page- level locking and surrogate primary key generation is to cluster on a different column.
One possibility is to create a non-clustered index on the surrogate primary key and a clustered index on some other column or set of columns.
For example, a table of employees could have a non-clustered index on the employee ID and a clustered index on last name, first name, which would be useful for sorting alphabetically. In this case, inserts are spread across the data pages based upon the distribution of the clustered index. For example, one process might be inserting employee Abbott while another is inserting employee Wilson. The first employee's row would be inserted toward the front of the table and the second employee's would be inserted toward the end. This is so even if Abbot has an employee ID of 101 and Wilson an employee ID of 102. At first glance, this method appears to solve the concurrency problem.
However, while Abbott's and Wilson's rows are far apart on the data pages of the table, a single index page probably contains both employee identifiers and pointers to both of these data pages. That index page is the last leaf-level page of the non- clustered index. When the rows are inserted, the index page must be updated before the transaction is complete. This update to the index page requires an exclusive lock. Because both of these concurrent inserts must acquire an exclusive lock on the same index page, a hot spot exists.
The last-page contention arguments still apply. The hot spot has not gone away. It has moved from the last data page to the last non-clustered index page.
In summary, a monotonic approach might be effective only in an environment that rarely has concurrent processes inserting into the same table.
1> create procedure get_next_key
1> select @next_key = 16807 *
1> if (@next_key <= 0)
While concurrency has been improved, the pseudo-random technique does have three significant disadvantages:
Each insert descends the index on the primary key randomly. Consequently, one insert will descend one path through the index while another insert will descend another path. While this prevents them from blocking, many more pages must be hit.
Many large OLTP databases have a 1 to 100 data cache to database size ratio. An approximate one percent chance of a page being cache results in a poor cache hit ratio.
Depending on the nature of the application, random keys might not result in an improvement in overall system performance. Therefore, a random approach would be most effective in an environment that is insert intensive but has a relatively large data cache.
A third alternative to surrogate primary key generation is the "composite key" approach. The surrogate primary key is a single column composed of multiple parts. The first part of the key is used to control the spread of the inserts throughout the data table and the second part is used to ensure uniqueness. The following example is credited to Hal Spitz of Sybase:
1> create procedure get_next_key @next_key char(20)In this example, the first part of the key is the SQL Server user ID. Other possible values include the client host process ID and SQL Server process ID. The first part of the key is used to improve concurrency by controlling the spread of the inserts.
Since this example uses the SQL Server user ID, all rows inserted by a given user would be grouped together. This grouping would occur on the data pages in the case of a clustered index on the key and on the leaf-level index pages in the case of a non-clustered index on the key. If each concurrent user logs in using a different SQL Server user ID, concurrent inserts are spread throughout the table, resulting in less contention.
The second part of the key in this example is based upon datetime because it provides a practically unique value. In addition to providing uniqueness, the second part of the key keeps the cache hit ratio from deteriorating.
Using the composite key approach, a given SQL Server user ID generates keys in a monotonic series. For example, SQL Server user ID 125 might generate the following values:
12519940411145439533This series causes each SQL Server user ID to consistently work in one area of the table or index. Consequently two consecutive inserts by the same SQL Server user ID will, more than likely, be directed to the same page in the database.
A secondary disadvantage is that the datetime values are part of a continuous sequence¯not a discrete sequence. There is no way to look for or control gaps in the key sequence.
A better solution for the insert-intensive OLTP environment would do all of the following:
For example, three concurrent processes can acquire next key values as follows: One process can work on the sequential series from 1 to 1,000,000, the second can work on the series from 1,000,001 to 2,000,000, and the third from 2,000,001 to 3,000,000.
An analogy can be made to a diner and its five wait persons:
What happens if a wait person quits (one less concurrent process)? The manager takes his or her pad of order forms and saves it.
What happens if the wait person is later replaced (a replaced concurrent process)? He or she is given the predecessor's pad of order forms to continue in the series.
One implementation of this approach is included at the end of this TechNote. The included implementation is written completely in Transact-SQL. An alternative implementation that would require less overhead could be written as an Open Server application.
In summary, a recycled series approach might be effective when both concurrency and cache hit ratio affect overall database server performance. This is usually the case in insert-intensive OLTP databases.
The various approaches are effective in different environments. The monotonic approach may provide best performance in a low activity environment. The pseudo-random approach may provide best performance in an insert-intensive environment with a large data cache. The composite approach may provide better performance than the previous two in an insert-intensive environment with a relatively small data cache. Finally, the recycled series approach also works well in an insert- intensive environment with a small data cache. However, the recycled series approach requires less overhead due to a smaller key and provides a way to manage gaps in the series of key values.
create table next_key
create unique clustered index next_key_spid
/* Insert a firstrow */
insert into next_key
create procedure get_next_key
declare @error_flag int
select @error_flag = 0
set rowcount 1
if (@@rowcount = 1)
declare @max_next_key int
select @next_key = (@max_next_key-1)/1000000+1
if not (@max_next_key is null)
if (@error_flag = 1)
update statistics next_key
exec sp_recompile next_key
by Gary Meyer