CODEWITHSUNDEEP
sqlorm
Pedro Werneck
Pedro Werneck

Reputation: 41898

Finding next gap within values

Suppose I have the following table:

id  name  base   index
0   A     2      0
1   B     2      2
2   C     2      4
3   D     2      6
4   E     2      8
5   F     2      10

So, index = base * i, where i is the position of that row in a sequence.

From time to time, some rows are deleted, for instance, if I delete rows named C and D:

id  name  base   index
0   A     2      0
1   B     2      2
4   E     2      8
5   F     2      10

New rows are always added after the last, so the next row would be MAX(index)+base=12 in this case, but the gap left between values in the index column due to the deleted rows would be a problem after some time. If instead of inserting last I insert it in the first available gap, the problem won't happen.

So, I doubt any queries to find the first available gap would be as efficient as the MAX(index), but what would the most efficient solution be? Maybe it's good enough.

In case it's not clear, I need to find the first row 'a' such that the row with the closest upper index value is more than a.index + a.base.

This is meant for an application using an ORM for any SQL databases, so it has to be strictly standard SQL.

edit

This is a simplification of the real table and the real problem, and I'm looking for a solution using the base and index columns only. Solutions involving adding new columns or indexing in other table are not practical for my application.

edit 2

It seems the base column is making it more complicated, but that isn't essential. The problem can be reduced to a table like:

id  name  index
0   A     0
1   B     1
4   E     4
5   F     5

Where I need to find the first row 'a' such that the row with the lowest index that's higher than a.index + x. In this case x = 1.

Enumerating without ordering first or leveraging on the id aren't reliable solutions, since those can change. For instance, a solution has to work if the rows are like this too:

id  name  index
0   A     0
23  F     5
45  E     4
90  B     1

Upvotes: 1

Views: 157

Answers (4)

Gordon Linoff
Gordon Linoff

Reputation: 1269693

Most SQL dialects support window functions, so you could do something like:

select min(id)
from 
(
   select t.*, 
      row_number() over (order by id) as rownum
   from t
)
where id <> rownum

This returns the first id that is out of sequence.

I might suggest, something similar to the first suggestion. When a row is deleted, store the id in another table of "available" ids. When inserting, look in this table first. If none are available then create a new one.

Upvotes: 0

gcbenison
gcbenison

Reputation: 11963

Well, one way that wouldn't depend on anything beyond standard SQL would be to keep a separate table of "all possible values of index":

SELECT * FROM indices LIMIT 7;
+------+
| idx  |
+------+
|    0 |
|    2 |
|    4 |
|    6 |
|    8 |
|   10 |
|   12 |
+------+
7 rows in set (0.00 sec)

Then let's say your users table looks like this, with the first gap occurring at index=4:

SELECT * FROM users;
+------+------+------+------+
| id   | name | base | idx  |
+------+------+------+------+
|    0 | A    |    2 |    0 |
|    1 | B    |    2 |    2 |
|    4 | E    |    2 |    8 |
|    5 | F    |    2 |   10 |
+------+------+------+------+
4 rows in set (0.00 sec)

You can use a LEFT JOIN with the indices table to find this first gap:

SELECT indices.*
FROM indices
LEFT JOIN users
USING(idx)
WHERE users.idx IS NULL
ORDER BY idx
LIMIT 1;

+------+
| idx  |
+------+
|    4 |
+------+
1 row in set (0.00 sec)

This will fail if the first gap occurs after the end of the indices table, in which case you could detect the error and extend the indices table.

Upvotes: 0

Steve Kass
Steve Kass

Reputation: 7184

It's not clear to me what your question means if there are multiple values of "base" in the table. Does the "row with the closest upper index value" have to have the same value of "base", for example?

In any case, this might be a start, if you are using a SQL platform that implements the function LEAD(). You may have to rephrase TOP in the appropriate dialect. Replace 999999999 with any value greater than the largest possible value of index+base.

with LeadAdded as (
  select 
    lead(index,1,999999999) over (order by index) as nxt,
    *
  from yourTable
)
  select top (1) *
  from LeadAdded
  where nxt > index + base;
  order by index

Upvotes: 1

Glenn
Glenn

Reputation: 9150

Instead of deleting the row, can you add another column to mark it as available? Then you could select the MIN(id) from your table that is marked 'AVAILABLE' with the given base. If not found, then you insert. That way you can avoid having gaps, keep a history, and maybe simplify?

Upvotes: 0

Related Questions