This is a solved problem, and it seems the technical folks over there lacked the skills to make it work. Having indexes is just the tip of the iceberg. Composite indexes, partitioning, sharding, caching, etc, can lower reads to a few seconds on disk.