Thread: Using Random Sequence as Key
Hello, I was wondering if noone can help me maybe someone could at least give me some directions where to look for info or where to ask: I wanted to index a table by a random key. Exemplifying, when a insert is made, the id value is automatically filled with a random number between 10000 and 99999. I'm pretty new in pgsql so I could use a howto or something, and I repeat, if you don't know how, directions to where I can find info on that or where I can ask someone that might know would be enough. Thank you
Bernardo de Barros Franco writes:
> I wanted to index a table by a random key. Exemplifying, when a insert is
> made, the id value is automatically filled with a random number between
> 10000 and 99999.
=> create table test (id int default random() * 89999 + 10000, content text);
CREATE
=> insert into test (content) values ('hi');
INSERT 36163 1
=> insert into test (content) values ('there');
INSERT 36164 1
=> insert into test (content) values ('blah');
INSERT 36165 1
=> select * from test; id | content
-------+---------61616 | hi72605 | there83469 | blah
(3 rows)
Verifying the default expression for correct boundaries is left as an
exercise. ;-)
--
Peter Eisentraut peter_e@gmx.net http://funkturm.homeip.net/~peter
Bernardo de Barros Franco writes:
> But my only question would be, in the example quoted would id be really the
> table index and is it unique?
Making unique *and* random numbers is a pretty complex (and slow) thing to
do in general. Consider redesigning your application.
>
> Thank you
>
> Quoting:
> >Bernardo de Barros Franco writes:
> >
> > > I wanted to index a table by a random key. Exemplifying, when a insert
> >is
> > > made, the id value is automatically filled with a random number between
> > > 10000 and 99999.
> >
> >=> create table test (id int default random() * 89999 + 10000, content
> >text);
> >CREATE
> >=> insert into test (content) values ('hi');
> >INSERT 36163 1
> >=> insert into test (content) values ('there');
> >INSERT 36164 1
> >=> insert into test (content) values ('blah');
> >INSERT 36165 1
> >=> select * from test;
> > id | content
> >-------+---------
> > 61616 | hi
> > 72605 | there
> > 83469 | blah
> >(3 rows)
> _________________________________________________________________________
> Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.
>
>
--
Peter Eisentraut peter_e@gmx.net http://funkturm.homeip.net/~peter
On Sun, Apr 15, 2001 at 10:58:40PM -0300, Bernardo de Barros Franco wrote: > I wanted to index a table by a random key. Exemplifying, when a insert is > made, the id value is automatically filled with a random number between > 10000 and 99999. I'm pretty new in pgsql so I could use a howto or Bernardo, Do you really need the keys to be random numbers? Can't the keys be sequential numbers, like 1,2,3,4...? That'd be a lot easier to make unique, and as far as the user is concerned, it'll be random for him/her.-Roberto -- +----| http://fslc.usu.edu USU Free Software & GNU/Linux Club |------+ Roberto Mello - Computer Science, USU - http://www.brasileiro.net http://www.sdl.usu.edu - Space Dynamics Lab, Developer Oh my GOSH! A Prompt!!! HELP!!!! A PROMPT !!!!! HEEEEELP !!!!!!!!!!!!!
Bernardo de Barros Franco writes: > Hello, I was wondering if noone can help me maybe someone could at least > give me some directions where to look for info or where to ask: > I wanted to index a table by a random key. As others have pointed out, making a unique random primary key is tough. What I do for my cookie on my web based login system is have two fields in my database, one's the "id SERIAL", the other is a "magiccookie CHAR(16)" which I populate with 16 random characters on the initial insert. My cookie is then of the format "id/magiccookie". In my login verification code I split on the "/" character and query on "WHERE id=$id AND magiccookie=$magiccooke". Even though the "id" field is encoded in the cookie in plain text a cracker can't just guess at the user id number because that 16 character magiccookie needs to match as well. This also lets me be pretty loose about the id information, I can use it in other public places, because only the magiccookie needs to be restricted to being known by the logged in user. Dan
Since I can't really redesign my application, I could index the table using a serial but still would need a field with the random and unique number. I tried using including a unique in : create table test (id int UNIQUE default random() * 89999 + 10000, content text); and it didn't return any errors, I'm just not sure if it actually worked. I needed the random field because if I use serial and the user gets a 34203 he's sure that 34202 exists, and that (probably, there where 34202 inserts before him (or at least an offset + some)). Using a random just makes the user totally blind. As I said I could use a serial for indexing the table but I NEED the random field and I need to to be unique since all the queries will be using it as a search parameter. If inserting this way is slow it's not such a big deal since it's a small db and inserts are seldom made. Thanks in advance for any help. Quoting: > On Sun, Apr 15, 2001 at 10:58:40PM -0300, Bernardo de Barros Franco wrote: > > > I wanted to index a table by a random key. Exemplifying, when a insert is > > made, the id value is automatically filled with a random number between > > 10000 and 99999. I'm pretty new in pgsql so I could use a howto or > > Bernardo, > > Do you really need the keys to be random numbers? Can't the keys be > sequential numbers, like 1,2,3,4...? That'd be a lot easier to make > unique, and as far as the user is concerned, it'll be random for him/her. >
It is a good way to solve it but since I don't want/can't use cookies in my application I could use only the random key but it would have to be unique or the where key=$key could refer to multiple lines or I would have to ask for the user to input both the random and the serial number wich wouldn't be very good either. That's the reason I've being trying to make a random key wich would be unique so I could ask for the user to type his order code and then select info from orders where ordercode=$ordercode and not have the risk of getting multiple answers (more then one line with that ordercode) or someone typing his ordercode-1 and accessing someone elses form. Ok, if I don't use a password or other protection even with random users can keep trying to guess but I don't have much of a problem with someone accessing someone else's form, I just don't want the user to let's say type his ordercode and by mistake type the last char say 1 less then his own and access someone else form and be completely lost. With random that still can happen but it is so less likely that will do. Thank you Quoting: > Bernardo de Barros Franco writes: > > Hello, I was wondering if noone can help me maybe someone could at least > > give me some directions where to look for info or where to ask: > > I wanted to index a table by a random key. > > As others have pointed out, making a unique random primary key is > tough. What I do for my cookie on my web based login system is have > two fields in my database, one's the "id SERIAL", the other is a > "magiccookie CHAR(16)" which I populate with 16 random characters on > the initial insert. > > My cookie is then of the format "id/magiccookie". In my login > verification code I split on the "/" character and query on "WHERE > id=$id AND magiccookie=$magiccooke". Even though the "id" field is > encoded in the cookie in plain text a cracker can't just guess at the > user id number because that 16 character magiccookie needs to match as > well. > > This also lets me be pretty loose about the id information, I can use > it in other public places, because only the magiccookie needs to be > restricted to being known by the logged in user.
Bernardo,
> I needed the random field because if I use serial and the user gets a
> 34203
> he's sure that 34202 exists, and that (probably, there where 34202
> inserts
> before him (or at least an offset + some)). Using a random just makes
> the
> user totally blind.
> As I said I could use a serial for indexing the table but I NEED the
> random
> field and I need to to be unique since all the queries will be using
> it as a
> search parameter.
> If inserting this way is slow it's not such a big deal since it's a
> small db
> and inserts are seldom made.
> Thanks in advance for any help.
Here's another suggestion for you then:
1. Add a sequence "Sales_sq"
1. write a custom function for new id numbers:
CREATE FUNCTION new_sales_id() RETURNS INT4 AS '
DECLAREtimeportion VARCHAR;serialportion INT4;
BEGINtimeportion := to_char(current_timestamp, ''ms'');
-- (or whatever the abbreviation for 2-digit milliseconds is)serialportion := 100*(nextval(''sales_seq''));RETURN
CAST(to_number(timeportion)AS INT4) + serialportion;
END;
3. Then set the id column to default to this new function.
This would give you (after you correct my mistakes) a number, the first
X digits of are Serial, and the last 2 digits based on the server's
internal clock. Thus, the numbers would *not* be sequential, and would
appear fairly random, but would be unique *without* and expensive check
for that value anywhere in the table for each insert.
-Josh Berkus
______AGLIO DATABASE SOLUTIONS___________________________ Josh Berkus Complete
informationtechnology josh@agliodbs.com and data management solutions (415) 565-7293 for law firms, small
businesses fax 621-2533 and non-profit organizations. San Francisco
It is a good way to solve it but since I don't want/can't use cookies in my application I could use only the random keybut it would have to be unique or the where key=$key could refer to multiple lines or I would have to ask for the userto input both the random and the serial number wich wouldn't be very good either. That's the reason I've being tryingto make a random key wich would be unique so I could ask for the user to type his order code and then select infofrom orders where ordercode=$ordercode and not have the risk of getting multiple answers (more then one line with thatordercode) or someone typing his ordercode-1 and accessing someone elses form. Do you have users logging in so that you know who is requesting the data? If so, just make a view that includes WHERE name = current_user to filter out all irrelevant (i.e., other people's) rows (inserts should set name to the appropriate user, of course). In that case a SERIAL will work fine, since there is no chance of seeing anyone else's information and the SERIAL is unique. More secure, also. Cheers, Brook
Hello Bernardo, there is a somewhat mathematical solution to your problem. You can use a unique key, say 0<= k < MAX for each record, and a second key which is computed from the first, say f(k), which will give you a unique permutation of the numbers 0,...,MAX-1. It will not be random, but it will be hard for someone to figure out the original unique key k, without knowning your method. Here is one way to compute f(k): (math follows, beware!) The Fibonacci numbers are a sequence defined as follows: F(0) = 0, F(1) = 1, F(n+2) = F(n+1)+F(n) (for n>=0). Now, for every fixed number N>=2, you can define a permutation f(k) of the numbers 0,...,F(N)-1 as follows: f(k) = (k*F(N-1)) mod F(N) For example, if N=6, we have F(6)=8 and F(5)=5, so for 0<= k <8, f(k) = 5*k mod 8 is a permutation. In particular, k = 0 1 2 3 4 5 6 7 f(k) = 0 5 2 7 4 1 6 3 So, since you need approximately 90000 numbers (10000 to 99999), you can use N=25, which will give you F(25)=75025 and F(24)=46368. Thus, you can have 75025 (slightly fewer than 90000) unique values, by translating k into f(k) = 46368*k mod 75025 Unless your users know number theory, this should work for you. Vasilis Bernardo de Barros Franco <electric_csf@hotmail.com> wrote: : Hello, I was wondering if noone can help me maybe someone could at least : give me some directions where to look for info or where to ask: : I wanted to index a table by a random key. Exemplifying, when a insert is : made, the id value is automatically filled with a random number between : 10000 and 99999. I'm pretty new in pgsql so I could use a howto or : something, and I repeat, if you don't know how, directions to where I can : find info on that or where I can ask someone that might know would be : enough. : Thank you
First of all, let me apologise for stepping so far back into the archives,
but I wanted to get this in the archives in case anyone else wanted to use
this.
There's a slight addendum here...as written, it's fairly likely that people
will get duplicate ID's using this system.
A small change gets rid of the problem: multiply the serialportion by the
number of digits you'll have in timeportion. So, if timeportion is three
digits, you'd multiply serialportion by 1000 and *then* add the timeportion.
Below, I use the mod operator '%' to make sure it's 3 digits or less.
Caveat: this will only work as long as you have less than 40 million users.
;^)
-Ken
create FUNCTION new_request_id()
RETURNS INT4
as' DECLARE timeportion INT4; serialportion INT4; BEGIN timeportion := cast
(date_part(''milliseconds'',timeofday()::timestamp) as integer); serialportion :=
nextval(''request_idfake_seq'')*1000; RETURN (timeportion % 1000) + serialportion; END;'
LANGUAGE 'plpgsql'
;
On Tuesday 17 April 2001 3:08 pm, Josh Berkus wrote:
> Bernardo,
>
> > I needed the random field because if I use serial and the user gets a
> > 34203
> > he's sure that 34202 exists, and that (probably, there where 34202
> > inserts
> > before him (or at least an offset + some)). Using a random just makes
> > the
> > user totally blind.
> > As I said I could use a serial for indexing the table but I NEED the
> > random
> > field and I need to to be unique since all the queries will be using
> > it as a
> > search parameter.
> > If inserting this way is slow it's not such a big deal since it's a
> > small db
> > and inserts are seldom made.
> > Thanks in advance for any help.
>
> Here's another suggestion for you then:
>
> 1. Add a sequence "Sales_sq"
>
> 1. write a custom function for new id numbers:
> CREATE FUNCTION new_sales_id() RETURNS INT4 AS '
> DECLARE
> timeportion VARCHAR;
> serialportion INT4;
> BEGIN
> timeportion := to_char(current_timestamp, ''ms'');
> -- (or whatever the abbreviation for 2-digit milliseconds is)
> serialportion := 100*(nextval(''sales_seq''));
> RETURN CAST(to_number(timeportion) AS INT4) + serialportion;
> END;
>
> 3. Then set the id column to default to this new function.
>
> This would give you (after you correct my mistakes) a number, the first
> X digits of are Serial, and the last 2 digits based on the server's
> internal clock. Thus, the numbers would *not* be sequential, and would
> appear fairly random, but would be unique *without* and expensive check
> for that value anywhere in the table for each insert.
>
> -Josh Berkus
>
>
>
>
>
>
> ______AGLIO DATABASE SOLUTIONS___________________________
> Josh Berkus
> Complete information technology josh@agliodbs.com
> and data management solutions (415) 565-7293
> for law firms, small businesses fax 621-2533
> and non-profit organizations. San Francisco
>
> ---------------------------(end of broadcast)---------------------------
> TIP 2: you can get off all lists at once with the unregister command
> (send "unregister YourEmailAddressHere" to majordomo@postgresql.org)
--
Ken Corey, CTO Atomic Interactive, Ltd. ken.corey@atomic-interactive.com