News

Welcome to End Point’s blog

Ongoing observations by End Point people

Text sequences

Somebody recently asked on the Postgres mailing list about "Generating random unique alphanumeric IDs". While there were some interesting solutions given, from a simple Pl/pgsql function to using mathematical transformations, I'd like to lay out a simple and powerful solution using Pl/PerlU

First, to paraphrase the original request, the poster needed a table to have a text column be its primary key, and to have a five-character alphanumeric string used as that key. Let's knock out a quick function using Pl/PerlU that solves the generation part of the question:

DROP FUNCTION IF EXISTS nextvalalpha(TEXT);
CREATE FUNCTION nextvalalpha(TEXT)
RETURNS TEXT
LANGUAGE plperlu
AS $_$
  use strict;
  my $numchars = 5;
  my @chars = split // => qw/abcdefghijkmnpqrstwxyzABCDEFGHJKLMNPQRSTWXYZ23456789/;
  my $value = join '' => @chars[map{rand @chars}(1..$numchars)];
  return $value;
$_$;

Pretty simple: it simply pulls a number of random characters from a string (with some commonly confused letters and number removed) and returns a string:

greg=# SELECT nextvalalpha('foo');
 nextvalalpha
--------------
 MChNf
(1 row)

greg=# SELECT nextvalalpha('foo');
 nextvalalpha
--------------
 q4jHm
(1 row)

So let's set up our test table. Since Postgres can use many things column DEFAULTS, including user-defined functions, this is pretty straightforward:

DROP TABLE IF EXISTS seq_test;
CREATE TABLE seq_test (
  id    VARCHAR(5) NOT NULL DEFAULT nextvalalpha('foo'),
  city  TEXT,
  state TEXT
);

A quick test shows that the id column is auto-propagated with some random values:

greg=#< PREPARE abc(TEXT,TEXT) AS INSERT INTO seq_test(city,state) 
greg=# VALUES($1,$2) RETURNING id;

greg=# EXECUTE abc('King of Prussia', 'Pennsylvania');
  id
-------
 9zbsd
(1 row)

INSERT 0 1

greg=# EXECUTE abc('Buzzards Bay', 'Massachusetts');
  id
-------
 4jJ5D
(1 row)

INSERT 0 1

So far so good. But while those returned values are random, they are not in any way unique, which a primary key needs to be. First, let's create a helper table to keep track of which values we've already seen. We'll also track the 'name' of the sequence as well, to allow for more than one unique set of sequences at a time:

DROP TABLE IF EXISTS alpha_sequence;
CREATE TABLE alpha_sequence (
  sname TEXT,
  value TEXT
);
CREATE UNIQUE INDEX alpha_sequence_unique_value ON alpha_sequence(sname,value);

Now we tweak the original function to use this new table.

CREATE OR REPLACE FUNCTION nextvalalpha(TEXT)
RETURNS TEXT
SECURITY DEFINER
LANGUAGE plperlu
AS $_$
  use strict;
  my $sname = shift;
  my @chars = split // => qw/abcdefghijkmnpqrstwxyzABCDEFGHJKLMNPQRSTWXYZ23456789/;
  my $numchars = 5;
  my $toomanyloops = 10000; ## Completely arbitrary pick
  my $loops = 0;

  my $SQL = 'SELECT 1 FROM alpha_sequence WHERE sname = $1 AND value = $2';
  my $sth = spi_prepare($SQL, 'text', 'text');

  my $value = '';
  SEARCHING:
  {
    ## Safety valve
    if ($loops++ >= $toomanyloops) {
      die "Could not find a unique value, even after $toomanyloops tries!\n";
    }
    ## Build a new value, then test it out
    $value = join '' => @chars[map{rand @chars}(1..$numchars)];
    my $count = spi_exec_prepared($sth,$sname,$value)->{processed};
    redo if $count >= 1;
  } 

  ## Store it and commit the change
  $SQL = 'INSERT INTO alpha_sequence VALUES ($1,$2)';
  $sth = spi_prepare($SQL, 'text', 'text');
  spi_exec_prepared($sth,$sname,$value);
  return $value;
$_$;

Alright, that seems to work well, and prevents duplicate values. Or does it? Recall that one of the properties of sequences in Postgres is that they live outside of the normal MVCC rules. In other words, once you get a number via a call to nextval(), nobody else can get that number again (even you!) - regardless of whether you commit or rollback. Thus, sequences are guaranteed unique across all transactions and sessions, even if used for more than one table, called manually, etc. Can we do the same with our text sequence? Yes!

For this trick, we'll need to ensure that we only return a new value if we are 100% sure it is unique. We also need to record the value returned, even if the transaction that calls it rolls back. In other words, we need to make a small 'subtransaction' that commits, regardless of the rest of the transaction. Here's the solution:

CREATE OR REPLACE FUNCTION nextvalalpha(TEXT)
RETURNS TEXT
SECURITY DEFINER
LANGUAGE plperlu
AS $_$
  use strict;
  use DBI;
  my $sname = shift;
  my @chars = split // => qw/abcdefghijkmnpqrstwxyzABCDEFGHJKLMNPQRSTWXYZ23456789/;
  my $numchars = 5;
  my $toomanyloops = 10000;
  my $loops = 0;

  ## Connect to this very database, but with a new session
  my $port = spi_exec_query('SHOW port')->{rows}[0]{port};
  my $dbname = spi_exec_query('SELECT current_database()')->{rows}[0]{current_database};
  my $dbuser = spi_exec_query('SELECT current_user')->{rows}[0]{current_user};
  my $dsn = "dbi:Pg:dbname=$dbname;port=$port";
  my $dbh = DBI->connect($dsn, $dbuser, '', {AutoCommit=>1,RaiseError=>1,PrintError=>0});

  my $SQL = 'SELECT 1 FROM alpha_sequence WHERE sname = ? AND value = ?';
  my $sth = $dbh->prepare($SQL);

  my $value = '';
  SEARCHING:
  {
    ## Safety valve
    if ($loops++ >= $toomanyloops) {
      die "Could not find a unique value, even after $toomanyloops tries!\n";
    }
    ## Build a new value, then test it out
    $value = join '' => @chars[map{rand @chars}(1..$numchars)];
    my $count = $sth->execute($sname,$value);
    $sth->finish();
    redo if $count >= 1;
  } 

  ## Store it and commit the change
  $SQL = 'INSERT INTO alpha_sequence VALUES (?,?)';
  $sth = $dbh->prepare($SQL);
  $sth->execute($sname,$value); ## Does a commit

  ## Only now do we return the value to the caller
  return $value;
$_$;

What's the big difference between this one and the previous version? Rather than examine the alpha_sequence table in our /current/ session, we figure out who and where we are, and make a completely separate connection to the same database using DBI. Then we find an unused value, INSERT that value into the alpha_sequence table, and commit that outside of our current transaction.Only then can we return the value to the caller.

Postgres sequences also have a currval() function, which returns the last value returned via a nextval() in the current session. The lastval() function is similar, but it returns the last call to nextval(), regardless of the name used. We can make a version of these easy enough, because Pl/Perl functions have a built-in shared hash named '%_SHARED'. Thus, we'll add two new lines to the end of the function above:

...
  $sth->execute($sname,$value); ## Does a commit
  $_SHARED{nva_currval}{$sname} = $value;
  $_SHARED{nva_lastval} = $value;
...

Then we create a simple function to display that value, as well as throw an error if called too early - just like nextval() does:

DROP FUNCTION IF EXISTS currvalalpha(TEXT)
CREATE FUNCTION currvalalpha(TEXT)
RETURNS TEXT
SECURITY DEFINER
LANGUAGE plperlu
AS $_$
  my $sname = shift;
  if (exists $_SHARED{nva_currval}{$sname}) {
    return $_SHARED{nva_currval}{$sname};
  }
  else {
    die qq{currval of text sequence "$sname" is not yet defined in this session\n};
  }
$_$;

Now the lastval() version:

DROP FUNCTION IF EXISTS lastvalalpha();
CREATE FUNCTION lastvalalpha()
RETURNS TEXT
SECURITY DEFINER
LANGUAGE plperlu
AS $_$
  if (exists $_SHARED{nva_lastval}) {
    return $_SHARED{nva_lastval};
  }
  else {
    die qq{lastval (text) is not yet defined in this session\n};
  }
$_$;

For the next tests, we'll create a normal (integer) sequence, and see how it acts compared to our newly created text sequence:

DROP SEQUENCE IF EXISTS newint;
CREATE SEQUENCE newint STARTS WITH 42;

greg=# SELECT lastval();
ERROR: lastval is not yet defined in this session

greg=# SELECT currval('newint');
ERROR:  currval of sequence "newint" is not yet defined in this session

greg=# SELECT nextval('newint');
 nextval
---------
      42
(1 row)

greg=# SELECT currval('newint');
 currval
---------
      42

greg=# SELECT lastval();
 lastval
---------
      42
greg=# SELECT lastvalalpha();
ERROR: error from Perl function "lastvalalpha": lastval (text) is not yet defined in this session

greg=# SELECT currvalalpha('newtext');
ERROR:  error from Perl function "currvalalpha": currval of text sequence "newtext" is not yet defined in this session

greg=# SELECT nextvalalpha('newtext');
 nextvalalpha
--------------
 rRwJ6

greg=# SELECT currvalalpha('newtext');
 currvalalpha
--------------
 rRwJ6

greg=# SELECT lastvalalpha();
 lastvalalpha
--------------
 rRwJ6

There is one more quick optimization we could make. Since the %_SHARED hash is available across our session, there is no need to do anything in the function more than once if we can cache it away. In this case, we'll cache away the server information we look up, the database handle, and the prepares. Our final function looks like this:

CREATE OR REPLACE FUNCTION nextvalalpha(TEXT)
RETURNS TEXT
SECURITY DEFINER
LANGUAGE plperlu
AS $_$
  use strict;
  use DBI;
  my $sname = shift;
  my @chars = split // => qw/abcdefghijkmnpqrstwxyzABCDEFGHJKLMNPQRSTWXYZ23456789/;
  my $numchars = 5;
  my $toomanyloops = 10000;
  my $loops = 0;

  ## Connect to this very database, but with a new session
  if (! exists $_SHARED{nva_dbi}) {
    my $port = spi_exec_query('SHOW port')->{rows}[0]{port};
      my $dbname = spi_exec_query('SELECT current_database()')->{rows}[0]{current_database};
    my $dbuser = spi_exec_query('SELECT current_user')->{rows}[0]{current_user};
    my $dsn = "dbi:Pg:dbname=$dbname;port=$port";
    $_SHARED{nva_dbi} = DBI->connect($dsn, $dbuser, '', {AutoCommit=>1,RaiseError=>1,PrintError=>0});
    my $dbh = $_SHARED{nva_dbi};
    my $SQL = 'SELECT 1 FROM alpha_sequence WHERE sname = ? AND value = ?';
    $_SHARED{nva_sth_check} = $dbh->prepare($SQL);
    $SQL = 'INSERT INTO alpha_sequence VALUES (?,?)';
    $_SHARED{nva_sth_add} = $dbh->prepare($SQL);
  }


  my $value = '';
  SEARCHING:
  {
    ## Safety valve
    if ($loops++ >= $toomanyloops) {
      die "Could not find a unique value, even after $toomanyloops tries!\n";
    }
    ## Build a new value, then test it out
    $value = join '' => @chars[map{rand @chars}(1..$numchars)];
    my $count = $_SHARED{nva_sth_check}->execute($sname,$value);
    $_SHARED{nva_sth_check}->finish();
    redo if $count >= 1;
  } 

  ## Store it and commit the change
  $_SHARED{nva_sth_add}->execute($sname,$value); ## Does a commit
  $_SHARED{nva_currval}{$sname} = $value;
  $_SHARED{nva_lastval} = $value;
  return $value;
$_$;

Having the ability to reach outside the database in Pl/PerlU - even if simply to go back in again! - can be a powerful tool, and allows us to do things that might otherwise seem impossible.

9 comments:

Ethan Rowe said...

Interesting.

Wouldn't you want to explicitly set the volatility on these functions?

What's the need for randomness? Is it simply to avoid the appearance of predictability?

Might it not suffice to interleave predictable, numerically-driven portions of a string with randomly-generated portions of a string? For instance:
- have a numeric sequence
- take the output of nextval and convert it to a string form (perhaps packing it into a base-36 "number" so you have digits 0-9, a-z); zero-pad the number to make it a fixed-length string
- generate a random string with the same "digit" range of the same size
- interleave the two

The sequence-driven portion alone ensures uniqueness per invocation, across transactions. The random portion gives unpredictability.

This may be really stupid so feel free to mock me without ruth.

Greg Sabino Mullane said...

Ethan: The default for functions is VOLATILE, but it wouldn't hurt to be explicit about it. Why the need for randomness? You'd have to ask the original poster, but I imagine the main impetus would be not being able to view other rows and/or derive information about them (e.g. creation time). The sequence + random is a good idea as well, and is certainly simpler than my solution (but to be fair, I tasked myself to answer the original question, however misguided it may have been - I suspect a schema using a five character text primary key may not have been thought through all the way).

Jon Jensen said...

Very clever, Greg.

It's important to note that reconnecting to the database may not work, or not as expected, because of pg_hba.conf restrictions:

(1) The connection may require md5, and you don't have the password.

(2) A connection may have been allowed and made from a particular host, but may not be allowed from localhost as is done here.

Aside from that, of course you burn up connection slots doing this, which should be considered as it may push a busy server over the edge.

I think if you really want to make a separate connection to track generated keys, it'd be best to have a separate user with that who is allowed to INSERT to the tracking table only, and never UPDATE or DELETE even from it, and only allow connections by that user from localhost for these special connections.

All that quite aside from whether this is a good idea. :) But it's a great vehicle for exploring the different semantics of sequences.

Luca said...

Why not create a table of monotonically increasing integers mapped to your random strings, fill it with lots of rows beforehand and simply use a normal sequence as a key to lookup the unique string from the key table? This would be enormously faster and would not require establishing a connection inside a function. Simply break the problem in two pieces and use a lookup table.
Uniqueness of strings can be guaranteed through simple constraints in the lookup table.
My few cents.

Greg Sabino Mullane said...

Jon: agree completely that the connection may not work (and that we may want to connect as a specific user, rather than the caller). However, the localhost is not a worry: we are connecting via the local Unix socket, not over TCP/IP. This is all somewhat of a proof of concept: if I was writing this for a production system, I'd cover more corner cases (and probably talk them out of the whole idea in the first place!)

Greg Sabino Mullane said...

Luca: the problem with that comes in the population of the table when you run out of values. Having the calling function do so is the only sane approach unless you have a daemon or cronjob, and the problem becomes how do two concurrent processes coordinate on which set of numbers to add to the table? We could do a try/catch around the inserts, but that's now getting as complex as the original approach. :)

Ethan Rowe said...

Talking them out of the idea seems best. A conclusion not dissimilar from Joshua's assessment of thermonuclear war.

radek said...

Ethan: the sequence-driven portion ensures uniqueness, but not anymore after being combined (I assume you mean XOR) with the random portion.

This solution becomes as good as the purely random one, which for length=5 base=36 gives 60466176 unique values -- 8.27% chance of a conflict on insert if the table contains 5M rows.

Ethan Rowe said...

radek: by "interleave" I meant a dumb intermixing of the strings, not an XOR of the sequence with a random integer.

So you get some sequence and transform it to a predictable fixed-length string. 5 characters in the range 0-9/a-z, for instance. And you get a randomly-generated string in the same range of the same length.
seq_string: 005ak
rdm_string: j4nm2

And mix them in some consistent fashion, such as alternating characters:
result: j040n5ma2k

This is guaranteed to be unique because the fixed lengths and consistent combination logic ensure that the sequence-generated (and thus unique) combination of characters always come at the same ordinal positions in the final string, and therefore ensure uniqueness.

A portion of the string is sequential and predictable, but you cannot use that alone to predict an overall value, because half of the characters are random.

It comes down to the reason for desiring random identifiers in the first place. I'm assuming the avoidance of predictability is desired, and this would get you at least part of the way there. It would not prevent somebody from conceiving of potentially valid keys, though. So it may be pointless.