MongoDB's query optimizer actually works like this, which is only tractable because it doesn't support joins.
Although, in practice, most tables would only have a relatively small number of columns upon which you'd want to consider building an index (usually on columns (often IDs) that you'd use to join to other tables), so that'd cut it down to O(m!) where m < n, and for larger tables, m << n.
<thinking out loud> Hmmmm, I wonder if you could use frequency information--or even the proportion of distinct values--of columns to guess a bit more intelligently... </thinking out loud>
This is actually pretty much how a basic relational query optimizer works in practice.
