Is this recursive random string generation computationally expensive?

Question

I have created a function to generate a unique referral code for a user when they sign up, I want to ensure uniqueness so I check if it already exists, if it does then I call the function again recursively:

        public function generateUniqueReferralCode()
        {
            $referral_code = str_random(8);

            if(User::where('referral_code', $referral_code)->exists()) {
                $referral_code = $this->generateUniqueReferralCode();
            }

            return $referral_code;
        }

My question is, is this computationally expensive? Can it be done in a more efficient way as it has to scan the user table? Lets say we have 1 million users, it will check against 1 million user records if the key already exists.

Adding a UNIQUE constraint in table column would be a better option here, if insertion fails try again. — Shub, May 25 '18 at 09:07
You can replace the recursion by a simple loop which is a bit faster, but in general I would say that the performance of the recursion should be not too bad as long as str_random(8) really generates random strings. But as always: Benchmark it :) — Simon Hessner, May 25 '18 at 09:07
@Shubanker You mean at database level? I have the following in my migration: `$table->string('referral_code')->unique()->nullable();` — user3574492, May 25 '18 at 09:08
in this case the constraint wouldn't allow duplicate referral codes to be inserted and will throw an error all you need is to handle them, also I am not sure why would you make it `nullable()` — Shub, May 25 '18 at 09:12
@Shubanker because they may or may not have a referral code. — user3574492, May 25 '18 at 09:13
In that case `UNIQUE` constraint wouldn't work as multiple `nulls` can't be added — Shub, May 25 '18 at 09:14
In MySQL it is fine to have multiple null values in the table with a unique constraint: https://stackoverflow.com/questions/3712222/does-mysql-ignore-null-values-on-unique-constraints — user3574492, May 25 '18 at 09:16
As suggested in one of the anwser, to be sure to create an unique refferal code with no need of use recursively :1/ get your last refferal code id (which is unique) - 2/ generate a random string - 3/ create your refferal code as rand_string + last_id. — Mickaël Leger, May 25 '18 at 09:40

score 0 · Answer 1 · answered May 25 '18 at 09:32

My approach would be a little simpler. Instead of checking all those records for uniqueness, I'll rather generate a random key and plant the primary key of the last record or the record to be generated.

For instance, here's my flow of thoughts

Generate a random key - 1234abc
Fetch the primary key of the last record. Result - 3
Append it to the key - 1234abc3 ( will always be unqiue )

score 0 · Accepted Answer · answered May 25 '18 at 09:33

PHP functions are pretty costly. So I think the following is a little faster (didn't benchmark):

public function generateUniqueReferralCode() {
    $referral_code = str_random(8);

    while (User::where('referral_code', $referral_code)->exists()) {
        $referral_code = str_random(8);
    }

    return $referral_code;
}

score 0 · Answer 3 · 2018-05-25T09:59:03.030

0

No, a database uses efficient indexing (search trees or hash codes) for efficient lookups, so that the number of records is virtually immaterial.

But why don't you just increment a counter to implicitly guarantee uniqueness ? (And add random salt if you want.)

edited May 25 '18 at 09:59

answered May 25 '18 at 09:51

Is this recursive random string generation computationally expensive?

3 Answers3