Решение, найденное с подсказки xmoonlight

Значит в PHP файл пихаем это:

$sock = stream_socket_client('unix:///tmp/echo.sock', $errno, $errst); 
fwrite($sock, $type); 
$response = fread($sock, 1024); 
fclose($sock);

А в Python файл пихаем это:

# Адрес файла, который будет мостиком для общения между PHP и Python
SERVER_PATH = '/tmp/echo.sock'

# Если файл уже есть, его надо удалять
if os.path.exists(SERVER_PATH):

    os.remove(SERVER_PATH)

# Создаем новый UNIX сервер
server_socket = socket.socket(socket.AF_UNIX, socket.SOCK_STREAM)
server_socket.bind(SERVER_PATH)
server_socket.listen()

while True:

    client, adress = server_socket.accept()
    message = client.recv(1024)
    # Печатаем входящее сообщение
    print('received:', message.decode("utf-8"))
    # Отправляем ответ 
    client.send('This is my Response!'.encode())

client.close()
server_socket.close()
print('UNIX сервер закрыт!')

Запускаем Python файл из под того же пользователя, что и PHP файл и вуаля, все работает.

Спасибо Arman и Папа Стифлера за подсказки. Решение, которое подошло полностью:

1. Добавил в таблицу новый столбец типа varchar
   
2. Создал для этой колонки самый обычный индекс
   
3. Написал скрипт на Python, который создает hash из URL для каждой строки
   
4. Переписал скрипт проверяющий налчие URL в базе так, чтобы он использовал hash
   

Теперь, чтобы запросы на существование записи вместо 60 секунд, выполняются в среднем меньше чем за секунду для таблицы с > 1 млн. строк.