Get a count based on the row order

Question

I have a table with this structure

Create Table Example (
[order] INT,
[typeID] INT
)

With this data:

order|type
1   7
2   11
3   11
4   18
5   5
6   19
7   5
8   5
9   3
10  11
11  11
12  3

I need to get the count of each type based on the order, something like:

type|count
7      1
11     **2**
18     1
5      1
19     1
5      **2**
3      1
11     **2**
3      1

Context

Lets say that this table is about houses, so I have a list houses in an order. So I have

• Order 1: A red house
• 2: A white house
• 3: A white house
• 4: A red house
• 5: A blue house
• 6: A blue house
• 7: A white house

So I need to show that info condensed. I need to say:

• I have 1 red house
• Then I have 2 white houses
• Then I have 1 red house
• Then I have 2 blue houses
• Then I have 1 white house

So the count is based on the order. The DENSE_RANK function would help me if I were able to reset the RANK when the partition changes.

Answer 1

I thought I'd post another approach I worked out, I think more along the lines of the dense_rank() work others were thinking about. The only thing this assumes is that _order is a sequential integer (i.e. no gaps).

Same data setup as before:

if object_id('tempdb.dbo.#t') is not null drop table #t
create table #t
(
    _order int primary key clustered,
    _type int,
    _grp int
)

insert into #t (_order, _type)
select 1,7
union all select 2,11
union all select 3,11
union all select 4,18
union all select 5,5
union all select 6,19
union all select 7,5
union all select 8,5
union all select 9,3
union all select 10,11
union all select 11,11
union all select 12,3

What this approach does is row_number each _type so that regardless of where a _type exists, and how many times, the types will have a unique row_number in the order of the _order field. By subtracting that type-specific row number from the global row number (i.e. _order), you'll end up with groups. Here's the code for this one, then I'll walk through this as well.

;with tr as
(
    select 
        -- Create an incrementing integer row_number over each _type (regardless of it's position in the sequence)
        _type_rid = row_number() over (partition by _type order by _order),
        -- This shows that on rows 6-8 (the transition between type 19 and 5), naively they're all assigned the same group
        naive_type_rid = _order - row_number() over (partition by _type order by _order),
        -- By adding a value to the type_rid which is a function of _type, those two values are distinct. 
        -- Originally I just added the value, but I think squaring it ensures that there can't ever be another gap of 1
        true_type_rid = (_order - row_number() over (partition by _type order by _order)) + power(_type, 2),
        _type, 
        _order
    from #t
    -- order by _order -- uncomment this if you want to run the inner select separately
)
select 
    _grp = dense_rank() over (order by max(_order)),
    _type = max(_type)
from tr
group by true_type_rid
order by max(_order)

What's Going On

First things first; I didn't have to create a separate column in the src cte to return _type_rid. I did that mostly for troubleshooting and clarity. Secondly, I also didn't really have to do a second dense_rank on the final selection for the column _grp. I just did that so it matched exactly the results from my other approach.

Within each type, type_rid is unique, and increments by 1. _order also increments by one. So as long as a given type is chugging along, gapped by only 1, _order - _type_rid will be the same value. Let's look at a couple examples (This is the result of the src cte, ordered by _order):

_type_rid            naive_type_rid       true_type_rid        _type       _order
-------------------- -------------------- -------------------- ----------- -----------
1                    8                    17                   3           9
2                    10                   19                   3           12
1                    4                    29                   5           5
2                    5                    30                   5           7
3                    5                    30                   5           8
1                    0                    49                   7           1
1                    1                    122                  11          2
2                    1                    122                  11          3
3                    7                    128                  11          10
4                    7                    128                  11          11
1                    3                    327                  18          4
1                    5                    366                  19          6

First row, _order - _type_rid = 1 - 1 = 0. This assigns this row (type 7) to group 0 Second row, 2 - 1 = 1. This assigns type 11 to group 1 Third row, 3 - 2 = 1. This assigns the second sequential type 11 to group 1 also Forth row, 4 - 1 = 3. This assigns type 18 to group 3 ... and so forth.

The groups aren't sequential, but they ARE in the same order as _order which is the important part. You'll also notice I added the value of _type to that value as well. That's because when we hit some of the later rows, groups switched, but the sequence was still incremented by 1. By adding _type, we can differentiate those off-by-one values and still do it in the right order as well.

The final outer select from src orders by the max(_order) (in both my unnecessary dense_rank() _grp modification, and just the general result order).

Conclusion

This is still a little wonky, but definitely well within the bounds of "supported functionality". Given that I ran into one gotcha in there (the off-by-one thing), there might be others I haven't considered, so again, take that with a grain of salt, and do some testing.

Answer 2

This solution is using a recursive CTE and is relying on a gapless order value. If you don't have this, you can create it with ROW_NUMBER() on the fly:

DECLARE @mockup TABLE([order] INT,[type] INT);
INSERT INTO @mockup VALUES
 (1,7)
,(2,11)
,(3,11)
,(4,18)
,(5,5)
,(6,19)
,(7,5)
,(8,5)
,(9,3)
,(10,11)
,(11,11)
,(12,3);

WITH recCTE AS
(
    SELECT m.[order]
          ,m.[type] 
          ,1 AS IncCounter
          ,1 AS [Rank]
    FROM @mockup AS m
    WHERE m.[order]=1

    UNION ALL

    SELECT m.[order]
          ,m.[type]
          ,CASE WHEN m.[type]=r.[type] THEN r.IncCounter+1 ELSE 1 END
          ,CASE WHEN m.[type]<>r.[type] THEN r.[Rank]+1 ELSE r.[Rank] END
    FROM @mockup AS m
    INNER JOIN recCTE AS r ON m.[order]=r.[order]+1
)
SELECT recCTE.[type]
      ,MAX(recCTE.[IncCounter])
      ,recCTE.[Rank]
FROM recCTE
GROUP BY recCTE.[type], recCTE.[Rank];

The recursion is traversing down the line increasing the counter if the type is unchanged and increasing the rank if the type is different.

The rest is a simple GROUP BY

Answer 3

So I have an answer, but I have to warn you it's probably going to get some raised eyebrows because of how it's done. It uses something known as a "Quirky Update". If you plan to implement this, please for the love of god read through the linked article and understand that this is an "undocumented hack" which needs to be implemented precisely to avoid unintended consequences.

If you have a tiny bit of data, I'd just do it row by agonizing row for simplicity and clarity. However if you have a lot of data and still need high performance, this might do.

Requirements

1. Table must have a clustered index in the order you want to progress in
2. Table must have no other indexes (these might cause SQL to read the data from another index which is not in the correct order, causing the quantum superposition of row order to come collapsing down).
3. Table must be completely locked down during the operation (tablockx)
4. Update must progress in serial fashion (maxdop 1)

What it does

You know how people tell you there is no implicit order to the data in a table? That's still true 99% of the time. Except we know that ultimately it HAS to be stored on disk in SOME order. And it's that order that we're exploiting here. By forcing a clustered index update and the fact that you can assign variables in the same update statement that columns are updated, you can effectively scroll through the data REALLY fast.

Let's set up the data:

if object_id('tempdb.dbo.#t') is not null drop table #t
create table #t
(
    _order int primary key clustered,
    _type int,
    _grp int
)

insert into #t (_order, _type)
select 1,7
union all select 2,11
union all select 3,11
union all select 4,18
union all select 5,5
union all select 6,19
union all select 7,5
union all select 8,5
union all select 9,3
union all select 10,11
union all select 11,11
union all select 12,3

Here's the update statement. I'll walk through each of the components below

declare @Order int, @Type int, @Grp int

update #t with (tablockx)
set @Order = _order,
    @Grp = case when _order = 1 then 1
                when _type != @Type then @grp + 1
                else @Grp
           end,
    @Type = _type,
    _grp = @Grp
option (maxdop 1)

1. Update is performed with (tablockx). If you're working with a temp table, you know there's no contention on the table, but still it's a good habit to get into (if using this approach can even be considered a good habit to get into at all).
2. Set @Order = _order. This looks like a pointless statement, and it kind of is. However since _order is the primary key of the table, assigning that to a variable is what forces SQL to perform a clustered index update, which is crucial to this working
3. Populate an integer to represent the sequential groups you want. This is where the magic happens, and you have to think about it in terms of it scrolling through the table. When _order is 1 (the first row), just set the @Grp variable to 1. If, on any given row, the column value of _type differs from the variable value of @type, we increment the grouping variable. If the values are the same, we just stick with the @Grp we have from the previous row.
4. Update the @Type variable with the column _type's value. Note this HAS to come after the assignment of @Grp for it to have the correct value.
5. Finally, set _grp = @Grp. This is where the actual column value is updated with the results of step 3.
6. All this must be done with option (maxdop 1). This means the Maximum Degree of Parallelism is set to 1. In other words, SQL cannot do any task parallelization which might lead to the ordering being off.

Now it's just a matter of grouping by the _grp field. You'll have a unique _grp value for each consecutive batch of _type.

Conclusion

If this seems bananas and hacky, it is. As with all things, you need to take this with a grain of salt, and I'd recommend really playing around with the concept to fully understand it if you plan to implement it because I guarantee nobody else is going to know how to troubleshoot it if you get a call in the middle of the night that it's breaking.