SQL Server: how to optimize "like" queries?

I have a query that searches for clients using "like" with wildcard. For example:

SELECT TOP (10) 
       [t0].[CLIENTNUMBER], 
       [t0].[FIRSTNAME], 
       [t0].[LASTNAME], 
       [t0].[MI], 
       [t0].[MDOCNUMBER]
  FROM [dbo].[CLIENT] AS [t0]
 WHERE (LTRIM(RTRIM([t0].[DOCREVNO])) = '0') 
   AND ([t0].[FIRSTNAME] LIKE '%John%') 
   AND ([t0].[LASTNAME] LIKE '%Smith%') 
   AND ([t0].[SSN] LIKE '%123%') 
   AND ([t0].[CLIENTNUMBER] LIKE '%123%') 
   AND ([t0].[MDOCNUMBER开发者_开发百科] LIKE '%123%') 
   AND ([t0].[CLIENTINDICATOR] = 'ON')

It can also use less parameters in "where" clause, for example:

SELECT TOP (10) 
       [t0].[CLIENTNUMBER], 
       [t0].[FIRSTNAME], 
       [t0].[LASTNAME], 
       [t0].[MI], 
       [t0].[MDOCNUMBER]
  FROM [dbo].[CLIENT] AS [t0]
 WHERE (LTRIM(RTRIM([t0].[DOCREVNO])) = '0') 
   AND ([t0].[FIRSTNAME] LIKE '%John%') 
   AND ([t0].[CLIENTINDICATOR] = 'ON')

Can anybody tell what is the best way to optimize performance of such query? Maybe I need to create an index? This table can have up to 1000K records in production.

To do much for a LIKE where the pattern has the form '%XXX%', you want to look up SQL Server's full-text indexing capability, and use CONTAINS instead of LIKE. As-is, you're doing a full table scan, because a normal index won't help with a search for an item that starts with a wild card -- but a full-text index will.

/* ... */
 WHERE (LTRIM(RTRIM([t0].[DOCREVNO])) = '0') 
   AND (contains([t0].[FIRSTNAME], 'John')) 
   AND (contains([t0].[LASTNAME], 'Smith')) 
   AND (contains([t0].[SSN], '123'))
   AND (contains([t0].[CLIENTNUMBER],'123')) 
   AND (contains([t0].[MDOCNUMBER], '123')) 
   AND ([t0].[CLIENTINDICATOR] = 'ON')

Looks like some databases (PostgreSQL 7.1+, MySQL v3.23.23+, Microsoft-SQL v???, ) already contains such things:

MySQL>> ALTER TABLE articles ADD FULLTEXT(body, title);
MySQL>> SELECT * FROM articles WHERE MATCH(title, body) AGAINST ('PHP')

MS-SQL>> SELECT ProductName FROM Products WHERE FREETEXT (ProductName, 'spread' )

PgSQL>> CREATE FUNCTION fti() RETURNS opaque AS '/path/to/fti.so' LANGUAGE 'C';
PgSQL>> CREATE TABLE articles_fti (string type, id oid);
....