Sudden drastic change in performance

Hello all,

I have a query with many joins, something like:

Select c1, c2, c3, sum(c5)
From V1
Join V2 on ...
Left join V3 on ...
Left join T4 on ...
Join T5 on ...
Join T6 on ...
Left join T7 on ...
Join T8 on ...
Left join T9 on ...
Where ...
Group by c1, c2, c3

The join clauses are fairly innocuous and work directly on foreign key relationships, so there is no voodoo there. Same for the where clause. The views are similar and also join 3-4 tables each. All in all, there are 3 of all the tables involved that have millions of rows and all the other tables have thousands of rows. In particular, T9 is totally empty.

If I remove T9 from the query, it takes 9s to run. If I keep T9, the query takes over 30mn to run! If I switch the order of T8/T9, then the same happens with T8. So I don't think this has to do with the tables themselves. I have updated all the statistics and reindexed all involved tables.

Any idea as to what could be causing this issue? Am I having one too many joins and tripping the query execution? The query plans are very large in both cases, so I figured I'd abstract the cases a bit for this question, but could provide those plans if someone thinks it'd be useful.

Thank you,
Laurent.