mysql clave primaria de dos columnas con incremento automático

Para las tablas MyISAM y BDB, puede especificar AUTO_INCREMENT en una columna secundaria en un índice de varias columnas. En este caso, el valor generado para la columnaAUTO_INCREMENT se calcula como MAX(auto_increment_column) + 1 WHEREprefix=prefijo dado. Esto es útil cuando desea colocar datos en grupos ordenados.

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 |
+--------+----+---------+

Para tu ejemplo:

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)