How to Find First Valid Row in SQL Based on Difference of Column Values

Question

I am trying to find a reliable query which returns the first instance of an acceptable insert range.

Research:

• some of the below links adress similar questions, but I could get none of them to work for me.
• Find first available date, given a date range in SQL
• Find closest date in SQL Server
• MySQL difference between two rows of a SELECT Statement
• How to find a gap in range in SQL
• and more...

Objective Query Function:

• InsertRange(1) = (StartRange(i) - EndRange(i-1)) > NewValue

Where InsertRange(1) is the value the query should return. In other words, this would be the first instance where the above condition is satisfied.

Table Structure:

• Primary Key: StartRange
• StartRange(i-1) < StartRange(i)
• StartRange(i-1) + EndRange(i-1) < StartRange(i)

Example Dataset

Below is an example User table (3 columns), with a set range distribution. StartRanges are always ordered in a strictly ascending way, UserID are arbitrary strings, only the sequences of StartRange and EndRange matters:

StartRange  EndRange    UserID
312         6896        user0
7134        16268       user1
16877       22451       user2
23137       25142       user3
25955       28272       user4
28313       35172       user5
35593       38007       user6
38319       38495       user7
38565       45200       user8
46136       48007       user9

My current Query

I am trying to use this query at the moment:

SELECT t2.StartRange, t2.EndRange 
FROM user AS t1, user AS t2 
WHERE (t1.StartRange - t2.StartRange+1) > NewValue 
ORDER BY t1.EndRange 
LIMIT 1

Example Case

Given the table, if NewValue = 800, then the returned answer should be 23137. This means, the first available slot would be between user3 and user4 (with an actual slot size = 813):

InsertRange(1) = (StartRange(i) - EndRange(i-1)) > NewValue
InsertRange    = (StartRange(6) - EndRange(5))   > NewValue
   23137       =    25955       -     25142      >   800

More Comments

• My query above seemed to be working for the special case where StartRanges where tightly packed (i.e. StartRange(i) = StartRange(i-1) + EndRange(i-1) + 1). This no longer works with a less tightly packed set of StartRanges

Answer 1

Keep in mind that SQL tables have no implicit row order. It seems fair to order your table by StartRange value, though.

We can start to solve this by writing a query to obtain each row paired with the row preceding it. In MySQL, it's hard to do this beautifully because it lacks the row numbering function.

This works (http://sqlfiddle.com/#!9/4437c0/7/0). It may have nasty performance because it generates O(n^2) intermediate rows. There's no row for user0; it can't be paired with any preceding row because there is none.

   select MAX(a.StartRange) SA, MAX(a.EndRange) EA, 
          b.StartRange SB, b.EndRange EB , b.UserID
     from user a
     join user b ON a.EndRange <= b.StartRange
    group by b.StartRange, b.EndRange, b.UserID

Then, you can use that as a subquery, and apply your conditions, which are

1. gap >= 800
2. first matching row (lowest StartRange value) ORDER BY SB
3. just one LIMIT 1

Here's the query (http://sqlfiddle.com/#!9/4437c0/11/0)

SELECT SB-EA Gap, 
       EA+1 Beginning_of_gap, SB-1 Ending_of_gap, 
       UserId UserID_after_gap
  FROM (
       select MAX(a.StartRange) SA, MAX(a.EndRange) EA, 
              b.StartRange SB, b.EndRange EB , b.UserID
         from user a
         join user b ON a.EndRange <= b.StartRange
        group by b.StartRange, b.EndRange, b.UserID
        ) pairs
  WHERE SB-EA >= 800
  ORDER BY SB
  LIMIT 1

Notice that you may actually want the smallest matching gap instead of the first matching gap. That's called best fit, rather than first fit. To get that you use ORDER BY SB-EA instead.

Edit: There is another way to use MySQL to join adjacent rows, that doesn't have the O(n^2) performance issue. It involves employing user variables to simulate a row_number() function. The query involved is a hairball (that's a technical term). It's described in the third alternative of the answer to this question. How do I pair rows together in MYSQL?