Key Points About Surrogate Keys

Roy Hann, Rational Commerce Limited

Session #: NT020S Presented at CA-World '96 New Orleans, Louisiana, USA August 1996

Abstract This presentation introduces the notion of a surrogate key, with illustrations of how surrogate keys are useful. Techniques for generating surrogate keys in CA-Ingres applications are described, and are analyzed from the point of view of allocation performance and insertion problems. Techniques for efficiently generating keys are presented. Variations on the basic surrogate key are developed, including pseudo-random order keys and verifiable keys.

Note: this paper was slightly updated in October 2002, and an addendum on primary keys was added in August 2003.  This addendum overrides advice suggested under the subheading "The Solution", and should in fact cause us all to reconsider whether we even need surrogate keys any longer.

A Typical Problem

Frequently when we design databases we discover that there is no natural key that we can rely on in our application. Consider the following (simplified) real-world example, from an application developed to study and manage the improvement of beef cattle. Beef cattle are identified by different people in many different ways. There is the farm name, by which the animal is known on the farm--and possibly to the world if it is a famous sire. Farm names are names such as "Thunder Beef IV" or "Haven Great Heart". Farm names are therefore much like human names in that there is no central coordination in assigning them, and there is a moderately high probability of ambiguous naming, i.e. two or more animals with the same name. The latter problem is very common as some farms like to re-use a good name over and over. Clearly we can't use the farm name as a totally reliable, unambiguous method of identifying an animal's records.

Animals also have a tattoo number. The tattoo number is usually assigned by the breed association for the particular breed of animal. There is in fact an ISO standard for beef cattle tattoos, but the standard requires such a long number that it is not often used. Instead a truncated number is assigned which omits the international identifier. That would be fine, except that cattle are often traded internationally, with Australian, American, and Canadian cattle flowing back and forth. This raises the possibility, at least in principle, of an animal which originates in Australia being imported into Canada with a tattoo number that conflicts with another tattoo number on an animal already in Canada. To make matters worse, historically the breed associations did not include a breed identifier in their tattoo numbers, so that animals from the same country but of different breeds may have the same number too. There is also the producer's ear-tag number, which is the animal's number within its herd, but these numbers are not useful off the farm. There is also a purebred registration number, but only about 10% of animals will have one of these. There are even more numbers besides these, and some numbers can change from time to time anyway (as for instance when the animal moves to another herd).

As you can see, none of these identifiers are suitable for propagating throughout the database as a key. Although this may be a somewhat extreme example, problems like this are familiar to everyone regardless of their application domain. For instance hospital databases have exactly the same problem identifying patients.

Compounding the Problem

Even when a potentially reliable natural key exists, if we are relying on human operators to enter the key value we should be reluctant to propagate it throughout the database because of the difficulty of correcting it when a user inevitably enters an incorrect value. 

Another Common Problem

Sometimes our problem is different, though a lot simpler. We just want to preserve the order in which rows were added to the database for some reason, and there is no way to recover that ordering by sorting on an existing key in the data. In this situation we sometimes add a row number when the row is stored. (I don't actually advocate doing this; I believe that if the ordering cannot be deduced from the data, then either the logical model is defective or the desire to have an ordering is wrong. But in the real world, right or wrong, users often demand this.)

And Yet Another

Sometimes tables that have a key that consists of a long string can cause problems for the optimizer. The utility that collects statistics on key value distributions for the optimizer only examines the leftmost 8 bytes of the string. [Note: this was true at the time of writing, but is no longer an issue. --RH October 2002]   If the string is longer than that, and if it is relatively unvarying on the left, then the statistics may suggest that the key is not very selective, even if it is completely unique. The optimizer would then ignore a very good key when it is evaluating query plans. To solve this problem we can replace the long key value with a more concise artificial value. (There are other potential solutions too, like adjusting the statistics manually, or turning off the use of statistics for queries involving this table.)

The Solution

The solution to the beef cattle identification problem is to generate a totally arbitrary "animal number" in the application and to cross-reference the "animal number" to all the natural identifiers in one place, and then to use the "animal number" as the key everywhere else in the database. If an incorrect tattoo number is entered by an operator, it needs to be corrected in only the place where it is cross-referenced to the "animal number". There is no need for the animal even to have a pre-existing tattoo number. (Employee numbers are another familiar example of the same solution to the same problem.)   [Since I originally wrote this, advances in support for declaritive referential integrity constraints make this suggestion irrelevant.  See the addendum for current advice.  --RH August 2003]

The arbitrary "animal number" and the artificial "row number" are examples of a surrogate key--a value used to uniquely identify an entity without using a real data value or "natural" key. An important property of these surrogate keys is that they are totally synthetic and hence they have no information content at all. This means they can never be wrong, and so we don't need to write code to update them.  This simple point turns out to have fantastically important consequences.

The rest of this presentation will deal with generating these content-free surrogate key values, and the surprising pitfalls that are hidden in this outwardly simple and easy-to-implement concept. We will also explore how to solve a variety of other problems using exotic surrogate key value generators.

Possible Implementations

There are a couple of candidate implementations of this solution that need to be disposed of quickly before we discuss the technique that this paper recommends. Anyone who has had a little experience with CA-Ingres will be aware of the tuple identifier (TID) that addresses every row in the table. Some people have been seduced into using this TID as a convenient surrogate key value. For example in a master-detail relationship, after inserting the master row into the database they have looked up the TID of that row and used it in the foreign key in the detail table. The code might look something like this:

select :tid = tid
from master_tbl where ...;
insert into detail_tbl ( fk_value, ... ) values ( :tid, ... );
...

For a while this will not only work, but it will be very fast too, because the TID is the physical address of the row in the master table. Any time an application needs to locate the row in the master table corresponding to a detail row, it has its exact address in the detail table.

Or at least it is there until the first time the master table is re-organized. (As it will be for instance when a MODIFY command is executed on it.) When that happens the row in the master table will probably get a new TID, and the relationship between the detail and the master will be irretrievably lost. To make it even worse a new row may be placed where the old row used to be, and that will be the row selected by the TID in the detail row, so the error may go undetected. For this reason the TID must never be used as a surrogate key value, under any circumstances.

The second possible implementation that we will dismiss is somewhat more contentious. It is more contentious because it is supplied by the CA-Ingres product precisely to solve the surrogate key value generation problem. Unfortunately, there are very good reasons not to take advantage of it. But first let us understand how it works.

CA-Ingres provides two logical key types: table_key and object_key. These are respectively an 8-byte and a 16-byte value. A column in a table can be declared to be of type table_key or type object_key, and (optionally) to be system_maintained. If it is declared to be system_maintained, then the value of the column is automatically initialized by CA-Ingres when a row is inserted. System maintained table_key values are guaranteed to remain unique within the table. System maintained object_key values are unique in the database. To outward appearance then, the system supplied logical key types are the perfect solution to some of the problems of generating surrogate key values, which should not be surprising since that is their intended purpose.

Unfortunately this otherwise excellent solution has a couple of really serious drawbacks. The most significant problem is that the CA-Ingres COPY...FROM command cannot load values into a column that is a logical key type "with system_maintained". That is a problem because one must be able to use COPYDB and UNLOADDB in a variety of situations, such as doing an upgrade, or porting to a new computer system, or as a last-ditch salvage operation. But both of these utilities rely on COPY...FROM to reload the database so using system maintained keys makes them unusable.

There is a work-around for this problem which will be shown later, but it is sufficiently complicated and wasteful of space that the alternate technique that is recommended in this paper may be preferable, especially considering some of the extra versatility offered.

The technique that is advocated here is to construct a surrogate key generator from scratch. Such a generator can be almost as efficient as the system supplied logical key value generator, but with none of the problems, and it offers the opportunity to tailor the sequence of values generated to suit different applications. For instance, although a random sequence of values is useful in some situations, in other applications a sequential value is required. A "home brewed" sequence generator can be constructed that provides both types of numbers equally efficiently.

Constructing A Surrogate Key Generator

The most important property of any usable surrogate key value generator is that it will never generate the same value twice. To be useful we must be able to rely on the surrogate key to identify only the one record (or group of related records) that we are interested in. The solution that first comes to mind is to generate sequential numbers. By noting the last value allocated, and adding one to get the next value, we are guaranteed to get unique numbers very simply.  This kind of key generator is often implemented in the following way.

Example 1

First a table (called generator here) is created, with one row and one column:

CREATE TABLE generator ( keyval INTEGER NOT NULL WITH DEFAULT ) WITH JOURNALING;
GRANT SELECT, UPDATE TO PUBLIC;

This table is then accessed in the following way to obtain sequential numbers for a surrogate key value:

SELECT keyval INTO :keyval FROM generator;
...
UPDATE generator SET keyval = keyval+1;
COMMIT;

This fragment of code appears to do what is required, and in fact it might work most of the time on systems that have relatively few concurrent users. However it has a couple of flaws that must be corrected if it is to be reliable in all cases.

The first flaw is quite elementary but frequently overlooked. In a multi-user system this code is capable of allocating duplicate surrogate key values to successive users. This can occur when a second (or third or fourth) user requests a surrogate key value at the same time as the first requestor. The problem is that by default the SELECT statement takes only a shared lock on the page. A shared lock only prevents another user from updating the row, it does not prevent another user from reading that row, and so another user is free to come and read the same data and so get the same surrogate key value.  [Actually this might not really lead to duplicate numbers being used.  But if not, it will cause a resource deadlock, which is only slightly better. --RH October 2002]

One solution is to take advantage of the fact that an UPDATE statement takes an exclusive lock on the page. Once a user has an exclusive lock on a page, no other user can even read that page until the user who locked it releases their exclusive lock. Actually, it is not that simple. It is possible to read a page that has been locked exclusively by first issuing the SET LOCKMODE SESSION WHERE READLOCK=NOLOCK command (or some similar variant of the SET LOCKMODE command). This is highly inadvisable in most applications and would certainly be a serious problem for this key value generator. [...]  Doing the UPDATE first and then doing the SELECT guarantees that a second user cannot read the same key value until after the first user commits. The more correct code looks like this:

Example 2

UPDATE generator SET keyval = keyval+1;
SELECT keyval INTO :keyval FROM generator;
...
COMMIT;

Of course if this code is relying on the UPDATE to take and hold an exclusive lock, autocommit cannot be turned on while this code is executed. If there is a chance that this code will be used in an application that has issued the SET AUTOCOMMIT ON command, it must be protected with some boilerplate code to detect and handle that.

Performance Problems--Lock Contention

We have deliberately designed the key value generator so that no two sessions can access the generator table at the same time, so that no two sessions ever get the same key value. This solves the problem of accidentally creating ambiguous key values, but it does so at a very high cost. It induces the problem of "lock contention". The users end up queuing for access to the generator table and they experience (potentially) seriously degraded response time. In a small system with only a few users it may be tolerable, but in general, with a large number of users and locks that are held for significant periods of time, this sort of centralized key-generator can be a crippling bottleneck damaging overall system performance.

To make the problem clear, suppose that the application accesses the generator table and obtains a new surrogate key value. Then suppose that the application displays a data entry frame and waits for the user to enter some data. After the user has entered the data, the application may subject it to a verification process that requires a number of database look-ups. Finally the application stores the data and then COMMITs the entire transaction, at which point the lock on the generator table is released. Now suppose that after the application displays the data-entry screen the user goes to a 3 hour meeting. As described here, the generator table will be locked for 3 hours unless the DBA intervenes. This is a far-fetched illustration, but it shows the problem, and even if the user enters their data promptly, there will still be a substantial period of "think time" during which the generator table will be locked. The busier the system is, the shorter the tolerable lock duration will be. In a really busy system a lock held for even a significant fraction of a second may be intolerable.

Reducing the Impact of Lock Contention--Last-Minute Locking

One way to improve performance is to design the application so that the surrogate key value can be generated at the last possible moment in the transaction. That way the lock on the generator table will not be acquired until the last moment, and it will be released promptly. (In general we should always attempt to lock tables in the order least-busy first, so that the locks on the busiest tables are taken as late as possible and released as soon as possible; this is nothing new.) If we do nothing else, we should endeavor not to permit any user "think-time" after the time the lock on the generator table is acquired.

If the application demands gap-free numbering, this may be the best we can do to eliminate lock-contention. That is because we not only have to guarantee that no two sessions ever get the same key value, we must also guarantee that no key value is ever wasted. Therefore the lock on the generator table must be held until the key value is actually used and the entire transaction is committed. But if the demand for gap-free numbering can be relaxed then there is plenty of room to improve performance still further.

Regard Gapless Number Sequences as Evil

The next step towards a solution is to ask whether a gap-free number sequence is actually required. Frequently there is no reason to demand a gap-free number sequence. If the purpose of the surrogate key is only to provide a unique identification then there is no reason to insist on a gap-free numbering sequence (in fact, there may be excellent reasons to insist that it actually be non-sequential--more about that later). Similarly, if the surrogate key is only a sort key, there is no reason to insist that the sequence be gap-free, only that it be strictly increasing. We should regard gap-free number sequences as a great evil, to be avoided if possible because there just is no simple, low-cost way to generate one.

Once this requirement is eliminated we can design the application to allocate a surrogate key value and then immediately COMMIT, before beginning the "real" transaction. If the "real" transaction is subsequently rolled back or never even begun, and the generated surrogate key value is wasted, we don't care. Because the COMMIT is done immediately the lock on the generator table is held only long enough to process the update and log the transaction. But we can still do even better than this.

Pre-allocating Surrogate Key Values

If we are prepared to accept gaps in the number sequence at all, we should be prepared to accept gaps of any size. In which case we can reduced lock contention to almost nothing by pre-allocating blocks of numbers at one time and storing them, ready to use, in our application. For instance we may generate a hundred consecutive numbers to use later, and if we end up using only 30, we just won't care. We will look at this idea in detail.

Pre-allocation in an application program written in a language like C or CA-OpenROAD is fairly easy. The code from Example 2 above is altered to increment keyval by a value greater than 1. In this example keyval will be incremented in units of 100, so the application will be able to obtain 100 surrogate key values with just one database update and one briefly held exclusive lock. The application will note the first and last values in the sequence it has reserved, and it will be responsible for sequencing through all the reserved values. The code would be similar to this:

Example 3

nextval = lastval = 0;
while (...) do
    if nextval = lastval then
        /* allocate another block of values */
        UPDATE generator SET keyval = keyval + 100;
        SELECT :nextval = keyval-100, :lastval = keyval FROM generator;
        COMMIT;
    endif;
    ...
    /* increment the internally maintained surrogate key value */
    nextval = nextval + 1;
endwhile;

In this example the increment is hard-coded as 100. It is actually better practice to store the size of the increment in the generator table . This allows the size of the increment to be tuned globally, without any program changes. If the increment column is called incsz then the code above would be written as:

UPDATE generator SET keyval = keyval + incsz;
SELECT :nextval = keyval-incsz, :lastval = keyval;

Keep the State of Different Sequence Generators Separate

We have said that surrogate key values have to be unique, but we ignored one detail that gives us still further options to improve performance. Surrogate key values need not be universally unique, they only need to be unique within their domain. (Domains are not a concept that CA-Ingres supports explicitly.) For simplicity here, the concept is illustrated by a few examples. The "domain" of employee numbers is distinct from the "domain" of animal numbers, and both are distinct from the domain of order numbers. There is no logically meaningful reason ever to join on an employee number and an animal number. They have absolutely nothing to do with each other. Therefore there is no logical necessity for the two numbers sequences to be distinct. It doesn't matter if the same value exists in both series because it is fundamentally incorrect to ever relate them.

If we can have multiple independent key generator functions that do not need to coordinate the values they generate, then we have an opportunity to reduce contention still further. The key value generator for one domain does not need to share state information with the generator for another domain, so it doesn't need to be locked out by it and the two could operate completely concurrently. To make sure they do, we need to keep in mind that CA-Ingres and CA-OpenIngres (for the moment) use page-level locking. [This was true at the time of writing.  Ingres II fully supports row-level locking today, however one should still not plan to exploit it, except as a last-resort. --RH October 2002]  This means that if any row in a page is updated then an exclusive lock is taken on the whole page and hence also on all the other rows in that page. If the key generator state for several different surrogate key domains is kept in the same page then all the generator functions will be competing unnecessarily with each other for access to that page. To fix this problem we either need to use multiple generator tables, one for each surrogate key domain, or organize the generator table as a HASH table with a key to identify which generator uses which row. By structuring it as a HASH table and adjusting the value of MINPAGES we can ensure that each row has a page to itself and hence a page lock on that page will affect only the generator function for that surrogate key domain.

This leads to the following new definition of the generator table:

CREATE TABLE generator
(
    domain VARCHAR(10) NOT NULL NOT DEFAULT,
    keyval INTEGER NOT NULL WITH DEFAULT
)
WITH JOURNALING;
INSERT INTO generator ( domain ) VALUES ( 'emp_nr' );
...
MODIFY generator TO HASH ON domain WITH MINPAGES = ...;
GRANT SELECT, UPDATE TO PUBLIC;

After adjusting MINPAGES, we can check that each row has a page to itself with the following query:

select domain, tid/512 as page_nr from generator order by page_nr; commit;

The code to generate an employee number (identified with a key of "emp_nr") might look like this:

UPDATE generator SET keyval = keyval + 1 WHERE domain = 'emp_nr';
SELECT :keyval = keyval FROM generator WHERE domain = 'emp_nr';
...

Patching Up the Native Logical Key Types

Before leaving the subject of generating surrogate key values as efficiently as possible, let us revisit the native CA-Ingres logical key types. As noted above, using them can lead to catastrophic difficulties with the UNLOADDB and COPYDB utilities, and with the COPY...FROM command. However these system maintained logical keys are still very attractive. If you do not require some of the versatility that can be had by constructing a key value generator from scratch, it may be worth trying to work around the problem with the table_key and object_key types. The work-around is not entirely straightforward, and it relies upon the fact that the COPY...FROM command will not cause any rules defined on a table to be fired.

When creating a table with a system maintained logical key type the trick is to create two columns of the same logical key type. One should be declared to be system maintained, and the other should not. The column which is not system maintained should be the one used in the primary and secondary keys on the table. (Ironically, the column which is system maintained should not be used for a key, ever.) A rule is then defined on the table to be fired after an INSERT, which should invoke a procedure to copy the value from the system maintained column to the other (key) column.

If table foo is defined by:

CREATE TABLE foo
(
    manual_key TABLE_KEY NOT SYSTEM_MAINTAINED,
    auto_key TABLE_KEY WITH SYSTEM_MAINTAINED,
    ...
);
MODIFY foo TO ... ON manual_key;

We can define a procedure to copy the key value from auto_key to manual_key by:

CREATE PROCEDURE inssurkey ( tid INTEGER4 NOT NULL ) AS
BEGIN
    UPDATE foo SET manual_key = auto_key WHERE tid = :tid;
END;

The rule to execute this procedure is then:

CREATE RULE inssurkey AFTER INSERT INTO foo
EXECUTE PROCEDURE inssurkey ( tid = new.tid );

With this work-around, the values in manual_key will be copied out and in with no difficulty so COPYDB and UNLOADDB will work fine. It doesn't matter that the system maintained column will get reinitialized during the processing because its value is only used for a moment, just after the row is inserted. The main drawback of this work-around is that it is potentially quite wasteful, due to the large size of the logical key types, and it doubles the processing and I/O required to insert a row.

Generating Key Values With Special Properties

Having shown how to generate key values in efficient ways, so that the generator function does not seriously degrade overall system performance, let us look at some of the different kinds of key value sequences that we can generate for different purposes. Initially we assumed that the only property we wanted from the surrogate key value generator was uniqueness. However there may be other properties that would be useful. Two additional properties will be discussed here: random-order key values, and verifiable key values.

Random-Order Keys

It is sometimes advantageous to generate key values in random order. Note that we want values that are supplied in random order and emphatically not random numbers. Random numbers may repeat, which would be disastrous for a surrogate key. Before showing one of several approaches to generating values in a random order, we should look at why we would want to do such a thing in the first place.

The most powerful use of random-order keys is in B-tree tables, where they can be used to dramatically improve the performance of systems with many concurrent users performing INSERTs into the B-tree. B-trees are a very popular data structure for several reasons: they do not suffer from overflow as much as other structures, and they provide good look-up performance. Unfortunately they can suffer from a couple of problems when we use a sequential primary key value.

One problem is that inserting large numbers of new rows can cause considerable waste of space. When a page is split, half the data is moved to the next page. The resulting free space is never re-used. This not only wastes space, it also reduces cache efficiency. B-trees are also prone to serious lock contention problems in applications that are INSERT-intensive where the primary key is a sequential value. A brief walk-through of a typical example will make this clear:

Session 1 generates a key value k and uses that value for the primary key column of a row inserted into a B-tree. Session 2 generates a key value k+1 and uses that value for the primary key column of a row inserted into the same B-tree. The value k for the primary key means that session 1 inserts its row into page p of the B-tree, and because this is an INSERT, session 1 takes an exclusive lock on page p. In most cases, unless the page is now full, the value k+1 for the primary key means that session 2 will also attempt to insert its row into page p. But page p is locked, and will remain locked until session 1 does a COMMIT or a ROLLBACK, potentially quite some time later. Session 2 is therefore forced to wait. With more users and more sessions, the problem becomes worse. Even with a 100,000 page table, sequential key values will vector all the users to the just the one  page within that large table and concurrency will collapse.

There are two solutions to this lock contention problem. Convert the table to a HASH table, so that sequential values vector sessions to different pages throughout the table. (However the overflow and maintenance problems of HASH tables may make this option unacceptable.) Alternatively, use a B-tree still, but ensure that successively assigned key values are "far apart" and not monotonic (i.e. not strictly increasing or strictly decreasing).  [Note, as a general rule we would should avoid designing systems that depend on a particular physical organization of the data in order to work properly. Random order keys will ensure that we do not depend on a particular physical organization. --RH October 2002]

Just what "far apart" means is not easy to quantify, but for practical purposes we will be satisfied if it means that the number of times two sessions get vectored to the same page at the same time is close to zero. (Note that we are talking explicitly about multiple sessions here, and implicitly only about sessions inserting a very small number of rows into a table at one time. The situation with batch processes and bulk insertions is somewhat different. We will return to those in a moment.)

There are any number of ways to generate successive values that are far apart, the real trick is to be sure to generate values that are unique too. There are a couple of ways to do that, but just one will be shown here.

Constructing a Random-Order Value Generator

The generator shown here is an implementation of the so-called additive congruential method of generating values in pseudo-random order. It is based on a shift-register and an XOR-gate, and it has its origins in cryptography. It is attractive for our purpose because (i) it tends to generate successive values that are (usually) "far apart" , (ii) it does not repeat until it has generated every possible value, (iii) it produces uniformly distributed values, and (iv) it is easy to detect when it has cycled through all the values it can generate.

To see how such a generator operates we will walk through all the iterations of the 4-bit generator illustrated in the diagram below:

Initially the shift register contains the value 0001. The two low-order (rightmost) bits are XOR-ed together, giving 1, and the result is fed into the high-order (leftmost) bit position and the previous register contents shift one bit right. At the end of one iteration the register contains the value 1000. In the next iteration the two low order bits are 0, so a 0 is deposited in the high-order position and the register ends up with the value 0100. The entire series is shown in the table below:

It might not be obvious that successive values are all that far apart when we are looking at a tiny 4-bit register, but it is clear that the values are generated in no obvious order, all possible values except 0 are eventually produced, and the termination condition is clear--the generator cycles back to 1. With larger register sizes successive values are rarely "close".

Simulating Bit-Operations in Ingres

This looks like a great algorithm for generating guaranteed-unique keys in a pseudo-random order, but unfortunately it is expressed in terms of fundamental bit operations like XOR and SHIFT. CA-Ingres does not offer these functions; if we are forced to use them they would make this algorithm awkward to use in OpenROAD and ABF, and impossible in a database procedure.  [This was true at the time of writing, but Ingres II now supplies bit-manipulation functions.  Sadly they are not useful here. --RH October 2002]

Fortunately it is possible to simulate them, and although the simulation is somewhat tortured compared with what would be possible if we could use the bit operations supported by the hardware, the computational overhead is still trivial (as will be shown later). We take advantage of the fact that shifting a binary number is equivalent to multiplying or dividing it by two, and it turns out that we can use ordinary arithmetic addition as a substitute for the XOR operation. The only other tool we need is the mod() function. Consider the 4-bit shift register shown above again. We will number each bit from right to left, starting at 0. Bit-0 is the low-order bit (i.e. the 2**0 bit), bit-3 is the high-order bit (i.e. the 2**3 bit).

Suppose the content of this conceptual shift register is held in the ordinary CA-Ingres integer4 variable called keyval. The first step is to extract each bit so that we can operate on it. The low-order bit can be obtained by taking mod(keyval,2). This takes the value of keyval and divides it by 2, and returns the remainder. If keyval is odd (i.e. bit-0 is 1) we get 1. If keyval is even (i.e. bit-0 is 0) we get 0.

If we now divide keyval by 2, that is, shift it right 1 bit, we can use the mod function again, to get the value of bit-1. If the value of keyval is initially as shown above, then mod(keyval,2) is 1, and mod(keyval/2,2) is 0. This process of shifting right (dividing by 2) and taking the result modulo 2 can be repeated until every bit in the word has been extracted.

Now that we have extracted the value of bit-0 and bit-1, we add them together and reduce the result modulo 2. The result of this operation is identical to XOR.

The result of this computation then has to be shifted 3 bits left (i.e. multiplied by 2**3, =8) and fed back into the shift register in the high-order position (bit-3). The previous content of the shift register has to be shifted right 1 bit (divided by 2) first. This is all carried out at once in the following CA-Ingres expression:

keyval/2+mod(mod(keyval,2)+mod(keyval/2,2),2)*8

This can easily be incorporated into the surrogate key generator shown in Example 2 above:

UPDATE generator SET keyval=keyval/2+mod(mod(keyval,2)+mod(keyval/2,2),2)*8;
SELECT keyval INTO :keyval FROM generator;
...
COMMIT;