Optimizing LIKE OR Selects

I'm having problems optimizing a sql select statement that uses a LIKE statement coupled with an OR clause. For simplicity sake, I'll demonstrate this with a scaled down example:



table Company, fields CompanyID, CompanyName

table Address, fields AddressID, AddressName

table CompanyAddressAssoc, fields AssocID, CompanyID, AddressID



CompanyAddressAssoc is the many-to-many associative table for Company and Address. A search query is required that, given a search string ( i.e. 'TEST' ), return all Company -> Address records where either the CompanyName or AddressName starts with the parameter:

Select c.CompanyID, c.CompanyName, a.AddressName

FROM Company c

LEFT OUTER JOIN CompanyAddressAssoc caa ON caa.CompanyID = c.CompanyID

LEFT OUTER JOIN Address a ON a.AddressID = caa.AddressID

WHERE ((c.CompanyName LIKE 'TEST%') OR (a.AddressName LIKE 'TEST%))



There are proper indexes on all tables. The execution plan creates a hash table on one LIKE query, then meshes in the other LIKE query. This takes a very long time to do, given a dataset of 500,000+ records in Company and Address.

Is there any way to optimize this query, or is it a problem with the base table implementation?

Any advice would be appreciated.