Hole-less Sequence

[chrisrlong]

I've heard the complaint a few times about holes in sequences. I even heard one or twice that people had actual requirements to provide sequential keys *with no holes*. Something just triggered this memory in me brain and it started me thinking...

How can such a thing be accomplished without great pain?

The only solutions I can think of off the top of my head are to single-thread the inserts or actually 'search' for holes to plug. However, I rather suspect that using the second solution would actually defeat the purpose of the original requirement.

So, this only leaves one with single-threading the inserts. By this, I mean creating a table with the 'sequence' counter in it. When doing an insert:
- lock the counter row
- increment the counter
- do the insert
- commit

So the counter can only get incremented if you actually commit, and nobody else can possibly get to and update the counter *until* you commit. You have created an artificial throttle, thereby effectively single-threading the inserts.

Of course, this would be very painful to the concurrency of the database.

But is there any other way to do this?

- Chris

[Zaggy]

I would push it up into the application, if possible. If you cannot, then use a sequence without caching. I think this may help instead of doing a single-threaded approach. These are just some ideas. Create a trigger that inserts the sequence after commit.

[Edited by Zaggy on 04-25-2001 at 08:40 PM]

[chrisrlong]

Thanks for the thoughts, but unfortunately, they don't hold up.

Neither the application nor an after-statement trigger will work for incrementing IDs. This is because *nobody* can see all the un-committed transactions in the database. Therefore, any external process, whether it is from the app, a trigger, or a procedure, will fall victim to the following scenario:

User 1............................User 2
Tries to calc the next ID
......................................Tries to calc the next ID
Searches the table for
the max ID......................Searches the table for the Max ID
Returns 5.........................Returns 5
So, uses 6 and updates/
inserts record....................So, uses 6 and update/inserts
........................................record - Is now blocked by user 1
Commits...........................Duplicate Key Error


Either of these solutions is the same:
- Searching the table for the max(ID), or
- Checking a 'counter' value in a table *without maintaining an exlusive lock until the insert commits*

Both solutions fall victim to multi-user anomolies

As for a cache-less sequence, that is not actually the same as what I specified. In my solution, the lock is obtained before the value is changed (same as sequence), but the lock is not released until the calling process is done with the actual insert and issues a commit. This guarantees that the sequence *cannot* be incremented without a record actually being inserted.

A non-cached sequence will:
- Start an autonomous transaction
- Lock the sequence
- Increment the Value
- Commit the autonomous transaction
- Return the value

So, in this solution, User 1 could get a sequence value and then rollback, never having actually inserted a record, thereby creating a 'hole' in the sequence.

Thanks for the feedback, though.

Any more ideas out there?

- Chris

[Thomasps]

Hi..
Holeless sequences is, I think, difficult to achieve.. But you can simulate it using wiht the help of a table.
create a Table with

seq_no number
status char

Then cache the sequence into a index oraganised table indexed on seq_no. Suppose in the begining cache first 1000 sequence numbers into the table. let the users select the seq_no from the table. Once the users selected the seq_number mark it as selected in the staus. On commit delete the entry from the table. Again create a trigger ON DELETE to cache next 1000 sequences when the ROWCOUNT(*) of the cache table is less than , say 100.

This way you will get a holeless sequence... Wow.. Too much...

Thanks..

[akkerend]

Your solution only works if no rows can be deleted. If rows can be deleted, you get a hole in the sequence column. What is the problem with holes?

[chrisrlong]

First, *every* solution produces holes when rows get deleted, I think this was understood with the original requirements (I'm assuming) - Personally, I have *no* problem with holes . As I said in my original post, I have heard about situations where some requirement existed where some candidate key on the table *had* to be sequential and *could not* have holes (I am assuming that they would further state: "The only time a hole should exist is if a row was deleted", OR "No rows will ever be deleted". But I am making assumptions there, all I *do* know is that I have several times heard of people being *required* to create hole-less sequences, so I was simply wondering what that might entail.

So back to Thomasps:
-------------------------

We can "simulate" it?? - I like that!

While the index-organized and caching aspects are interesting, I don't see how they offer any benefit. How does a transaction know which number to grab next? It must do a SELECT MAX() WHERE status <> 'selected'.

So, user 1 selects the first entry. IF they *do not* commit until after they insert that row, then user 2 waits behind them - this is the single-threaded solution I proposed. IF user 1 commits the counter table right away, then user 2 will grab entry 2. What happens if User 1 then does a rollback? The sequence has been updated but no record was inserted - we now have the hole again. If I'm missing something please tell me.

Another thought:
--------------------
Again, I am not sure when or why such a requirement might exist. So, if anyone has actually had this requirement, please let me know the details...

So therefore, I don't know if this thought would be acceptable, but...

We could:

When the sequence is aquired, add an entry to a table saying that "User X aquired sequence number X". Then, upon insert we could have a trigger to remove that entry. Therefore, if a hole *were* created, we would at least know who or what created it.- just a thought


- Chris

[Zaggy]

I did a data conversion for a website and the new app server required that the primary keys start with zero and have no holes. During the conversion process, we created and managed our numbers at the application level, becuase that was the easiest way. Doing it at the DB level can become a headache. I hope you find a proper solution that suits your needs.

[jmodic]

Chris,

I belive your sollution from your first post is the most straightforward and also the most efficient way of getting hole-less sequence numbers. All other sollutions sooner or later clash at the concurrency isues.

It is also my strong belive that the demand for hole-less sequence numbers is totally artifficial - I'm sure that in very very few cases the one who demands this can also provide an acceptable and argumented explanation why thes feture should be implemented at all.

Here are two quotes regarding this topic from Thomas Kyte, the one who I respect the most (or at least one of them) regarding the Oracle Database issues:

Quotes from Tom Kyte
It is normal for a sequence to have gaps -- you must expect a sequence to have gaps. There is only 1 way to generate a gap free sequence and that is to use a single database table to generate them (and hence you will serialize all operations -- very very slow).
....
I have never found this [gaps] to be a serious issue -- the need for consecutive numbers is always found to be a totally artificial need and when reviewed in light of the performance implications of using a serial, blocking method to get consecutive numbers -- is always dropped as a "requirement".

[chrisrlong]

Agreed. If Tom Kyte said it - I believe it!!

Thanks for all the feedback,

- Chris

[Thomasps]

Hi..

My solution (I know it is not strightforward... But they want it!) creates hole-less sequence. Well let us consider the various situations..

1. Delete a Row: Normally any standard application will never physically delete a row from a table. Only mark as cancelled or invalid. Incase deleteion, is responsile for drop back the seqnence number to the sequence table. SO we can reuse the sequence number. (I never said we will get continuce sequence.. So you can tell me that it is not a sequence.. But there is no holes)
2. User1 gets first unused number, say 101, and user2 gets next number, is 102. Mark two numbers are selected. Suppose the user1 Rolled back and User2 commited. Then mark the 101 as unselected and delete 102...

Where is the hole then?