How to optimize indexes on MySQL query with various sorts
WHERE playable_character = 0 AND
    date_published BETWEEN date_sub(now(), INTERVAL 3 YEAR) AND now()


Start with the "=" item, then do the range:

INDEX(playable_character, date_published);


"Pagination", a la ORDER BY rating DESC LIMIT 4000, 1000; is best done by remember where you "left off". That way, you don't have scan over the 4000 records that you don't need.