Find first available block that does not intersect a range

[Karch]

Given a number of numeric ranges, I need to find the first available row
(range) that can accomodate a requested block of contiguous values. For
example, given the following table definition:

CREATE TABLE [dbo].[tbl_AllocatedRange](
[RangeID] [int] IDENTITY(1,1) NOT NULL,
[RangeStart] [bigint] NOT NULL,
[RangeEnd] [bigint] NOT NULL,
CONSTRAINT [PK_tbl_AllocatedRange] PRIMARY KEY CLUSTERED
(
[RangeID] ASC
)

And the following DML:

INSERT INTO [dbo].[tbl_AllocatedRange] ([RangeID], [RangeStart], [RangeEnd])
VALUES ( 1, 100, 200 );

INSERT INTO [dbo].[tbl_AllocatedRange] ([RangeID], [RangeStart], [RangeEnd])
VALUES ( 2, 500, 650 );

INSERT INTO [dbo].[tbl_AllocatedRange] ([RangeID], [RangeStart], [RangeEnd])
VALUES ( 3, 2000, 2200 );

INSERT INTO [dbo].[tbl_AllocatedRange] ([RangeID], [RangeStart], [RangeEnd])
VALUES ( 4, 4000, 8000 );

INSERT INTO [dbo].[tbl_AllocatedRange] ([RangeID], [RangeStart], [RangeEnd])
VALUES ( 5, 16000, 25000 );

INSERT INTO [dbo].[tbl_AllocatedRange] ([RangeID], [RangeStart], [RangeEnd])
VALUES ( 6, 25001, 50000 );

INSERT INTO [dbo].[tbl_AllocatedRange] ([RangeID], [RangeStart], [RangeEnd])
VALUES ( 7, 100000, 200000 );

A request for a block of 10000, should return the row where RangeID=6
because that is the first available position where I could allocate a
contiguous block of 10000 without intersecting any of the values in the
existing ranges.

[Alex Kuznetsov]

SELECT MIN(RangeID) FROM [dbo].[tbl_AllocatedRange] r
WHERE NOT EXISTS(SELECT 1 FROM [dbo].[tbl_AllocatedRange] r1 WHERE
r1.RangeStart BETWEEN r.RangeEnd AND r.RangeEnd + 10000)

[Karch]

Thanks. That works great if I can depend on the allocated ranges being in
increasing order with the RangeID. What if the allocated ranges are not
dependable with regard to the RangeID? So, someone enters another reserved
range at RangeID=8, for example.

INSERT INTO [dbo].[tbl_AllocatedRange] ([RangeID], [RangeStart], [RangeEnd])

VALUES ( 8, 0, 0 );

And requests an allocation of 1....the query below will produce RangeID=1
as the first available when it should produce RangeID=8.

"Alex Kuznetsov" <AK_TIRE...@hotmail.COM> wrote in message
news:1180713051.7...@q75g2000hsh.googlegroups.com...

[Alex Kuznetsov]

On Jun 1, 11:31 am, "Karch" <nos...@absotutely.com> wrote:
> Thanks. That works great if I can depend on the allocated ranges being in
> increasing order with the RangeID. What if the allocated ranges are not
> dependable with regard to the RangeID? So, someone enters another reserved
> range at RangeID=8, for example.
>
> INSERT INTO [dbo].[tbl_AllocatedRange] ([RangeID], [RangeStart], [RangeEnd])
> VALUES ( 8, 0, 0 );
>
> And requests an allocation of 1....the query below will produce RangeID=1
> as the first available when it should produce RangeID=8.
>

> "Alex Kuznetsov" <AK_TIREDOFS...@hotmail.COM> wrote in message

Instead of SELECT MIN(RangeID)

use SELECT TOP 1 RangeID
...
ORDER BY RangeID

[Alejandro Mesa]

Karch,

Try:

declare @i int

set @i = 10000

select
*
from
[dbo].[tbl_AllocatedRange] as a
where
[RangeStart] = (
select
min(b.[RangeStart])
from
[dbo].[tbl_AllocatedRange] as b
where
b.[RangeStart] + @i <= b.[RangeEnd]
)
GO

-- SQL Server 2005

create index tbl_AllocatedRange_RangeStart_nu_nc_ix
on dbo.[tbl_AllocatedRange]([RangeStart])
include ([RangeID], [RangeEnd])
go

declare @i int

set @i = 10000

;with cte
as
(
select
[RangeID], [RangeStart], [RangeEnd],
row_number() over(order by [RangeStart]) as rn
from
[dbo].[tbl_AllocatedRange]
where
[RangeStart] + @i <= [RangeEnd]
)
select

[RangeID], [RangeStart], [RangeEnd]

from
cte
where
rn = 1
go

AMB

[Karch]

Hmmm...making that change doesn't seem to work with the example below. Query
still returns RangeID=1 when it should return RangeID=8

"Alex Kuznetsov" <AK_TIRE...@hotmail.COM> wrote in message

news:1180716811.5...@q66g2000hsg.googlegroups.com...

[Alex Kuznetsov]

On Jun 1, 1:18 pm, "Karch" <nos...@absotutely.com> wrote:
> Hmmm...making that change doesn't seem to work with the example below. Query
> still returns RangeID=1 when it should return RangeID=8
>

SELECT TOP 1 RangeID FROM [dbo].[tbl_AllocatedRange] r

WHERE NOT EXISTS(SELECT 1 FROM [dbo].[tbl_AllocatedRange] r1 WHERE

r1.RangeStart BETWEEN r.RangeEnd AND r.RangeEnd + 90 AND r.RangeID <>
r1.RangeID)
ORDER BY [RangeStart]

RangeID
-----------
8

(1 row(s) affected)

[Karch]

The CTE also works great for the ascending values, but has the same problem
as the previous solution if I add this to the data set:

INSERT INTO [dbo].[tbl_AllocatedRange] ([RangeID], [RangeStart], [RangeEnd])

VALUES ( 8, 0, 0 );

And requests an allocation of 1....the CTE query will produce RangeID=1

as the first available when it should produce RangeID=8.

This is important because there may be lower valued ranges inserted later in
time - and therefore have a higher RangeID. So, I can depend on the ranges
increasing along with the identity on RangeID. Basically I need to simply be
looking at the RangeStart and RangeEnd in every existing row and return the
row or RangeID with the lowest RangeEnd that will accomodate the requested
block of a given size.

"Alejandro Mesa" <Alejan...@discussions.microsoft.com> wrote in message
news:4CB9A3CF-35CA-4A43...@microsoft.com...

[Karch]

Perfect! Thanks! Worked like a charm.

"Alex Kuznetsov" <AK_TIRE...@hotmail.COM> wrote in message

news:1180722405.8...@q66g2000hsg.googlegroups.com...

[--CELKO--]

Let's add some constraints and reduce those BIGINTs to just INTEGER
unless you really need it.

CREATE TABLE AllocatedRanges
(range_id INTEGER NOT NULL PRIMARY KEY,
range_start INTEGER NOT NULL
CHECK (range_start >= 0),
range_end INTEGER NOT NULL
CHECK (range_end >= 0),
CHECK (range_start <= range_end));

This will get you all of the candidates, but in RDBMS, there is no
concept of an ordering so talking about the "first avaialble" range
needs more definition.

SELECT range_id, (range_end - range_start)+1 AS range_size, @my_size
AS my_size
FROM AllocatedRanges
WHERE (range_end - range_start)+1 >= @my_size;

We can do it with the lowest range id:

SELECT MIN(range_id)
FROM AllocatedRanges
WHERE (range_end - range_start)+1 >= @my_size;

But the usual requirement is to find the best fit, not the first
one.

SELECT range_id
FROM AllocatedRanges
WHERE (range_end - range_start)+1 =
(SELECT MIN((range_end - range_start)+1 - @my_size)
FROM AllocatedRanges AS A1
WHERE ((range_end - range_start)+1 - @my_size) >= 0);

[Alex Kuznetsov]

On Jun 1, 2:45 pm, --CELKO-- <jcelko...@earthlink.net> wrote:
> Let's add some constraints and reduce those BIGINTs to just INTEGER
> unless you really need it.
>
> CREATE TABLE AllocatedRanges
> (range_id INTEGER NOT NULL PRIMARY KEY,
> range_start INTEGER NOT NULL
> CHECK (range_start >= 0),
> range_end INTEGER NOT NULL
> CHECK (range_end >= 0),
> CHECK (range_start <= range_end));
>

yep it makes sence. Also we can use RI to make sure these intervals do
not overlap.

>
> But the usual requirement is to find the best fit, not the first
> one.
>

I am not following. I think it depends. Suppose these intervals are
appointments at the dentist office. Suppose I need a 60 minute
appointment ASAP. Suppose for me the earliest fit is the best. In my
real life experience such priorities are quite common. What are your
real life scenarios when the best fit is better than the earliest?