[prev in list] [next in list] [prev in thread] [next in thread] 

List:       postgresql-general
Subject:    [GENERAL] Mapping output from a SEQUENCE into something non-repeating/colliding
From:       Craig Ringer <craig () postnewspapers ! com ! au>
Date:       2009-04-30 8:54:08
Message-ID: 49F96730.4000706 () postnewspapers ! com ! au
[Download RAW message or body]

Hi

This must be a fairly common requirement, but either I don't know how to
ask Google about it or there's not as much out there as I would've expected.

I'm looking for a way to map the output from a monotonically increasing
sequence (not necessarily gapless - ie a normal Pg SEQUENCE) into a
fairly random different value in the availible space with a 1:1
input->output relationship. In other words, for the input "27" the
output will always be the same (say 32 bit) number, and no other input
will produce that output.

Note that I'm *NOT* looking for a PRNG that takes the previous output as
its input. That'd force me to use the same techniques as for a gapless
sequence in Pg, with all the associated horror with locking and
deadlocks, the performance issues, etc.

Does anyone here know of a good algorithm to do this that doesn't just
iterate `n' times through a PRNG with the same seed, but instead does a
true non-colliding space mapping?

If I find something good and there aren't any existing Pl/PgSQL
implementations I'll post one for others' use, since I'm pretty sure it
must come up a lot. You don't want your database to send out "invoice
#1" or "customer #1" after all.

(I'm also going to be looking for efficient ways to calculate effective
check digits for arbitrary numbers within a certain range, too, and will
post something for that, but that comes later).

--
Craig Ringer

-- 
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general
[prev in list] [next in list] [prev in thread] [next in thread]