[Answer]-How can I optimize this order_by query in Django?

This isn’t something you can do in Django. The way to optimize this is in the database.

Run EXPLAIN against the actual query that this generates – in fact, the Django debug toolbar can do that for you – and note whether the relevant subqueries and JOINs are using indexes, rather than full-table scans. You’ll probably need to create an index for the Paginator table on item, today to start with.