Why did a query change its execution plan and how to anticipate the change? 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.
The Optimizer takes the parsed representation of SQL statement and Statistics to generate final execution plan with the lowest cost. During this process the Optimizer generates multiple plans and compares them. Execution plans may change as the Optimizer inputs(Parsed SQL Statement and Statistics) get changed.


  Why Execution Plans Change
  
  Execution plans can and do change as the underlying optimizer inputs change.
  EXPLAIN PLAN output shows how the database would run the SQL statement when
  the statement was explained. This plan can differ from the actual execution plan a SQL
  statement uses because of differences in the execution environment and explain plan
  environment.
  The Oracle Documentation clearly states that Execution plans can differ when we change Schemas and have changes in Costs.


If we run the same SQL statement in different database under different Schemas then also the resulting plan can be different. Even the schema and database is same but the Cost of the execution plan is different then also the optimizer can choose different execution plans. Bind variables, size of the data and its statistics, optimizer's parameters may influence the Cost.

Guessing why the Execution plan has been changed is difficult because we don't have the metadata(which are dynamic) of your database on which we have to query for further investigation and its time consuming task.

You can use SQL Tuning Adviser, SQLTXPLAN, SQL Trace etc to make it easier to find the elements affecting the execution plan. 

For details:
Oracle Database SQL Tuning Guide