Filtering data ordered by rowversion

Question

I have a SQL table of data with the following structure :

CREATE TABLE Data(
    Id uniqueidentifier NOT NULL,
    Date datetime NOT NULL,
    Value decimal(20, 10) NULL,
    RV timestamp NOT NULL,
 CONSTRAINT PK_Data PRIMARY KEY CLUSTERED (Id, Date)
)

The number of distinct Ids ranges from 3000 to 50000.
The size of the table varies up to over a billion rows.
One Id can cover between a few rows up to 5% of the table.

The single most executed query on this table is :

SELECT Id, Date, Value, RV
FROM Data
WHERE Id = @Id
AND Date Between @StartDate AND @StopDate

---

I now have to implement incremental retrieval of data on a subset of Ids, including updates.
I then used a request scheme in which the caller provide a specific rowversion, retrieve a block of data and use the maximum rowversion value of the returned data for the subsequent call.

I have written this procedure :

CREATE TYPE guid_list_tbltype AS TABLE (Id uniqueidentifier not null primary key)

CREATE PROCEDURE GetData
    @Ids guid_list_tbltype READONLY,
    @Cursor rowversion,
    @MaxRows int
AS
BEGIN
    SELECT A.* 
    FROM (
        SELECT 
            Data.Id,
            Date,
            Value,
            RV,
            ROW_NUMBER() OVER (ORDER BY RV) AS RN
        FROM Data
             inner join (SELECT Id FROM @Ids) Ids ON Ids.Id = Data.Id
        WHERE RV > @Cursor
    ) A 
    WHERE RN <= @MaxRows
END

Where @MaxRows will range between 500,000 and 2,000,000 depending on how chunked the client will want his data.

---

I have tried different approaches :

1. Indexing on (Id, RV) :

    CREATE NONCLUSTERED INDEX IDX_IDRV ON Data(Id, RV) INCLUDE(Date, Value);

Using the index, the query seek the rows where RV = @Cursor for each Id in @Ids, read the following rows then merge the result and sort.
Efficiency then depends on the relative position of @Cursor value.
If it is close to the end of data (ordered by RV) the query is instantaneous and if not the query can take up to minutes (never let it run to the end).

the problem with this approach is that @Cursor is either near the end of data and the sort isn't painful (not even needed if the query return less rows than @MaxRows) either it is further behind and the query has to sort @MaxRows * LEN(@Ids) rows.

1. Indexing on RV :

    CREATE NONCLUSTERED INDEX IDX_RV ON Data(RV) INCLUDE(Id, Date, Value);

Using the index, the query seek the row where RV = @Cursor then read every row discarding the non-requested Ids until it reaches @MaxRows.
Efficiency then depends on the % of requested Ids (LEN(@Ids) / COUNT(DISTINCT Id)) and their distribution.
More requested Id % means less discarded rows which means more efficient reads, less requested Id % means more discarded rows which means more reads for the same amount of resulting rows.

The problem with this approach is that if the requested Ids contains only a few elements, it might have to read the whole index to get the desired rows.

1. Using Filtered index or indexed views

    CREATE NONCLUSTERED INDEX IDX_RVClient1 ON Data(Id, RV) INCLUDE(Date, Value)
    WHERE Id IN (/* list of Ids for specific client*/);

Or

    CREATE VIEW vDataClient1 WITH SCHEMABINDING
    AS
    SELECT
        Id,
        Date,
        Value,
        RV
    FROM dbo.Data
    WHERE Id IN (/* list of Ids for specific client*/)

    CREATE UNIQUE CLUSTERED INDEX IDX_IDRV ON vDataClient1(Id, Rv);

This method allows for perfectly efficient indexing and query execution plans but come with disadvantages : 1. Practically, I will have to implement dynamic SQL to create the indexes or views and modify the requesting procedure to use the right index or view. 2. I will have to maintain one index or view by existing client, including storage. 3. Every time a client will have to modify his list of requested Ids, I will have to drop the index or view and recreate it.

---

I can't seem to find a method that will suit my needs.
I'm looking for better ideas to implement incremental data retrieval. Those ideas could imply reworking the requesting scheme or the database schema although I'd prefer a better indexing approach if there is one.

Answer 1

One solution is for the client application to remember the maximum rowversion per ID. The user-defined table type would change to:

CREATE TYPE
    dbo.guid_list_tbltype
AS TABLE 
    (
    Id      uniqueidentifier PRIMARY KEY, 
    LastRV  rowversion NOT NULL
    );

The query in the procedure can then be rewritten to use the APPLY pattern (see my SQLServerCentral articles part 1 and part 2 - free login required). The key to good performance here is the ORDER BY - it avoids unordered pre-fetching on the nested loops join. The RECOMPILE is necessary to allow the optimizer to see the cardinality of the table variable at compilation time (probably resulting in a desirable parallel plan).

ALTER PROCEDURE dbo.GetData

    @IDs        guid_list_tbltype READONLY,
    @MaxRows    bigint

AS
BEGIN

    SELECT TOP (@MaxRows)
        d.Id,
        d.[Date],
        d.Value,
        d.RV
    FROM @Ids AS i
    CROSS APPLY
    (
        SELECT
            d.*
        FROM dbo.Data AS d
        WHERE
            d.Id = i.Id
            AND d.RV > i.LastRV
    ) AS d
    ORDER BY
        i.Id,
        d.RV
    OPTION (RECOMPILE);

END;

You should get a post-execution query plan like this (estimated plan will be serial):

Answer 2

If possible, I would redesign the table. If we can have VersionNumber as an incremental integer with no gaps, that the task of retrieving the next chunk is a totally trivial range scan. All we need is the following index:

CREATE NONCLUSTERED INDEX IDX_IDRV ON Data(Id, VersionNumber) INCLUDE(Date, Value);

Of course, we need to make sure that VersionNumber starts with one and has no gaps. This is easy to do with constraints.

Answer 3

What I would have done:

In this instance, your PK should be a "Surrogate Key" Identity Field that auto-increments.
Since you're already in the billions, it would be best to go with a BigInt.
Let's call it DataID.
This will:

• Add 8 Bytes to every record in your Clustered Index.
• Save 16 Bytes on every record in every Non-Clustered Index.
• What you had was a "Natural Key": a UniqueIdentifyer (16 Bytes) w/ a DateTime (8 Bytes).
• That's 24 Bytes in every Index Record to reference back to the Clustered Index!
• This is why we have Surrogate Keys as Smaller Incrementing Integers.

Set your new BigInt PK (DataID) to use a Clustered-Index:
This will:

• Ensure the most recently created records are placed near the end.
• Allow for faster Indexing with other Non-Clustered Indexes.
• Allow for future expansion as an FK to other Tables.

Create a Non-Clustered-Index around (Date,Id).
This will:

• Speed up your most commonly used queries.
• You could add "Value", but it will increase the size of your index, which makes it slower.
• I'd suggest trying it in and outside of the Index to see if there is a vast difference in performance.
• I'd recommend not to use "Include" if you do add it.
• Just tack in on like so (Date,Id,Value) - but only if your testing shows it improves performance.

Create a Non-Clustered Index on (RV,ID).
This will:

• Always keep your Indexes as small as possible.
• Unless you notice crazy-huge performance gains with having the Date and Value in your Indexes, I'd suggest you leave them out to conserve disk space. Give it a try without them first.
• If you do add Date or Value, do not use "Include", instead add them to the ordering of the Index.
• Thanks to the DataID Incrementing on new Inserts into your Clustered PK, your recent RV's will usually appear near the end (unless you're updating swaths of data from the past all the time).