Basically, we have version we're upgrading from, hardware type (Alewife or Davis), and object store type (M or EC). The specifics don't really matter; these just happen to be ours.
So the first thing a tester is going to do is to make up a complete matrix and then start running down the list, right? Err.... let's think about that for a second. We've kept this matrix tight, so it's not too long if we did want to do it all, but that completionism is not the best use of our time.
We have an enterprise product, and one of the side-effects of that is that we know what our customers are running in the field. So let's use that: for a given combination of variables, if no customer is currently or will ever run it, we can skip it. For example, no customer is running 3.3EFS1 on all Davises and we know that no customer would be upgraded to that release while they're running Davises (they would go directly to 4.x), so we don't have to do any testing in that scenario.
Completionism is attractive, but it may not be the most efficient thing to do. Sure, set up your matrix, but think about it as you go through it - don't be a slave to the boxes!