Have you tried Scalyr? I am an employee at Scalyr and been in the infra space for quite a while. I think our logging product is the best I've used personally. Searches are actually fast.
Speed hasn't really been an issue with any of the providers I've tried except Loggly which has a very slow UI if you run into big messages. Even with ingesting 200gb of logs a day at one job, per environment, Sumo wasn't slow that I recall.
Of course, we didn't try to negotiate, but it looks more expensive than Sumo. At one company we were spending around $600k a year on it, and it looks like you would cost closer to 1m.
Not to be rude, but jumping into comment sections about your competitor's S1 and replying to comments praising them looks pretty bad.
If I can't have grep, I'll probably always beg for SumoLogic. It's great, at least compared to what I've used so far.