Even Amazon's music search sucks. It can never find the song unless you provide an accurate name. Its fuzzy matching sucks too, doesn't even account for regional trend in songs.
Apple's music search sucks too, especially if your music tastes are even slightly outside the mainstream. It simply doesn't personalize per user, so when I search, I have to wade through a list of unfamiliar band and musician names until I type almost the whole thing. For a company whose motto once upon a time was "design is how it works", this is inexcusable.