Make multi-subselect more efficient?

Question

I've got a select query that returns the next record alphabetically with relation to the given ID:

SELECT * 
FROM contacts 
WHERE client_id = 22844 
AND deleted_at IS NULL 
AND 
( 
  ( 
    last_name = (
      SELECT last_name 
      FROM contacts 
      WHERE client_id = 22844 AND id = 717604
    ) 
    AND first_name > (
      SELECT first_name 
      FROM contacts 
      WHERE client_id = 22844 AND id = 717604
    )
  ) 
  OR ( 
    last_name > (
      SELECT last_name 
      FROM contacts 
      WHERE client_id = 22844 AND id = 717604
    ) 
  ) 
) 

ORDER BY last_name, first_name 
LIMIT 1

There are individual indices on first_name, last_name, deleted_at and client_id.

Is there any way to rewrite this to be more efficient? It currently takes about 250ms - 300ms when a particular client has about 3000 contacts.

Currently using mysql 5.5

EDIT:

Turns out to be an order of magnitude faster if I leave out the deleted_at IS NULL condition. I might just stop using soft-deletion and move deleted records to an archive instead.

Answer 1

Here is an alternative method. It enumerates the rows after the desired row is seen:

SELECT c.*
FROM (SELECT c.*,
             (@rn := if(c.id = 717604 or @rn > 0, @rn + 1, 0) as rn                
      FROM contacts c CROSS JOIN
           (SELECT @rn := 0) params
      WHERE c.client_id = 22844 AND c.deleted_at IS NULL 
      ORDER BY c.last_name, c.first_name
     ) c
WHERE rn = 2;

For this query, you want indexes on contacts(client_id, deleted_at, last_name, first_name).

EDIT:

The performance on your query seems reasonable. However, the best indexes are contacts(client_id, id, last_name) and contacts(client_id, id, first_name)

Answer 2

SELECT  b.*
    FROM  
      ( SELECT  last_name, first_name
            FROM  contacts
            WHERE  client_id = 22844
              AND  id = 717604 
      ) AS a
    JOIN  contacts AS b
    WHERE  deleted_at IS NULL
      AND    b.last_name >= a.last_name
      AND  ( b.first_name > a.first_name
         OR  b.last_name > a.last_name 
           )
    ORDER BY  b.last_name, b.first_name
    LIMIT  1; 
-- and have these indexes on contacts:
INDEX(client_id, id),
INDEX(last_name, first_name)