What is the optimal indexing strategy for a relation table?

Question

A relation table is the common solution to representing a many-to-many (m:n) relationship.

In the simplest form, it combines foreign keys referencing the two relating tables to a new composite primary key:

A        AtoB     B
----     ----     ----
*id      *Aid     *id
data     *Bid     data

How should it be indexed to provide optimal performance in every JOIN situation?

1. clustered index over (Aid ASC, Bid ASC) (this is mandatory anyway, I guess)
2. option #1 plus an additional index over (Bid ASC, Aid ASC)
3. or option #1 plus an additional index over (Bid ASC)
4. any other options? Vendor-specific stuff, maybe?

Answer 1

I made some tests, and here is the update:

To cover all possible cases, you'll need to have:

CLUSTERED INDEX (a, b)
INDEX (b)

This will cover all JOIN sutiations AND ORDER BY

Note that an index on B is actually sorted on (B, A) since it references clustered rows.

As long as your a and b tables have PRIMARY KEY's on id's, you don't need to create additional indexes to handle ORDER BY ASC, DESC.

See the entry in my blog for more details:

• Indexing a link table