seleccione 1 fila aleatoria con filtrado complejo

Tengo dos soluciones de problemas.

1) Con id aleatorio, desde https://stackoverflow.com/a/4329447/2051938

SELECT *
FROM profiles AS r1
JOIN
    (SELECT CEIL(RAND() *
                     (SELECT MAX(id)
                        FROM profiles)) AS id)
        AS r2
WHERE
    r1.id >= r2.id
    AND
    r1.first_name IS NOT NULL
AND
NOT EXISTS (
    SELECT *
    FROM proposal
    WHERE
        proposal.to_id = r1.id
)
LIMIT 0 , 1

2) Con ORDER BY RAND()

SELECT *
FROM
    (
        SELECT *
        FROM profiles
        WHERE
            profiles.first_name IS NOT NULL
        ORDER BY RAND()
    ) AS users
WHERE
    NOT EXISTS (
        SELECT *
        FROM proposal
        WHERE
            proposal.to_id = users.id
    )
LIMIT 0 , 1

La primera solución es más rápida pero tiene un problema con "agujeros en id " y cuando obtuviste id desde el final (los usuarios pueden terminar antes de que haya una coincidencia)

¡La segunda solución es más lenta pero sin fallas!