Otimização de

Banco de Dados

Plano Lógico de Consultas

Módulo 2
Plano Lógico de Consultas
Plano Lógico de Consultas
Introdução ao Plano Lógico de Consultas

O Plano Lógico de Consultas é uma representação da consulta SQL em

termos de operações da Álgebra Relacional. Ele descreve a sequência
de operações lógicas necessárias para produzir o resultado da consulta,
independentemente de como essas operações serão fisicamente
executadas. É a fase onde a consulta é transformada em uma árvore de
operações relacionais, antes que os detalhes de implementação (como o
uso de índices ou algoritmos de junção específicos) sejam decididos.
Plano Lógico de Consultas
Avaliando operadores relacionais

No plano lógico, cada nó da árvore representa um operador relacional. A avaliação desses operadores
no nível lógico foca na transformação e redução dos dados, sem se preocupar com os custos de I/O ou
CPU ainda.

Seleção (σ) Projeção (π)

Filtra linhas de uma relação que satisfazem uma condição.
Seleciona um subconjunto de colunas de uma relação. Reduz o
Reduz o número de linhas e deve ser aplicada o mais cedo
número de colunas e o volume de dados transportados.
possível.

Junção (⋈) Agregação (G) e Agrupamento

Agrupa tuplas com base em colunas e aplica funções
Combina linhas de duas ou mais relações. A ordem das
agregadas. Reduz o número de linhas para o número de
junções é criticamente importante no plano lógico.
grupos únicos.
Renomear (ρ)
Renomeia campos e tabelas para uso nas consultas.
Plano Lógico de Consultas
Avaliando operadores relacionais

Seleção (σ)
Função Impacto Lógico
Filtra linhas de uma relação (tabela) que satisfazem Reduz o número de linhas. Idealmente, deve ser
uma condição específica. aplicada o mais cedo possível na árvore lógica.

Exemplo: Na consulta SQL: SELECT * FROM Produtos WHERE categoria = 'Eletrônicos'

Álgebra Relacional: σ categoria = 'Eletrônicos' (Produtos)
 Plano Lógico de Consultas
Avaliando operadores relacionais

Função
Projeção (π)
Seleciona um subconjunto de colunas de uma relação, descartando as colunas não especificadas.

Impacto Lógico
Reduz o número de colunas. Idealmente aplicada cedo no plano para evitar o transporte de dados desnecessários.

Exemplo:
Na consulta SQL:
SELECT nome_produto, preco
FROM Produtos

Expressão em Álgebra Relacional:

πnome_produto, preco (Produtos)
 Plano Lógico de Consultas
Avaliando operadores relacionais

Junção (⋈)

Função:
Combina linhas de duas
ou mais relações com
base em uma condição de
junção.

Impacto
Lógico: Inner Join Left/Right Join
Pode aumentar ou diminuir Retorna apenas os registros que têm correspondência Retorna todos os registros da tabela esquerda/direita e
o número de linhas, em ambas as tabelas. É o tipo de junção mais comum. os registros correspondentes da outra tabela.
dependendo do tipo de
junção e da cardinalidade
das relações.
Full Outer Join Cross Join
Exemplo: Retorna todos os registros quando há uma Retorna o produto cartesiano das duas tabelas (todas
Clientes JOIN Pedidos ON correspondência em qualquer uma das tabelas. as combinações possíveis).
[Link] =
Pedidos.id_cliente.
 Plano Lógico de Consultas
Avaliando operadores relacionais

Agregação (G) e Agrupamento (GROUP BY) Ordenação (ORDER BY)

Função: Agrupa tuplas com base em uma ou mais colunas e aplica Função e Impacto Lógico
funções agregadas (SUM, AVG, COUNT, etc.) aos grupos. Ordena o conjunto de resultados por uma ou mais
colunas.
Impacto Lógico: Reduz o número de linhas para o número de
grupos únicos, mas pode exigir processamento intensivo. Não altera o número de linhas ou colunas, mas impõe
uma ordem.
SELECT categoria, COUNT(*) No plano lógico, o otimizador tenta evitar a ordenação
FROM Produtos se uma ordem já pode ser inferida de outras operações
GROUP BY categoria (como um índice).

Funções de Agregação Comuns:

COUNT(): Conta o número de linhas Exemplo: Na consulta
SUM(): Soma os valores de uma coluna SELECT nome_produto, preco
AVG(): Calcula a média dos valores FROM Produtos
MIN()/MAX(): Encontra o valor mínimo/máximo ORDER BY preco DESC
STDDEV(): Calcula o desvio padrão
A ordenação é aplicada após a projeção, organizando os resultados
em ordem decrescente de preço.
Plano Lógico de Consultas
Avaliando operadores relacionais

Operadores de Conjunto
Os operadores de conjunto combinam resultados de múltiplas consultas com base em regras de teoria dos conjuntos. Eles podem ser
custosos se os conjuntos forem grandes ou se exigirem remoção de duplicatas.

União (∪) Interseção (∩) Diferença (−)

Combina os resultados de duas consultas, Retorna apenas os registros que Retorna os registros da primeira
removendo duplicatas. As consultas devem aparecem em ambos os resultados das consulta que não aparecem na
ter esquemas compatíveis (mesmo número consultas. As consultas devem ter segunda. As consultas devem ter
e tipo de colunas). esquemas compatíveis. esquemas compatíveis.
 Plano Lógico de Consultas
Avaliando operadores relacionais
Princípios de Avaliação Lógica
O otimizador de consultas
aplica regras de transformação
e heurísticas ao plano lógico
para otimizá-lo antes de
considerar os detalhes físicos.
Estas transformações são
baseadas em propriedades
algébricas e estatísticas das
operações.

"Pushing down" seleções Combinar projeções

Mover operações de seleção para o mais próximo possível das Se várias projeções ocorrerem em sequência, elas podem ser
tabelas base para filtrar dados cedo e reduzir o volume de dados combinadas em uma única operação de projeção,
processados nas operações subsequentes. eliminando operações redundantes.

Reordenar junções Predicate pushdown e pullup

Encontrar a melhor ordem para unir tabelas, geralmente Mover predicados (condições) para cima ou para baixo na
priorizando junções que produzem resultados intermediários árvore de consulta para otimizar a execução, dependendo da
menores para minimizar o custo total. seletividade e do custo de avaliação.
Plano Lógico de Consultas
Avaliando operadores relacionais
Álgebra Relacional
É uma linguagem formal que descreve as operações básicas para manipular conjuntos de dados (relações). Ela
fornece a base teórica para a linguagem SQL e é fundamental para entender como o otimizador de consultas
funciona.
Os operadores da álgebra relacional podem ser divididos em duas categorias principais:

σ Seleção (Selection) π Projeção (Projection)

Filtra tuplas de uma relação com base em uma condição. Seleciona um subconjunto de atributos de uma relação.

⋈ Junção (Join) ∪ União (Union)

Combina tuplas de duas relações com base em uma condição. Combina tuplas de duas relações compatíveis.

− Diferença (Difference) × Produto Cartesiano (Cartesian Product)

Retorna tuplas que estão na primeira relação, mas não na Combina cada tupla da primeira relação com cada tupla
segunda. da segunda.
Plano Lógico de Consultas
Avaliando operadores relacionais

Exemplo! Tabelas de Referência

Considerando as seguintes relações (tabelas) para os exemplos de álgebra relacional:

Clientes Pedidos

id_cliente nome cidade email id_pedido id_cliente data valor

1 Ana Silva Cuiabá ana@[Link] 101 1 2023-01-15 R$ 150,00

2 Bruno Costa São Paulo bruno@[Link] 102 3 2023-01-20 R$ 85,50

Rio de
3 Carla Mendes carla@[Link] 103 2 2023-02-05 R$ 220,00
Janeiro
4 Daniel Santos Cuiabá daniel@[Link] 104 1 2023-02-10 R$ 75,00

5 Elena Oliveira Belo Horizonte elena@[Link] 105 5 2023-02-15 R$ 320,00

Estas tabelas serão utilizadas nos próximos slides para demonstrar os diferentes operadores da
álgebra relacional e como eles transformam os dados.
Plano Lógico de Consultas
Avaliando operadores relacionais

Exemplo 1: Seleção (σ)

Vamos selecionar todos os clientes que moram em Cuiabá:

Expressão em Álgebra Relacional: σ cidade = 'Cuiabá' (Clientes)

Tabela Original: Clientes Resultado da Seleção

id_cliente nome cidade email id_cliente nome cidade email

1 Ana Silva Cuiabá ana@[Link] 1 Ana Silva Cuiabá ana@[Link]

2 Bruno Costa São Paulo bruno@[Link] 4 Daniel Santos Cuiabá daniel@[Link]

3 Carla Mendes Rio de Janeiro carla@[Link]

Explicação:
4 Daniel Santos Cuiabá daniel@[Link]
O operador de seleção (σ) filtra as tuplas que
5 Elena Oliveira Belo Horizonte elena@[Link] satisfazem a condição especificada
Neste caso, apenas os clientes com cidade = 'Cuiabá'
são retornados
Equivalente em SQL:
O esquema (colunas) permanece o mesmo, apenas
SELECT * FROM Clientes WHERE cidade = 'Cuiabá'
as linhas são filtradas
Plano Lógico de Consultas
Avaliando operadores relacionais

Exemplo 2: Projeção (π)

A projeçãoseleciona um subconjunto de colunas de uma relação, descartando as colunas não especificadas.
Tabela Original: Clientes
Consulta SQL:
SELECT nome, cidade FROM Clientes; id_cliente nome cidade email

1 Ana Silva Cuiabá ana@[Link]

π nome, cidade (Clientes)
2 Bruno Costa São Paulo bruno@[Link]
Resultado da Projeção 3 Carla Mendes Rio de Janeiro carla@[Link]

nome cidade 4 Daniel Santos Cuiabá daniel@[Link]

Ana Silva Cuiabá 5 Elena Oliveira Belo Horizonte elena@[Link]

Bruno Costa São Paulo

Carla Mendes Rio de Janeiro
Daniel Santos Cuiabá
Elena Oliveira Belo Horizonte
Plano Lógico de Consultas
Avaliando operadores relacionais
Exemplo 3: Junção Natural (⋈)
A junção natural combina duas relações com base em atributos de mesmo nome. Vamos combinar as
tabelas Clientes e Pedidos
: com base no atributo comum id_cliente
SQL: SELECT * FROM Clientes NATURAL JOIN Pedidos
Álgebra Relacional: Clientes ⋈ Pedidos

Resultado da Junção:
id_cliente nome cidade id_pedido data valor
1 Ana Silva Cuiabá 101 2023-01-15 R$ 150,00
1 Ana Silva Cuiabá 104 2023-02-10 R$ 75,00
2 Bruno Costa São Paulo 103 2023-02-05 R$ 220,00
Plano Lógico de Consultas
Avaliando operadores relacionais

Exemplo 4: União (∪)

A união combina os resultados de duas consultas, removendo duplicatas. As consultas devem ter esquemas
compatíveis (mesmo número e tipo de colunas).

SQL: (SELECT nome FROM Clientes) UNION (SELECT nome FROM Fornecedores)

Álgebra Relacional: π nome (Clientes) ∪ π nome (Fornecedores)

Resultado da União Observações

nome A união remove duplicatas automaticamente

Ana Silva Para manter duplicatas, use UNION ALL em SQL
Bruno Costa As colunas devem ser compatíveis em tipo
Carla Mendes A ordem das colunas deve ser a mesma
Daniel Santos O nome das colunas vem da primeira consulta
Elena Oliveira
Fábio Martins
Gabriela Lima
Henrique Alves
Plano Lógico de Consultas
Avaliando operadores relacionais

Exemplo 5: Diferença (-)

A operação de diferença retorna os elementos que estão no primeiro conjunto, mas não estão no segundo conjunto.
Problema: Encontrar clientes que não fizeram nenhum pedido.
SQL: SELECT id_cliente, nome FROM Clientes WHERE id_cliente NOT IN (SELECT id_cliente FROM Pedidos)
Álgebra Relacional: π id_cliente, nome (Clientes)
- π id_cliente, nome (Clientes ⋈ Pedidos)

Resultado da Operação de Diferença

id_cliente nome
4 Daniel Santos

O resultado mostra o cliente Daniel Santos (id_cliente = 4), que

está na tabela Clientes mas não fez nenhum pedido.
Plano Lógico de Consultas
Otimizador de Consulta Relacional

O otimizador de consulta é o componente do SGBD responsável por transformar uma consulta

SQL em um plano de execução eficiente. Ele utiliza a álgebra relacional como base para
representar e transformar consultas.

Características do Otimizador Baseado em Custo

O otimizador moderno utiliza estatísticas e modelos de custo para avaliar diferentes planos de
execução e escolher o mais eficiente.

Transformações Algébricas: Estatísticas:

Aplica regras de equivalência da álgebra Utiliza informações sobre tabelas, índices e
relacional para gerar planos alternativos. distribuição de dados para estimar custos.
Modelos de Custo: Espaço de Busca:
Estima o custo de cada operação em Explora múltiplas alternativas de planos de
termos de I/O, CPU e memória. execução para encontrar o mais eficiente.
Plano Lógico de Consultas
Otimizador de Consulta Relacional

Como Funciona o Otimizador

O otimizador de consulta trabalha em três etapas principais para transformar uma consulta SQL em
um plano de execução eficiente:

1 2 3

Geração de Alternativas Estimativa de Custo Seleção do Melhor Plano

Aplica regras de transformação Utiliza estatísticas da base de dados Compara custos estimados
algébrica dos planos
Calcula custo de I/O, CPU e memória
Gera planos de execução alternativos Seleciona o plano de menor custo
Considera seletividade de predicados
Considera diferentes ordens de junção Considera restrições de recursos
Estima tamanho dos resultados
Avalia uso de índices disponíveis Gera o plano de execução final
intermediários
Plano Lógico de Consultas
Paralelismo de Consultas
O paralelismo de consultas é uma técnica avançada de otimização que divide o processamento de uma consulta
em múltiplas tarefas executadas simultaneamente, aproveitando sistemas com múltiplos processadores ou
clusters de servidores.

Tipos de Paralelismo em
Bancos de Dados
O paralelismo pode ser
implementado em
diferentes níveis do
sistema de banco de
dados:

Paralelismo Intraoperação: Divide uma única operação (como Paralelismo Interoperação: Executa diferentes operações de
junção ou varredura) em subtarefas paralelas. uma consulta simultaneamente (pipeline).

Paralelismo Interconsulta: Executa múltiplas consultas Paralelismo Distribuído: Distribui o processamento entre
independentes em paralelo. múltiplos nós em um cluster ou sistema distribuído.
Plano Lógico de Consultas
Paralelismo de Consultas
O paralelismo de consultas divide o processamento em múltiplas unidades de trabalho que podem ser
executadas simultaneamente, reduzindo significativamente o tempo de resposta para consultas complexas.

1 Fragmentação
A consulta é dividida em fragmentos menores que podem ser processados independentemente. Isso pode envolver
particionar tabelas por linhas (horizontal) ou colunas (vertical).

2 Distribuição
Os fragmentos são distribuídos entre múltiplos processadores, núcleos ou nós de um cluster. Cada unidade de
processamento trabalha em sua parte da consulta simultaneamente.

3 Execução Paralela
Cada fragmento é processado independentemente, aproveitando os recursos de hardware disponíveis. Operações
como varreduras de tabela, junções e agregações são executadas em paralelo.

4 Agregação de Resultados
Os resultados parciais de cada fragmento são combinados para formar o resultado final da consulta. Esta etapa
pode envolver operações como união, mesclagem ou agregação de conjuntos de
resultados.
Plano Lógico de Consultas
Paralelismo de Consultas
Operações Comumente Paralelizáveis
As seguintes operações em bancos de dados podem ser eficientemente paralelizadas para melhorar
o desempenho:
Seleção (σ) e Projeção (π) Agregação (GROUP BY)
Operações de filtragem e projeção são altamente Funções de agregação como COUNT, SUM, AVG podem ser
paralelizáveis, pois podem ser aplicadas calculadas em paralelo para diferentes grupos e depois
independentemente a diferentes partições dos dados. combinadas.

Junção (⋈) Operações de Conjunto

Junções podem ser paralelizadas através de técnicas como União (∪), Interseção (∩) e Diferença (-) podem ser
hash partitioning, onde os dados são distribuídos entre nós paralelizadas aplicando as operações em partições
com base em funções hash aplicadas às colunas de junção. correspondentes dos conjuntos.

Ordenação (ORDER BY) Varredura de Tabela

Algoritmos como merge sort paralelo permitem A leitura de grandes tabelas pode ser dividida entre múltiplos
que diferentes partes dos dados sejam ordenadas processos, cada um lendo uma parte diferente da tabela.
simultaneamente e depois mescladas.
Plano Lógico de Consultas
Paralelismo de Consultas

Desafios e Considerações do Paralelismo

Embora o paralelismo ofereça ganhos significativos de desempenho, sua implementação eficaz
enfrenta diversos desafios:
Sobrecarga de Comunicação Sincronização e Concorrência
A troca de dados entre nós paralelos pode introduzir Gerenciar o acesso concorrente aos dados compartilhados
latência significativa, especialmente em sistemas pode exigir mecanismos de bloqueio que reduzem o
distribuídos com comunicação de rede. paralelismo efetivo.

Balanceamento de Carga Complexidade de Implementação

Distribuir o trabalho uniformemente entre os nós é crucial Desenvolver e manter sistemas de banco de dados
para evitar que alguns processadores fiquem ociosos paralelos é significativamente mais complexo do que
enquanto outros estão sobrecarregados. sistemas seriais, exigindo algoritmos especializados e
técnicas de otimização.
Dependências de Dados
Custo-Benefício
Algumas operações têm dependências inerentes que O investimento em hardware adicional e software
limitam o grau de paralelismo possível. Por exemplo, especializado para paralelismo deve ser justificado pelos
algumas etapas podem precisar aguardar os resultados ganhos de desempenho obtidos.
de etapas anteriores.
 Referências
Date, C. J. An Introduction to Database Systems. 8th ed. Addison-Wesley, 2003.
Ramakrishnan, Raghu; Gehrke, Johannes. Database Management Systems. 3rd ed. McGraw-Hill
Education, 2002.
Garcia-Molina, Hector; Ullman, Jeffrey D.; Widom, Jennifer. Database Systems: The Complete Book.
2nd ed. Pearson Prentice Hall, 2009.
Celko, Joe. Joe Celko's SQL Performance Tuning. 4th ed. Morgan Kaufmann, 2010.
Shasha, Dennis. Database Tuning: Principles, Experiments, and Best Practices. Morgan Kaufmann,
2002.
Saraswathi, S. Database Management Systems: Concepts, Techniques & Applications. PHI Learning,
2018.
Kyte, Tom; Harrison, Darl. Expert Oracle Database Architecture: Oracle Database 11g Internals and
Performance Tuning. 2nd ed. Apress, 2010.
Fim da Aula