Hey there,
I think that his opening is perfectly fine, it is not like he falls behind compared to your mercenary with his spice merchant at the early game, considering he starts trashing coppers earlier. This also allows him to better trash estates and curses with his mercenary. His second witch seems a must buy, because at that point he has not trashed his urchin and he wants to make sure he does so. However the interesting part is the comparison of the decks after turn 8.
You have 14 cards with one more village and he has 13, so let's call the number of cards even for simplification. The number of cards that both of you have that can either remove cards from your deck or add to the opponent is the same. You have 2 mercs and a witch for a total of 5 cards and he has 1 merc 2 witches and a spice merchant. The main difference between both decks is that he has 1 more card that shifts/draws. He has 4 and you have 3. He manages to play 3 of his 4 such cards on turn 9 buying a village and a nobles at turn 9 and 10 which really bring the deck together. This gives him also great turns at turn 11 and 12. By the end of turn 12 the difference in your decks is big.
Your draws seem worse during those turns, but I think he did have a more solid base to start from at turn 9.