The implemented solution seems to have worked, and response times are back to normal. The incident was caused by an upgrade of the software version of our main database, which unexpectedly behaved slightly differently on planning queries. The solution was to remove an index that "confused" the query planner to select a more "expensive" query in the newer version of the database software. Once identified, the fix was easy, but we struggled to understand what was going on and it took a significant amount of research and experiments to make sure that we understood the problem correctly and that the fix was a proper one. We apologize to everyone affected by the degraded performance for the past 36 hours.