• Introduction¯Four Approaches to Surrogate Key Generation
• Monotonic Series
• Pseudo-Random Numbers
• Comparing Monotonic and Pseudo-Random Cache Hit Ratios
• Composite Key Approach
• Recycled Series Approach
• Trigger-Based Implementation
• Performance Comparison of the Four Approaches
• Author's Note
• Recycled Series Implementation Example

Introduction¯Four Approaches to Surrogate Key Generation

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:

• Monotonic series
• Pseudo-random numbers
• Composite key
• Recycled series

Monotonic Series

1, 2, 3, 4, ...

1, 3, 4, 8, ...

15 March 1994, 21 March 1994, 1 April 1994, ...

Methods

• Max Plus One
• Enhanced Max Plus One
• Next Key Table
• Identity Property

Max Plus One

1> declare @next_key select @next_key =

2> max(key_column) + 1 from data_table

3> go

1> insert into data_table (key_column, ...)

2> values (@next_key, ...)

3> go

Enhanced Max Plus One

1> declare @next_key select @next_key = 

2> max(key_column) + 1 from data_table

3> holdlock


4> go

1> insert into data_table (key_column, ...)

2> values (@next_key, ...)

3> go

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 Table

1> begin tran


2> declare @next_key 

3> update next_key set next_key = next_key + 1
4> select @next_key = next_key + 1 

5> from next_key

6> insert into data_table (key_column, ...) 


7> values (@next_key, ...)

8> commit tran

9> go

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 Property

Concurrency Issues

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 on the data table
• Clustered index on the key
• Non-clustered index on the key
• Non-clustered index on the key with a clustered index on some other key

No Index Concurrency

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 Concurrency

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 Concurrency

Clustered Index on Other Key Concurrency

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.

Pseudo-Random Numbers

1> create procedure get_next_key 


2> @next_key int output 

3> as update next_seed 

4> set next_seed = next_seed + 1

5> go

1> select @next_key = 16807 * 


2> (next_seed % 127773) - 2836 * 

3> (next_seed / 127773)

4> go

1> if (@next_key <= 0) 


2> select @next_key = @next_key + 2147483547

3> go

---

Note
The above example is based upon an algorithm written by Malcolm Colton of Sybase (Malcolm Colton, Sybase Client Technical Services Technical Memo, December 1990). Park and Miller receive credit for the pseudo-random algorithm (Stephen K. Park and Keith W. Miller, "Random Number Algorithms: Good Ones Are Hard to Find," Comm. ACM, Vol. 31, Number 10, October 1988).

---

Next-Seed Table

Concurrency

While concurrency has been improved, the pseudo-random technique does have three significant disadvantages:

• This technique requires a next-seed table and a singled- threaded transaction to access. That is, only one process at a time can obtain a next-seed value.
• Random keys are considerably more difficult which to work with.
• A favorable cache hit ratio has been significantly sacrificed by moving to the pseudo-random technique.

Comparing Monotonic and Pseudo-Random Cache Hit Ratios

Monotonic Caching

Pseudo-Random Caching

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.

Composite Key Approach

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) 


2> output as select ltrim(rtrim(str(suser_id()))+

3> rtrim(convert(char(8),getdate(),112))+

4> rtrim(convert(char(4),datepart(hh,getdate())))+

5> rtrim(convert(char(4),datepart(mi,getdate())))+

5> rtrim(convert(char(4),datepart(ss,getdate())))+


6> rtrim(convert(char(4),datepart(ms,getdate()))))

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:

12519940411145439533 

12519940411145440666 

12519940411145442466

Disadvantages

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:

• Promote high concurrency by having concurrent inserts by different processes lock different parts of the table and index
• Promote a high cache hit ratio by causing consecutive inserts by the same process to hit the same part of the table and index
• Use a key small enough for efficient use of space (specifically index pages)
• Provide a means to control gaps in the sequence

Recycled Series Approach

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:

• Concurrency¯Wait persons do not share one large book of order forms. Each wait person uses his or her own pad of forms.
• Uniqueness¯Each order form has a unique order number.
• Cache Hit¯The next order form is always right there in the pad except in the case where it is the last form. In that case, the wait person gets a new pad from the manager.
• Audit Trail¯By examining which order forms have been received at the cash register and by looking at each wait person's current pad, the manager can determine if there are any missing orders.

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.

Trigger-Based Implementation

Performance Comparison of the Four Approaches

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.

Recycled Series Implementation Example

/* /* /* /* /* /* /* /* /* /* /* /* /* /*

Recycled series approach to surrogate primary generation. Designed to promote high concurrency without sacrificing the cache hit ratio under page-level locking. Effective in a insert-intensive OLTP environment with a relatively small data cache. Based upon presentation given at the 1994 International Sybase User Conference and Training Meeting. Gary Meyer, meyer@netcom.com May 8, 1994 Create the next key table and force one row per page.

*/ */ */ */ */ */ */ */ */ */ */ */ */ */

create table next_key

  (spid    int       not null,


  next_key int       not null,

  filler1  char(255) not null,

  filler2  char(255) not null,

  filler3  char(255) not null,

  filler4  char(255) not null,

  filler5  char(255) not null,


  filler6  char(255) not null)

go

create unique clustered index next_key_spid 

on next_key (spid)

go

/* Insert a firstrow                             */

insert into next_key

  (spid, next_key,


  filler1, filler2,

  filler3, filler4,

  filler5, filler6)

values

  (0, 0,

  replicate("x",250), replicate("x",250),


  replicate("x",250), replicate("x",250),

  replicate("x",250), replicate("x",250))

go

 


/*

/*
Create the stored procedure to generate the
next key value

*/

*/

create procedure get_next_key

@next_key int = null output

as

declare @error_flag int

 


/*
/*

First, check if this process already has a
series

*/

*/

select                                  

@next_key = next_key + 1                

from next_key holdlock                  


where spid = @@spid

This process has its own series

if (@@rowcount<=(@next_key-1)%1000000)

Update the next_key table with the new next_key

  begin

  update next_key                       

  set next_key = @next_key              

  where spid = @@spid

  end

This process does not hav its own series
(Exception processing)

else                                    

                                        

  begin                                 

  declare @old_spid int

Lock the table

  update next_key                       

  set spid = spid

  select @error_flag = 0

Try to grab an unused series that has been
abandoned by another process

  set rowcount 1

  select                                

  @old_spid = spid,                     

  @next_key = next_key + 1              

  from next_key                         

  where not spid in 


    (select spid

    from master..sysprocesses) 

  order by next_key   /*look for the one with*/

                      /* the lowest next_key value*/

Got an old unused series

  if (@@rowcount = 1)                  



    begin

    set rowcount 0


    update next_key       /*claim next series as own*/ 

    set next_key = @next_key,

    spid = @@spid

    where

    spid = @old_spid

    end

Did not find an old series

Delete row when an old series has been
completely consumed

  else

    begin

    set rowcount 0

    delete                              

    from next_key                       

    where spid = @@spid

Determine the value to use to start a new
series

    declare @max_next_key int

    select                              

    @max_next_key = max(next_key)       

    from next_key

    select @next_key = (@max_next_key-1)/1000000+1

    select @next_key = @next_key*1000000+1

Start the new series

    if not (@max_next_key is null)      


      insert into next_key

        (spid, next_key,

        filler1, filler2,

        filler3, filler4,

        filler5, filler6)

      values


        (@@spid, @next_key,

        replicate("x",250), replicate("x",250),

        replicate("x",250), replicate("x",250),

        replicate("x",250), replicate("x",250))

Otherwise, error

    else



      begin                                     

      raiserror 20000 'next_key table is empty.'


      select @error_flag = 1

      end

    end

  end

if (@error_flag = 1)

  return 1


else

  return 0

go

Make sure that the stored procedure uses row-
level locking on the next key table

update statistics next_key

go

exec sp_recompile next_key

go

by Gary Meyer