SQL Server 2005 - Query optimization for fetching large number of rows from table with 750 million rows Brief on application:

This is audio fingerprinting application, being developed in Java with Microsoft SQL Server 2005 database.

I have one application to create fingerprints of original songs and put these fingerprints in database. To store fingerprint in database I have table:

CREATE TABLE [dbo].[fp_core](
    [hashkey] [bigint] NOT NULL,
    [note_id] [int] NOT NULL,
    [timeoffset] [int] NOT NULL
) ON [PRIMARY]


The application processes song and takes 100 sample per second, so around 15000 samples for complete song. These sample values are stored in database, 1 row for each sample as {HASHKEY, NOTE_ID, TIMEOFFSET}. For fingerprint of complete song, I may have around 15000 rows in fp_core table. I am planning to put fingerprints of 50000 songs in database, so around 750 million rows will be in fp_core table.

I have other application to process recordings and detect songs played in it. Process is, create set of HASHKEY from recording audio, same as for creating fingerprint of original song. Recording audio will generate around 20000-30000 HASHKEYs. Then application retrieves rows from fp_core table for all matching HASHKEYs generated by recording audio.

To retrieve data from fp_core table by processing recording, I am doing is, filling these all HASHKEYs of recording in one more table, table is:

CREATE TABLE [dbo].[fp_core_keys](
    [hashkey] [bigint] NOT NULL
) ON [PRIMARY]


then I am joining these two tables to retrieve all matching rows, the query is:

select fp.hashkey, fp.note_id, fp.timeoffset
from dbo.fp_core fp 
INNER JOIN dbo.fp_core_keys keys ON fp.hashkey = keys.hashkey


I have following indexes:

CREATE CLUSTERED INDEX [index_fp_core] ON [dbo].[fp_core] 
(
    [hashkey] ASC
)WITH (SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, IGNORE_DUP_KEY = OFF, ONLINE = OFF) ON [PRIMARY]

CREATE UNIQUE CLUSTERED INDEX [IX_fp_core_keys] ON [dbo].[fp_core_keys] 
(
    [hashkey] ASC
)WITH (SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, IGNORE_DUP_KEY = OFF, ONLINE = OFF) ON [PRIMARY]


Problem:

Retrieving data using above query is so slow, taking time around 40 seconds.

Right now, here is stats:

Query:

select count(hashkey) from fp_core
go
select count(distinct(hashkey)) from fp_core


Result:

57177764
13675633


Plan:



Can anybody help me?
If you are determined to retain your existing table structure, the best indexes will be something like:

create index ix1 on fp_core(hashkey, note_id, timeoffset);
create index ix1 on fp_core_keys(hashkey);


You mention that the hashkeys can be different for the same song, but it sounds like you have some mechanism for detecting similar songs - if possible, add an additional column called 'songid' to your fp_core table and then query on this single value using a WHERE clause.