Atualmente estou usando:

SELECT * 
FROM 
  table AS t1
  JOIN (
    SELECT (RAND() * (SELECT MAX(id) FROM table where column_x is null)) AS id
  ) AS t2 
WHERE 
  t1.id >= t2.id
  and column_x is null
ORDER BY t1.id ASC
LIMIT 1

Isso normalmente é extremamente rápido, no entanto, quando eu incluo a coluna destacada_x sendo Y (nula), fica lento.

Qual seria a solução de consulta aleatória mais rápida em que a coluna X dos registros é nula?

ID é PK, a coluna X é int (4). A tabela contém cerca de um milhão de registros e mais de 1 GB de tamanho total, dobrando a cada 24 horas atualmente.

column_x é indexado.

O ID da coluna pode não ser consecutivo.

O mecanismo de banco de dados usado neste caso é o InnoDB.

Obrigado.