Some sort of “different auto-increment indexes” per a primary key values

I have got a table which has an id (primary key with auto increment), uid (key refering to users id for example) and something else which for my question won’t matter.

I want to make, lets call it, different auto-increment keys on id for each uid entry.

So, I will add an entry with uid 10, and the id field for this entry will have a 1 because there were no previous entries with a value of 10 in uid. I will add a new one with uid 4 and its id will be 3 because I there were already two entried with uid 4.

...Very obvious explanation, but I am trying to be as explainative an clear as I can to demonstrate the idea... clearly.

1. What SQL engine can provide such a functionality natively? (non Microsoft/Oracle based)
2. If there is none, how could I best replicate it? Triggers perhaps?
3. Does this functionality have a more suitable name?
4. In case you know about a non SQL database engine providing such a functioality, name it anyway, I am curious.

Thanks.

MySQL's MyISAM engine can do this. See their manual, in section Using AUTO_INCREMENT:

For MyISAM tables you can specify AUTO_INCREMENT on a secondary column in a multiple-column index. In this case, the generated value for the AUTO_INCREMENT column is calculated as MAX(auto_increment_column) + 1 WHERE prefix=given-prefix. This is useful when you want to put data into ordered groups.

The docs go on after that paragraph, showing an example.

The InnoDB engine in MySQL does not support this feature, which is unfortunate because it's better to use InnoDB in almost all cases. I avoid using MyISAM.

You can't emulate this behavior using triggers (or any SQL statements limited to transaction scope) without locking tables on INSERT. Consider this sequence of actions:

1. Mario starts transaction and inserts a new row for user 4.
2. Bill starts transaction and inserts a new row for user 4.
3. Mario's session fires a trigger to computes MAX(id)+1 for user 4. You get 3.
4. Bill's session fires a trigger to compute MAX(id). I get 3.
5. Bill's session finishes his INSERT and commits.
6. Mario's session tries to finish his INSERT, but the row with (userid=4, id=3) now exists, so Mario gets a primary key conflict.

In general, you can't control the order of execution of these steps without some kind of synchronization.

The solutions to this are either:

• Get an exclusive table lock. Before trying an INSERT, lock the table. This is necessary to prevent concurrent INSERTs from creating a race condition like in the example above. It's necessary to lock the whole table, since you're trying to restrict INSERT there's no specific row to lock (if you were trying to govern access to a given row with UPDATE, you could lock just the specific row). But locking the table causes access to the table to become serial, which limits your throughput.

• Do it outside transaction scope. Generate the id number in a way that won't be hidden from two concurrent transactions. By the way, this is what AUTO_INCREMENT does. Two concurrent sessions will each get a unique id value, regardless of their order of execution or order of commit. But tracking the last generated id per userid requires access to the database, or a duplicate data store. For example, a memcached key per userid, which can be incremented atomically.

It's relatively easy to ensure that inserts get unique values. But it's hard to ensure they will get consecutive ordinal values. Also consider:

• What happens if you INSERT in a transaction but then roll back? You've allocated id value 3 in that transaction, and then I allocated value 4, so if you roll back and I commit, now there's a gap.
• What happens if an INSERT fails because of other constraints on the table (e.g. another column is NOT NULL)? You could get gaps this way too.
• If you ever DELETE a row, do you need to renumber all the following rows for the same userid? What does that do to your memcached entries if you use that solution?