sql server 2014 - Find gaps in sequence on 2 different fields group by third field

Question

I need to detect the gaps between the sequences for each different seller considering that sequence is in 2 different rows considering only supplied range (avoiding numbers below the first record and numbers above the last record):

I have a table with orders where relevant fields are:

    SellerID | OrderID |   OID   |
    seller1  | 123456  |         |
    seller1  | 123457  |         |
    seller1  | 123458  | 123460  |
    seller1  | 123459  | 123460  |
    seller2  | 234567  |         | (first record)
    seller1  | 123455  |         | 
    seller2  | 234568  | 234570  |
    seller2  | 234569  | 234570  | 
    seller1  | 123463  |         |
    seller1  | 123466  |         |
    seller1  | 123453  |         | (first record)
    seller2  | 234572  |         | (last record)
    seller1  | 123470  |         | (last record)

I expect a result like this:

    seller 1 | 123454
    seller 1 | 123461
    seller 1 | 123462
    seller 1 | 123464
    seller 1 | 123465
    seller 1 | 123467
    seller 1 | 123468
    seller 1 | 123469
    seller 2 | 234571

it is quite easy also for me to find gaps in a single row and for single seller: I used this query that I repeat for every seller:

Declare @SellerID nvarchar(50)='seller1'
SELECT s1.OrderID
FROM Orders s1
LEFT JOIN Orders s2
ON s1.OrderID = s2.OrderID -1
WHERE s2.OrderID IS NULL
and SellerID=@SellerID
order by s1.OrderID asc 

but I do not know how to modify in way to check for the sequence in the 2 columns

moreover, is there a way to achieve this in a single query instead of repeating for each seller?

Answer 1

You can use CROSS APPLY to "unpivot" multiple columns. This query will give you a list of orders (unpivoted). I've added a third column, which is the LEADing (i.e. next) OrderID, if there is any:

SELECT o.SellerID, x.OrderID,
       LEAD(x.OrderID, 1) OVER (
           PARTITION BY o.SellerID
           ORDER BY x.OrderID) AS _nextOrderID
FROM Orders AS o
CROSS APPLY (
    SELECT o.OrderID
    UNION ALL
    SELECT o.OID AS OrderID WHERE o.OID IS NOT NULL
    ) AS x(OrderID);

This gives you:

SellerID   OrderID     _nextOrderID
---------- ----------- ------------
seller1    123453      123455
seller1    123455      123456
seller1    123456      123457
seller1    123457      123458
seller1    123458      123459
seller1    123459      123460
seller1    123460      123460
seller1    123460      123463
seller1    123463      123466
seller1    123466      123470
seller1    123470      NULL
seller2    234567      234568
seller2    234568      234569
seller2    234569      234570
seller2    234570      234570
seller2    234570      234572
seller2    234572      NULL

Now, if we subtract the OrderID from the _nextOrderID, we get the gap (how many orders are "missing"):

SELECT o.SellerID, x.OrderID,
       LEAD(x.OrderID, 1) OVER (
           PARTITION BY o.SellerID
           ORDER BY x.OrderID)-x.OrderID AS _gap
FROM Orders AS o
CROSS APPLY (
    SELECT o.OrderID
    UNION ALL
    SELECT o.OID AS OrderID WHERE o.OID IS NOT NULL
    ) AS x(OrderID);

.. which looks something like this:

SellerID   OrderID     _gap
---------- ----------- -----------
seller1    123453      2
seller1    123455      1
seller1    123456      1
seller1    123457      1
seller1    123458      1
seller1    123459      1
seller1    123460      0    <- 0 because you have two OrderID=123460
seller1    123460      3
seller1    123463      3
seller1    123466      4
seller1    123470      NULL
seller2    234567      1
seller2    234568      1
seller2    234569      1
seller2    234570      0
seller2    234570      2
seller2    234572      NULL

So where _gap<=1, we don't want to return any rows. Where _gap=4, we want to insert 3 rows, from OrderID+1 to OrderID+3. There are a few ways to do this, but I'm going to stick with CROSS APPLY here as well.

I'm putting the query above in a subquery (called sub in my example), and for each row in that result, I'm going to CROSS APPLY any dummy table. If you expect large gaps, you may want to create a separate table with a single IDENTITY column for this purpose, but I'm just going to use the Orders table along with a ROW_NUMBER():

SELECT sub.SellerID, sub.OrderID+n.rownum AS OrderID
FROM (
    SELECT o.SellerID, x.OrderID,
           LEAD(x.OrderID, 1) OVER (
               PARTITION BY o.SellerID
               ORDER BY x.OrderID)-x.OrderID AS _gap
    FROM Orders AS o
    CROSS APPLY (
        SELECT o.OrderID
        UNION ALL
        SELECT o.OID AS OrderID WHERE o.OID IS NOT NULL
        ) AS x(OrderID)
    ) AS sub
CROSS APPLY (
    --- For each row in sub, where _gap>1, return
    --- (_gap) number of rows, starting with 1, 2, 3, ..., (_gap-1).
    SELECT TOP (sub._gap-1)
           ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) AS rownum
    FROM Orders    -- or any dummy table
    ) AS n
--- Only where there's actually a gap:
WHERE sub._gap>1;

Finally, at the top, we add n.rownum to sub.OrderID to get the missing OrderID.

Here's the final output:

SellerID   OrderID
---------- --------------------
seller1    123454
seller1    123461
seller1    123462
seller1    123464
seller1    123465
seller1    123467
seller1    123468
seller1    123469
seller2    234571

Answer 2

One idea would be to use a CTE to extract a combined list of IDs, then replace Orders with the CTE name, eg:

with

allids as
(select SellerID,OrderID from Orders
 union
 select SellerID,OID     from Orders where OID is not NULL)

select ...
from   allids s1
left
join   allids s2
...

OP mentions having a query that finds the gaps for a single column, so I'm assuming OP could use the (above) cte to replace references to Order ... in the mean time ...

---

One not-necessarily-the-cleanest gap-finding query that eliminates the need for the @SellerID variable:

with

-- build a list of all OrderIDs, by SellerID

allids (SellerID, OrderID)
as
(select SellerID,
        OrderID
 from   Orders
 union
 select SellerID,
        OID
 from   Orders
 where  OID is not NULL),

-- find the max(OrderID), by SellerID; to be used to limit a) cte recursion and b) final result

maxIDs (SellerID, maxOrderID)
as
(select SellerID,
        max(OrderID)
 from   allids
 group by SellerID),

-- use a recursive cte to fill in gaps of missing OrderID's

recurse (SellerID, gapID)
as
(-- find first 'missing' OrderID in a gap

 select a.SellerID,
        a.OrderID + 1
 from   allids a
 where  not exists(select 1
                   from   allids b
                   where  b.SellerID = a.SellerID
                   and    b.OrderID  = a.OrderID + 1)

 union all

 -- find successive 'missing' OrderIDs

 select a.SellerID,
        a.gapID + 1
 from   recurse a
 where  not exists(select 1
                   from   allids b
                   where  b.SellerID = a.SellerID
                   and    b.OrderID  = a.gapID + 1)

 and    a.gapID < (select maxOrderID 
                   from   maxIDs m
                   where  m.SellerID = a.SellerID)
)

select r.SellerID,
       r.gapID

from   recurse r

where  r.gapID < (select maxOrderID
                  from   maxIDs m
                  where  m.SellerID = r.SellerID)

order by 1,2

-- if gaps could be expected to span more than 1000 'missing' OrderIDs,
-- update the MaxRecursion option accordingly:

option (MaxRecursion 1000);

 SellerID |  gapID
 -------- | ------
 seller1  | 123454
 seller1  | 123461
 seller1  | 123462
 seller1  | 123464
 seller1  | 123465
 seller1  | 123467
 seller1  | 123468
 seller1  | 123469
 seller2  | 234571

Here's a dbfiddle for the recursive cte

---

Not particularly fond of recursive queries when I can't be 100% sure of how deep the recursion needs to go, so wanted a to look at how to do this without recursion.

The gist of this idea is to find the start/end points of the gaps, and use a sequence generator to fill in the missing OrderIDs.

NOTE: I've discarded my initial sequence generator and replaced with @Daniel's sequence generator.

with

-- build a list of all OrderIDs

allids (SellerID, OrderID)
as
(select SellerID,
        OrderID
 from   Orders
 union
 select SellerID,
        OID
 from   Orders
 where  OID is not NULL),

-- find the first 'missing' OrderID for each gap

gapStart (SellerID, startOrderID)
as
(select a1.SellerID,
        a1.OrderID + 1

 from   allids a1
 where  not exists(select 1
                   from   allids a2
                   where  a2.OrderID = a1.OrderID + 1)),

-- now find the end of each gap

gaps (SellerID, startOrderID, endOrderID)
as
(select gs.SellerID,
        gs.startOrderID,
        min(OrderID) - 1

 from   gapStart gs

 join   allids   a
 on     a.SellerID = gs.SellerID
 and    a.OrderID  > gs.startOrderID

 group by gs.SellerID,
          gs.startOrderID)

-- display the gaps

select g.SellerID,
       g.startOrderID + n.rn - 1 as OrderID

from   gaps g

-- generate a sequence (1..N) where N = difference between gaps.startOrderID and gaps.endOrderID

cross
apply (select top(g.endOrderID - g.startOrderID + 1)
              row_number() over (order by (select NULL)) as rn
       from   Orders) as n

order by 1,2;

 SellerID |  gapID
 -------- | ------
 seller1  | 123454
 seller1  | 123461
 seller1  | 123462
 seller1  | 123464
 seller1  | 123465
 seller1  | 123467
 seller1  | 123468
 seller1  | 123469
 seller2  | 234571

Here's a dbfiddle for the gap/sequence idea.

Answer 3

Gap and Island problem are best solved using number table or calendar table. It is so easy,so short and no compromise with performance.

Also these utility table are helpful in so many other scenarios.

So once you can create and populate number table as you wish.

create table tblnumber(number int not null)
insert into tblnumber (number)
select ROW_NUMBER()over(order by a.number) from master..spt_values a
, master..spt_values b
CREATE unique clustered index CI_num on tblnumber(number)

Sample Data,

create table #t(SellerID varchar(20),OrderID int,OID int)
insert into #t VALUES
    ('seller1',123456, null ) ,('seller1',123457, null)
    ,('seller1',123458,123460) ,('seller1',123459,123460)
    ,('seller2',234567,  null),('seller1',123455,  null) 
    ,('seller2',234568,234570 ),('seller2',234569,234570) 
    ,('seller1',123463, null),('seller1',123466,null)
    ,('seller1',123453, null),('seller2',234572, null) 
    ,('seller1',123470, null) 

;With CTE as
(
select SellerID,min(OrderID)MinOID,max(OrderID)MaxOID from #t
group by SellerID
)
,CTE1 AS(
select n.number,SellerID from tblnumber n
cross apply(select * from cte C  where (n.number)
between c.minoid and c.maxoid  )ca  
)

select SellerID,number as OrderID from cte1 c
where not exists
(select t.SellerID from #t t 
where t.OrderID=c.number or t.OID=c.number)
order by c.number

    drop table #t

Also query can be further optimize depending upon your real scenario and number of rows involved.