While finding the best selection of indexes is an important task the problem appears highly challenging as (i) indexes mutually affect their impact on performance and (ii) the number of index combinations can be enormous. Current selection approaches have limitations when problems are large and ignore the fact that future workloads are partially stochastic. In this paper, we propose a solver-based approach to find effective index selections for large-scale workloads. Our decomposition concept allows to deal with large candidate sets and makes it possible to address risk-averse problem versions, where multiple potential future workloads are taken into account. We demonstrate the applicability and the effectiveness of our approach for the TPC-DS benchmark workload. Our numerical results show that compared to state-of-the-art LP approaches index selections can be computed orders of magnitudes faster while still obtaining near-optimal performance results.