Stored Procedure - Search Parameter across multiple columns

Question

I have the following query that does the job just fine, but I'm wondering whether there is a better way to be doing it inside the WHERE clause.

Any comments/feedback on improving it would be appreciated.

SELECT
    C.ClientID, 
    C.FirstName + ' ' + C.LastName as FullName, 
    C.DOB,
    G.Gender, 
    G.GenderIcon, 
    C.VerificationCode, 
    MAX(V.StartDate) as LastVisitDate
FROM 
    Client C
LEFT JOIN 
    Visit V ON C.ClientID = V.ClientID
INNER JOIN 
    Gender G ON C.GenderID = G.GenderID
WHERE
    (FirstName like '%' + @Criteria + '%' or
     LastName like '%' + @Criteria + '%' or
     VerificationCode like '%' + @Criteria + '%')

Answer 1

Other than looking into things like full-text searching, no. If one column is vastly more likely to contain the matches than the others and you have covering indexes, you could use three queries and run them separately, but given the columns you return they likely all involve table scans anyway. You may also consider querying for LIKE @Criteria + '%' first, since that can use an index to support an efficient range scan (more efficient than reading all rows, in any case). None of this improves the worst case, though.