coping with long natural string key I have inherited a (quite) big database (for my standards at least, since by no means I call myself a DBA or DB dev).
So, on this DB they used a unique natural string as the primary key on EVERY table. In my novice experience it seems that is slowing joins down.
Just to get some more info on this, our main table is having roughly 1.5 million rows, the key is a taxing office id number, which might have some leading 0s, so they went and declared this as a varchar(12), in order not to loose the leading 0.
One of our secondary table has more than 3 million rows, and an other one with roughly the same number of rows as the main table. Each of these tables (and many more of smaller size) are using the same varchar(12) as a foreign key to the main table mentioned before.  

Questions  


Would it make any difference using an int instead of this varchar as
key? 
If 1=Y then : There are a few applications that are using this
database and they are all using this key for joining tables. Is
there a way to keep the old columns for joining the tables, but get
some advantage using some int column for the key? i.e. can i change the key, but keep the same old queries?


Edit:
One major limitation on changing the queries is that most are not stored procedures. They are hard coded inside the actual applications
INT is 4 bytes.  VARCHAR(12) is a little longer.  I would gladly use either for a PRIMARY KEY without worrying about performance.

A BTree is efficiently structured such that a longer key does not impact performance much.

If you switch that value to INT, perhaps with ZEROFILL, the speed up will be small.

If you add an INT AUTO_INCREMENT, then you are likely to slow down some uses of the table.  For more details, let's see some queries, including inserts and updates.