This may seem counterintuitive, but Beta Search will be slow at first because it's not getting enough traffic. The web servers spin down if they're not getting requests. The speed in beta is not representative of what you will see once it's in production.