Ответ
Да.
CREATE NONCLUSTERED INDEX MyInd on users (user_name, user_birth_date);
это не то же самое, чтоCREATE NONCLUSTERED INDEX MyInd on users (user_birth_date, user_name);
При создании составного индекса сначала строится обычный индекс для его первой колонки, а потом уже на основе него строится индекс для второй колонки и так дальше.
Другими словами, колонки, по которым поиск выполняется чаще всего, должны стоять в составном индексе первыми.
@sqlhub