Open issues sorted index

A project-management app's 'my open issues, sorted by updated-at' query is slow: it filters by (assignee_id, status='open') and sorts by updated_at, over a 500M-row issues table, and shows 50 rows per page. The query currently filters on an index but then does 50 random heap fetches per page and re-sorts. p95 is 400ms; target 50ms. Reads vastly outnumber writes but writes are frequent (issues update often). Design the indexing fix, explain why it works, and the cost you're accepting.