SQL - many-to-many table primary key
SqlPrimary KeyMany to-ManySql Problem Overview
This question comes up after reading a comment in this question:
https://stackoverflow.com/questions/2190089/database-design/2190101
When you create a many-to-many table, should you create a composite primary key on the two foreign key columns, or create a auto-increment surrogate "ID" primary key, and just put indexes on your two FK columns (and maybe a unique constraint)? What are the implications on performance for inserting new records/re-indexing in each case?
Basically, this:
PartDevice
----------
PartID (PK/FK)
DeviceID (PK/FK)
vs. this:
PartDevice
----------
ID (PK/auto-increment)
PartID (FK)
DeviceID (FK)
The commenter says:
> making the two IDs the PK means the > table is physically sorted on the disk > in that order. So if we insert > (Part1/Device1), (Part1/Device2), > (Part2/Device3), then (Part 1/Device3) > the database will have to break the > table apart and insert the last one > between entries 2 and 3. For many > records, this becomes very problematic > as it involves shuffling hundreds, > thousands, or millions of records > every time one is added. By contrast, > an autoincrementing PK allows the new > records to be tacked on to the end.
The reason I'm asking is because I've always been inclined to do the composite primary key with no surrogate auto-increment column, but I'm not sure if the surrogate key is actually more performant.
Sql Solutions
Solution 1 - Sql
With a simple two-column many-to-many mapping, I see no real advantage to having a surrogate key. Having a primary key on (col1,col2) is guaranteed unique (assuming your col1 and col2 values in the referenced tables are unique) and a separate index on (col2,col1) will catch those cases where the opposite order would execute faster. The surrogate is a waste of space.
You won't need indexes on the individual columns since the table should only ever be used to join the two referenced tables together.
That comment you refer to in the question is not worth the electrons it uses, in my opinion. It sounds like the author thinks the table is stored in an array rather than an extremely high performance balanced multi-way tree structure.
For a start, it's never necessary to store or get at the table sorted, just the index. And the index won't be stored sequentially, it'll be stored in an efficient manner to be able to be retrieved quickly.
In addition, the vast majority of database tables are read far more often than written. That makes anything you do on the select side far more relevant than anything on the insert side.
Solution 2 - Sql
No surrogate key is needed for link tables.
One PK on (col1, col2) and another unique index on (col2, col1) is all you need
Unless you use an ORM that can't cope and dictates your DB design for you...
Edit: I answered the same here: SQL: Do you need an auto-incremental primary key for Many-Many tables?
Solution 3 - Sql
An incremental primary key could be needed if the table is referenced. There might be details in the many-to-many table which needed to be pulled up from another table using the incremental primary key.
for example
PartDevice
----------
ID (PK/auto-increment)
PartID (FK)
DeviceID (FK)
Other Details
It's easy to pull the 'Other Details' using PartDevice.ID as the FK. Thus the use of incremental primary key is needed.
Solution 4 - Sql
The shortest and most direct way I can answer your question is to say that there will be a performance impact if the two tables you are linking don't have sequential primary keys. As you stated/quoted, the index for the link table will either become fragmented, or the DBMS will work harder to insert records if the link table does not have its own sequential primary key. This is the reason most people put a sequentially incrementing primary key on link tables.
Solution 5 - Sql
So it seems like if the ONLY job is to link the two tables, the best PK would be the dual-column PK.
But if it serves other purposes then add another NDX as a PK with a foreign keys and a second unique index.
Index or PK is the best way to make sure there are no duplicates. PK lets tools like Microsoft Management Studio do some of the work (creating views) for you