June 25th, 2007 by depesz | Tags: | 4 comments »
Did it help? If yes - maybe you can help me?

polish disclaimer begin;

w celu trenowania języka, oraz by poszerzyć teoretyczny zasięg bloga będę teraz starał się pisać po anglijsku. wytykanie błędów mile widziane.

polish disclaimer commit;

ok, so you're trying to build something that needs random-text record identifiers. perhaps a new tinyurl-kind-of-service.

and you are thinking about a way to implement random text generation in a way that:

  • there will be no direct information which record was added just after given one (knowing it's textual id). i mean – the text id's cannot be sequential like a, b, c, d, …
  • the code should be as small as possible. we do not want to start with 40-characters behemoths just to make sure no-one can know which ones were before another.
  • it should be as simple as possible.

requirements 1 and 2 are almost contrary, but we can manage.

first – let's assume we will generate random id's out of these characters: a-z, A-Z, 0-9. this gives us 62 different characters.

now. let's do it that way:

  1. assume current_length to be 1
  2. generate random string of length = current_length
  3. if this id is already taken, increment current_length and repear from step 2
  4. voila. new id generated.

it matches both first and second requirement from list.

as for simplicity.

let's try to implement:

first, let's create a test table with unique constraint on text-id field (i keep numerical id “just in case"):

CREATE TABLE test_table (
id BIGSERIAL,
random_code TEXT NOT NULL DEFAULT '',
something TEXT ,
PRIMARY KEY (id)
);
CREATE UNIQUE INDEX ui_test_table_random_code ON test_table (random_code);

now, let's create function for random string generation:

CREATE OR REPLACE FUNCTION get_random_string(string_length INT4)
RETURNS TEXT
LANGUAGE 'plpgsql'
AS $BODY$
DECLARE
possible_chars TEXT = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz';
output TEXT = '';
i INT4;
pos INT4;
BEGIN
FOR i IN 1..string_length LOOP
pos := 1 + cast( random() * ( length(possible_chars) - 1) as INT4 );
output := output || substr(possible_chars, pos, 1);
END LOOP;
RETURN output;
END;
$BODY$;

code looks simply i guess. in case it doesn't – ask question in comments area.

now. the master-code, which is a trigger:

CREATE OR REPLACE FUNCTION trg_test_table_get_random_code()
RETURNS TRIGGER
LANGUAGE 'plpgsql'
AS $BODY$
DECLARE
string_length INT4 = 1;
temprec RECORD;
new_string TEXT;
BEGIN
LOOP
new_string := get_random_string(string_length);
SELECT count(*) INTO temprec FROM test_table WHERE random_code = new_string;
IF temprec.count = 0 THEN
NEW.random_code := new_string;
EXIT;
END IF;
string_length := string_length + 1;
IF string_length >= 30 THEN
raise exception 'random string of length == 30 requested. something''s wrong.';
END IF;
END LOOP;
RETURN NEW;
END;
$BODY$;
CREATE TRIGGER trg_test_table_get_random_code BEFORE INSERT ON test_table FOR EACH ROW EXECUTE PROCEDURE trg_test_table_get_random_code();

basically this trigger is implementation of algorithm i wrote couple of lines above.

is it done? basically yes.

after 10 inserts i got this content of table:

# select * from test_table;
id | random_code | something
----+-------------+-----------
1 | x | x
2 | B | x
3 | w | x
4 | U | x
5 | b | x
6 | OE | x
7 | N | x
8 | zn | x
9 | Y | x
10 | JY | x
(10 rows)

if you know your database-things you will see that the code has one serious (or not serious, depending on your view) problem.

if two inserts will happen at the same time, it is possible that one of them will raise exception of unique violation.

this is because there is a race condition between select count(*) and actual insert which takes place only after trigger finishes.

is there no hope? there is. but we have to modify the way we insert data to test table.

until now, i was able to simply: insert into test_table (something) values (‘x'); and it called my trigger code which set the random_code to whatever ‘s appropriate.

but if i want this to be a more fault-proof, i need to throw away the trigger, and force client to do inserts using select's.

like this:

CREATE OR REPLACE FUNCTION smart_insert(IN in_something TEXT, OUT new_key TEXT)
LANGUAGE 'plpgsql'
AS $BODY$
DECLARE
string_length INT4 = 1;
BEGIN
LOOP
new_key := get_random_string(string_length);
BEGIN
INSERT INTO test_table(something, random_code) VALUES (in_something, new_key);
RETURN;
EXCEPTION WHEN unique_violation THEN
-- do nothing
END;
string_length := string_length + 1;
IF string_length >= 30 THEN
raise exception 'random string of length == 30 requested. something''s wrong.';
END IF;
END LOOP;
END;
$BODY$;

and now, i can:

select smart_insert('x');

done.

or is it?

what if you'd like to be able to generate these text keys in more than one table? (for simplicity sake let's assume all of them have the same fields).

in such a case we would modify the function to be:

CREATE OR REPLACE FUNCTION smart_insert(IN table_name TEXT, IN in_something TEXT, OUT new_key TEXT)
LANGUAGE 'plpgsql'
AS $BODY$
DECLARE
string_length INT4 = 1;
use_sql TEXT;
BEGIN
LOOP
new_key := get_random_string(string_length);
BEGIN
use_sql := 'INSERT INTO ' || quote_ident( table_name ) || ' (something, random_code) VALUES (' || quote_literal(in_something) || ', ' || quote_literal(new_key) || ')';
EXECUTE use_sql;
RETURN;
EXCEPTION WHEN unique_violation THEN
-- do nothing
END;
string_length := string_length + 1;
IF string_length >= 30 THEN
raise exception 'random string of length == 30 requested. something''s wrong.';
END IF;
END LOOP;
END;
$BODY$;

and then i could do:

select smart_insert('test_table', 'xxx');

  1. 4 comments

  2. # Acid
    Jun 29, 2007

    hm.. but i’m thinking that, when we will have a lot of records in DB, 30 requests to generate id will by enought (nie wystarczy?).. but it’s ony my thinking…

  3. Jun 29, 2007

    remember that every next call uses longer keys.
    for example – 10th select will use key that has 10 characters.
    since each character is randomized form pool of 62 letters/digits, it means that 10-character long string has 839299365868340224 possible variants.
    that’s quite a lot.
    i honestly dont think that anyone in standard setup will even need more than 5 characters (916132832 variants)

  4. # Acid
    Jun 29, 2007

    ok i don;t do couting ;] true, it’s very imposible to have 839299365868340224 records in db :]

  5. Jun 29, 2007

    it’s not impossible, just not very likely.
    on the other hand – 30 character long identifiers give 591 222 134 364 399 413 463 902 591 994 678 504 204 696 392 694 759 424 possible distinct identifiers.
    i think that even if we would make a giant union of all tables in all databases around the world – we will not match this number.

Leave a comment