Help me optimize this SQL Server 2005 query

I have this query that's running too slow. I'm not sure what all info I should provide in order to make it easy for you to help me, but I'll take a stab at it and then add more when you big-brains inevitably ask for stuff that I either didn't think to include or don't know what is.

I want to identify customers (but using only part of their address -- accommodating households and businesses) who first registered a purchase in 2006.

My first attempt was:

select
    distinct a.line1 + '|' + substring(a.zip,1,5)
from 
    registrations r
    join customers c on r.custID = c.id
    join addresses a on c.addressID = a.id
where year(r.purchaseDate) = 2006
    and a.line1 + '|' + substring(a.zip,1,5) not in (
        select
            distinct a.line1 + '|' + substring(a.zip,1,5)
        from
            registrations r
            join customers c on r.custID = c.id
            join addresses a on c.addressID = a.id
        where
            year(r.purchaseDate) < 2006
    )

and when it was running too long, I switched a NOT EXISTS (with which I am less comfortable, but willing to experiment) like

select
    distinct a.line1 + '|' + substring(a.zip,1,5)
from
    registrations r
    join customers c on r.custID = c.id
    join addresses a on c.addressID = a.id
where
    year(r.purchaseDate) = 2006
    and not exists (
        select
            1
        from
            registrations r
            join customers c on r.custID = c.id
            join addresses ia on c.addressID = ia.id
        where
            ia.line1 + '|' + substring(ia.zip,1,5) = a.line1 + '|' + substring(a.zip,1,5) and
            year(r.purchaseDate) < 2006
        )
group by
    a.line1 + '|' + substring(a.zip,1,5)

But it runs too long too. Like no results in 17 hours kind of too long. I think the first thing to consider is where my SQL might be wrong or sub-optimal but in case it's not that, I want to also give you enough info to consider the environment.

So, diagnostic info. You probably don't care, but just in case: it's running on a G6 server with four quads and 20 GB RAM; each query is limited to occupying four processors to keep performance up for request开发者_运维技巧s from the web server; when I'm running this query, we're clearing off other big imports and reports because of deadlocks but the web server is customer-facing and can't be stopped.) There are roughly: 15 million registrations, 11 million customers and 8.6 million addresses. I rebuilt all of the indexes just to be sure that fragmentation wasn't the problem. However, I'm not really sure how to index properly, so I'm totally open to this being a problem -- some of these indexes were a result of me futzing around and some were scripts that one of the MS analysis tools gave me to improve performance. I'm also not exactly sure how to convey index info to you, so I'll just give the create scripts:

ALTER TABLE [dbo].[registrations] ADD  CONSTRAINT [PK_flatRegistrations_1] PRIMARY KEY CLUSTERED 
(
    [Id] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]

.

ALTER TABLE [dbo].[customers] ADD  CONSTRAINT [PK_flatCustomers_1] PRIMARY KEY CLUSTERED 
(
    [Id] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]

.

ALTER TABLE [dbo].[addresses] ADD  CONSTRAINT [PK_addresses] PRIMARY KEY CLUSTERED 
(
    [ID] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]


CREATE NONCLUSTERED INDEX [addresses] ON [dbo].[addresses] 
(
    [line1] ASC,
    [line2] ASC,
    [city] ASC,
    [state] ASC,
    [zip] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]


CREATE NONCLUSTERED INDEX [deliverable] ON [dbo].[addresses] 
(
    [addressDeliverable] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]


CREATE NONCLUSTERED INDEX [_dta_index_addresses_5_1543676547__K9_K1_6] ON [dbo].[addresses] 
(
    [addressDeliverable] ASC,
    [ID] ASC
)
INCLUDE ( [zip]) WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]


CREATE NONCLUSTERED INDEX [_dta_index_addresses_5_1543676547__K1_K9_6] ON [dbo].[addresses] 
(
    [ID] ASC,
    [addressDeliverable] ASC
)
INCLUDE ( [zip]) WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]


CREATE NONCLUSTERED INDEX [_dta_index_addresses_5_1543676547__K1_6] ON [dbo].[addresses] 
(
    [ID] ASC
)
INCLUDE ( [zip]) WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, SORT_IN_TEMPDB = OFF, IGNORE_DUP_KEY = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]

Thanks a bunch for your time!

I think your Not Exists subquery's table alias is wrong. Try this:

select  r.custID,
        a.line1 + '|' + substring(a.zip,1,5) 
from    registrations r     
join    customers c on r.custID = c.id     
join    addresses a on c.addressID = a.id 
where   r.purchaseDate between '2006-01-01' and '2006-12-31'      
and not exists (         
        select  1         
        from   registrations ir             
        join customers ic on ir.custID = ic.id           
        join addresses ia on ic.addressID = ia.id         
        where   ia.line1 = a.line1
        and     substring(ia.zip,1,5) = substring(a.zip,1,5) 
        and     ir.purchaseDate < '2006-12-31'        
        )

My first try would be replace:

year(r.purchaseDate) = 2006

with:

r.purchaseDate BETWEEN '2006-01-01' and '2006-12-31 23:59:59' 

and also year(r.purchaseDate) < 2006 with r.purchaseDate < '2006-01-01'.

and make sure that there is an index on purchaseDate.

Next thing (if you have enough resources to run it):

 -- create temporary table to prepare data
CREATE TABLE #addrs (yearr int, pattern varchar(100)) -- depends on a.line1 length

-- calculate all patterns for purchase before 1st Jan 2007
INSERT INTO 
  #addrs (yearr, pattern)
SELECT
  YEAR(r.purchaseDate),
  a.line1 + '|' + substring(a.zip,1,5)
from
    registrations r
    join customers c on r.custID = c.id
    join addresses a on c.addressID = a.id
where
    r.purchaseDate < `2007-01-01`

-- optionally, but could be useful in query below
CREATE INDEX idx_temp ON #addrs (pattern, yearr)  

-- original query rewritten
SELECT
  DISTINCT pattern
FROM
  #addrs a
WHERE
  a.yearr = 2006
  and not exists (
    select top 1 1 
    from 
       #addrs aa 
    where 
       aa.pattern = a.pattern
       and aa.yearr < 2006
  )

Second solution could have some typos and could not compile from first try. It's just an idea.

SubString(A.zip, 1, 5) must be causing the table scan. Is this one time query? If so, get the result of the below query and store it in a new table. Make indexes on AddressToCompare and PurchaseDate and run your subsequent query against the new table.

Select
      R.ID
    , R.CustID
    , C.AddressID
    , A.line1 + '|' + SubString(A.zip, 1, 5) As AddressToCompare
    , R.PurchaseDate
From
    Registrations R
    Inner Join Customers C On R.CustID = C.ID
    Inner Join addresses A On C.AddressID = A.ID
Where
    R.PurchaseDate <= '2006-12-31'

First your logic is poor, business and customers move in and out of addresses, so comparing on the address rather than the customer is a guarantee of wrong results. Just becasue ABC copmany ordered something in 2002 does not mean that DEF company didn;t have thier first corder in 2006 as ABC comapny and DEF Company have no relationship to each other. If you need relationships of people inteh same company or household then havea table to to store them properly, don;t rely on incorrect hack.

Assuming you can't do this and this is aproces that will run more than once, then you need to persist a column inthe address table with

line1 + '|' + substring(zip,1,5)

This prevents you from having to calculate it on the fly.