That query needs this index, which is both “composite” and “covering”:
INDEX(user_service_id, user_id) -- in this order
But what will you do with the millions of rows that you get? Sounds like it will choke the client, whether it comes fast or slow.
See my Index Cookbook
“very dynamic” — Not a problem.
“cache” — the dynamic nature defeats caching.
“cardinality” — not important, except to point out that there will be millions of rows.
“millions of rows” — that takes time to deliver to the client. The number of rows delivered is the biggest factor in cost.
“select entire table, then filter in client” — That will be even slower! (See “millions of rows”.)