You don't even need to look at the entire index. See the point where chicken jumps from 15, to 582? We know we can then skip to at least 582 in all the other indexes we're looking at. (Which is doable as the indexes are going to be stored as some sort of tree we can retrieve a particular range out of) This is pretty much a merge join http://en.wikipedia.org/wiki/Sort-merge_join
Incidentally you can make indexes on Ingredient->Page/Cuisine->Page rather than maintaining Page indexes for specific ingredients/cuisines. So with just two indexes you can filter out any Cuisine/Ingredient combo (You can even do multiple ingredients! As it's an intersection though, multiple cuisines wouldn't be useful as few dishes are likely to fall under multiple cuisines, you could still do it though.)
Incidentally you can make indexes on Ingredient->Page/Cuisine->Page rather than maintaining Page indexes for specific ingredients/cuisines. So with just two indexes you can filter out any Cuisine/Ingredient combo (You can even do multiple ingredients! As it's an intersection though, multiple cuisines wouldn't be useful as few dishes are likely to fall under multiple cuisines, you could still do it though.)