Question 1:
When we execute a query, does the execution plan change for each and every time when executing the query?
If yes, any performance hit?
If no, then if we change something in the table, i.e adding an index, how does the databse know that there is something it can use to change the execution plan for faster execution?
QUestion 2:
But what is the general order of execution while executing a join query, especially if there are lot of joins ( outer, inner , natural , if many outer).
(Assuming SQL Server here, you didn't specify...)
Execution plans are cached, and to the degree you parameterize your queries, can be reused.
When you modify the underlying table or indexes, SQL Server knows the modification date of these things vs. the cached execution plan, and can re-evaluate the query for the new conditions. Same thing when statistics are updated... sometimes the actual data drives the plan, not just the table/index design.
Joins are not done in an order based on inner vs outer, but rather based on what the optimizer thinks will result in the query being executed most quickly. The details will vary between databases. But basically, the query optimizer tries to optimize the use of indexes.
Suppose you had this query:
select a.foo, b.bar
from a
join b on b.b_id=a.b_id
where a.some_number=42;
Now suppose that you have a unique index on b.b_id but no index on a.some_number.
The query optimizer then has two choices: It could do a full-file sequential read on b, and then for each b do a full-file sequential read on a looking for a match on b_id and some_number=42. That is read a^b records. Or it could do a full-file sequential read on a looking for some_number=42, then for each a it could use the index to quickly find the record from b with matching b_id. That is, read a*2 records. Well obviously the second plan is much better, so that's what it will choose.
As you add more tables the calculation becomes more complicated, but the principle is the same. Joins that result in a quick index read using values found in other tables will be done later, after the other tables have been read. Tables that must be read sequentially no matter what, or where the read is based on constants rather than values from other records, are generally read first.
You have at most two plans in cache (one parallel, one non-parallel). Then the plan is used with an Execution Context per user. More info in my answer here
SQL is declarative. This means you tell the engine what you want and the optimiser works out the best plan (within reason, it might take 2 weeks to work out the best one). This is why you can rewrite queries many different ways to get the same answer.
Like any rules about RDBMS, there are exceptions. For complex queries, the optimiser will not go through every permutation so the JOIN order can matter: it depends when the optimiser decides it's had enough...