Efficiently Filter Large Set With Disjunctions Let's say I have a single table

CREATE TABLE Ticket (
    TicketId int NOT NULL,
    InsertDateTime datetime NOT NULL,
    SiteId int NOT NULL,
    StatusId tinyint NOT NULL,
    AssignedId int NULL,
    ReportedById int NOT NULL,
    CategoryId int NULL
);


In this example TicketId is the Primary Key.

I want users to be able to create "partially ad-hoc" queries against this table. I say partially because a few parts of the query will always fixed:


The query will always perform a range filter on an
InsertDateTime
The query will always ORDER BY InsertDateTime DESC
The query will page results


The user can optionally filter on any of the other columns. They can filter on none, one, or many. And for each column the user may select from a set of values which will be applied as a disjunction. For example:

SELECT
    TicketId
FROM (
    SELECT
        TicketId,
        ROW_NUMBER() OVER(ORDER BY InsertDateTime DESC) as RowNum
    FROM Ticket
    WHERE InsertDateTime &gt;= '2013-01-01' AND InsertDateTime &lt; '2013-02-01'
      AND StatusId IN (1,2,3)
      AND (CategoryId IN (10,11) OR CategoryId IS NULL)
    ) _
WHERE RowNum BETWEEN 1 AND 100;


Now assume the table has 100,000,000 rows.

The best I can come up with is a covering index that includes each of the "optional" columns:

CREATE NONCLUSTERED INDEX IX_Ticket_Covering ON Ticket (
    InsertDateTime DESC
) INCLUDE (
    SiteId, StatusId, AssignedId, ReportedById, CategoryId
);


This gives me a query plan as follows:


SELECT

Filter

Top

Sequence Project (Compute Scalar)

Segment

Index Seek







It seems pretty good. About 80%-90% of the cost comes from the Index Seek operation, which is ideal.

Are there better strategies for implementing this kind of searching?

I don't necessarily want to offload the optional filtering to the client because in some cases the result set from the "fixed" part could be 100s or 1000s. The client would then also be responsible for sorting and paging which might too much work for the client.
If this particular work load is the majority of queries against the table you might consider:

ALTER TABLE Ticket ADD CONSTRAINT PK_Ticket PRIMARY KEY NONCLUSTERED (TicketId);

CREATE UNIQUE CLUSTERED INDEX IX_Ticket_Covering ON Ticket (
    InsertDateTime ASC
);


Considerations:


can you use datetime2 (SQL 2008+; flexible precision)
will InsertDateTime be unique within your precision
if the times are not constrained unique sql will add a hidden uniquifier column of type int. This is added to all nonclutred index so they can reference the correct clustered record 


Advantages:


Adds new rows to the end of the table 
prevent writing the optional filter columns twice (once in the clustered, and once on the index leaf for the include)
majority of you time will still be on a cluster index seek with more or less filers. 
then add other nonclustered index for most popular column pairs