Re: [GENERAL] using ID as a key - Mailing list pgsql-general

And here's the description of the "high-low" algorithm for
programs to create unique id's in a multi-user environement.


*** Structure of the identifier ***

Contents of the identifier:

 a) session-id
 b) current number within session
 c) class id

These are three numbers. You may create a unique string to get
the id value into a single column.

In our product we decided to print each number to base 36 (to get well
defined ascii string. Fill the number a) and b) with special
characters (e.g. '#') to get strings with lengh of 6.

Then we do the same with c) but the max string length is here 3.

The total size of the id is stored in a column defined via
char(15). You will define an index on the column.

Very nice would be an index handling something like "right(id,3)",
because then you may not only query for a specific id value but
also for all instances of a special class.

*** Structure of the table doing the initial information transfer ***

We need a special table on the database server. They have three columns:

  FX1 -- holding the next valid id within this session
  FX2 -- holding the session number

A row can be written as (internal/session). These rows can be
seen as parameters which can be used from clients to generate unique
identifier.

*** How does it work ***

In the beginning the session table is empty or holds some session
informations. The starting client locks the table.

 -> If the session-table is empty the client inserts a pair (0/2).
    (session 2, id 0 within this session)

    and uses 1 as it's own session number and 0 as the id number.


 -> if the session-table is not empty is looks for the rows with the
    highest (h) and lowest session number (l).

    -> if both numbers are equal it stores a new row into the session
       table the value-pair (0/h+1) and uses the row (h) for further
       work. It removes the row (h) - or actually updates the row (h)
       to become the row (h+1).

    -> otherwise the application removes this row with session number
       (l) and uses row (l) for further work.

The application unlocks the session-table.

*** After the initialization phase *

Now the application can create unique id's without doing a query
against the database (just be increment the id number within the
session). There may be the case where the application has created
so many objects that it uses all available numbers within a session:
ok, then it goesback to the initialization phase and calculates the
next session row.

If the application terminates is lockes the table and stores it's
actual values (?,session number) into the database. Other clients
may use this number in the future.

If the application crashes you may loose some id's -- but this is
not practically a problem.


If something is not clear - please ask.


Marten Feldtmann