We have a job using a dynamic query in production for years now and its execution took 5-6 seconds up until our last code deploy. Now the same query takes days to finish. It's a relatively simple nested select that joins 5-6 tables, the largest of which have a few hundred thousand rows (others are mostly small lookup tables).
This same query runs on different database instances very quickly (with much more data and exactly the same codebase).
I'm well aware that tools like explain plan only show predicted execution plan, but the explain plan on this particular instance is very poor (for comparisson, it doesn't use an index which seems to be used on all other instances).
My question is - without changes in query, table structure the query uses or a significant change in the amount of data read, why has the execution plan changed so drastically and how can I anticipate for such a change?
added info The query in question starts with a SELECT DISTINCT... We noticed that on this db instance, if we remove the distinct (which then doesn't necessarily give us the correct results) the execution plan is very similar to the original, much quicker one.
Edit: Satistics were run straight after the last code deploy.