Actual very different than estimated - what to do in the first step!

You run a query / stored procedure, etc. and - bad performance... The you also see that the actual very different than estimated data in the execution plan.

There are 1,000,000 things to think about, 1,000,000 blogs posts about reasons, actions and so on about such a case.

BUT:

First of all, in those scenarios - before all the complicated things:

• Check the logic that behind the query, 
• Check that this logic is implemented in the query,
• Check that the tables order and joins is acording to the DB structure and logic.

See that the query is written as you would expect according to the database and/or the application logic.

After that - in most of the cases - 90% of the work will be done!