Rewriting the query and/or adding nonclustered indexes won't help, unless you basically rewrite the entire table by including a gazillion in the nonclus index(es) -- and constantly maintain it as another column gets referenced in a query.

The way to really solve these types of query issues is to first get the best clustered indexes.

If you (almost) always specify a date range when querying dbo.Player, as in the sample queries/code you posted, change the indexes as scripted below.

Naturally this may take quite a while, as the tables will have to be written/rewritten during this process. Of course remove the "ONLINE = ON," if that doesn't work on your system.

ALTER TABLE dbo.PartnerPlayer DROP CONSTRAINT fk_PartnerPlayer_partnerIdPlayerId;

DROP INDEX IX_Player_partnerIddtCreated ON dbo.Player;

ALTER TABLE dbo.Player DROP CONSTRAINT PK_Player;

CREATE CLUSTERED INDEX CL_Player ON dbo.Player ( dtCreated ) WITH ( FILLFACTOR = 99, SORT_IN_TEMPDB = ON ) ON [PRIMARY];

CREATE UNIQUE CLUSTERED INDEX CL_Player ON dbo.Player ( dtCreated, partnerId, playerId ) WITH ( FILLFACTOR = 99, SORT_IN_TEMPDB = ON ) ON [PRIMARY];

CREATE UNIQUE NONCLUSTERED INDEX IX_Player_partnerId_playerId ON dbo.Player ( partnerId, playerId ) WITH ( FILLFACTOR = 96, ONLINE = ON, SORT_IN_TEMPDB = ON ) ON [PRIMARY];

CREATE CLUSTERED INDEX CL_PartnerPlayer ON dbo.PartnerPlayer ( partnerId, playerId ) WITH ( FILLFACTOR = 96, SORT_IN_TEMPDB = ON ) ON [PRIMARY];

ALTER TABLE [dbo].[PartnerPlayer] WITH CHECK

ADD CONSTRAINT [fk_PartnerPlayer_partnerIdPlayerId] FOREIGN KEY([partnerId], [playerId])

REFERENCES [dbo].[Player] ([partnerId], [playerId]);

ALTER TABLE [dbo].[PartnerPlayer] CHECK CONSTRAINT [fk_PartnerPlayer_partnerIdPlayerId];

Edit: Changed index definition.