4

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?

3

Or a more traditional approach:

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:

enter image description here

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
1

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
1

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
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.