Find first available block that does not intersect a range

SQL Apprentice Question
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.


Celko Answers
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);


Original Source