How to improve performance of a query matching on the same table I have a requirement to find potentially matching customer records in the same table. The logic is as per below. However this seems to perform at O(N²). Is there anyway to improve the performance here? I've tried setting indexes, hashing the columns and comparing on that, etc but performance remains terrible over a large dataset. I've also added the query plan below.

SELECT
    C1.CustomerId AS Customer1, 
    C2.CustomerId AS Customer2
FROM Customer C1
INNER JOIN Customer C2
    ON 
    C1.CustomerId != C2.CustomerId
    AND
    (C1.FirstName = C2.FirstName OR C1.BirthDate = C2.BirthDate)
    AND
    (
        C1.EmailAddress = C2.EmailAddress
        OR
        C1.MobilePhoneNumber = C2.MobilePhoneNumber
        OR
        (
            C1.HomeAddressLine1 = C2.HomeAddressLine1
            AND
            (
                C1.HomePostCode = C2.HomePostCode
                OR
                C1.HomeSuburb = C2.HomeSuburb
            )
        )
    )
You can split your query into two different queries allowing for two different covering indexes to help you find the rows faster.

One query that checks FirstName and another that checks BirthDate.

select C1.CustomerId,
       C2.CustomerId
from dbo.Customer as C1
  inner join dbo.Customer as C2
    on C1.CustomerId &lt;&gt; C2.CustomerId and
       C1.FirstName = C2.FirstName and
            (
              C1.EmailAddress = C2.EmailAddress or 
              C1.MobilePhoneNumber = C2.MobilePhoneNumber or 
              (
                 C1.HomeAddressLine1 = C2.HomeAddressLine1 and
                (C1.HomePostCode = C2.HomePostCode or C1.HomeSuburb = C2.HomeSuburb)
              )
            );


select C1.CustomerId,
       C2.CustomerId
from dbo.Customer as C1
  inner join dbo.Customer as C2
    on C1.CustomerId &lt;&gt; C2.CustomerId and
       C1.BirthDate = C2.BirthDate and
            (
              C1.EmailAddress = C2.EmailAddress or 
              C1.MobilePhoneNumber = C2.MobilePhoneNumber or 
              (
                 C1.HomeAddressLine1 = C2.HomeAddressLine1 and
                (C1.HomePostCode = C2.HomePostCode or C1.HomeSuburb = C2.HomeSuburb)
              )
            );


The index you need to support those queries:

create nonclustered index IX_FirstName on dbo.Customer(FirstName) 
  include(EmailAddress, MobilePhoneNumber, HomeAddressLine1, HomePostCode, HomeSuburb);

create nonclustered index IX_BirthDate on dbo.Customer(BirthDate) 
  include(EmailAddress, MobilePhoneNumber, HomeAddressLine1, HomePostCode, HomeSuburb);


In my rather limited test case I saw an improvement from more time than I care to wait down to 4 seconds*.

The query plans I got for the two queries.






*I actually started the original query and forgot about it. Scratched my head trying to figure out why my computer was sluggish and found that the query had been running for 40 minutes.