Xin ý kiến về tốc độ với DB lớn?

Hello các bác, Tình hình là em có vài cái db MySQL có cái lên tới 3-40 triệu row. Và tốc độ query của nó là ác mộng của em, server thì em xài gói thấp nhất của Vultr 5$/tháng nên đương nhiên nó yếu. Web thì xài Cloudflare nên cứ trang nào chậm quá timeout của Cloudflare là nó quăng lỗi. Em đã bật slow_query_log rà từng câu query chậm và explain, thêm index và khắc phục nhưng ko cải thiện được mấy. Em cũng có dùng memcache nhưng chỉ có thể cache một số trang, user/bot mà chui vào trang chưa cache thì cũng vẫn đâm đầu vào tường. Em có xem MySQL partition, chia table ra từng partition theo thời gian, tốc độ thì ổn nhưng có những câu query mình cần lấy hết table thì nó lại thành vòng lẩn quẩn :D. Em có nghe nói về tốc độ thần sầu của nosql/mongodb nhưng chưa xài qua nên chưa biết thế nào. Xin các bác cho em lời khuyên ạ.