Какой индекс построить для часто выполняемой выборки профилей мужчин старше 35 лет? Почему порядок полей важен и поможет ли индекс только по gender?

Для выборки пользователей по полу (gender) или возрасту (age) оптимально создать два отдельных индекса, так как запросы могут фильтровать по одному из этих полей независимо:

CREATE INDEX idx_users_gender ON users(gender);
CREATE INDEX idx_users_age ON users(age);

Если же часто встречаются запросы с фильтрацией по обоим полям одновременно, можно добавить составной индекс:

CREATE INDEX idx_users_gender_age ON users(gender, age);

Но для выборки по одному полю составной индекс будет менее эффективен, чем отдельные индексы. Поэтому в большинстве случаев лучше использовать два отдельных индекса.