As Remus says it depends on your workload.
I want to address a misleading aspect of the accepted answer though.
For queries that are performing an equality search on all columns in the index there is no significant difference.
The below creates two tables and populates them with identical data. The only difference is that one has the keys ordered from most to least selective and the other the reverse.
CREATE TABLE Table1(MostSelective char(800), SecondMost TINYINT, Least CHAR(1), Filler CHAR(4000) null);
CREATE TABLE Table2(MostSelective char(800), SecondMost TINYINT, Least CHAR(1), Filler CHAR(4000) null);
CREATE NONCLUSTERED INDEX MyINDX on Table1(MostSelective,SecondMost,Least);
CREATE NONCLUSTERED INDEX MyINDX2 on Table2(Least,SecondMost,MostSelective);
INSERT INTO Table1 (MostSelective, SecondMost, Least)
output inserted.* into Table2
SELECT TOP 26 REPLICATE(CHAR(number + 65),800), number/5, '~'
FROM master..spt_values
WHERE type = 'P' AND number >= 0
ORDER BY number;
Now doing a query against both of the tables...
SELECT *
FROM Table1
WHERE MostSelective = REPLICATE('P', 800)
AND SecondMost = 3
AND Least = '~';
SELECT *
FROM Table2
WHERE MostSelective = REPLICATE('P', 800)
AND SecondMost = 3
AND Least = '~';
... Both of them use an index fine and both are given the exact same cost.
The ASCII art in the accepted answer is not in fact how indexes are structured. The index pages for Table1 are represented below (click the image to open in full size).
The index pages contain rows containing the whole key (in this case there is actually an additional key column appended for the row identifier as the index was not declared as unique but that can be disregarded further information about this can be found here).
For the query above SQL Server doesn't care about the selectivity of the columns. It does a binary search of the root page and discovers that the Key (PPP...,3,~ ) is >=(JJJ...,1,~ ) and < (SSS...,3,~ ) so it should read page 1:118. It then does a binary search of the key entries on that page and locates the leaf page to travel down to.
Altering the index in order of selectivity doesn't affect either the expected number of key comparisons from the binary search or the number of pages that need to be navigated to do an index seek. At best it might marginally speed up the key comparison itself.
Sometimes ordering the most selective index first will make sense for other queries in your workload though.
E.g if the workload contains queries of both the following forms.
SELECT * ... WHERE MostSelective = 'P'
SELECT * ...WHERE Least = '~'
The indexes above aren't covering for either of them. MostSelective is selective enough to make a plan with a seek and lookups worthwhile but the query against Least isn't.
However this scenario (non covering index seek on subset of leading column(s) of a composite index) is only one possible class of query that can be helped by an index. If you never actually search by MostSelective on its own or a combination of MostSelective, SecondMost and always search by a combination of all three columns then this theoretical advantage is useless to you.
Conversely queries such as
SELECT MostSelective,
SecondMost,
Least
FROM Table2
WHERE Least = '~'
ORDER BY SecondMost,
MostSelective
Would be helped by having the reverse order of the commonly prescribed one - as it covers the query, can support a seek and returns rows in the desired order to boot.
So this is an often repeated piece of advice but at most it's a heuristic about the potential benefit to other queries - and it is no substitute for actually looking at your workload.
