Oracle – Decreasing vs Increasing Column VARCHAR2 Performance

Your table is a "heap," which means that it doesn't have a clustered index. The short version of what that means is that your data isn't laid out on the disk in a logical way. A heap really isn't an optimal structure for an actively updated table. Here's an excellent video on heaps.

So, my suggestions--please test them before deploying them in production--are:

BEGIN TRANSACTION

USE fp; ALTER TABLE fp_core ADD ID bigint NOT NULL IDENTITY (1, 1)
GO

USE fp; CREATE CLUSTERED INDEX IX_fp ON fp_core (ID) WITH (STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
GO

COMMIT

This will take some time to complete AND will be a blocking query, so do it during downtime.

This will give you a clustered index and lay out your table on a completely random sequential number, unfortunately, but since you don't have any non-unique values that might be the best course of action.

I would then include the columns note_id and timeoffset in your nonclustered index on HASHKEY.

BEGIN TRANSACTION

USE [fp]
GO

IF  EXISTS (SELECT * FROM sys.indexes WHERE object_id = OBJECT_ID(N'[dbo].[fp_core]') AND name = N'IX_Agency_TIMESTAMP')
DROP INDEX [IX_fp_core] ON [dbo].[fp_core] WITH ( ONLINE = OFF )
GO

USE [fp]
GO

CREATE NONCLUSTERED INDEX [IX_fp_core] ON [dbo].[fp_core] 
(
    [hashkey] ASC
)
INCLUDE ( [note_id],[timeoffset])
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, FILLFACTOR = 80) ON [PRIMARY]
GO

COMMIT

(Or you could do it through the GUI. If you right-click on the index and choose properties, there's an included columns pane.)

This will hopefully have the effect of replacing your heap scans with nonclustered index seeks, but since your query has a "where in [30,000 items], it might do a index scan instead. Either way, it won't be rooting around in the heap, which I expect will be a good thing.

Answering my own question, as future readers will benefit from it :

Seems like we might be hitting Longer latency for SQL Server 2012 database when you use Service Broker, database mirroring, and Availability Groups. This is fixed in SQL server 2012 SP2 CU1. The KB 2976982 has a typo(AlawysOn). So if you are searching by AlwaysON, it wont show up.

After the patch was applied, the issue was fixed.