Smallest available integer in subset of table - SQL

Question

I'm working with an existing table that stores a start date, end date, and an integer used for ordering.

For a given start & end date, I need to be able to determine the smallest available integer for entries with an overlapping date range.

So for example, my table might store these records:

July 8th -> July 9th with an ordering index of 0.

July 9th -> July 10th with an ordering index of 1.

July 9th -> July 11th with an ordering index of 2.

Then, given the date range July 10th -> July 11th, I would want to set the ordering index to 0.

It needs to work where there could be no other entries within the entry date range (so it could default to 0). Date ranges aren't always two dates apart, and the ordering index doesn't have a limit.

Here is what I have that only returns one above the maximum order index:

SELECT ISNULL(MAX(order_index),-1) + 1 FROM table
WHERE start_date <= @end AND end_date >= @start)

I tried working with this answer, but couldn't get the desired result.

you are looking for the smallest integer, why did you use `MAX` ? — KrazzyNefarious, Jul 06 '15 at 19:44
@TabAlleman It would be 0 because between July 10th and 11th, order indexes 1 and 2 are already used but 0 is available because the July 8th to 9th record is not within the range. — James, Jul 06 '15 at 20:00

score 1 · Accepted Answer · edited May 23 '17 at 12:14

How about something like this?

declare @SampleData table ([BeginDate] date, [EndDate] date, [Order] int);
insert @SampleData values
    ('2015-07-08', '2015-07-09', 0),
    ('2015-07-09', '2015-07-10', 1),
    ('2015-07-09', '2015-07-11', 2);

declare @Start date = '2015-07-10';
declare @End date = '2015-07-11';

with [OrderingCTE] as
(
    select
        [Order],
        [Ideal Order] = row_number() over (order by [Order]) - 1
    from
        @SampleData
    where
        [BeginDate] <= @End and
        [EndDate] >= @Start
)
select coalesce
(
    min(case [Order] when [Ideal Order] then null else [Ideal Order] end),
    max([Order]) + 1
)
from
    [OrderingCTE];

The CTE produces two orderings for each record in the source table: [Order] is the actual value stored in the record, and [Ideal Order] is what that value would be if all possible orderings (starting with zero) were in use within the given date range.

If at any point the [Ideal Order] differs from the [Order], you can infer that the current [Ideal Order] value has not been used and is therefore the minimum available value. If this is not true at any point, then the minimum available value is one greater than the largest value that has been used thus far; that's the second half of the COALESCE at the bottom of the script.

As a final note: the question you linked has another answer raises concerns about a possible race condition that can arise, depending on how you're trying to use the data that you query in this way. I'd strongly recommend taking a look at it if you haven't already done so.

If this was used inside a scalar-valued function, how could I return the result? — James, Jul 06 '15 at 20:25
All you'd do is declare a scalar variable (say, `@Result`), change the line that says `select coalesce` to read `select @Result = coalesce`, and then `return @Result` afterward. The logic of the query doesn't change at all. Refer to [Types of Functions](https://technet.microsoft.com/en-us/library/ms177499(v=sql.105).aspx) for examples. — Joe Farrell, Jul 06 '15 at 22:16
Beautiful. I had to return 0 if null at the end, but otherwise this did the trick. — James, Jul 07 '15 at 13:35

Gordon Linoff · Answer 2 · 2015-07-07T02:15:31.310

0

I think you can do this by enumerating the values. If I assume that the order indexes are not duplicated, then you can use row_number() and some arithmetic to find the "holes". Additional logic is needed to handle the edge cases.

with t as (
      select t.*,
             row_number() over (order by order_index) as seqnum,
             min(order_index) over () as minoi,
             max(order_index) over () as maxoi
      from table t
      where start_date <= @end and end_date >= @start
     )
select (case when min(minoi) > 0 then 0
             when min(minoi) is null then min(maxoi + 1)
             else min(minoi + seqnum - 1)
        end)
from t 
where order_index <> minoi + seqnum - 1 or
      order_index = maxoi

edited Jul 07 '15 at 02:15

answered Jul 06 '15 at 19:43

Gordon Linoff

1,242,037
58
646
786

Looks promising, ends up with this error: Column 't.maxoi' is invalid in the select list because it is not contained in either an aggregate function or the GROUP BY clause. – James Jul 06 '15 at 20:28
^Then add `[t.maxoi]` to your `GROUP BY` clause – J.S. Orris Jul 06 '15 at 20:32

score 0 · Answer 3 · answered Jul 06 '15 at 20:04

I would try something like this:

SELECT
  COALESCE(
    MIN(CASE WHEN t2.order_index IS NULL THEN t1.order_index - 1 ELSE NULL END),
    MAX(t1.order_index) + 1,
    0)
FROM TheTable t1
LEFT JOIN TheTable t2
  ON t2.order_index = t1.order_index - 1
    AND t2.start_date <= @end
    AND t2.end_date >= @start
WHERE t1.start_date <= @end
  AND t1.end_date >= @start

Smallest available integer in subset of table - SQL

3 Answers3