В вашей задаче, вам не нужен ни MD5, ни автоинкрементный INT, как советовали выше.
Используйте в качестве первичного ключа бинарное поле и вписывайте в него 16-байтные UUID4-последовательности, а пользователям можете отдавать их в виде 32-символьной HEX-строки.
Про накладные расходы. По сравнению с int64, каким должен быть автоинкрементный счётчик, размер поля окажется больше всего на 8 байт (в 2 раза), что для вашего случая — совсем не проблема.
Убедитесь лишь, что ваши индексы всегда умещается целиком в физической памяти, а не хранятся частично или полностью в свопе на диске. Природа UUID такова, что он генерирует равномерно распределенные значения, а значит, поиск по такому индексу будет подвержен эффекту «случайного поиска» (random lookup). И если ваш индекс хотя бы частично хранится на диске, то это может привести к многочисленным random seeks и очень медленной