Error: 8646, Severity: 21, State: 1.
Unable to find index entry in index ID 1, of table 1877581727, in database 'db name here'. The indicated index is corrupt or there is a problem with the current update plan. Run DBCC CHECKDB or DBCC CHECKTABLE. If the problem persists, contact product support.

Recently ran into a serious issue with SQL Server issueing the above message under load.  After shutting things down and running check db there was no corruption, but every time a particular stored procedure was executed under load, stack dumps would occur with the above message in the Error Log.

With the help of Microsoft support we isolate the issue to a particular delete statement that was being executed with a join to another table and a where clause.  The query was performing a hash join and there is some bug that was causing a problem.  Microsoft continues to research the issue, but recommended we use a query hint to force a merge join to resolve the problem.  Testing indicates that the problem has gone away.

Old Query:

DELETE FROM {child table}
FROM {child table} aq, {parent table} a
WHERE aq.id = a.id
AND ( a.status_id in (4, 5, 6, 7)
OR type_id = 3
OR a.match_id =2 
AND a.id%@p_in_threads = @p_in_thread_no

New Query

DELETE FROM {child table}
FROM {child table} aq, {parent table} a
WHERE aq.id = a.id
AND ( a.status_id in (4, 5, 6, 7)
OR type_id = 3
OR a.match_id =2 
AND a.id%@p_in_threads = @p_in_thread_no
option (merge join)