How to effectively tune a query that does not even finish (SQL Monitoring and ASH in action)

Have you ever been called to tune a query that runs forever?

Even worse, what if the query is very complex, you don't know anything about the "logic" behind the SQL - since it was written by someone else - and when you see the execution plan it is several pages long?
Moreover, what if the query is for retrieving a list of customers for a business critical campaign that has to run asap, and therefore the beloved management is over your shoulder, waiting for you to solve the problem!

Problem Definition

Never ending queries, or at least queries that cannot finish within an acceptable time frame are quite common in large Data Warehouses. Unfortunately, in this situation one cannot use methods where execution statistics are gathered first and then analysis of the execution steps can take place. Simply because the query does not finish!