Within a Sequence

This month I discovered Itzik Ben-Gan have posted a two-part article about how to find a sub-sequence within a sequence.
See part 1 here http://sqlmag.com/t-sql/identifying-subsequence-in-sequence-part-1
and part 2 here http://sqlmag.com/t-sql/identifying-subsequence-in-sequence-part-2

Part 1 is about iterative solutions and the best one was 3.5 seconds and about 400,000 reads.
Part 2 is about set-based solutions and the best one was 3 seconds and 5,300,000 reads.

When you realize the problem is a special case of Relational Division (a case I call Ordered Relational Division), the solution is quite simple.

— SwePeso
DECLARE @Items INT = (SELECT COUNT(*) FROM @P);

SELECT MIN(t.KeyCol) AS MinKey,
MAX(t.KeyCol) AS MaxKey
FROM dbo.T1 AS t
INNER JOIN @P AS p ON p.Val = t.Val
GROUP BY t.KeyCol – p.KeyCol
HAVING COUNT(*) = @Items;

This solution takes about 1 second to execute and used 14,000 reads.

Leave a Reply