O plano de execução (query execution plan) é uma sequencia de tarefas com o objetivo de analisar, interpretar, compilar e sugerir uma árvore de execução capaz de executar a especificação de uma instrução SQL. Com a analise de um plano de execução, podemos obter detalhes sobre as decisões tomadas pelo SGBD, além de todos os índices utilizados e pontos de otimização. Ele é dividido em algumas etapas:

Query Parser
Nesse ponto é verificado a sintaxe e transformação da instrução em uma árvore de analise, também conhecido como: “parse tree”, uma árvore lógica detalha “o que fazer”.

Algebrizer
Cria uma árvore lógica com base na arvore de analise (parse tree), com as operações lógicas que devem ser realizadas para a execução da instrução.

Resolução de nomes
Verifica a estrutura mencionada.

Vinculação (Binding)
Cria um vinculo das instruções utilizadas com os objetos físicos do banco de dados.

Otimizador (Optimizer)
Utiliza a árvore de analise e metadados coletados sobre colunas, tabelas, indices, constraints, estatísticas e hardware. O optimizer usa essas informações para gerar um plano de execução compilado, indicando ao SQL Server os passos exatos para serem executados. Nesse ponto é detalhado “como fazer”.

Simplificador
Nessa etapa o SQL Server cria uma árvore de saida melhor que uma dada árvore de entrada, como por exemplo: reduzir a quantidade de colunas agrupadas, decidir a ordem com que algumas instruções são executadas, etc.

Exploração
Nessa etapa, deve-se reduzir os custos demandados pela instrução SQL, reduzindo a quantidade de recursos utilizados para execução, desta forma ele realiza testes explorando diversas alternativas para a composição da árvore de execução: Unir tabela1 com tabela2 (em um post em breve devo descrever os tipos de join no plano de execução), por exemplo.

Implementação
Transforma “o que fazer” em “como fazer”, join em hash join (falarei sobre isso depois…)

Fases de busca (Search Phases)
Como o processo de decisão do melhor plano de execução envolve muitos testes, o processo é divido em fases, se uma determinada fase o custo ficar baixo o sulficiente, o optimizer para e devolve o plano de execução atual, do contrário ele passa para a fase seguinte.

Fases de busca > Fase 1
Contem um número limitado de regras aplicados para consultas de até 4 tabelas, só considera hash join e loop join.

Fases de busca > Fase 2
Utiliza mais algumas regras de transformação e diferentes tipos de join, sem utilizar paralelismo (grau 5 de paralelismo, veja no link: http://technet.microsoft.com/pt-br/library/ms188611(v=sql.105).aspx)

Fases de busca > Fase 3
Utiliza todas regras disponiveis, tipos de joins, compara estimativas de execuções em diversos graus de paralelismo e escolhe o menos custoso.

Query Execution
Nesse passo o plano de execução está gerado, e pode ser passado para o storage engine (mecanismo de armazenamento; um dos dois principais componentes do Sql Server: storage engine e query processor), onde a consulta pode ser executada (como assim pode? Ela não vai?!), acredito que na maioria dos casos sim, porem existem 2 fatores que podem influenciar na mudança:
* O plano de execução pode exceder o limite de uma execução em paralelo, com uma execução que está utilizando N processadores.
* As estatisticas para gerar o plano de execução estava fora de data, ou mudou desde de a data de geração do plano atual.

Tentei sei sucinto nesse post, espero que ajudado.