Query takes time on comparing non numeric data of two tables, how to optimize it?

I have two DBs. The 1st db has CallsRecords table and 2nd db has Contacts table, both are on SQL Server 2005.

Below is the sample of two tables.

Contact table has 1,50,000 records
CallsRecords has 75,000开发者_C百科 records

Indexes on CallsRecords:
CallFrom
CallTo
PickUP

Indexes on Contacts:
PhoneNumber

alt text http://img688.imageshack.us/img688/8422/calls.png

I am using this query to find matches but it take more than 7 minutes.

SELECT *
    FROM CallsRecords r INNER JOIN Contact c ON r.CallFrom = c.PhoneNumber 
        OR r.CallTo = c.PhoneNumber OR r.PickUp = c.PhoneNumber

In Estimated execution plan inner join cost 95%

Any help to optimize it.

You could try getting rid of the or in the join condition and replace with union all statements. Also NEVER, and I do mean NEVER, use select * in production code especially when you have a join.

SELECT <Specify Fields here>
FROM CallsRecords r INNER JOIN Contact c ON r.CallFrom = c.PhoneNumber  
UNION ALL
SELECT <Specify Fields here>    
FROM CallsRecords r INNER JOIN Contact c ON r.CallTo = c.PhoneNumber 
UNION ALL
SELECT <Specify Fields here> 
FROM CallsRecords r INNER JOIN Contact c ON r.PickUp = c.PhoneNumber 

Alternatively you could try not using phone number to join on. Instead create the contacts phone list with an identity field and store that in the call records instead of the phone number. An int field will likely be a faster join.

Is there an index on the fields you are comparing? Is this index being used in the execution plan?

Your select * is probably causing SQL Server to ignore your indexes, and causing each table to be scanned. Instead, try listing out only the columns you need to select.

There is so much room for optimization

1. take out * (never use it, use column names)
2. specify the schema for tables (should be dbo.CallRecords and dbo.Contact)
3. Finally the way the data is stored is also a problem. I see that there are a lot of "1" in CallID as well as ContactID. Is there any Clustered Index (primary key) in those two tables?
4. I would rather take out your joins and implement union all as suggested by HLGem. And I agree with him it is better to search on IDs than long strings like this.

HTH