[dmurray]

You could tell it "you have a budget of X GB for disk space, choose the indexes that best optimize the queries given the budget cap."

Not perfect, because some queries may be more time-critical than others.

You could even annotate every query (INSERT and UPDATE as well as SELECT) with the dollar amount per execution you're willing to pay to make it 100ms faster, or accept to make it 100ms slower. Then let it know the marginal dollar cost of adding index storage, throw this all into a constraint solver and add the indexes which are compatible with your pricing.