Hmmmm...

First of all, this highlights the problems with multi-part PKs. IMHO, every table should have an abstracted, single-value numeric PK. This makes multiple things easier including the size and complexity of multi-parent children. If you had this setup, for instance, you would only need a single-field index for every FK, instead of the multiple field indexes you now require.

Unfortunately, you are already down this road, so what else can we do? First of all, the FK index is only a problem if you can delete from the parent (or change the PK value, but since you should never be changing PK values anyway, this shouldn't really be an issue). Hopefully, this would eliminate some of the tables from the equation. However, I'm sure you looked at that and still have an issue with at least some of your tables. So we need a bunch of indexes on, unfortunately, multi-part, overlapping keys. The only thing I can suggest is that you try to make some of them 'out of order'. I haven't tested this yet (I don't have multi-part PKs :) ), so please let me know if it works. For your provided example, you have FKs on:

- Col1, Col2
- Col1, Col2, Col3
- Col1, Col2, Col5

First of all, a single index on Col1, Col2, Col3 will cover both of the first 2 cases, since the first case is a left, leading subset of the second case.
As for the third case, can you possibly make an index on Col5, Col2, Col1 or Col5, Col1, Col2? The multi-part key *as a whole* matches the left-leading part of the index, so it might 'count' in Oracle's eyes, I'm not sure. Let me know if it works. The other advantage would be that if Col5 is also an FK (by itself) , then this index would cover that as well.

Good Luck, and let me know what you

- Chris

(Isn't this a nice little 'feature'? :) )