SQL Server 2012 - Frequent SELECT and UPDATE on bit column. Index doesn't help

Question

I have a SQL Server table with about 2 million rows in, this table stores short textual documents. Here's my schema:

CREATE TABLE Documents (
    documentId bigint IDENTITY NOT NULL,
    content nvarchar(MAX) NOT NULL,
    isIndexed bit NOT NULL
)

I have a separate Lucene-based indexer process that does this:

SELECT TOP 1 documentId, content FROM Documents WHERE isIndexed = 0

It then performs the indexing operation before executing this:

UPDATE Documents SET isIndexed = 1 WHERE documentId = @documentId

Initially this worked fine. When every document in the table was not indexed (i.e. all isIndexed values were 0) then each retrieval took about 5ms.

However as more and more documents were indexed then the retrieval time slowly increased. Currently it's about 150ms - a 30 time speed reduction. I note that the UPDATE statement always seems to run in under 2ms, so I know that's not a problem.

From the start the table has always had a non-clustered index on the isIndexed column, but the Actual Execution Plan shows the SQL Server uses an Index Scan (rather than Seek).

What can I do to speed up the system?

I am aware that the "isIndexed" column existing is bad in itself, but due to how the indexer works it can't request documents by documentId directly. For this and other reasons I can't accept any answers that don't solve the immediate problem at hand.

Answer 1

An index on the bit column isn't going to help at all because of selectivity. You should consider a filtered index:

CREATE INDEX unindexed ON dbo.Documents(documentId) WHERE IsIndexed = 0;

You should also include an ORDER BY documentId in your SELECT.

Though you should test this in a staging environment because it may help your SELECT but may offset that with a more expensive UPDATE.

Answer 2

The table (now) has the following non-clustered indexes:

IX_Indexed_ASC (Non-Unique) ( IsIndexed ASC, DocumentId ASC )
IX_Indexed_DESC (Non-Unique) ( IsIndexed DESC, DocumentId ASC )
IX_IsIndexed_Filtered (Non-Unique) ( DocumentId ASC WHERE IsIndexed = 0 )
IX_DocumentId_Indexed (Unique) ( DocumentId ASC, IsIndexed ASC )

And the clustered index:

PK_Documents ( DocumentId ASC )

I changed my query from this:

SELECT
    TOP 1 DocumentId,
    Content,
    IsIndexed
FROM
    Documents
WHERE
    IsIndexed = 0

to this:

SELECT 
    DocumentId,
    Content,
    IsIndexed

FROM
    Documents
WHERE
    DocumentId = (
        SELECT
            TOP 1 DocumentId
        FROM
            Documents
        WHERE
            IsIndexed = 0
    )

And now the queries execute in under 10ms again. The Actual Execution Plan reports that it's performing two index seek operations on IX_Indexed_ASC and IX_DocumentId_Indexed.