Как решить проблему с долгим поиском по базе

Нужен код для генерации рандомного slug из 3 символов, напиример ХХХ проверки на наличие такого же slug в базе, и если сгенерирован уникальный slug то вписываем его в базу, а если он уже существует, то генерируем другой и проверяем, и так по кругу.

Код у меня есть, но проблема в том что эсли записей slug в базе MySQL много, то и времени на проверку при создании нового slug уходит много.

Как логичнее пострить код (по какому принцыпу) чтоб при генерации нового не тратить время на проверку всей базы на наличие этого slug?