Tips on improving/refactoring slow query?

Question

Let's play lotto!

Ok. I have a numbers table with 80 rows (numbers 1-80):

create table dbo.numbers (knum tinyint primary key identity);

I have a table with the drawid, and each number drawn.

create table dbo.draws (drawid int, drawnumber tinyint);

Now, given that the draws table may have data like:

drawid drawnumber
 1 10
 1 36
 1 54
 1 75
 2 9
 2 45
 2 46
 2 72

I want to find out when was the last time every possible three-number permutation occurred.

I'm using this:

declare @curdraw int
select @curdraw = max( drawid)-100 from draws;
select TOP 10 K1,K2,K3, @curdraw-max(d1.drawid) from THREES 
inner join DrawNumbers d1 WITH (NOLOCK) ON K1 = D1.DRAWNUMBER
INNER JOIN DRAWNUMBERS D2 WITH (NOLOCK) ON K2 = D2.DRAWNUMBER AND D1.DRAWID = D2.DRAWID
INNER JOIN DRAWNUMBERS D3 WITH (NOLOCK) ON K3 = D3.DRAWNUMBER AND D1.DRAWID = D3.DRAWID
WHERE D1.DRAWID < @CURDRAW
GROUP BY K1, K2, K3
ORDER BY @curdraw-max(d1.drawid) DESC

(Oh, and table Threes is a table with all 492,000+ three-number combinations from 1-80)

Is there a better way to do what I'm trying to do here? This particular query is just very slow and I'm sure someone with better math/grouping skills could do better.

---

Answers to comments - clarifications:

• It's for a keno game. Every draw has 20 numbers out of the 80. I just showed 4 each as an example.

• Two years of accumulated draws, at 254 draws a day with 20 numbers per draw... Drawnumber table is currently 3.7 mil rows. Also, what I'm looking for specifically is "out of every 3-number combination possible can you give me a sorted list of how long it has been since any one of them has hit, ordered by that length".

• The top 10 is merely because I don't need to see all 490K results.

The primary keys:

USE [OKD] 
GO 
ALTER TABLE [dbo].[DrawNumbers] 
 ADD CONSTRAINT [PK_DrawNumbers] 
 PRIMARY KEY CLUSTERED 
 ( [DrawID] ASC, [DrawNumber] 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]
GO
USE [OKD] 
GO
ALTER TABLE [dbo].[threes] 
 ADD PRIMARY KEY CLUSTERED 
 ( [THREEID] 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]
GO

• Andriy M: What indices have you got? How slow is your very slow and how fast do you want it to be?
• Jon Seigel: "out of every 3-number combination possible" -- 80 total numbers, combinations of 3, no repeats = 80 choose 3 = 82,160. The result set should have that many rows, or fewer if combinations that haven't been hit don't show up.

Answer 1

Changing it to use a CTE will be faster probably - they normally give the optimizer a better chance at optimising the query.

with currentdraw as (
select k1,k2,k3 from THREES 
inner join DrawNumbers d1 WITH (NOLOCK) ON K1 = D1.DRAWNUMBER
INNER JOIN DRAWNUMBERS D2 WITH (NOLOCK) ON K2 = D2.DRAWNUMBER AND D1.DRAWID = D2.DRAWID
INNER JOIN DRAWNUMBERS D3 WITH (NOLOCK) ON K3 = D3.DRAWNUMBER AND D1.DRAWID = D3.DRAWID
WHERE D1.DRAWID = @CURDRAW
), previousdraws as (
select d1.drawid, k1,k2,k3 from THREES 
inner join DrawNumbers d1 WITH (NOLOCK) ON K1 = D1.DRAWNUMBER
INNER JOIN DRAWNUMBERS D2 WITH (NOLOCK) ON K2 = D2.DRAWNUMBER AND D1.DRAWID = D2.DRAWID
INNER JOIN DRAWNUMBERS D3 WITH (NOLOCK) ON K3 = D3.DRAWNUMBER AND D1.DRAWID = D3.DRAWID
WHERE D1.DRAWID < @CURDRAW
)
select previousdraws.*
from previousdraws p
inner join currentdraw c
on p.k1 = c.k1 and p.k2 = c.k2 and p.k3 = c.k3
order by drawid desc

Your best indexes will probably be:

create index ix1 on THREES (k1,k2,k3);
create index ix1 on DrawNumbers (drawid, drawnumber);

• Kin Shah: CTE will be faster probably - they normally give the optimizer a better chance at optimising the query This is not completely true. See some excellent answers at (dba.stackexchange.com/a/14492/8783) and (dba.stackexchange.com/a/13117/8783) by @JNK
• Dave Clary: I'm setting this as the answer because the solution I came up with was a hybrid between an actual static table with the various combinations, and a CTE connecting this table with the results table. Plus, this was the only answer given. Well done, Dave! :)
• Dave Hilditch: As always, you should measure performance as performance depends not only on the query, but also the data, the business logic available (for optimisations) and other variables like stats, server performance and more. I can tell you that I have successfully used CTEs to measurably improve performance dozens of times.