I would suggest an approach where both criteria have to be met to make it into the list of results. Try to keep the goal that the user is trying to reach in mind. If they are searching for shoes by brand A in size 9 they probably are not interested in shoes by brand B in size 9 or shoes by brand A in other sizes than 9.
If that leaves you with too little results you might want to offer a second category of results (or suggestions) with items close to the specified criteria
Say the selected brand & size return less than x results then you could add a heading below them "Results close to your search" and display results by other brands. This approach would probably increase the development efforts but might be worth the effort.