Algorithm for generating a random number

I'm looking to generate a random number and issue it to a table in a database for a particular user_id. The catch is, the same number can't be used twice. There's a million ways to do this, but I'm hoping someone very keen on algorithms has a clever way of solving the problem in an elegant solution in that the following criteria is met:

1) The least amount of queries to the database are made. 2) The least amount of crawling through a data structure in memory is made.

Essentially the idea is to do the following

1) Create a random number from 0 to 9999999
2) Check the database to see if the number exists
OR
2) Query the database for all numbers
3) See if the returned result matches whatever came from the db
4) If it matches, repeat step 1, if not, problem is solved.

Thanks.

No your algorithm is not scalable. What I've done before is to issue numbers serially (+1 each time) and then pass them through an XOR operation to jumble the bits thus giving me a seemingly random numbers. Of course they aren't really random, but they look so to users eyes.

[Edit] Additional information

This algorithm's logic goes like this you use a known sequence to generate unique numbers and then you deterministically manipulate them, so they don't look serial anymore. The general solution is to use some form of encryption, which in my case was an XOR flipflop, because its as fast as it can get, and it fulfills the guarantee that numbers will never collide.

However you can use other forms of encryption, if you want prefer even more random looking numbers, over speed (say you don't need to generate many ids at a time). Now the important point in choosing an encryption algorithm is "the guarantee that numbers will never collide". And a way to prove if an encryption algorithm can fulfill this guarantee is to check if both the original number and the result of the encryption have the same number of bits, and that the the algorithm is reversible (bijection).

[Thanks to Adam Liss & CesarB for exapanding on the solution]

Why don't you just use a GUID? Most languages should have a built-in way to do this. It's guaranteed to be unique (with very reasonable bounds).

Want an over-the-top solution?

I assume randomness is not intended to be encryption-quality, but just enough to discourage guessing the longevity of a user, by user_id.

During development, generate a list of all 10 million numbers in string form.

Optionally, perform some simple transformation, like adding a constant string to the middle. (This is just in case the result is too predictable.)

Pass them into a tool that generates Perfect Hash functions, such as gperf.

The resulting code can be used to quickly encode the user's id at runtime into a unique hash value that is guaranteed not to clash with any other hash values.

Try the statement in mysql SELECT CAST(RAND() * 1000000 AS INT)