Natural versus Surrogate Primary Keys in a Distributed SQL Database

There’s a subtle, but critical, difference between the two notions business-unique key and primary key in a relational database. For example, in a “users” table, the “user_id” could be the primary key while the “email_address” (which must be not null and unique) could be the business-unique key. The columns that implement each notion may or may not coincide. This post shows that, especially in a distributed SQL database, it’s better that they do not coincide. In other words, that it’s better to choose a surrogate—and therefore generated—primary key. We will see how the de facto standard method for generating surrogate key values in a monolithic SQL database has notable drawbacks in a distributed database—and show you the preferred alternative.

YugabyteDB is an open source, high-performance distributed SQL database built on a scalable and fault-tolerant design inspired by Google Spanner. YugabyteDB uses its own special distributed document store called DocDB. But it provides SQL and stored procedure functionality by re-using the “upper half” of the standard PostgreSQL source code. This is explained in the two part blog post “Distributed PostgreSQL on a Google Spanner Architecture”: (1) Storage Layer; and (2) Query Layer.

What are surrogate primary keys

I’m going to take these two rules as axiomatic:

• Every table must have a defined primary key constraint.
• Every table must have at least one business unique key. One of these might coincide with the primary key; or maybe none coincide. A business unique key that doesn’t coincide with the primary key must have its own unique, not null constraint.

I’ll define these two terms, primary key and business unique key, and justify my stance that the rules that I stated are axiomatic, soon.

A huge amount of SQL teaching, and testcase development, uses a table created along these lines:

create table users(
  user_id int
    generated always as identity
    constraint items_items_pk primary key,

  email_address text
    constraint items_name_nn not null
    constraint items_name_unq unique,

  preferred_given_name varchar,

  family_name varchar not null

  ...);

The definition of business-unique key is operational: it’s a value that means something in the business world; and ordinary people specify that value to retrieve the facts about a single table row of interest. A user’s email address certainly meets these criteria. After all, any email address will, by construction, be unique on the whole planet—and presently beyond!

The definition of primary key is formal: it’s the column list that’s the argument for the defined primary key constraint. And, according to proper practice, it’s a primary key, and only this, that can be the target of a foreign key constraint. A user’s email address is also a candidate to be the table’s primary key—at least this choice might tempt the beginner.

I must have seen hundreds—if not thousands—of documentation accounts, blog posts, bug testcases, and so on that illustrate their point with some variant of a “users” table (very often specialized to “employees”). And I’ve never seen a single one that uses “email_address” as the primary key. Why is this? It’s because a person can at any moment change the email address that they want to use in some particular system. Propagating such changes to foreign key columns in other tables is, in general a nightmare, and for this reason most seasoned practitioners of table design stick to the rule that primary keys must be immutable—both with respect to value and with respect to datatype. Experience—sometimes painful—has shown that it’s hugely difficult to identify an immutable, unique, phenomenon in the business world that could serve as a table’s natural primary key.

So… if neither “email_address”, nor any other naturally occurring value, can be used as the primary key of the “users” table, what can be? The only remaining choice is to make the primary key a synthetic value with no meaning in the business world that the table models—in other words a surrogate.

The only way, then, to reconcile the requirements that every table must have at least one business-unique key and that every table must have a primary key is to separate the notions so that a table has both. This implies that the primary key, because it holds a synthetic value, must be generated behind the scenes. (A surrogate primary key is almost always just a single column.) Another very familiar illustration of this point is given by a vehicle’s identification number—its VIN. My car’s VIN has this format: “xxxx xxxxx xxx xxxx”. It was clearly generated! This notion was invented precisely because the natural business unique key, the vehicle’s registration mark, is subject to change during a car’s lifetime.

Operations that change a table’s content—like ”insert” and “delete”—when its business-unique key and its primary key are distinct, are obviously more expensive than when they coincide. (This is because the business-unique key, when it’s distinct, needs its own secondary index.) To put this another way, using a surrogate primary key is more expensive than using a natural primary key. It’s for this reason that two religions—I might almost say two cults—have emerged. One allows and encourages natural primary keys; and the other bans them and insists on using a distinct column for the surrogate primary key. But life is always like this: a trade-off between short term expediency and long term proper practice.

It now should be clear to readers where I stand on this point: in my book, the natural primary key cult is close to the Flat Earth Society!

Primary keys in YugabyteDB

Tables in a distributed SQL database are likely to have a very much larger row count than tables in a monolithic database. Data volume is, after all, among the critical factors that drive the choice to use YugabyteDB. This means that the pain brought by changing the primary key and dealing with the consequences in child tables—huge as this is in a monolithic database—becomes close to insuperable in a distributed database.

Even in the exceedingly rare case that a table happens not to be the target of a single foreign key constraint, and when the present limitation that primary keys in YugabyteDB really are immutable is lifted (see the appendix), changing the structure of such a table’s primary key will be expensive. The plan is to build the new table in the background and then to execute a quick swap between the old table and its replacement. This means that downtime will be minimized. Nevertheless, the operation will steal resources from the cluster’s normal duties so that performance will suffer during the rebuild.

How to populate a surrogate primary key in YugabyteDB

Precisely because the values used by a surrogate primary key constraint have no significance in the user’s world, they must be generated behind the scenes automatically using an explicit or implicit trigger-based scheme. And for the same reason (and as mentioned), such a primary key constraint is almost always defined on exactly one column.

The de facto standard approach for a monolithic SQL database

This pattern is typically used in a monolithic SQL database:

create table t(k int generated always as identity, ...);

(You might see something more commodious than “int”, or its equivalent in the database system at hand, if the designer expects the table to hold, over time, in excess of four billion rows—unlikely as this might seem in the context of a monolithic database.)

The syntax might vary according to the database system’s vendor. The effect of “generated…  as identity” is implicitly to generate a sequence (you can see it with the \dmeta-command) that is used by an invisible, system-generated trigger to populate the so-annotated column. However, though a sequence doesn’t behave transactionally (you still “use up” values that it supplies even when you roll back), its use in a distributed database nevertheless brings a “distributed transaction” cost. Briefly, this follows from the requirement that each node must be able to pull a unique value from a sequence. You might think that supplying each node with a largish batch of values from a central “oracle”, each time the last batch is used up, might alleviate the problem. But such a scheme still brings significant design challenges, and associated costs, when the overall design requires that there be no single point of failure—in other words no central “oracle”!

The recommended approach for YugabyteDB

Because of the relatively poor performance of sequences in a distributed SQL database, a reliable pseudo-random generator is preferred in YugabyteDB. YugabyteDB inherits the ability to create so-called PostgreSQL extensions. And, as is explained in the documentation here, it’s very easy to do this (as a superuser):

create extension pgcrypto;

(This installs the extension in the schema that is current when the statement is issued. And you then grant “usage” on the schema to other users who need to use its facilities.) This is literally all you have to do. Following this, you can now create a table like this:

create table t(k uuid default some_schema.gen_random_uuid(), ...);

UUID stands for “Universally unique identifier” (see this Wikipedia article). And, true to its name, the “gen_random_uuid()” function populates the table’s surrogate primary key column automatically by returning a different value on each call, no matter on which computer it’s called—just what you need in a multi-node YugabyteDB cluster. The probability of collision is vanishingly small—so small that you need not take account of collision risk with defensive application code.

My informal timing tests, using this:

insert into t(v) select * from generate_series(1, 1000000);

after each of the two “create table” variants that I show above, show that “default gen_random_uuid()” is about twice as fast as “generated always as identity”.

Note: I used a single node YugabyteDB cluster on my MacBook for the test. You can expect to see different ratios in different environments. But you can reliably expect to see that “gen_random_uuid()” is noticeably faster than “generated always as identity”.

Notice that autogeneration of the surrogate primary key column implies an “insert… returning k into” scheme when you create a new master row and some child detail rows for it in a single transaction.

Alternatives to “gen_random_uuid()”

The documentation here explains how to create the “uuid-ossp” extension. This involves more effort by the administrator than installing “pgcrypto”; but it’s certainly a practical choice.

This extension brings several alternative pseudo-random UUID generator functions. One example is “uuid_generate_v4()”. Some people prefer this to “gen_random_uuid()” because part of its return value depends on the host machine’s MAC address. My timing tests show it to be just a hair faster than “gen_random_uuid()”. But I’d expect the difference to disappear in the noise in ordinary use by an application that uses a YugabyteDB cluster.

Note: The “clock_timestamp()” SQL built-in—it reads the system clock and needs no extension installation—might seem to be a tempting choice. However, because its nominal precision is 1 microsecond, collisions are bound to occur fairly frequently in a multi node system that ingests rows on each node at a high rate. Anyway, my informal timing test showed it to have about the same speed as “gen_random_uuid()”—so there’s no reason to consider it.

Conclusion

In this post, I’ve defined the terms natural primary key and surrogate primary key, told you about the religious tension between the natural key aficionados and the surrogate key aficionados, and shown you that the debate takes on a “difference in degree becomes a difference in kind” character when you do the table design for any distributed SQL database and in particular for a YugabyteDB cluster because the table row counts are expected to be huge. Here’s my recommendation:

• Specify a surrogate primary key for every table in your design.
• Identify at least one business-unique key and create a not null, unique constraint on each.
• Define the column that participates in every primary key constraint with datatype “uuid” and populate it declaratively using “default gen_random_uuid()”—or, if you prefer, one of the functions, like “uuid_generate_v4()”, that are brought by the “uuid-ossp” extension.

You can think of this like an insurance policy. You might resent paying the premium—extra column(s) with secondary index(es). But you accept that the modest cost is justified with respect to the ruinous cost of changing the definition of a natural primary key—when you realize that, contrary to your initial understanding of the world that you’re modelling, you have no choice but to do this.

What’s next?

• Compare YugabyteDB in depth to databases like CockroachDB, Google Cloud Spanner and MongoDB.
• Get started with YugabyteDB on the cloud or container of your choice.
• Contact us to learn more about licensing, pricing or to schedule a technical overview.

Appendix:
In the short term, primary keys in YugabyteDB really are immutable

As mentioned in the overview at the start, YugabyteDB’s SQL subsystem is implemented by re-using the “upper half” of the standard PostgreSQL source code. This is explained in the blog post “Distributed PostgreSQL on a Google Spanner Architecture—Query Layer”. This means that PostgreSQL syntax is accepted. However, you’ll sometimes see a semantic error to the effect that the attempted functionality isn’t yet supported. (The message text includes either a link to the issue in our GitHub repository that tracks the effort to implement the missing functionality or an invitation to the user to file a new issue and explain the use case where the missing functionality is problematic.) PostgreSQL supports the following operations on primary key columns:

• When you create a table without a primary key:
  • You can alter the table to create a primary key constraint on a list of existing columns.
  • You can alter the table to add a new column making it the primary key.
• When you create a table with a primary key:
  • You can alter the table to drop the primary key constraint.
  • You can alter the table to drop a column that the primary key constraint spans.
  • You can alter the datatype of a column (and this includes changing the width of a varchar column) that the primary key constraint spans.
  • You can change a value in a column that the primary key constraint spans.

Here are some examples:

alter table t
add constraint t_pk primary key(non_pk_column);

alter table t
add column new_column int constraint t_pk primary key;

alter table t
drop column part_of_the_pk;

update t
set part_of_the_pk = 2
where part_of_the_pk = 1 and the_other_part_of_the_pk = 2;

alter table t
alter column k type varchar(20);

The listed functionality is not yet supported in YugabyteDB. But we plan to close this gap presently.