mysql two column primary key with auto-increment

if you are using myisam

http://dev.mysql.com/doc/refman/5.0/en/example-auto-increment.html

For MyISAM and BDB 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.

CREATE TABLE animals (
    grp ENUM('fish','mammal','bird') NOT NULL,
    id MEDIUMINT NOT NULL AUTO_INCREMENT,
    name CHAR(30) NOT NULL,
    PRIMARY KEY (grp,id)
) ENGINE=MyISAM;

INSERT INTO animals (grp,name) VALUES
    ('mammal','dog'),('mammal','cat'),
    ('bird','penguin'),('fish','lax'),('mammal','whale'),
    ('bird','ostrich');

SELECT * FROM animals ORDER BY grp,id;

Which returns:

+--------+----+---------+
| grp    | id | name    |
+--------+----+---------+
| fish   |  1 | lax     |
| mammal |  1 | dog     |
| mammal |  2 | cat     |
| mammal |  3 | whale   |
| bird   |  1 | penguin |
| bird   |  2 | ostrich |
+--------+----+---------+

For your example:

mysql> CREATE TABLE mytable (
    ->     table_id MEDIUMINT NOT NULL AUTO_INCREMENT,
    ->     database_id MEDIUMINT NOT NULL,
    ->     other_column CHAR(30) NOT NULL,
    ->     PRIMARY KEY (database_id,table_id)
    -> ) ENGINE=MyISAM;
Query OK, 0 rows affected (0.03 sec)

mysql> INSERT INTO mytable (database_id, other_column) VALUES
    ->     (1,'Foo'),(1,'Bar'),(2,'Baz'),(1,'Bam'),(2,'Zam'),(3,'Zoo');
Query OK, 6 rows affected (0.00 sec)
Records: 6  Duplicates: 0  Warnings: 0

mysql> SELECT * FROM mytable ORDER BY database_id,table_id;
+----------+-------------+--------------+
| table_id | database_id | other_column |
+----------+-------------+--------------+
|        1 |           1 | Foo          |
|        2 |           1 | Bar          |
|        3 |           1 | Bam          |
|        1 |           2 | Baz          |
|        2 |           2 | Zam          |
|        1 |           3 | Zoo          |
+----------+-------------+--------------+
6 rows in set (0.00 sec)

Here's one approach when using innodb which will also be very performant due to the clustered composite index - only available with innodb...

http://dev.mysql.com/doc/refman/5.0/en/innodb-index-types.html

drop table if exists db;
create table db
(
db_id smallint unsigned not null auto_increment primary key,
next_table_id int unsigned not null default 0
)engine=innodb;

drop table if exists tables;
create table tables
(
db_id smallint unsigned not null,
table_id int unsigned not null default 0,
primary key (db_id, table_id) -- composite clustered index
)engine=innodb;

delimiter #

create trigger tables_before_ins_trig before insert on tables
for each row
begin
declare v_id int unsigned default 0;

  select next_table_id + 1 into v_id from db where db_id = new.db_id;
  set new.table_id = v_id;
  update db set next_table_id = v_id where db_id = new.db_id;
end#

delimiter ;


insert into db (next_table_id) values (null),(null),(null);

insert into tables (db_id) values (1),(1),(2),(1),(3),(2);

select * from db;
select * from tables;

you can make the two column primary key unique and the auto-increment key primary.