How do I find a "gap" in running counter with SQL?

Question

I'd like to find the first "gap" in a counter column in an SQL table. For example, if there are values 1,2,4 and 5 I'd like to find out 3.

I can of course get the values in order and go through it manually, but I'd like to know if there would be a way to do it in SQL.

In addition, it should be quite standard SQL, working with different DBMSes.

Answer 1

Finding the lowest unused number after zero (so starting with 1), tested in sqlite but should work in mariadb/mysql also:

SELECT  bicyclenumber + 1
FROM    bicycles outertable
WHERE   NOT EXISTS (
        SELECT NULL
        FROM   bicycles innertable
        WHERE  innertable.bicyclenumber = outertable.bicyclenumber + 1
          AND  innertable.owner = 321
        )
  AND outertable.owner = 321
UNION
SELECT 1 AS bicyclenumber
WHERE NOT EXISTS (
    SELECT NULL
    FROM   bicycles
    WHERE  bicyclenumber = 1 AND owner = 321
)
ORDER BY bicyclenumber
LIMIT 1

This works to give every user their own set of numbers that will track an individual bicycle. When a bicycle row is deleted, the gap will be reused, also when the first bicycle is deleted (in contrast to the top answer, which will not work when there is no data yet and be ever-increasing unless the first entry is never removed).

Usage

You can place this between () to make it a subquery and use it in an insert like so:

INSERT INTO bicycles (owner, bicyclenumber, name) VALUES(321, (...), 'Quicksilver')

Where ... is replaced with the giant query above. I need it in two different queries so made the subquery a PHP variable, though that feels quite ugly (better solutions are welcome).

Customisations

• If you do not need to have it per-user, just remove any part that says AND owner = 321
• If you want to start at 0 or a different number, replace SELECT 1 and WHERE filternumber = 1 with the desired number

Answer 2

try this one:

create table #numbers ( id int,num int );

insert into #numbers values (1,1),(2,2),  (3,4),(4,5),(5,5),(6,6),(7,10),  (8,15);

 select 
    d1.id start_gap_id,
    d2.id end_gap_id,
    d1.num start_gap_num,
    d2.num end_gap_num,
    d2.num - d1.num - 1 gap  from #numbers d1
join #numbers d2 on d1.id + 1 = d2.id
where (d2.num - d1.num - 1) > 0
    
drop table #numbers

Answer 3

In MySQL and PostgreSQL:

SELECT  id + 1
FROM    mytable mo
WHERE   NOT EXISTS
        (
        SELECT  NULL
        FROM    mytable mi 
        WHERE   mi.id = mo.id + 1
        )
ORDER BY
        id
LIMIT 1

In SQL Server:

SELECT  TOP 1
        id + 1
FROM    mytable mo
WHERE   NOT EXISTS
        (
        SELECT  NULL
        FROM    mytable mi 
        WHERE   mi.id = mo.id + 1
        )
ORDER BY
        id

In Oracle:

SELECT  *
FROM    (
        SELECT  id + 1 AS gap
        FROM    mytable mo
        WHERE   NOT EXISTS
                (
                SELECT  NULL
                FROM    mytable mi 
                WHERE   mi.id = mo.id + 1
                )
        ORDER BY
                id
        )
WHERE   rownum = 1

ANSI (works everywhere, least efficient):

SELECT  MIN(id) + 1
FROM    mytable mo
WHERE   NOT EXISTS
        (
        SELECT  NULL
        FROM    mytable mi 
        WHERE   mi.id = mo.id + 1
        )

Systems supporting sliding window functions:

SELECT  -- TOP 1
        -- Uncomment above for SQL Server 2012+
        previd + 1
FROM    (
        SELECT  id,
                LAG(id) OVER (ORDER BY id) previd
        FROM    mytable
        ) q
WHERE   previd <> id - 1
ORDER BY
        id
-- LIMIT 1
-- Uncomment above for PostgreSQL

Answer 4

SELECT ID+1 FROM table WHERE ID+1 NOT IN (SELECT ID FROM table) ORDER BY 1;

Answer 5

The first thing that came into my head. Not sure if it's a good idea to go this way at all, but should work. Suppose the table is t and the column is c:

SELECT 
    t1.c + 1 AS gap 
FROM t as t1 
LEFT OUTER JOIN t as t2 ON (t1.c + 1 = t2.c)
WHERE t2.c IS NULL 
ORDER BY gap ASC 
LIMIT 1

Edit: This one may be a tick faster (and shorter!):

SELECT 
    min(t1.c) + 1 AS gap 
FROM t as t1 
LEFT OUTER JOIN t as t2 ON (t1.c + 1 = t2.c) 
WHERE t2.c IS NULL

Answer 6

Here is an alternative to show the range of all possible gap values in portable and more compact way :

Assume your table schema looks like this :

> SELECT id FROM your_table;
+-----+
| id  |
+-----+
|  90 |
| 103 |
| 104 |
| 118 |
| 119 |
| 120 |
| 121 |
| 161 |
| 162 |
| 163 |
| 185 |
+-----+

To fetch the ranges of all possible gap values, you have the following query :

• The subquery lists pairs of ids, each of which has the lowerbound column being smaller than upperbound column, then use GROUP BY and MIN(m2.id) to reduce number of useless records.
• The outer query further removes the records where lowerbound is exactly upperbound - 1
• My query doesn't (explicitly) output the 2 records (YOUR_MIN_ID_VALUE, 89) and (186, YOUR_MAX_ID_VALUE) at both ends, that implicitly means any number in both of the ranges hasn't been used in your_table so far.

> SELECT  m3.lowerbound + 1, m3.upperbound - 1 FROM
  (
    SELECT m1.id as lowerbound, MIN(m2.id) as upperbound FROM
    your_table m1 INNER JOIN your_table
    AS m2 ON m1.id < m2.id GROUP BY m1.id
  )
  m3 WHERE m3.lowerbound < m3.upperbound - 1;

+-------------------+-------------------+
| m3.lowerbound + 1 | m3.upperbound - 1 |
+-------------------+-------------------+
|                91 |               102 |
|               105 |               117 |
|               122 |               160 |
|               164 |               184 |
+-------------------+-------------------+

Answer 7

If the numbers in the column are positive integers (starting from 1) then here is how to solve it easily. (assuming ID is your column name)

    SELECT TEMP.ID 
    FROM (SELECT ROW_NUMBER() OVER () AS NUM FROM 'TABLE-NAME') AS TEMP 
    WHERE ID NOT IN (SELECT ID FROM 'TABLE-NAME')
    ORDER BY 1 ASC LIMIT 1

Answer 8

DECLARE @Table AS TABLE(
[Value] int
)

INSERT INTO @Table ([Value])
VALUES
 (1),(2),(4),(5),(6),(10),(20),(21),(22),(50),(51),(52),(53),(54),(55)
 --Gaps
 --Start    End     Size
 --3        3       1
 --7        9       3
 --11       19      9
 --23       49      27


SELECT [startTable].[Value]+1 [Start]
     ,[EndTable].[Value]-1 [End]
     ,([EndTable].[Value]-1) - ([startTable].[Value]) Size 
 FROM 
    (
SELECT [Value]
    ,ROW_NUMBER() OVER(PARTITION BY 1 ORDER BY [Value]) Record
FROM @Table
)AS startTable
JOIN 
(
SELECT [Value]
,ROW_NUMBER() OVER(PARTITION BY 1 ORDER BY [Value]) Record
FROM @Table
)AS EndTable
ON [EndTable].Record = [startTable].Record+1
WHERE [startTable].[Value]+1 <>[EndTable].[Value]

Answer 9

I wrote up a quick way of doing it. Not sure this is the most efficient, but gets the job done. Note that it does not tell you the gap, but tells you the id before and after the gap (keep in mind the gap could be multiple values, so for example 1,2,4,7,11 etc)

I'm using sqlite as an example

If this is your table structure

create table sequential(id int not null, name varchar(10) null);

and these are your rows

id|name
1|one
2|two
4|four
5|five
9|nine

The query is

select a.* from sequential a left join sequential b on a.id = b.id + 1 where b.id is null and a.id <> (select min(id) from sequential)
union
select a.* from sequential a left join sequential b on a.id = b.id - 1 where b.id is null and a.id <> (select max(id) from sequential);

https://gist.github.com/wkimeria/7787ffe84d1c54216f1b320996b17b7e

Answer 10

If your counter is starting from 1 and you want to generate first number of sequence (1) when empty, here is the corrected piece of code from first answer valid for Oracle:

SELECT
  NVL(MIN(id + 1),1) AS gap
FROM
  mytable mo  
WHERE 1=1
  AND NOT EXISTS
      (
       SELECT  NULL
       FROM    mytable mi 
       WHERE   mi.id = mo.id + 1
      )
  AND EXISTS
     (
       SELECT  NULL
       FROM    mytable mi 
       WHERE   mi.id = 1
     )  

Answer 11

The following solution:

• provides test data;
• an inner query that produces other gaps; and
• it works in SQL Server 2012.

Numbers the ordered rows sequentially in the "with" clause and then reuses the result twice with an inner join on the row number, but offset by 1 so as to compare the row before with the row after, looking for IDs with a gap greater than 1. More than asked for but more widely applicable.

create table #ID ( id integer );

insert into #ID values (1),(2),    (4),(5),(6),(7),(8),    (12),(13),(14),(15);

with Source as (
    select
         row_number()over ( order by A.id ) as seq
        ,A.id                               as id
    from #ID as A WITH(NOLOCK)
)
Select top 1 gap_start from (
    Select 
         (J.id+1) as gap_start
        ,(K.id-1) as gap_end
    from       Source as J
    inner join Source as K
    on (J.seq+1) = K.seq
    where (J.id - (K.id-1)) <> 0
) as G

The inner query produces:

gap_start   gap_end

3           3

9           11

The outer query produces:

gap_start

3

Answer 12

Found most of approaches run very, very slow in mysql. Here is my solution for mysql < 8.0. Tested on 1M records with a gap near the end ~ 1sec to finish. Not sure if it fits other SQL flavours.

SELECT cardNumber - 1
FROM
    (SELECT @row_number := 0) as t,
    (
        SELECT (@row_number:=@row_number+1), cardNumber, cardNumber-@row_number AS diff
        FROM cards
        ORDER BY cardNumber
    ) as x
WHERE diff >= 1
LIMIT 0,1

I assume that sequence starts from `1`.

Answer 13

            -- PUT THE TABLE NAME AND COLUMN NAME BELOW
            -- IN MY EXAMPLE, THE TABLE NAME IS = SHOW_GAPS AND COLUMN NAME IS = ID

            -- PUT THESE TWO VALUES AND EXECUTE THE QUERY

            DECLARE @TABLE_NAME VARCHAR(100) = 'SHOW_GAPS'
            DECLARE @COLUMN_NAME VARCHAR(100) = 'ID'


            DECLARE @SQL VARCHAR(MAX)
            SET @SQL = 
            'SELECT  TOP 1
                    '+@COLUMN_NAME+' + 1
            FROM    '+@TABLE_NAME+' mo
            WHERE   NOT EXISTS
                    (
                    SELECT  NULL
                    FROM    '+@TABLE_NAME+' mi 
                    WHERE   mi.'+@COLUMN_NAME+' = mo.'+@COLUMN_NAME+' + 1
                    )
            ORDER BY
                    '+@COLUMN_NAME

            -- SELECT @SQL

            DECLARE @MISSING_ID TABLE (ID INT)

            INSERT INTO @MISSING_ID
            EXEC (@SQL)

            --select * from @MISSING_ID

            declare @var_for_cursor int
            DECLARE @LOW INT
            DECLARE @HIGH INT
            DECLARE @FINAL_RANGE TABLE (LOWER_MISSING_RANGE INT, HIGHER_MISSING_RANGE INT)
            DECLARE IdentityGapCursor CURSOR FOR   
            select * from @MISSING_ID
            ORDER BY 1;  

            open IdentityGapCursor

            fetch next from IdentityGapCursor
            into @var_for_cursor

            WHILE @@FETCH_STATUS = 0  
            BEGIN
            SET @SQL = '
            DECLARE @LOW INT
            SELECT @LOW = MAX('+@COLUMN_NAME+') + 1 FROM '+@TABLE_NAME
                    +' WHERE '+@COLUMN_NAME+' < ' + cast( @var_for_cursor as VARCHAR(MAX))

            SET @SQL = @sql + '
            DECLARE @HIGH INT
            SELECT @HIGH = MIN('+@COLUMN_NAME+') - 1 FROM '+@TABLE_NAME
                    +' WHERE '+@COLUMN_NAME+' > ' + cast( @var_for_cursor as VARCHAR(MAX))

            SET @SQL = @sql + 'SELECT @LOW,@HIGH'

            INSERT INTO @FINAL_RANGE
             EXEC( @SQL)
            fetch next from IdentityGapCursor
            into @var_for_cursor
            END

            CLOSE IdentityGapCursor;  
            DEALLOCATE IdentityGapCursor;  

            SELECT ROW_NUMBER() OVER(ORDER BY LOWER_MISSING_RANGE) AS 'Gap Number',* FROM @FINAL_RANGE

Answer 14

If You use Firebird 3 this is most elegant and simple:

select RowID
  from (
    select `ID_Column`, Row_Number() over(order by `ID_Column`) as RowID
      from `Your_Table`
        order by `ID_Column`)
    where `ID_Column` <> RowID
    rows 1

Answer 15

It works for empty tables or with negatives values as well. Just tested in SQL Server 2012

 select min(n) from (
select  case when lead(i,1,0) over(order by i)>i+1 then i+1 else null end n from MyTable) w

Answer 16

Here is standard a SQL solution that runs on all database servers with no change:

select min(counter + 1) FIRST_GAP
    from my_table a
    where not exists (select 'x' from my_table b where b.counter = a.counter + 1)
        and a.counter <> (select max(c.counter) from my_table c);

See in action for;

• PL/SQL via Oracle's livesql,
• MySQL via sqlfiddle,
• PostgreSQL via sqlfiddle
• MS Sql via sqlfiddle

Answer 17

For PostgreSQL

An example that makes use of recursive query.

This might be useful if you want to find a gap in a specific range (it will work even if the table is empty, whereas the other examples will not)

WITH    
    RECURSIVE a(id) AS (VALUES (1) UNION ALL SELECT id + 1 FROM a WHERE id < 100), -- range 1..100  
    b AS (SELECT id FROM my_table) -- your table ID list    
SELECT a.id -- find numbers from the range that do not exist in main table
FROM a
LEFT JOIN b ON b.id = a.id
WHERE b.id IS NULL
-- LIMIT 1 -- uncomment if only the first value is needed

Answer 18

select min([ColumnName]) from [TableName]
where [ColumnName]-1 not in (select [ColumnName] from [TableName])
and [ColumnName] <> (select min([ColumnName]) from [TableName])

Answer 19

This one accounts for everything mentioned so far. It includes 0 as a starting point, which it will default to if no values exist as well. I also added the appropriate locations for the other parts of a multi-value key. This has only been tested on SQL Server.

select
    MIN(ID)
from (
    select
        0 ID
    union all
    select
        [YourIdColumn]+1
    from
        [YourTable]
    where
        --Filter the rest of your key--
    ) foo
left join
    [YourTable]
    on [YourIdColumn]=ID
    and --Filter the rest of your key--
where
    [YourIdColumn] is null

Answer 20

Your answers all work fine if you have a first value id = 1, otherwise this gap will not be detected. For instance if your table id values are 3,4,5, your queries will return 6.

I did something like this

SELECT MIN(ID+1) FROM (
    SELECT 0 AS ID UNION ALL 
    SELECT  
        MIN(ID + 1)
    FROM    
        TableX) AS T1
WHERE
    ID+1 NOT IN (SELECT ID FROM TableX) 

Answer 21

There isn't really an extremely standard SQL way to do this, but with some form of limiting clause you can do

SELECT `table`.`num` + 1
FROM `table`
LEFT JOIN `table` AS `alt`
ON `alt`.`num` = `table`.`num` + 1
WHERE `alt`.`num` IS NULL
LIMIT 1

(MySQL, PostgreSQL)

or

SELECT TOP 1 `num` + 1
FROM `table`
LEFT JOIN `table` AS `alt`
ON `alt`.`num` = `table`.`num` + 1
WHERE `alt`.`num` IS NULL

(SQL Server)

or

SELECT `num` + 1
FROM `table`
LEFT JOIN `table` AS `alt`
ON `alt`.`num` = `table`.`num` + 1
WHERE `alt`.`num` IS NULL
AND ROWNUM = 1

(Oracle)

Answer 22

My guess:

SELECT MIN(p1.field) + 1 as gap
FROM table1 AS p1  
INNER JOIN table1 as p3 ON (p1.field = p3.field + 2)
LEFT OUTER JOIN table1 AS p2 ON (p1.field = p2.field + 1)
WHERE p2.field is null;

Answer 23

Inner join to a view or sequence that has a all possible values.

No table? Make a table. I always keep a dummy table around just for this.

create table artificial_range( 
  id int not null primary key auto_increment, 
  name varchar( 20 ) null ) ;

-- or whatever your database requires for an auto increment column

insert into artificial_range( name ) values ( null )
-- create one row.

insert into artificial_range( name ) select name from artificial_range;
-- you now have two rows

insert into artificial_range( name ) select name from artificial_range;
-- you now have four rows

insert into artificial_range( name ) select name from artificial_range;
-- you now have eight rows

--etc.

insert into artificial_range( name ) select name from artificial_range;
-- you now have 1024 rows, with ids 1-1024

Then,

 select a.id from artificial_range a
 where not exists ( select * from your_table b
 where b.counter = a.id) ;

Answer 24

This works in SQL Server - can't test it in other systems but it seems standard...

SELECT MIN(t1.ID)+1 FROM mytable t1 WHERE NOT EXISTS (SELECT ID FROM mytable WHERE ID = (t1.ID + 1))

You could also add a starting point to the where clause...

SELECT MIN(t1.ID)+1 FROM mytable t1 WHERE NOT EXISTS (SELECT ID FROM mytable WHERE ID = (t1.ID + 1)) AND ID > 2000

So if you had 2000, 2001, 2002, and 2005 where 2003 and 2004 didn't exist, it would return 2003.