The same general rules are going to apply to this as they would to any other set of indexes. You're talking about having 1-16 different criteria for searching the table. There's no short answer for how to index that. You could try 16 different indexes and hope that index intersection supports what you need (although, that assumes that all 16 columns are good candidates for having a useful index, if the data is not selective the index will be a waste of time). That's unlikely to work very well. Instead, you can try to identify the most commonly combined columns in the sixteen and then create compound indexes based on the appropriate key values. The thing is, there's no way to tell you what to index without a more thorough understanding of the query patterns. Also, you need to consider the clustered index. That should usually be on the most common access path to the data because the clustered index defines data storage.

Just a question, why denormalize the storage? Is performance slow if you just do the JOIN operations?