Your query:

While https://stackoverflow.com/users/205608/o-jones has good answer, there's a scope of further optimisation.

SELECT * 
FROM account
WHERE client_id = ?
  AND disabled IN (?)
  AND (username LIKE '%?%' OR name LIKE '%?%' OR surname LIKE '%?%')
ORDER BY name, surname
LIMIT ?;

Your constraints: client_id might have high number of rows.

How to optimize this query?

Observation 1:

No index would binary search on username LIKE %?% or other similar LIKE statements. One has to do a full index scan (this is different from table scan that currently your query might be doing, its order of magnitudes faster).

Observation 2:

The conjunction between clauses in your query is OR i.e. username, name OR surname. That implies, you have to do a composite index containing these three.

Observation 3:

The other clauses contain client_id , disabled. However, selectivity of either of these are not as high. So, an individual index on any of these columns is of no use. However, a composite index containing these columns + above three columns do make sense but is optional [But index selection would only work if these guys are present]. So, till now we are at: client_id,disabled,username,name,surname [I1]

Observation 4:

You want to optimize ORDER BY clause as well. Only way to do that, is to keep the data physically sorted in the order of your clause. Remember, index is always physically sorted. So, let's change

client_id,disabled,username,name,surname

To:

name,surname,username,client_id,disabled

Long term items:

1. Consider partitioning your data.

2. The above index will speed up your query but would have negative consequences. So, you might want to drop the last two items and use an index hint.