全部の組み合わせの複合インデックスなんて必ずしも使われないだろ。
単一カラムインデックスだけだと選択性が悪い使用頻度が高い組み合わせに複合インデックスを追加していけばいいんでは。
あと、もしDWHみたいに各部分キーのカラムのカーディナリティが低いならビットマップインデックスを検討してみるとか。