How do I get first unused ID in the table?

Question

I have to write a query wherein i need to allocate a ID (unique key) for a particular record which is not being used / is not being generated / does not exist in database.

In short, I need to generate an id for a particular record and show it on print screen.

E. g.:

ID  Name

1   abc
2   def
5   ghi

So, the thing is that it should return ID=3 as the next immediate which is not being generated yet, and after this generation of the id, I will store this data back to database table.

It's not an HW: I am doing a project, and I have a requirement where I need to write this query, so I need some help to achieve this.

So please guide me how to make this query, or how to achieve this.

Thanks.

I am not able to add comments,, so thats why i am writing my comments here.. I am using MySQL as the database..

My steps would be like this:-

1) Retrieve the id from the database table which is not being used..

2) As their are no. of users (website based project), so i want no concurrency to happen,, so if one ID is generated to one user, then it should lock the database, until the same user recieves the id and store the record for that id.. After that, the other user can retrieve the ID whichever is not existing.. (Major requirement)..

How can i achive all these things in MySQL,, Also i suppose Quassnoi's answer will be worth,, but its not working in MySQL.. so plz explain the bit about the query as it is new to me.. and will this query work in MySQL..

Answer 1

I named your table unused.

SELECT  id
FROM    (
        SELECT  1 AS id
        ) q1
WHERE   NOT EXISTS
        (
        SELECT  1
        FROM    unused
        WHERE   id = 1
        )
UNION ALL
SELECT  *
FROM    (
        SELECT  id + 1
        FROM    unused t
        WHERE   NOT EXISTS
                (
                SELECT  1
                FROM    unused ti
                WHERE   ti.id = t.id + 1
                )
        ORDER BY
                id
        LIMIT 1
        ) q2
ORDER BY
        id
LIMIT 1

This query consists of two parts.

The first part:

SELECT  *
FROM    (
        SELECT  1 AS id
        ) q
WHERE   NOT EXISTS
        (
        SELECT  1
        FROM    unused
        WHERE   id = 1
        )

selects a 1 is there is no entry in the table with this id.

The second part:

SELECT  *
FROM    (
        SELECT  id + 1
        FROM    unused t
        WHERE   NOT EXISTS
                (
                SELECT  1
                FROM    unused ti
                WHERE   ti.id = t.id + 1
                )
        ORDER BY
                id
        LIMIT 1
        ) q2

selects a first id in the table for which there is no next id.

The resulting query selects the least of these two values.

Answer 2

Depends on what you mean by "next id" and how it's generated.

If you're using a sequence or identity in the database to generate the id, it's possible that the "next id" is not 3 or 4 but 6 in the case you've presented. You have no way of knowing whether or not there were values with id of 3 or 4 that were subsequently deleted. Sequences and identities don't necessarily try to reclaim gaps; once they're gone you don't reuse them.

So the right thing to do is to create a sequence or identity column in your database that's automatically incremented when you do an INSERT, then SELECT the generated value.

Answer 3

Should work under MySql.

SELECT TOP 100
    T1.ID + 1 AS FREE_ID 
FROM TABLE1 T1
LEFT JOIN TABLE2 T2 ON T2.ID = T1.ID + 1
WHERE T2.ID IS NULL

Answer 4

/*
This is a query script I wrote to illustrate my method, and it was created to solve a Real World problem where we have multiple machines at multiple stores creating transfer transactions in their own databases,
that are then synced to other databases on the store (this happens often, so getting the Nth free entry for the Nth machine should work) where the transferid is the PK and then those are synced daily to a MainFrame where the maximum size of the key (which is the TransactionID and StoreID) is limited.  
*/

--- table variable declarations
/* list of used transaction ids (this is just for testing, it will be the view or table you are reading the transaction ids from when implemented)*/

DECLARE @SampleTransferIDSourceTable TABLE(TransferID INT)     

/* Here we insert the used transaction numbers*/

DECLARE @WorkTable TABLE (WorkTableID INT IDENTITY (1,1), TransferID INT) 

/*this is the same table as above with an extra column to help us identify the blocks of unused row numbers (modifying a table variable is not a good idea)*/

DECLARE @WorkTable2 TABLE (WorkTableID INT , TransferID INT, diff int)  

--- Machine ID declared

DECLARE @MachineID INT

-- MachineID set

SET @MachineID = 5

-- put in some rows with different sized blocks of missing rows.
-- comment out the inserts after two to the bottom to see how it handles no gaps or make 
-- the @MachineID very large to do the same.
-- comment out early rows to test how it handles starting gaps.

INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 1 )
INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 2 )
INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 4 )
INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 5 )
INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 6 )
INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 9 )
INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 10 )
INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 20 )
INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 21 )
INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 24 )
INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 25 )
INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 30 )
INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 31 )
INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 33 )
INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 39 )
INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 40 )
INSERT @SampleTransferIDSourceTable ( TransferID ) VALUES ( 50 )

-- copy the transaction ids into a table with an identiy item.
-- When implemented add where clause before the order by to limit to the local StoreID
-- Zero row added so that it will find gaps before the lowest used row.

INSERT @WorkTable (TransferID)

SELECT 0

INSERT @WorkTable (TransferID)

SELECT TransferID FROM @SampleTransferIDSourceTable ORDER BY TransferID   

-- copy that table to the new table with the diff column 

INSERT @WorkTable2

SELECT WorkTableID,TransferID,TransferID - WorkTableID 

  FROM @WorkTable              

--- gives us the (MachineID)th unused ID or the (MachineID)th id beyond the highest id used.

IF EXISTS (

SELECT Top 1

       GapStart.TransferID  + @MachineID - (GapStart.diff + 1)

  FROM @WorkTable2 GapStart

 INNER JOIN @WorkTable2 GapEnd

    ON GapStart.WorkTableID = GapEnd.WorkTableID - 1

   AND GapStart.diff < GapEnd.diff

   AND gapEnd.diff >= (@MachineID - 1)

 ORDER BY GapStart.TransferID

 )

SELECT Top 1

       GapStart.TransferID  + @MachineID - (GapStart.diff + 1)

  FROM @WorkTable2 GapStart

 INNER JOIN @WorkTable2 GapEnd

    ON GapStart.WorkTableID = GapEnd.WorkTableID - 1

   AND GapStart.diff < GapEnd.diff

   AND gapEnd.diff >= (@MachineID - 1)

 ORDER BY GapStart.TransferID

ELSE 

SELECT MAX(TransferID) + @MachineID FROM @SampleTransferIDSourceTable

Answer 5

The correct way is to use an identity column for the primary key. Don't try to look at the rows already inserted, and pick an unused value. The Id column should hold a number large enough that your application will never run out of valid new (higher) values.

In your description , if you are skipping values that you are trying to use later, then you are probably giving some meaning to the values. Please reconsider. You probably should only use this field as a look up (a reference) value from another table.

Let the database engine assign the next higher value for your ID. If you have more than one process running concurrently, you will need to use LAST_INSERT_ID() function to determine the ID that the database generated for your row. You can use LAST_INSERT_ID() function within the same transaction before you commit.

Second best (but not good!) is to use the max value of the index field plus one. You would have to do a table lock to manage the concurrency issues.

Answer 6

are you allowed to have a utility table? if so i would create a table like so:

CREATE TABLE number_helper (
    n INT NOT NULL
   ,PRIMARY KEY(n)
);

Fill it with all positive 32 bit integers (assuming the id you need to generate is a positive 32 bit integer)

Then you can select like so:

SELECT MIN(h.n) as nextID
FROM my_table t
LEFT JOIN number_helper h ON h.n = t.ID
WHERE t.ID IS NULL

Haven't actually tested this but it should work.