Segurança de Sistemas de

Informações
Prof. Sidney Nicolau Venturi Filho

Execução de Comandos
Segurança de Sistemas de
Informações
Prof. Sidney Nicolau Venturi Filho

Conceitos Básicos
 Processamento de Consultas
• Um SGBD possui um arsenal de métodos para
executar consultas e recuperar dados. Quando uma
consulta SQL é submetida ao SGBD, ele reescreve a
consulta em um formato interno e gera um plano de
execução para a mesma.
• O plano de execução especifica a seqüência de
algoritmos que precisam ser aplicados sobre os
dados para retornar o resultado da consulta que foi
submetida.
• Os métodos de acesso são algoritmos e estruturas
de dados especiais que podemos utilizar para
recuperar dados diretamente a partir das tabelas.
 Otimização e Execução de Consultas
• O sistema gerenciador de bancos de dados chega até o
resultado de uma consulta através de um processo que
segue várias etapas. Neste processo, dois momentos
são fundamentais: a otimização da consulta e a
execução da consulta.
• Com a otimização da consulta, o SGBD reescreve a
consulta em um formato interno e, a partir daí, inicia
uma busca de quais operações básicas podem ser
utilizadas para resolver a solicitação. Quando o SGBD
determina todas as operações básicas que precisam ser
utilizadas e em que ordem elas precisam ser aplicadas,
ele conseguiu gerar um plano de execução.
• De posse do plano de execução, a segunda etapa do
processo é iniciada. O SGBD executa cada uma das
operações especificadas no plano de execução até
chegar a um resultado final. Este resultado é retornado
para quem submeteu a consulta ao SGBD.
Otimização e Execução de Consultas
 Otimização e Execução de Consultas
O processo de submissão de uma consulta segue os seguintes passos
• Análise Sintática: nesta etapa, a sintaxe da consulta é verificada e erros são
apontados. Se a consulta estiver sintaticamente correta, o SGBD a
submeterá à verificação de sua semântica.
• Análise Semântica ou Validação: aqui o SGBD verifica a existência de
tabelas, visões e colunas, bem como realiza verificações de tipos dos
atributos e dados utilizados na consulta.
• Reescrita de consulta: uma vez que a consulta é validada quanto a sua
sintaxe e semântica, o banco de dados reescreve o SQL em uma
representação interna mais simples e/ou mais eficiente (em geral, alguma
representação canônica derivada da álgebra relacional).
• Otimização da consulta: através de um conjunto de regras de
transformação, o SGBD manipula a sua representação interna da consulta
e procura a estratégia de execução considerada mais eficiente.
• Geração de Código: de posse do plano de acesso otimizado, ocorrem as
chamadas ao processador de execução (run time) do SGBD. O código
pode ser
– Interpretado: executado diretamente
– Compilado: armazenado e executado posteriormente quando chamado.
Otimização e Execução de Consultas
Otimização e Execução de Consultas
Otimização e Execução de Consultas
Otimização e Execução de Consultas
Otimização e Execução de Consultas
Otimização e Execução de Consultas
Otimização e Execução de Consultas
Otimização e Execução de Consultas
Segurança de Sistemas de
Informações
Prof. Sidney Nicolau Venturi Filho

Otimizador de Consulta
 Otimizador de consultas
O otimizador de consultas é o coração do SGBD, pois “escolhe” o
plano de acesso mais adequado para executar uma consulta
SQL, em tempo hábil.
Ele recebe um plano lógico de execução e aplica transformações
a fim de gerar um plano ótimo.
• Abordagens clássicas:
– Otimização por regras: Plano de execução é gerado ao se
aplicar heurísticas tidas como eficientes (independente de
estatísticas). Por exemplo, o otimizador poderia sempre
escolher utilizar um índice que esteja disponível sobre uma
coluna.
– Otimização por custo: Determina que plano de execução é
o mais eficiente ao considerar diferentes “caminhos de
acesso” usando as estatísticas sobre os objetos do
esquema (tabelas e índices) acessados pelo comando
SQL (mais eficiente e recomendado)
 Parâmetros de otimização
• Parâmetro de inicialização ou ajustado em tempo de execução
(ALTER SESSION) ⇒ OPTIMIZER_GOAL:
– CHOOSE: O otimizador escolhe entre a técnica baseada em custo e
regra dependendo das estatísticas disponíveis. Se o dicionário contém
estatísticas para ao menos uma das tabelas acessadas, então o
otimizador usa a técnica baseada em custo. Senão, o otimizador usa a
técnica baseada em regra.
– ALL_ROWS: O otimizador usa a técnica baseada em custo
(independente da presença de estatísticas) com o objetivo de obter a
melhor vazão (mínimos recursos usados para processar a consulta).
– FIRST_ROWS: O otimizador usa a técnica baseada em custo
(independente da presença de estatísticas) com o objetivo de obter o
melhor tempo de resposta (mínimos recursos usados para retornar a
primeira linha).
– RULE: O otimizador escolhe a técnica baseada em regra
 Estatísticas
A otimização por custo demanda estatísticas
• Para gerar estatísticas em uma tabela cada SGBD disponibiliza
comandos:
– Oracle e PostgreSQL: analyze;
– DB2: runstats;
– SQLServer: create/update statistics;
• Tipos de estatísticas
– de tabelas: número de linhas, blocos, tamanho de registro médio
– de colunas: número de valores distintos, número de NULLs, histograma de
valores
– de índices: número de folhas, níveis, clustering.
– de sistema: utilização típica de I/O e de CPU.
• A partir destas informações, o SGBD pode estimar o custo envolvido em
acessar a tabela de forma seqüêncial ou através de índices.
• Com estes custos iniciais, o SGBD realiza cálculos para determinar os custos
das operações subseqüentes aplicadas no plano de acesso. Isto leva à
determinação do custo total do plano de acesso.
 Planos de Execução
O plano de execução é o roteiro que o SGBD segue para recuperar as
linhas especificadas pela consulta. Uma série de detalhes sobre como
a consulta deve ser processada é especificada no plano. Em especial,
quais operações serão aplicadas para resolver a consulta e em que
ordem elas serão processadas.
• O que é especificado no plano de execução:
– Ordem de acesso às tabelas
– Ordem de operações de seleção, projeção e junção
– Índices utilizados
– Tipos de junção
– Ordenações
– Tabelas intermediárias
• Existem dois tipos básicos de operação:
– Métodos de acesso (varreduras seqüenciais e indexadas)
– Outras operações (junções, uniões, ordenação, etc...)
Otimização baseada em custo
 Otimização baseada em custo
• Query Transformer: Transforma uma consulta SQL
em uma expressão algébrica.
• Estimator
– Fator de seletividade
– Cardinalidade
– Custo (CPU + E/S + comunicação)
• Plan Generator: Gera um conjunto de planos
equivalentes, porém com custos diferentes
– Ordem de junção
– Ordem dos operadores
– Algoritmos de junção (sort-merge, nested loops, hash
join, etc.)
 Otimização baseada em custo
• Principais caminhos de acesso
– TABLE ACCESS (bom para baixa seletividade)
• FULL SCAN
• BY ROW ID
– INDEX SCAN (bom para baixa seletividade)
• Unique
• Range
• Full
• Hash join
– JOIN
• Nested-Loop
• Sort-Merge
• Hash Join (não disponível em otimização baseada em regra)
• Cluster Join
 Otimização baseada em regra
• Usa praticamente os mesmos caminhos de acesso
da otimização baseada em custo
– Não contém HASH JOIN
• Utiliza heurísticas para gerar os planos de
execução
– Regras de comutatividade e associatividade
• (A U C) JOIN (B U C) ⇒ (A JOIN B) U C
– Junção de seleção ⇒ Seleção de junção
– Seleção e projeção são antecipadas sobre a junção
– Busca por índices são preferidas
– etc.
Segurança de Sistemas de
Informações
Prof. Sidney Nicolau Venturi Filho

Tipos de Varreduras
 Varredura Seqüencial
• Leitura seqüencial de todas as páginas de uma tabela
– Geralmente é a opção feita pelo otimizador quando precisa
selecionar a totalidade das linhas da tabela, não existindo outro
método de acesso adequado ou devido a utilização de alguns
operadores como IS NULL, LIKE, <>, …
– Comumente chamada de full table scan
– SGBDs costumam implementar sequential prefetch (read
ahead)
– Eficiente para consultar todas ou quase todas as linhas de uma
tabela
– rowid Scan: Leitura de um conjunto de registros específicos da
tabela a partir de seus endereços físicos
Varredura Seqüencial
 Varredura Indexada
Leitura dos dados através de um ou mais índices
– Comumente chamada de indexed table scan
– Vários índices possíveis: árvores B+, bitmaps, árvores R,
hashing.
– Eficiente para recuperar subconjunto restrito dos dados
– Índices podem ser "clusterizados" ou "não-clusterizados"
– Ao usar um índice para varrer uma tabela, a recuperação da
linha do resultado tende a ser ordens de grandeza mais
rápida do que através de uma varredura seqüencial.
• Varreduras seqüenciais e indexadas por múltiplos índices
podem ser usadas no mesmo plano, dependendo das
condições de seleção da consulta (cláusula WHERE). Os
resultados das varreduras são combinados.
Varredura Indexada
Varredura Indexada
Varredura Indexada
 Ordenação (Sorting)

• Operação básica para diversas outras

operações físicas
• Resolve a cláusula ORDER BY
• Se o conjunto a ser ordenado não cabe
em memória, esta operação pode ser
muito cara
• Pode ser utilizada em DISTINCT, UNION,
INTERSECTION, JOIN…
 Eliminação de Duplicatas e Agregações
• Estas operações são implementadas
em geral através de uma ordenação
(sorting) para realizar o agrupamento
(GROUP BY)
• Após a ordenação pelo critério de
agregação, o resultado é varrido e a
operação é computada
• Também é possível resolver este tipo
de operação através de técnicas de
hash
 Operações de Conjuntos
UNION e UNION ALL
– UNION ALL: realiza uma operação de
concatenação entre os conjuntos (concatenate)
– UNION: realiza a concatenação (concatenate)
seguida de eliminação de duplicatas (sort ou
hash)
Intersecção e Diferença
– Operações de conjunto semelhantes a eliminação
de duplicatas
– Em geral, são resolvidas com ordenações (sort)
seguidas da operação propriamente dita
– Também é possível utilizar métodos de hash
 Otimização baseada em custo

• Exemplos
SELECT *
FROM EMP
WHERE Name = ‘Jackson’

TABLE ACCESS FULL SCAN

SELECT *
FROM EMP
WHERE Empno = 7369

TABLE ACCESS BY INDEX ROW ID

INDEX UNIQUE SCAN (PK_EMP)
 Otimização baseada em custo

• Exemplos SELECT *
FROM PROJECT
WHERE PNAME LIKE 'Contas%'

TABLE ACCESS BY INDEX ROW ID

INDEX RANGE SCAN (SYS_C01)
SELECT *
FROM PROJECT
WHERE PNAME LIKE ‘%Contas'

TABLE ACCESS FULL SCAN

Segurança de Sistemas de
Informações
Prof. Sidney Nicolau Venturi Filho

Algoritmos de Junção
 Junções
• Os algoritmos clássicos utilizados em junções
são:
– Loops Aninhados (Nested Loops Join)
– Ordenação/Intercalação (Merge Join)
– Hashing (Hash Join)
• Existem outros algoritmos:
– Cluster Join
– Hybrid hash join
– Star join (em esquemas estrela de Data
Warehouses)
– ...
Nested Loops
Nested Loops
Nested Loops
 Nested-Loops

SELECT *
FROM EMP, DEPT
WHERE [Link] = [Link]
 Cluster Join

SELECT *
FROM EMP, DEPT
WHERE [Link] = [Link]
 Merge Join

SELECT *
FROM EMP, DEPT
WHERE [Link] = [Link]
 Hash Join

SELECT *
FROM EMP, DEPT
WHERE [Link] = [Link]
 Como o otimizador escolhe o método de junção ?
Nested-Loops:
É ineficiente quando a junção retorna um
grande número de linhas (> 10000)
• Custo = custo de acesso de A + (custo
de acesso de B * cardinalidade de A)
• Usar Quando:
– Outer table pequena ou filtrada
– Índice clusterizado para acessar inner table
– Poucas páginas da inner table acessadas
 Como o otimizador escolhe o método de junção ?
Merge Join:
Em otimização baseada em regras, Merge Join é o
mais eficiente quando retorna um grande número de
linhas
• Custo = custo de acesso de A + custo de
acesso de B + (custo de ordenação de A +
custo de ordenação de B)
• Usar Quando:
– São acessadas muitas linhas das duas tabelas
– Não existem índices adequados
– Atributos de junção com muitos valores repetidos
 Como o otimizador escolhe o método de junção ?
Hash Join:
É o mais eficiente (custo) quando a junção retorna um
grande número de linhas
• Custo = (custo de acesso de A * número de
partições hash de B) + custo de acesso de B
• Usar Quando:
– Hash table é pequena, cabendo em memória
– Atributo de junção da menor tabela é único
– Não existem índices para a junção
 Como o otimizador escolhe o método de junção ?
Cluster join:
é o mais indicado quando há clustering
(tabelas ou índices)
– Custo de acesso de A
 Otimização baseada em custo

• Exemplos
SELECT W.*
FROM EMPLOYEE E, WORKS_ON W
WHERE [Link] = [Link] AND [Link] > 800

NESTED LOOPS
TABLE ACCESS FULL (WORKS_ON)
TABLE ACESS BY INDEX ROWID
INDEX UNIQUE SCAN (SYS_C01)
 Otimização baseada em custo

• Exemplos
SELECT W.*
FROM WORKS_ON W, EMPLOYEE E
WHERE [Link] = [Link] AND [Link] > 800

NESTED LOOPS
TABLE ACCESS FULL SCAN (EMPLOYEE)
INDEX RANGE SCAN (SYS_C012)
/* – Chave primária de WORKS_ON
Segurança de Sistemas de
Informações
Prof. Sidney Nicolau Venturi Filho

Dicas de Otimização
 Algumas práticas de otimização
• Melhorando o desempenho de consultas
Evite junções longas e pesadas
• Use consultas aninhadas
– Crie índices para atributos freqüentemente
consultados
– Maximizar o uso do índice pelo otimizador
– Substitua um conjunto grande de predicados
por INTERSECT e MINUS
 Quando índices são usados
• Comparar se um atributo é igual a um valor (!= não
leva ao uso do índice)
• Comparar se um atributo pertence a uma faixa de
valores (>, <, LIKE ‘A%’)
– LIKE ‘%A’ ou LIKE ‘%A%’ não usam o índice
• Se funções não são usadas sobre os atributos
(UPPER, SUBSTR, etc.)
– Exceto funções MAX e MIN
• Se não há checagem de IS NULL ou IS NOT NULL
• Se um o primeiro campo de um índice de múltiplas
colunas é comparado em equivalência com um valor
• Se o índice é seletivo
Algumas práticas de otimização
Algumas práticas de otimização
OBRIGADO

FIM