Problemet här var som jag beskrev i uppdatering 2 av min fråga. MySQL använder index för att snabbt utföra ORDER BY-operationer. Mer specifikt använder MySQL B-träd att indexera kolumner (som tidsstämplar - p.time/r.time), som tar upp lite mer utrymme men möjliggör snabbare sortering.
Problemet med min fråga var att den sorterades efter tidskolumnen i två tabeller, med tidsstämpeln från repost-tabellen om den var tillgänglig och posttabellen annars. Eftersom MySQL inte kan kombinera B-träden från båda tabellerna, kan den inte utföra snabb indexsortering på kolumner från två olika tabeller.
Jag modifierade min fråga och tabellstruktur på två sätt för att lösa detta.
1) Utför filtrering baserat på blockerade användare först, så beställning behöver endast göras på inlägg som är tillgängliga för den aktuella användaren. Detta var inte roten till problemet, utan är praktisk optimering. t.ex.
SELECT * FROM (SELECT * FROM Post p WHERE p.author_id NOT IN (4, 5, 6...))...
2) Behandla varje inlägg som ett repost av dess författare, så att varje inlägg garanterat har ett repost och repost.time som kan indexeras och sorteras på. t.ex.
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
I slutet av dagen kom problemet till ORDER BY - detta tillvägagångssätt minskade frågetiden från cirka 8 sekunder till 20 ms.