# Find continuous records with equal values

I have a table named "TOOLS" .

Sample data:

``````ID       TAG
1         0
2         1
3         1
4         1
5         0
6         0
7         1
8         1
9         0
``````

So, the SQL query should select sum of TOOLS having continuous `1` in field `TAG` for a specified row, for example `ID=2` then the query returns 3 in this sample. It also returns 2 for `ID=7`.

How can I do it?

``````SELECT @ID ID, SUM(a.TAG) r
FROM @tools a
WHERE a.ID Between @ID And ( SELECT MIN(ID) FROM @tools b WHERE b.ID > @ID AND b.TAG = 0 )
``````

The trouble with all these lovely window function-based solutions is that if you write them as pseudo-code you get something like this:

`Do something across ALL the IDs, then work out the sequence, then aggregate...`

You also can't inject the ID at any point as it invalidates the window range. Even @JulienVavasseur's solution which uses an ID variable, will scan 999,999 rows in a 1 million row table where the `@ID` is 2. Basically these solutions do not scale well. So if you have 1 million or 1 billion rows in your tools table, well the query will take a long time, 4+ seconds versus 0-50ms in my simple test rig (see below). Now maybe you might have only 10 rows but it's a bad habit to write code that doesn't scale IMHO. You might know the volume today but you might not tomorrow.

More traditional set-based solutions can often work best, even recursive CTEs (under certain conditions) and these were the first two that occurred to me:

``````DECLARE @tools TABLE ( ID INT PRIMARY KEY, TAG INT NOT NULL )

;WITH cte AS (
SELECT TOP 1000000 ROW_NUMBER() OVER ( ORDER BY ( SELECT 1 ) ) rn
FROM master.sys.columns c1
CROSS JOIN master.sys.columns c2
CROSS JOIN master.sys.columns c3
)
INSERT INTO @tools ( ID, TAG )
SELECT rn, CAST( ( rn % 7 ) AS BIT )
FROM cte

DECLARE @id INT = 2

-- Set-based with subquery
SELECT @ID ID, SUM(a.TAG) r
FROM @tools a
WHERE a.ID Between @ID And ( SELECT MIN(b.ID) FROM @tools b WHERE b.ID > @ID AND b.TAG = 0 )

-- CTE
;WITH cte AS
(
SELECT ID, ID AS parentID, TAG
FROM @tools t
WHERE ID = @id
UNION ALL
SELECT b.ID, a.parentID, a.TAG
FROM cte a
INNER JOIN @tools b ON b.ID = a.ID + 1
WHERE b.TAG = 1
)
SELECT parentID AS ID, SUM(TAG) TAG
FROM cte
GROUP BY parentID
OPTION ( MAXRECURSION 999 );        -- <-- this can be set to 0 but set to lower boundary for safety
``````

Plugging the other solutions into my test rig does not end well for them:

In my tests, my recursive CTE solution (which normally would be thought of unfavourably as RBAR) performs the best with short sequences (< ~10,000), although this dips with really long sequences; My subquery was best with these.

I would be interested to see if a window-based approach could out-perform either of these two, even with different indexes eg I was surprised not to see a LAG / LEAD solution here. Does anyone know Itzik? : )

• Did you have an index on `(tag, id)` when performing the tests? – ypercubeᵀᴹ Feb 22 '16 at 15:21
• @ypercubeᵀᴹ No, index was as per test rig where ID is primary key. I've experimented with temp tables (#) where performance improves a lot for the window functions (presumably because of parallelism) but still (at least 1) order of magnitude slower than the 'ordinary' query with subquery and recursive CTE. – wBob Feb 22 '16 at 15:28
• I would think that the ordinary query would also benefit from a tag index - and some of the other answers/queries. And shouldn't that `between` be `id >= .. and id < ..`? – ypercubeᵀᴹ Feb 22 '16 at 15:30
• Logically you are right, but it makes no difference in this instance as TAG is 1 or 0. Good catch. – wBob Feb 22 '16 at 15:41
• Ah yeah, you used `SUM()` - I was thinking of `COUNT()` ;) – ypercubeᵀᴹ Feb 22 '16 at 17:36

The base idea behind it , is to use `COUNT(*) OVER(PARTITION BY T.[TAG] ORDER BY T.[ID])` = count the records that respect the condition.

``````DECLARE @Tools TABLE
([ID] int, [TAG] int)
;

INSERT INTO @Tools
([ID], [TAG])
VALUES
(1, 0),
(2, 1),
(3, 1),
(4, 1),
(5, 0),
(6, 0),
(7, 1),
(8, 1),
(9, 0)

;

;WITH CTE
AS (
SELECT
T.[ID]
,T.[TAG]
,COUNT(*) OVER(PARTITION BY T.[TAG] ORDER BY T.[ID]) AS COUNT_RECOURDS
,T.ID - COUNT(*) OVER(PARTITION BY T.[TAG] ORDER BY T.[ID]) AS GRP
FROM
@Tools AS T
WHERE
T.[TAG] = 1
)
SELECT
MIN(ID) AS ID
,COUNT(*) AS noRec
FROM CTE
GROUP BY
GRP
``````

This is the output (intermediar output) of the `CTE`

``````ID          TAG         COUNT_RECOURDS GRP
2           1           1              1
3           1           2              1
4           1           3              1
7           1           4              3
8           1           5              3
``````

And group by field `GRP`, you will obtain:

``````ID          noRec
2           3
7           2
``````

Query:

``````DECLARE @id int = 2

SELECT [@id] = @id, ID = MIN(ID)
, [Count] = COUNT(*)
FROM (
SELECT *
, n = ROW_NUMBER() OVER(ORDER BY TAG) - ROW_NUMBER() OVER(ORDER BY ID)
FROM @Tools
WHERE ID >= @id
) rn
WHERE TAG = 1
GROUP BY n
HAVING MIN(ID) = @id
``````

SQL Fiddle here.

Output:

``````@id     ID  Count
2       2   3
``````

Or

``````@id     ID  Count
2       7   2
``````

First `ROW_NUMBER` orders ID by TAG. Second `ROW_NUMBER` assigns a consecutive ID and makes sure there is no GAP between IDs.

Note that:

• if @id-1 has `TAG=1` it is not counted (=> `@id=3` return 2)
• it returns nothing (no row) for an @id value with `TAG=0`.

If you want to get the first ID with `TAG=1` following @id, this query can be used:

``````SELECT TOP(1) [@id] = @id, ID = MIN(ID)
, [Count] = COUNT(*)
FROM (
SELECT *
, n = ROW_NUMBER() OVER(ORDER BY TAG) - ROW_NUMBER() OVER(ORDER BY ID)
FROM @Tools
WHERE ID >= @id
) rn
WHERE TAG = 1
GROUP BY n
ORDER BY n DESC
``````

Output:

``````@id     ID  Count
1       2   3
``````

Or

``````@id     ID  Count
6       7   2
``````

A slight variation of sabin's and Juliens answers:

``````select min(id) as id, count(1) as cnt
from (
select id, tag
, row_number() over (order by id)
- row_number() over (partition by tag order by id) as grp
from tools
)
where tag = 1
group by grp;
``````

It will produce the same result even if there is gaps in the id sequence.

The idea is that:

``````row_number() over (order by id)
``````

enumerates all rows. This will be the same as id if id starts with 1 and has no gaps.

``````row_number() over (partition by tag order by id) as grp
``````

enumerates all rows for each tag [0,1]. If the difference between these enumeration changes, it means that the tag changed. We can therefore pick the min(id) and count() the rows within each such grp.