Most efficient way of getting the next unused id

Question

(related to http://stackoverflow.com/questions/3439571/finding-the-lowest-unused-unique-id-in-a-list and http://stackoverflow.com/questions/2116056/getting-unused-unique-values-on-a-sql-table)

Suppose I have a table containing on id column and some others (they don't make any difference here):

+-----+-----+
| id  |other|
+-----+-----+

The id has numerical increasing value. My goal is to get the lowest unused id and creating that row. So of course for the first time I run it will return 0 and the the row of this row would have been created. After a few executions it will look like this:

+-----+-----+
| id  |other|
+-----+-----+
|  0  | ... |
|  1  | ... |
|  2  | ... |
|  3  | ... |
|  4  | ... |
+-----+-----+

Fairly often some of these rows might get deleted. Let's assume the rows with the id's of 1 and 3 are removed. No the table will look like this:

+-----+-----+
| id  |other|
+-----+-----+
|  0  | ... |
|  2  | ... |
|  4  | ... |
+-----+-----+

If I now run again the query it would like to get back the id 1 and this row should be created:

| id  |other|
+-----+-----+
|  0  | ... |
|  1  | ... |
|  2  | ... |
|  4  | ... |
+-----+-----+

The next times the query runs it should return the id's 3, 5, 6, etc.

What's the most effective way to run those kinds of query as I need to execute them fairly often in a second (it is fair to assume that the the id's are the only purpose of the table)? Is it possible to get the next unused row with one query? Or is it easier and faster by introducing another table which keeps track of the unused id's?

If it is significantly faster it is also possible to get a way to reuse any hole in the table provided that all numbers get reused at some time.

Bonus question: I plan to use SQLite for this kind of storing information as I don't need a database except for storing these id's. Is there any other free (as in speech) server which can do this job significantly faster?

Answer 1

I think I'd create a trigger on delete, and insert the old.id in a separate table. Then you can select min(id) from that table to get the lowest id.

disclaimer: i don't know what database engine you use, so i don't know if triggers are available to you.

Answer 2

Normally you'd let the database handle assigning the ids. Is there a particular reason you need to have the id's sequential rather than unique? Can you, instead, timestamp them, and just number them when you display them? Or make a separate column for the sequential id, and renumber them?

Alternatively, you could not delete the rows themselves, but rather, mark them as deleted with a flag in a column, and then re-use the id's of the marked rows by finding the lowest numbered 'deleted' row, and reusing that id.

Answer 3

The database doesn't care if the values are sequential, only that they are unique. The desire to have your id values sequential is purely cosmetic, and if you are exposing this value to users -- it should not be your primary key, nor should there be any referential integrity based on the value because a client could change the format if desired.

The fastest and safest way to deal with the id value generation is to rely on native functionality that gives you a unique integer value (IE: SQLite's autoincrement). Using triggers only adds overhead, using MAX(id) +1 is extremely risky...

Summary

Ideally, use the native unique integer generator (SQLite/MySQL auto_increment, Oracle/PostgreSQL sequences, SQL Server IDENTITY) for the primary key. If you want a value that is always sequential, add an additional column to store that sequential value & maintain it as necessary. MySQL/SQLite/SQL Server unique integer generation only allows one per column - sequences are more flexible.

Answer 4

Like Dennis Haarbrink said; a trigger on delete and another on insert :

The trigger on delete would take the deleted id and insert it in a id pool table (only one column id)

The trigger on before insert would check if an id value is provided, otherwise it just query the id pool table (ex: SELECT MIN(id) FROM id_pool_table) and assign it (i.g. deletes it from the id_pool_table)