Search is incredibly slow
Though it is not the solution, turning off conversations (Menu > View > Conversations) can help.