Спасибо
Arman и
Папа Стифлера за подсказки. Решение, которое подошло полностью:
- Добавил в таблицу новый столбец типа varchar
- Создал для этой колонки самый обычный индекс
- Написал скрипт на Python, который создает hash из URL для каждой строки
- Переписал скрипт проверяющий налчие URL в базе так, чтобы он использовал hash
Теперь, чтобы запросы на существование записи вместо 60 секунд, выполняются в среднем меньше чем за секунду для таблицы с > 1 млн. строк.