The site is served via AWS CloudFront. It is SPA app hosted on S3. The API is on Heroku. No mem-cache anywhere. To search we use ElasticSearch hosted on AWS. We bump up the specs to speed it up but that was not the core problem.

I suspect Heroku Postgres DB. We didn't used some Hobby version and I think it is the real bottle neck + some unnecessary middleware for the API that also requires DB.

maybe a mem-cache then?

DB's have limited connections and are often billed as such, the mem-cache might help if there are any repeatable things. It might not be useful for your solution though since everyone searches for their own things all the time.

Increasing DB plan did the job.