My Oxford Concise Dictionary says a sequence is a "set of things belonging next to each other on some principle of order" or a "series without gaps." Yet IBM DB2®, Microsoft SQL Server 2000, and Oracle9i can make sequences with both disorder and gaps. That's okay, because the main use of sequences — getting short unique numbers for primary keys — is more efficient if some compromises happen. Let's look at the compromises and efficiencies of sequences in Oracle / DB2 SEQUENCE objects and DB2 / SQL Server IDENTITY columns. I'll use a convention for some of the specialized vocabulary: a "Special Term" will be in quotes the first time it appears and will be capitalized if it's a noun.

The Old Way: SELECT MAX and Key Tables

Before DB2 version 7.2, Oracle6, and SQL Server 6.0, users coded their own sequence generators with "SELECT MAX" or with "Key Tables."

SELECT MAX code looks like this:

BEGIN
  DECLARE Current_Value INTEGER;
  SELECT MAX(identity_column) INTO Current_Value FROM Table1;
  INSERT INTO Table1 VALUES (Current_Value + 1, ...);
END;

This code finds the highest value for a column: the "Current Value" of the sequence. The code adds one to the Current Value, and puts the result into a new row. It guarantees a true monotonic sequence because values always increase. (In a SQL monotonic sequence, the values always increase or always decrease.) The code has two flaws: A SELECT followed by an INSERT in the same area can cause deadlocks, and two concurrent users will see the same value if they SELECT at the same time. So the code must either be in a SERIALIZABLE transaction, or Table1 must be locked. SELECT MAX is bad for concurrency.

Key Table code looks like this:

BEGIN
  DECLARE Current_Value INTEGER;
  UPDATE Key_table SET Current_Value = Current_Value + 1;
  SELECT Current_Value INTO Current_Value FROM Key_table;
  INSERT INTO Table1 VALUES (Current_Value, ...);
END;

This code maintains a one-row table that always has the latest Current Value. The technique is more flexible and the isolation level can be lower, but there's still a bottleneck. Besides, updating a user table is clearly overkill for something as elementary as incrementing an integer.

The way to avoid overkill is to accept two conditions: The container of the Current Value need not be locked throughout a transaction, and need not be written to disk at the end of a transaction (or conversely, need not be unwritten if the transaction ends with ROLLBACK). Such conditions are impossible with an ordinary SQL table, so a user cannot make an efficient sequence generator with tables. The DBMS must provide a different kind of object: one that has the two overkill-avoidance conditions built into its definition.

The New Way: Built-In Sequences

Here is a picture of a DBMS instance:

--------  -----------------  -------------------------------
- Disk -  - Global Memory -  - Local Memory For Session #1 -
- 5000 -  - ...           -  - ...                         -
--------  -----------------  -------------------------------

                              -------------------------------
                              - Local Memory For Session #2 -
                              - ...                         -
                              -------------------------------

                              -------------------------------
                              - Local Memory For Session #3 -
                              - ...                         -
                              -------------------------------

The DBMS has disk storage, some global memory accessible to all connections, and three private per-connection memory areas. Somewhere on disk is a single value called the "Last Number," which in the diagram has an arbitrary start value: 5000.

Suppose one of the sessions executes a SELECT that calls NEXTVAL. NEXTVAL is the function for getting the next value in a sequence, that is, the value after the Current Value. Here's how Oracle typically handles NEXTVAL:

• Copy the disk value 5000 from disk to global memory.
• Add 20 to the disk value and write, so the disk value becomes 5020.
• Generate 20 values within global memory, from 5001 to 5020.
• Copy one value (5001) from global memory to the local memory of the session that called NEXTVAL.
• Declare the value to be "consumed" and remove 5001 from global memory.

At the end of one NEXTVAL call, the instance looks like this:

--------  -----------------  -------------------------------
- Disk -  - Global Memory -  - Local Memory For Session #1 -
- 5020 -  - 5002 to 5020  -  - 5001                        -
--------  -----------------  -------------------------------

                              -------------------------------
                              - Local Memory For Session #2 -
                              - ...                         -
                              -------------------------------

                              -------------------------------
                              - Local Memory For Session #3 -
                              - ...                         -
                              -------------------------------

The steps that affect the disk need only happen every 20th time — the DBMS can grab 20 numbers with each disk read/write. So if Session #2 now calls NEXTVAL, the only steps needed are the copying of one value from global to local memory and the consuming of the value. The DBMS instance then looks like this:

--------  -----------------  -------------------------------
- Disk -  - Global Memory -  - Local Memory For Session #1 -
- 5020 -  - 5003 to 5020  -  - 5001                        -
--------  -----------------  -------------------------------

                              -------------------------------
                              - Local Memory For Session #2 -
                              - 5002                        -
                              -------------------------------

                              -------------------------------
                              - Local Memory For Session #3 -
                              - ...                         -
                              -------------------------------

There are several things to notice here.

• Session #1 and Session #2 have local copies of different numbers. There's no danger that one will see the other's.
• The numbers in global memory are a "Cache."
• Session #3 has nothing: It would be misleading if Session #3 could read any of the numbers on disk, in the Cache, or in other sessions' local memories.
• Commonly one says that there can be no CURRVAL ("get Current Value" function) if no NEXTVAL ("get next after Current Value" function) has been executed yet.
• There has been no mention of the operations associated with "ACID transactions." The updating of Last Number on disk cannot be rolled back, nor can the consuming of numbers in Cache be committed. NEXTVAL and CURRVAL are operations that happen during a transaction, but don't form part of it.

That's the gist. Here's some pseudocode that restates how NEXTVAL works in more detail.

1. Let the "Cache Size" be a fixed value. (I used 20 in the example because 20 is the default for both IBM and Oracle.) Let there be an array in the Cache whose size is "Cache Size." Call this array the "Cache."

2. Lock the Cache.

3. If (this is the first time) or (all cached numbers are consumed)

• Copy the "Last Number" on disk to N ("Last Number" is sometimes called the high water mark)
• Fill the Cache with numbers from (N + 1) to (N + Cache Size)
• Write the number (N + Cache Size) to disk
• This step as a whole is the "Grab."

4. Copy a number from the Cache to the local memory for the session executing a NEXTVAL call.

5. Remove the number from the Cache, i.e., "consume" it.

6. Unlock the Cache.

So much for the universals — some details can also depend on the DBMS. Here's three examples:

• The Cache might be lost if it's kicked out of memory because it hasn't been used for a while, or the Cache might be pinned in memory.
• Each DBMS picks a different time to decide when a local-memory copy is obsolete (at end of transaction, at end of statement, or merely at end of "scope," which means there are different values inside or outside a trigger).
• Oracle will store the on-disk Last Number in a system table (USER_SEQUENCES), but DB2 will simply read and write the Last Number from the transaction log.

The most important variation is that there can be parallel servers. In that case, there is still only one Last Number on disk, but there are two Caches. Then Server #1 can grab 20 numbers (say, 5001—5020) before Server #2 grabs 20 other numbers (say, 5021—5040). But Server #1 can consume its Cache more slowly because its users rarely call NEXTVAL. Therefore, it's possible that a number in Server #2's Cache (say, 5039) will be consumed before a number in Server #1's Cache (say, 5019). With parallel servers it is hard to guarantee that numbers will be issued in order, unless the Cache Size is one.

The biggest worry is that there can be crashes or hurried shutdowns (usually known as shutdown/aborts). This is not a worry that a duplicate number can be issued after a crash — that is impossible because the Last Number is written on disk before any session gets a Current Value, and Current Values are always less than the Last Number. However, the Last Number reflects the last Grab as if it was complete. If the numbers between 5001 and 5020 are grabbed, but there is a crash after 5005 is consumed, then all the unconsumed numbers between 5006 and 5020 are "burnt" — they will never be used because when the DBMS restarts, it will begin with the Last Number: 5020. (I am sure that this description is true for DB2 and Oracle. I am unsure about some details for Microsoft.)

What's neat and efficient about the plan is the fact that (a) disk synchronization happens only every 20 times you call NEXTVAL instead of every transaction and (b) locking and logging overheads associated with table-updates are avoided because there's no worry about committing or rolling back NEXTVAL's effect. What's a little less desirable is that (a) sequence gaps will occur if there are ROLLBACKs (because the numbers will be "consumed" but never used), (b) sequence gaps will occur if there are crashes (because the numbers will be burnt), and (c) sequences can be disordered (because with parallel servers a larger number can be issued before a smaller number).

SQL's Simple Sequence Syntax

To show how standard the specifications are for sequence generators, Table 1 shows a CREATE SEQUENCE statement using all possible clauses. Each clause contains the default value and starts on a separate line. The statement is split into three columns: one for SQL:2003 (as it stands in the August 2002 draft), DB2, and Oracle. Where a clause is unsupported, I've left a blank space.

xx_seq

xx_seq

xx_seq

Table 1: Three Variations of CREATE SEQUENCE.

The columns of Table 1 are nearly the same, so you can see how portable CREATE SEQUENCE is. Most of the clauses (data type, start value, minimum value, maximum value, and whether to recycle values) describe accidental characteristics, so I'll skip on to the important lines of Table 1:

xx_seq: It's fairly common to end a sequence name with the letters _seq. This seems a reasonable convention.

• AS INTEGER: A sequence will often be BIGINT or some truly big-range data type. IBM uses INTEGER as a default, but likes DECIMAL(28,0) in some contexts; Oracle uses a 28-digit number that cannot be changed; and the SQL:2003 document says the default is implementation-defined. The desirability of having short 4-byte numbers (INTEGERs) has to be balanced against the chance of running out of numbers if the range is too small. Remember that an INTEGER is signed, so you must start with a negative number if you want to take advantage of its full 4-billion-number range.
• INCREMENT BY 1: Everyone agrees that the default increment should be one, so I used "add 1" in the example. Occasionally users define larger increments to provide space for manual INSERTs or overlapping sequences.
• CACHE 20: Both IBM and Oracle decided the default should be "CACHE 20" so I used Cache Size is 20 in the example. I know of people who have increased to "CACHE 5000" to reduce the disk writes that Grabs cause. They point out that crashes are rare and that the maximum effect of a crash is 5000 burnt numbers, which is a trivial matter to them. Gaps should only matter if there's some auditing purpose for the sequence, such as matching sequence numbers with invoice numbers.

NEXTVAL and CURRVAL

Hamlet (Act 5 Scene 2) could say, "what to this was sequent, thou knowest already." But thou doesn't, so the DBMS must provide functions for retrieving sequence values. They look like this:

NEXT VALUE FOR xx_seq

NEXTVAL FOR xx_seq

xx_seq.NEXTVAL

PREVVAL FOR xx_seq

xx_seq.CURRVAL 

We already know NEXTVAL.

CURRVAL/PREVVAL are non-standard functions that peek at the copy in the local session memory. This can be confusing for two reasons: (1) the local copy is meaningless until after NEXTVAL has caused a copy from the Cache, and (2) the local copy gets out of sync with the value in the Cache if another session calls NEXTVAL. (Incidentally, the DB2 manual has an error: it refers to a CURRVAL function, but CURRVAL is an Oracle function. DB2's function name is PREVVAL.)

Putting a sequence together and using it for a primary key using SQL:2003 syntax for the NEXTVAL function, looks like this:

CREATE SEQUENCE xx_seq ...                 /* make the sequence */
...                                        /* time passes */

SELECT NEXT VALUE FOR xx_seq INTO xx ...  /* this is one way to do it */
INSERT INTO Table1 VALUES
  (xx,...)
...
INSERT INTO Table1 VALUES                 /* this is another way */
  (NEXT VALUE FOR xx_seq, ...)

Compare this to the code for Key Tables. Sequence generators are a fast replacement for Key Tables.

IDENTITY Columns

An IDENTITY column is an exact-numeric column (e.g., an INTEGER column), with its own attached sequence generator. Table 2 shows a table definition with an IDENTITY clause in three syntaxes.

Table 2: Three Variations of CREATE TABLE ... IDENTITY.

This is where Microsoft enters the picture. SQL Server 2000's syntax is less standard and less rich — the only optional argument is "(seed, increment)", which corresponds to the "START WITH n INCREMENT BY n" subclause in SQL:2003 and DB2. But usually that's all you need.

Internally, an IDENTITY column's sequence generator works just like the sequence generators that you make with CREATE SEQUENCE. Externally, the difference is that INSERT is simpler with IDENTITY columns: You don't need to call a NEXTVAL function. You just have to use defaults when inserting. For example, for the "Table1" table illustrated above, you'd just say:

INSERT INTO Table1 (column0) VALUES (0)

Summing up the options: All of The Big Three support sequences via either CREATE SEQUENCE or IDENTITY, although only IBM supports both. Making external sequences with CREATE SEQUENCE is more flexible, but making internal sequences with IDENTITY properties is more straightforward.

Hot Spots

Suppose User A and User B are both INSERTing at the same time, using the same sequence generator to get primary-key values. They'll get nearly the same sequence values (for example 5000 and 5001). Therefore they'll probably access the same page in the primary-key index. That means there will be contention, and that's natural: When primary keys are numbers that follow a single monotonic sequence and multiple users do Inserts, "hot spots" will appear. On the other hand, when only one user does Inserts, there is no hot spot. Instead, the monotonic sequencing is beneficial: The last index page is likely to stay in cache, so transactions will be faster.

Thus with many concurrent Inserts you want to discourage monotonics; with few concurrent Inserts you want to encourage monotonics. Depending where you fit on the continuum, entertain one of these notions:

• ONLY ONE INSERTER. Change nothing; the defaults are ideal.
• TWO CONCURRENT INSERTERS. Create two sequence generators. One will descend from zero ("START WITH 0 INCREMENT BY -1" in IBM syntax), and is for exclusive use by Session #1. The other will ascend from one ("START WITH 1 INCREMENT BY 1"), and is for exclusive use by Session #2.
• SEVERAL CONCURRENT INSERTERS. Reverse the digits of the number before inserting it into the key column. For example, let 5001 become 1005, let 5002 become 2005, and so on. With Oracle, you don't need to reverse the digits in the column itself-you can use a reverse-key index. The numbers will thus be distributed rather than concentrated.
• MANY CONCURRENT INSERTERS. Make up a number X using a random-number generator or taking a value that will be specific to a session, such as the user's branch or the Node ID. Concatenate X with the number from the sequence generator. For example, using Microsoft syntax:

CREATE TABLE Table1 (
   cust_id INTEGER IDENTITY (1,1),
   session_id INTEGER, 
   PRIMARY KEY (session_id, cust_id))

With this system, if Session #1 gets sequence number 5001, the primary key will be 01/5001, and if Session #2 gets sequence number 5002, the primary key will be 02/5002. Again there is distribution to avoid the hot spot, but perhaps there will be better cache hit ratios if a single session does multiple Inserts at nearly the same time.

Tips and Predictions

Tip: If you don't care about the key size and you want to avoid even the slight contention that occurs at Grab time, use a GUID instead of a sequence.

Prediction: Someday, DBMS optimizers will skip the uniqueness test when you create a unique index on an IDENTITY column, because in certain cases they're unique by definition.

Tip: If you really can't stand gaps and disorder, create the sequence with a NO CACHE clause. This will make the DBMS do a Grab, and thus a disk write, every time you call NEXTVAL.

Prediction: When Microsoft and Oracle catch up to IBM, they will use similar syntax because IBM is close to the proposed SQL Standard. To put it cutely: Microsoft's "SQL-2003" will look more like ANSI/ISO's "SQL:2003" although spelling will differ (dash '-' instead of colon ':') and pronunciation will differ ("Sequel 2003" instead of "S-Q-L 2003").

References

Bowman, Judith. "Comparing Autonumbering Methods in Different Relational Database Management Systems." (registration required)
Syntax examples for several DBMSs.

Lewis, Jonathan. "What Next? All about Sequences."
An Oracle overview from 1999.

Moreau, Tom. "Identity Crisis."
Triggers, Identity columns, and SQL Server 2000.

Oracle Support. "Bulletin: Caching Oracle Sequences."
Some changes that occurred in Oracle version 8.

Peterson, Erik. "Partitioning Applications to Take Advantage of Oracle's Parallel Server."
The section about sequences would apply to any DBMS.

Sybase Support. "How Surrogate Primary Key Generation Affects Concurrency and the Cache Hit Ratio."
Avoiding hot spots with monotonic key generation under Sybase.

--

Peter Gulutzan co-wrote a 1078-page book on the current standard: SQL-99 Complete, Really (CMP Books 1999). His understanding of portability grew while he benchmarked IBM, Informix, Ingres, InterBase, Microsoft, MySQL, Oracle, and Sybase DBMSs for a book which Addison-Wesley published approximately yesterday (September 2002): SQL Performance Tuning.