O problema aqui foi como descrevi na atualização 2 da minha pergunta. O MySQL usa índices para executar operações ORDER BY rapidamente. Mais especificamente, o MySQL usa B-trees para indexar colunas (como timestamps - p.time/r.time), que usam um pouco mais de espaço, mas permitem uma classificação mais rápida.
O problema com minha consulta foi que ela estava classificando pela coluna de tempo em duas tabelas, usando o carimbo de data/hora da tabela de repostagem, se disponível, e a tabela de postagem, caso contrário. Como o MySQL não pode combinar as árvores B de ambas as tabelas, ele não pode realizar uma classificação rápida de índice em colunas de duas tabelas diferentes.
Modifiquei minha estrutura de consulta e tabela de duas maneiras para resolver isso.
1) Realize a filtragem com base em usuários bloqueados primeiro, para que a ordenação seja feita apenas em postagens acessíveis pelo usuário atual. Esta não foi a raiz do problema, mas é a otimização prática. por exemplo.
SELECT * FROM (SELECT * FROM Post p WHERE p.author_id NOT IN (4, 5, 6...))...
2) Trate cada postagem como uma repostagem de seu autor, para que cada postagem tenha um repost e repost.time para indexar e classificar. por exemplo.
SELECT * FROM (...) LEFT JOIN p.reposts repost ON (p.id = repost.post_id AND
repost.time = (
SELECT MIN(r.time) FROM Repost r WHERE p.id = r.post_id
AND r.user_id IN (1, 2, 3...) AND r.user_id NOT IN (4, 5, 6...))
))
WHERE (repost.id IS NOT NULL) ORDER BY repost.time DESC LIMIT 0, 10
No final do dia, o problema se resumia a ORDER BY - essa abordagem reduziu o tempo de consulta de cerca de 8 segundos para 20 ms.
