How to structure predicate to trigger a clustered index seek after a certain record with a composite key?

Question

I have a table with a 4-part composite clustered primary key (A, B, C, D), ordered on A,B,C,D.

I must walk this entire table in batches by taking N records, then taking the next N records starting at whatever value comes after the last key examined (K1,K2,K3,K4). The key values are not contiguous.

I'm trying to construct the predicate to seek to the next batch of records, given a last read record with composite key (K1,K2,K3,K4).

If the ID wasn't composite, I'd just run a select statement like "select top N from Table where ID > K1". However, because it's a 4-part composite key, I have to construct a special predicate to deal with the fact that D can be less than K4, as long as any or all of A, B, and C are greater than K1, K2, and K3.

In some database engines, I understand that such a composite key comparison can be made using set syntax like:

where (A,B,C,D) > (K1,K2,K3,K4)

Question 1: Does SQL Server support the above set comparison syntax?

If not, then I suspect I'll have to structure the predicate like this:

One Key	Two Keys	Three Keys	Four Keys
where (A > K1) order by A	where (A = K1 and B > K2) OR (A > K1) order by A, B	where (A = K1 and B = K2 and C > K3) OR (A = K1 and B > K2) OR (A > K1) order by A, B, C	where (A = K1 and B = K2 and C = K3 and D > K4) OR (A = K1 and B = K2 and C > K3) OR (A = K1 and B > K2) OR (A > K1) order by A, B, C, D

Question 2: Are the above predicates equivalent to the set comparison (A,B,C,D) > (K1,K2,K3,K4)? Or am I missing conditions.

Question 3: Given that the order by statement matches the clustered index key order, is SQL Server database engine smart enough to recognize this predicate's form and choose the optimal option of seeking to the record with key (K1, K2, K3, K4) and then simply scanning forward from there starting at the next record? Or will it perform a series of seeks for for each part of the predicate combined by an OR operator? I would image that other database engines that recognize the format "where (A,B,C,D) > (K1,K2,K3,K4) order by A,B,C,D" are able to optimize it.

I found a similar question here, but the answer isn't satisfactory.

Answer 1

1. Does SQL Server support the above set comparison syntax?

No.

2. Are the above predicates equivalent to the set comparison (A,B,C,D) > (K1,K2,K3,K4)?

Yes.

3. Given that the order by statement matches the clustered index key order, is SQL Server database engine smart enough to recognize this predicate's form and choose the optimal option of seeking to the record with key (K1, K2, K3, K4) and then simply scanning forward from there starting at the next record? Or will it perform a series of seeks for each part of the predicate combined by an OR operator?

Separate seeking operations within a single Index Seek operator. You may need to write your statements carefully to get this most optimized outcome, depending on your SQL Server version.

See the related Q & A:

• Index seek to specific multi-column key, then get some rows in lexicographical order
• Most cost efficient way to page through a poorly ordered table?

Answer 2

i haven't worked this at all yet, but i think you are looking for a variation on this theme - with appropriate data types for @lasta, @lastb, @lastc, and @lastd as well as appropriate starting values.

DECLARE @lasta VARCHAR(5) = '', @lastb VARCHAR(5) = '', @lastc VARCHAR(5) = '', @lastd VARCHAR(5) = '';
DECLARE @N INT = 100000;

WHILE EXISTS
  (SELECT TOP (1) t.a, t.b, t.c, t.d
   FROM table t
   WHERE
     (t.a > @lasta)
   OR
     (t.a = @lasta
      AND t.b > @lastb)
   OR
     (t.a = @lasta
      AND t.b = @lastb
      AND t.c > @lastc)
   OR
     (t.a = @lasta
      AND t.b = @lastb
      AND t.c = @lastc
      AND t.d > @lastd)
   ORDER BY t.a ASC, t.b ASC, t.c ASC, t.d ASC)

   BEGIN

      SELECT TOP (N) t.a, t.b, t.c, t.d
      INTO #temp
      FROM table t
      WHERE
        (t.a > @lasta)
      OR
        (t.a = @lasta
         AND t.b > @lastb)
      OR
        (t.a = @lasta
         AND t.b = @lastb
         AND t.c > @lastc)
      OR
        (t.a = @lasta
        AND t.b = @lastb
        AND t.c = @lastc
        AND t.d > @lastd)
      ORDER BY t.a ASC, t.b ASC, t.c ASC, t.d ASC;

      SELECT TOP (1) @lasta = t.a, @lastb = t.b, @lastc = t.c, @lastd = t.d
      FROM #temp
      ORDER BY t.a DESC, t.b DESC, t.c DESC, t.d DESC;

      DROP TABLE #temp IF EXISTS;

   END

Answer 3

If you're doing this in a client app or can otherwise use a single session for all the pages, you can simply run select * from t order by k1,k2,k3 and only fetch and process 1000 rows at a time from the resultset.

A super-simple, but not performancee-optimal solution is to just use offset/fetch. The problem with it is that you don't get seek-to-first-row like you do with select top (@rows) * from t where key > @lastKeyVal order by key, and the query plan will scan and skip the @offset rows.

select *
from sales.salesorderdetail
order by SalesOrderID, SalesOrderDetailID
offset @offset rows
fetch next @rows rows only 

Possibly hinted to a non-clustered primary key to scan the narrowest data structure possible.

Answer 4

To me, it looks like your general understanding is one of the better approaches. In my testing with a data set it:

• Had 9 logical reads
• Completed in 139 milliseconds of execution time
• Didn't need to go parallel

I started by creating a table to work with for all combinations of INTs with 4 keys:

CREATE TABLE dbo.ClusteredIndexScanning
(
    A INT NOT NULL
    ,B INT NOT NULL
    ,C INT NOT NULL
    ,D INT NOT NULL
    ,Id INT NOT NULL /* Used to help me find the next row in the future */
    /*
        Adding to make the table bigger storage wise and require more pages.
        That way Read numbers between better and poorer queries are a little more dramatic
    */
    ,SpaceFiller CHAR(50) NOT NULL
    ,PRIMARY KEY (A ASC, B ASC, C ASC, D ASC)
);
GO

Then populated that table with each combination of INTs 1 - 100 (100,000,000 rows)

DECLARE @IdValues TABLE (ConfiguredValue INT NOT NULL);

INSERT INTO @IdValues (ConfiguredValue)
VALUES
(1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11),(12),(13),(14),(15),(16),(17),(18),(19),(20)
,(21),(22),(23),(24),(25),(26),(27),(28),(29),(30),(31),(32),(33),(34),(35),(36),(37),(38),(39),(40)
,(41),(42),(43),(44),(45),(46),(47),(48),(49),(50),(51),(52),(53),(54),(55),(56),(57),(58),(59),(60)
,(61),(62),(63),(64),(65),(66),(67),(68),(69),(70),(71),(72),(73),(74),(75),(76),(77),(78),(79),(80)
,(81),(82),(83),(84),(85),(86),(87),(88),(89),(90),(91),(92),(93),(94),(95),(96),(97),(98),(99),(100);

INSERT INTO dbo.ClusteredIndexScanning
(
    A
    ,B
    ,C
    ,D
    ,Id
    ,SpaceFiller
)
SELECT A.ConfiguredValue
,B.ConfiguredValue
,C.ConfiguredValue
,D.ConfiguredValue
,ROW_NUMBER() OVER(ORDER BY A.ConfiguredValue ASC, B.ConfiguredValue ASC, C.ConfiguredValue ASC, D.ConfiguredValue ASC) AS RowNumber
,'' AS SpaceFiller
FROM @IdValues AS A
    CROSS APPLY
    (
        SELECT *
        FROM @IdValues AS IV
    ) B
    CROSS APPLY
    (
        SELECT *
        FROM @IdValues AS IV
    ) C
    CROSS APPLY
    (
        SELECT *
        FROM @IdValues AS IV
    ) D;
GO

Then ran a query to get the top 100 rows after a specified A, B, C and D (I have your same filters, just in the reverse order but that shouldn't make a difference. Also if needed, the value for the TOP can be changed to a variable and the plan doesn't change.) (Here is the Paste The Plan):

DECLARE @A INT = 10
,@B INT = 20
,@C INT = 30
,@D INT = 40;

SELECT TOP(100) *
FROM dbo.ClusteredIndexScanning AS CIS
WHERE A > @A
OR (A = @A AND B > @B)
OR (A = @A AND B = @B AND C > @C)
OR (A = @A AND B = @B AND C = @C AND D > @D)
ORDER BY A ASC, B ASC, C ASC, D ASC;

Below is the output from STATISTICS IO and STATISICTS TIME

SQL Server parse and compile time: CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times: CPU time = 0 ms, elapsed time = 0 ms.

SQL Server parse and compile time: CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times: CPU time = 0 ms, elapsed time = 0 ms.

(100 rows affected)

Table 'ClusteredIndexScanning'. Scan count 2, logical reads 9, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

(1 row affected)

SQL Server Execution Times: CPU time = 0 ms, elapsed time = 123 ms. SQL Server parse and compile time: CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times: CPU time = 0 ms, elapsed time = 0 ms.

Answer 5

SQL Server doesn't support the kind of (A,B,C,D) > (K1,K2,K3,K4) syntax you're hoping for.

So, I believe your options are:

• Use something roughly analogous to the 4-key approach you've outlined above - assuming that the logic is sound (I skimmed the logic mentally - looks fine-ish to me, but I haven't tested it or scrutinized it thoroughly).
• Use a 'hack' that allows you to achieve ROUGHLY the same approach you're hoping to pull off via (A,B,C,D) > (K1,K2,K3,K4) syntax.

And, I'm guessing you already have a good idea on how to approximate said logic - using a computed (i.e., projected/persisted + indexed) composite key.

For anyone else reading along, the easiest way I can think to describe the use of a composite key here would be to slightly 'tweak' the syntax/description (or format) of the key mentioned above to something more-akin to, say, A:B:C:D.

Or, in other words (and to keep things conceptually trivial), assume that:

• A could contain values 1-100, B could contain values 1-100, and the same goes for C and D as well.
• We simply 'serialize' or 'plunk' these values down one after another to create a (overly-simplistic) composite key.

So, for example:

• 001:001:001:001 would be the absolute smallest composite key you could have and would point to A,B,C,D all having their own, discrete, 'keys' at values of 1.
• 100:100:100:100 would, in turn, be the largest composite key you could have.
• 001:098:085:009 would always be 'less than' 002:099:099:099 - even though the values for B,C,D are 'greater' in the second string.

Obviously, you'd need to do a BIT more work than the above to get either a binary collation (against this persisted + indexed column) to work as needed and/or to be wider and account for other data-types and so on. BUT, presuming that left-mostedness (like any other index) 'weighed more' that values further to the right, a HACK like this should work fine.

Yes, an approach like this will take a few extra bytes (a bigint, an ugly string, whatever) per row to manage and maintain - but:

• standard procedure when a CLIX doesn't meet your exact query needs is to create a new index (in this case, we merely extend that practice to use a derived column that gets indexed/persisted).
• depending upon the data and nature of A,B,C,D domains themselves, this approach (a 'hacked' composite key) MIGHT result in slightly cleaner code (easier factors for the code that's WALKING these rows at least) than the 4 key approach outlined above.
• I presume the hacked option would be a BIT easier to test/validate and, that, presumably, IF you were to introduce ANY other predicates to this A,B,C,D 'walking' logic later on, the approach with the hacked composite key would further probably be a bit easier to test, integrate, and maintain.

Or, as with all answers relative to something complex like this, your miles may vary.