Cesar2016-10-07 15-34-04824

Prévia do material em texto

FATEC/SO - Faculdade de Tecnologia de Sorocaba 
Departamento de Processamento de Dados 
Curso de Tecnologia em Processamento de Dados 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Processamento e otimização de consultas 
em bancos de dados relacionais 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Apostila elaborada pelo Professor Antonio Cesar de Barros Munari 
 
 
Aspectos físicos do armazenamento de dados 
Aspectos físicos do armazenamento de dados 
A discussão sobre os aspectos físicos do armazenamento de dados encontrada neste 
material utilizará como exemplo em diversas situações o modelo de dados referente a um 
controle bancário simplificado, cuja descrição geral é fornecida a seguir, juntamente com 
o modelo conceitual correspondente e o esquema lógico da base de dados. 
O caso do controle bancário simplificado 
O Banco Popular S/A possui inúmeras agências no interior do estado de São Paulo, 
contando atualmente com um número significativo de clientes. O procedimento para 
abertura de uma conta corrente é bastante rápido e simples, não havendo necessidade de 
se fazer um depósito inicial, já que alguns clientes utilizam a conta apenas para receber os 
seus salários. Como todo banco, existe a possibilidade da abertura de uma conta corrente 
conjunta (no caso de casais, por exemplo). Toda conta corrente está associada a uma 
agência bancária, mas nada impede que um cliente possua contas em agências diferentes, 
se isso for de seu interesse. Os movimentos de cada conta corrente (créditos e débitos) 
são armazenados pelos sistemas informatizados do banco, de maneira a tornar possível a 
emissão dos extratos bancários a que cada cliente tem direito. Além disso devem ser 
consideradas também as seguintes regras de negócio: 
a) Não existem duas contas corrente com o mesmo número, mesmo que em 
agências diferentes; 
b) Todo cliente possui uma senha específica para cada uma de suas contas 
corrente e se a conta for conjunta cada titular possui sua própria senha. 
c) Toda movimentação em conta corrente recebe um número seqüencial; 
d) O sistema deve permitir saber a data em que uma conta corrente foi aberta; 
e) Toda agência possui, além de um código, também um nome; que é utilizado 
em alguns documentos internos do banco. 
Modelos e níveis de abstração em um banco de dados 
Uma descrição como a apresentada para o funcionamento do controle das contas corrente 
pode ser expressa graficamente através de um diagrama de alto nível que procura 
representar com precisão os diversos elementos envolvidos, seus dados descritivos e 
relacionamentos relevantes. Esse tipo de diagrama representa aquilo que chamamos de 
modelo conceitual, onde o nível de abstração utilizado é muito alto e que tem por 
finalidade capturar os principais aspectos da realidade que sejam de interesse dentro do 
escopo do problema. Um instrumento típico para representar um modelo conceitual é o 
diagrama Entidade / Relacionamento, como o utilizado na figura 1 para modelar as 
especificações gerais do caso do controle bancário. 
 
Aspectos físicos do armazenamento de dados 
Figura 1: Modelo conceitual para o controle bancário simplificado. 
O modelo conceitual é, entretanto, muito abstrato para receber uma implementação direta 
sob um SGBD, pois deve ser independente da tecnologia computacional, já que procura 
retratar as coisas tais como ocorrem no mundo real. Assim, esse modelo de mais alto 
nível precisa ser detalhado de maneira a permitir sua materialização dentro de um 
produto de banco de dados. O modelo (ou esquema) lógico procura detalhar as 
especificações do nível conceitual para uma tecnologia computacional específica (como 
por exemplo a relacional ou a orientada a objetos) considerando ainda as características e 
limitações de um determinado produto de banco de dados. A figura 2 apresenta um 
diagrama lógico para uma implementação relacional do caso do controle bancário, e foi 
obtida a partir das especificações constantes no modelo conceitual mostrado 
anteriormente na figura 1. 
O esquema lógico é muito mais específico que o conceitual, mas ainda é genérico o 
suficiente para comportar mais de uma implementação física. Diversos aspectos de mais 
baixo nível podem ainda ser considerados para que as estruturas de dados 
correspondentes venham a ser construídas no banco de dados. A figura 3 procura mostrar 
a relação entre esses três níveis de abstração, dos quais o nível físico é aquele que merece 
maior atenção neste material. 
 
Cliente
Conta
Corrente
Agência
MovimentoMantém
Pertence
Possui
@Cód. Cliente
Nome
Endereço
Telefone
Dados Pessoais
Senha
@ Núm. Conta
Data Abertura
Saldo Atual
@ Núm. Mov.
Data Movim.
Tipo Mov.
Valor Movim.
Descr. Movim.
@ Núm. Agênc.
Nome Agência
Endereço
Telefone
Aspectos físicos do armazenamento de dados 
Clientes Contas
Agencias
Movimentos
Senha
CliContas
CdCliente
NmCliente
EndCliente
TelCliente
RGCliente
CPFCliente
CdCliente
NrConta
NrConta
DtAbertura
CdAgencia
VrSaldo
CdAgencia
NmAgencia
EndAgencia
TelAgencia
NrMov
NrConta
DtMov
TpMov
VrMov
DsMov
VrSaldoSexo
 
Figura 2: Esquema lógico (relacional) para o controle bancário simplificado. 
 
 
 
 
 
 
 
 
 
 
 
Figura 3: Relação entre os 3 níveis de abstração em um projeto de banco de dados. 
Modelo conceitual 
(coisas, objetos, entidades, 
relacionamentos, etc) 
Modelo lógico 
(tabelas, tipos de dados, regras 
de nomes, etc) 
Modelo físico 
(arquivos, páginas em disco, 
índices, etc) 
 
Realidade 
Hardware / Software 
Alto nível 
Baixo nível 
Aspectos físicos do armazenamento de dados 
Estruturas de armazenamento físico 
Armazenamento de dados 
O conteúdo de um banco de dados é fisicamente armazenado na forma de arquivos em 
disco e por isso está sujeito às características e limitações desse tipo de dispositivo, 
valendo aqui todos aqueles elementos básicos de gerenciamento em disco que geralmente 
são abordados em uma disciplina introdutória sobre sistemas operacionais e em obras 
como [TANEMBAUM, 1995]. A quantidade e variedade de tipos de arquivos utilizados 
pelos diversos SGBDs varia bastante, mas os princípios básicos de armazenamento dos 
dados são geralmente comuns. É importante lembrar que qualquer processamento sobre 
os dados ocorre na memória principal, o que implica na constante movimentação (leituras 
e gravações físicas) de informação entre o disco e a memória durante a operação do 
SGBD. 
Figura 4: Movimentação de dados entre a memória e o disco pelo SGBD. 
Os arquivos em disco de um banco de dados são organizados na forma de blocos ou 
páginas, que podem conter dados ou metadados. Uma operação de leitura física traz do 
disco o conteúdo de toda uma página, o que pode significar que mais de uma linha está 
sendo lida naquela operação, uma vez que tipicamente uma página possui um valor na 
faixa entre 2Kb e 32Kb e por isso geralmente contém dados de mais de uma linha de 
tabela, como pode ser visualizado na figura 5. 
Aspectos físicos do armazenamento de dados 
Movimentos 
 NrMov NrConta DtMov TpMov VrMov DsMov VrSaldo 
 <header da página> 
Página 1 1 1021 10/08/95 C R$ 500,00 Deposito R$ 500,00 
 2 1022 20/09/95 C R$ 750,00 Deposito R$ 750,00 
 3 1021 20/09/95 D R$ 120,00 Cheque R$ 380,00 
 
 <header da página> 
Página 2 4 1023 22/09/95 C R$ 400,00 Deposito R$ 400,00 
 5 1024 10/10/95 C R$ 920,00 Deposito R$ 920,00 
 
 
Figura 5: Distribuição dos dados da tabela Movimentos pelas páginas no disco. 
O exemplo da figura mostra que as 3 primeiras linhas da tabela Movimentos são 
armazenadas na mesma página física em disco, o que significa que quando uma delas 
deve ser lida, todas as outras são lidas também, já que aquela página inteira vai para a 
memória principal. Observe também que há um espaço livre em cada página, que é útil 
para acomodar algumas modificações e inclusões de dados na tabela. A figura também 
mostra queuma página possui, além de dados, algumas informações de controle sobre o 
seu conteúdo, chamadas metadados, como por exemplo a identificação da página, o seu 
tipo (se é uma página de dados ou de índice), quantas linhas ela contém, total de espaço 
livre, a data e hora da última atualização, etc. Os metadados costumam ficar armazenados 
em áreas reservadas no ínicio de cada página, chamadas de cabeçalhos ou headers. 
Também uma linha possui metadados, que indicam por exemplo o seu número de 
colunas, o tamanho útil de cada uma, identificadores de linha, etc. 
Uma linha de tabela é identificada por meio de um número interno que muitas vezes 
recebe o nome de RID (Row ID) ou TID (Tuple ID). A composição desse número varia 
conforme o SGBD utilizado, mas tipicamente envolve pelo menos o número do arquivo, 
do bloco e da linha, o que faz com que um RID possa ser considerado como uma espécie 
de ponteiro para a linha. No caso do Oracle 8, por exemplo, um RID possui 10 bytes de 
tamanho, e é composto por 4 informações, conforme mostra a figura 6. 
 
 
 
 
Figura 6: Organização interna de um RowId no Oracle 8. 
Os tipos de dados suportados pela linguagem de manipulação de dados (DML) do SGBD 
são implementados no nível físico através de estruturas de dados próprias, com uma 
significativa variação entre um produto e outro. O quadro a seguir procura mostrar como 
os tipos de dados mais comuns são implementados no SGBD Oracle 8. 
RowId: 00003894024033750001 
 
Número do objeto Número do arquivo Número da página Número da linha 
00003894 024 03375 0001 
 
Aspectos físicos do armazenamento de dados 
Tipo Descrição 
Char Possui um indicador de tamanho de 1 byte (para colunas com até 250 bytes) 
ou 3 bytes (para colunas com mais de 250 bytes). O conteúdo da coluna é 
preenchido com espaços em branco à direita, até o tamanho da coluna. São 
armazenados na linha na mesma ordem do create table. 
Varchar2 Possui um indicador de tamanho de 1 ou 3 bytes. São armazenadas na linha 
na mesma ordem do create table. Se a coluna contiver um nulo, isso é 
sinalizado como tamanho = 0. 
Number Não implementa diretamente os tipos numéricos convencionais, como 
Integer, Float, etc. Em vez disso, utiliza uma estrutura de tamanho variável, 
cujo tamanho depende dos valores a serem armazenados. 
Date Ocupa 7 bytes e inclui século, ano, mês, dia, hora, minuto e segundo. 
Com base nas informações que temos, podemos estimar com alguma precisão o tamanho 
real de uma linha de tabela. Vamos imaginar a tabela Movimentos, cuja estrutura é 
apresentada na figura 7. 
Coluna Tipo / Tamanho Observações 
NrMov NUMBER( 12 ) Número do movimento 
NrConta CHAR( 4 ) Número da conta 
DtMov DATE Data do movimento 
TpMov CHAR( 1 ) Tipo de movimento 
VrMov NUMBER( 12, 2 ) Valor do movimento 
DsMov VARCHAR2( 20 ) Descrição do movimento 
VrSaldo NUMBER( 12, 2 ) Saldo da conta após o movimento 
Figura 7: Descrição da estrutura da tabela Movimentos. 
O cálculo é o seguinte: 
Núm.bytes Descrição 
3 Cabeçalho de linha 
7 Indicadores de tamanho das colunas (7 colunas com tamanho < 250 bytes) 
4 Tamanho fixo da coluna NrConta 
7 Tamanho fixo da coluna DtMov 
1 Tamanho fixo da coluna TpMov 
9 Tamanho das colunas NrMov, VrMov, VrSaldo (aproximadamente)* 
20 Tamanho máximo da coluna DsMov 
51 Tamanho total aproximado por linha 
Aspectos físicos do armazenamento de dados 
*A quantidade de bytes para colunas numéricas é estimada com base em [LONEY & THERIAULT, 2000]. 
Tabelas com colunas de tamanho variável podem ser problemáticas do ponto de vista da 
alocação de espaço em disco, na medida em que mudanças no conteúdo de uma coluna 
podem levar ao aumento do tamanho físico da linha no disco. Em um caso extremo, uma 
linha armazenada em uma página pode receber uma atualização que modifique seu 
tamanho físico e force o SGBD a armazenar uma parte dessa linha em uma página e outra 
parte em outra página. Dizemos então que essa linha sofreu um encadeamento entre dois 
blocos e sempre que for necessário recuperar essa linha, o gerenciador deverá ler as duas 
páginas a partir do disco, degradando o desempenho geral da consulta. Para minimizar a 
ocorrência desse tipo de problema, um espaço físico geralmente é reservado em cada 
página para acomodar futuras extensões no tamanho das linhas já armazenadas na página. 
Essa margem de segurança, expressa em percentuais, é chamada de PCTFREE em alguns 
dialetos SQL (como do Oracle e SQL Base, por exemplo) e informada no momento da 
criação da tabela. Um valor típico para esse parâmetro é 10%, o que significa que novas 
linhas serão inseridas em uma página até que o espaço total ocupado na página atinja 
aproximadamente 90% do espaço total disponível (ou seja, tamanho da página – header 
da página – PCTFREE). Caso uma atualização faça com que uma linha não caiba mais 
inteiramente em uma página, ela é retirada de sua página original e colocada em uma 
nova página com espaço suficiente para contê-la. Se não houver páginas com tal 
capacidade, a linha é então encadeada. 
Para calcular o espaço físico da tabela inteira no disco é necessário determinar o seu 
número total de linhas e o número de páginas utilizadas. Para determinar o número de 
páginas utilizadas, é necessário saber o tamanho de cada página e o tamanho do espaço 
livre reservado em cada página. Vamos imaginar uma tabela Movimentos com 30000 
linhas, armazenadas em páginas de 2Kb com PCTFREE de 10%, com o cabeçalho de 
cada página ocupando 100 bytes. O cálculo é demonstrado no quadro a seguir. 
 
 
 
 
 
 
 
 
 
 
 
Valores iniciais 
 (Tp) Tamanho da página : 2048 bytes 
 (Cp) Cabeçalho da página : 100 bytes 
 (PctFree) Margem livre % : 10% = 0.1 
 (Tl) Tamanho da linha : 51 bytes (já calculado) 
 (Ql) Qtde linhas na tabela : 30000 linhas 
 
Cálculos 
 (BFree) Margem livre bytes : PctFree * (Tp – Cp) = 195 bytes 
 (Up) Espaço útil na página : Tp – Cp – BFree = 1753 bytes 
 (Qlp) Qtde de linhas / página : Up / Tl = 34 linhas 
 (Qp) Qtde de pág. p/ tabela : Ql / Qlp = 30000 / 34 = 883 pags 
 
Resultado 
 Tamanho total da tabela : Qp * 2048 = 
= 1808384 bytes  1,8 MB 
Aspectos físicos do armazenamento de dados 
Esse valor referem-se apenas ao tamanho requerido pelos dados da tabela e devem ser 
encarados como uma aproximação, uma vez que o valor exato consumido está sujeito a 
diversos outros fatores, tais como política de número de blocos alocados a cada vez pelo 
SGBD, tamanho e tipo dos índices utilizados para a tabela, etc. 
Aspectos físicos do armazenamento de dados 
Índices 
Os índices são recursos de projeto de banco de dados destinados a facilitar tarefas de 
pesquisa de linhas ou de ordenação dos dados de tabelas, como ocorre na emissão de 
relatórios ou de consultas em tela, por exemplo. Um índice é uma estrutura auxiliar que 
apresenta a ordem em que as linhas da tabela aparecem segundo um determinado critério. 
Uma tabela pode possuir vários índices, que oferecem diversas perspectivas distintas de 
seus dados, cada uma delas sob um critério de ordenação diferente, e são mantidos 
atualizados automaticamente pelo sistema. Assim, na tabela original os dados são 
armazenados em uma ordem física qualquer, mas quando acessados através de um índice, 
parecem estar organizados segundo um critério lógico específico. A leitura de uma tabela 
através de um índice envolve então, em princípio, dois tipos de acesso ao disco: um para 
recuperar as páginas do índice onde será feita a pesquisa e outro para trazer para a 
memória a(s) página(s) de dados. A ordenação lógica das tabelas representa um recurso 
praticamente obrigatório na construção de eficientes aplicações comerciais e mecanismos 
de indexação são disponibilizados pelos diferentes SGBDs para que a construção e 
utilização de índices seja simples e rápida. 
A seguir serão apresentados alguns exemplos de índices para ilustrar esse conceito e 
algumas de suas características de utilizaçãoe implementação física. Esses exemplos 
serão baseados na tabela "Contas" do controle bancário simplificado. 
Coluna Tipo / Tamanho Observações 
NrConta CHAR( 4 ) Número da conta 
DtAbertura DATE Data de abertura da conta 
CdAgencia CHAR( 4 ) Código da agência 
VrSaldo NUMBER Saldo atual da conta 
Figura 8: Descrição da estrutura da tabela Contas. 
 Contas 
# NrConta DtAbertura CdAgencia VrSaldo 
1 1025 25/10/95 0060 R$ 2100,00 
2 1021 10/08/95 0040 R$ 568,00 
3 1030 26/11/95 0040 R$ 500,00 
4 1022 01/09/95 0060 R$ 720,00 
5 1028 12/11/95 0050 R$ 1500,00 
6 1023 12/09/95 0040 R$ 150,00 
7 1029 17/11/95 0050 R$ 1050,00 
8 1026 04/11/95 0050 R$ 535,00 
9 1024 23/10/95 0050 R$ 1047,00 
10 1032 12/11/95 0060 
11 1027 10/11/95 0040 R$ 100,00 
12 1031 08/12/95 0060 R$ 50,00 
Figura 9: Tabela Contas com alguns dados de exemplo. 
 
Aspectos físicos do armazenamento de dados 
 
# Expressão Posição 
1 1021 2 
2 1022 4 
3 1023 6 
4 1024 9 
5 1025 1 
6 1026 8 
7 1027 11 
8 1028 5 
9 1029 7 
10 1030 3 
11 1031 12 
12 1032 10 
Figura 10: Representação lógica de um índice por ordem de Número da conta (NrConta). 
O índice possui uma lista com os valores da coluna chave ordenados, juntamente com a 
relação da posição de cada chave na tabela e implementa, portanto, um mapeamento entre 
os valores da chave, ordenados, e os registros físicos correspondentes na tabela, conforme 
mostra a figura a seguir. 
 Índice Tabela 
# Expressão Posição # NrConta DtAbertura CdAgencia VrSaldo 
1 1021 2 1 1025 25/10/95 0060 R$ 2100,00 
2 1022 4 2 1021 10/08/95 0040 R$ 568,00 
3 1023 6 3 1030 26/11/95 0040 R$ 500,00 
4 1024 9 4 1022 01/09/95 0060 R$ 720,00 
5 1025 1 5 1028 12/11/95 0050 R$ 1500,00 
6 1026 8 6 1023 12/09/95 0040 R$ 150,00 
7 1027 11 7 1029 17/11/95 0050 R$ 1050,00 
8 1028 5 8 1026 04/11/95 0050 R$ 535,00 
9 1029 7 9 1024 23/10/95 0050 R$ 1047,00 
10 1030 3 10 1032 12/11/95 0060 
11 1031 12 11 1027 10/11/95 0040 R$ 100,00 
12 1032 10 12 1031 08/12/95 0060 R$ 50,00 
 
 
 
 
 Ordem lógica Ordem física 
 (pela coluna NrConta) (das linhas na tabela) 
Figura 11: Índice como o mapeamento da ordem lógica para os dados físicos da tabela. 
 
Aspectos físicos do armazenamento de dados 
 
# Expressão Posição 
1 R$ 50,00 12 
2 R$ 100,00 11 
3 R$ 150,00 6 
4 R$ 500,00 3 
5 R$ 535,00 8 
6 R$ 568,00 2 
7 R$ 720,00 4 
8 R$ 1047,00 9 
9 R$ 1050,00 7 
10 R$ 1500,00 5 
11 R$ 2100,00 1 
12 10 
Figura 12: Representação lógica de um índice por ordem de Saldo da conta (VrSaldo). 
Além do índice pela chave primária, uma tabela pode necessitar de outros índices, 
chamados de índices secundários. Basicamente são utilizados para chaves estrangeiras e 
colunas utilizadas com muita freqüência como critério de seleção de linhas, tais como 
nomes e alguns códigos. 
# Expressão Posição 
1 0040 2 
2 0040 3 
3 0040 6 
4 0040 11 
5 0050 5 
6 0050 7 
7 0050 8 
8 0050 9 
9 0060 1 
10 0060 4 
11 0060 10 
12 0060 12 
Figura 13: Representação lógica de um índice por ordem de Código da agência (CdAgencia). 
Observe na figura 13 que para as linhas que possuem o mesmo valor para a chave do 
índice o critério de desempate para saber qual deles deve ser acessado primeiro é a ordem 
física na tabela. 
Aspectos físicos do armazenamento de dados 
 
# Expressão Posição 
1 00401021 2 
2 00401023 6 
3 00401027 11 
4 00401030 3 
5 00501024 9 
6 00501026 8 
7 00501028 5 
8 00501029 7 
9 00601022 4 
10 00601025 1 
11 00601031 12 
12 00601032 10 
Figura 14: Representação lógica de um índice por ordem de Código da agência e Número da conta 
(CdAgencia + NrConta) 
Este caso representa um índice cuja expressão chave é formada por mais de uma coluna. 
Esse tipo de chave é chamado de chave composta. No caso, as linhas aparecem por 
ordem de Código da agência e aquelas que possuem mesma agência aparecem por ordem 
de Número da conta. O funcionamento do índice é o mesmo dos exemplos anteriores mas 
neste caso é importante saber que um índice com uma chave composta por CdAgencia + 
NrConta não é equivalente a um índice com uma chave NrConta + CdAgencia. 
As figuras de 10 a 14 procuram oferecer uma adequada visão lógica dos índices, na forma 
de uma espécie de tabela auxiliar que reflete o conteúdo da tabela principal. Não é assim 
entretanto que os índices costumam ser fisicamente implementados nos SGBDs, já que 
existem estruturas de dados mais eficientes para essa finalidade, como as árvores, por 
exemplo. Nos bancos de dados atuais os índices geralmente são construídos por meio de 
árvores B+, que facilitam a tarefa de pesquisa no índice e permitem também um 
tratamento mais prático de operações que envolvem a leitura seqüencial ordenada dos 
dados. Um exemplo de índice B+ para o caso da figura 5 é apresentado a seguir. 
 
 
 
 
 
 
 
Figura 16: Implementação física de um índice por NrConta como uma árvore B+. 
 1026  
 
 1022  1024  
 
 1028  1030  
 
1021 1022 
 
1023 1024 
 
1025 1026 
 
1027 1028 
 
1029 1030 
 
1031 1032 / 
 
Aspectos físicos do armazenamento de dados 
Clusters 
Um cluster (ou agrupamento) de dados é uma estrutura que permite manter fisicamente 
próximos os dados de duas ou mais tabelas que são logicamente ligadas entre si. Isso 
significa procurar manter juntas no mesmo bloco físico do disco as linhas correlacionadas 
dessas tabelas, de tal maneira que quando há uma leitura física do disco, os dados dos 
relacionamentos são trazidos juntos para a memória, pois lê-se sempre a página de dados 
inteira e com isso economiza-se I/O. 
Exemplo: Tabelas Contas e CliContas do controle bancário 
Contas 
NrConta DtAbertura CdAgencia VrSaldo 
1021 10/08/95 0040 R$ 568,00 
1022 01/09/95 0060 R$ 720,00 
1023 12/09/95 0040 R$ 150,00 
1024 23/10/95 0050 R$ 1470,00 
1025 25/10/95 0060 R$ 2100,00 
 
Figura 17: Estrutura lógica das tabelas com alguns dados de exemplo. 
 
NrConta DtAbertura CdAgencia VrSaldo 
 CdCliente Senha 
1021 10/08/95 0040 R$ 568,00 
 00001 ****** 
1022 01/09/95 0060 R$ 720,00 
 00002 ****** 
1023 12/09/95 0040 R$ 150,00 
 00003 ****** 
 00004 ****** 
1024 23/10/95 0050 R$ 1470,00 
 00005 ****** 
1025 25/10/95 0060 R$ 2100,00 
 00006 ****** 
Figura 19: Estrutura física, com a organização dos dados em um cluster para as duas tabelas. 
O agrupamento (ou clusterização) de tabelas como mostrado no exemplo é indicado nas 
situações em que duas ou mais tabelas são sempre lidas em conjunto (em junções, 
portanto) e muito raramente são consultadas em separado, como geralmente ocorre em 
alguns relacionamentos mestre / detalhe envolvendo uma entidade associativa. As 
operações de gravação, por sua vez, ficam um pouco prejudicadas, além do que algum 
espaço adicional em disco e na memória principal acaba sendo necessário para 
administrar esse tipo de estrutura mais complexa. Nem todos os SGBDs suportam o 
cluster de tabelas (como o Oracle suporta), mas a maioria permite o agrupamento de 
índices (como o SQL Server, por exemplo). 
Chaves 
do 
Cluster 
CliContas 
CdCliente NrConta Senha 
00001 1021 ****** 
00002 1022 ****** 
00003 1023 ****** 
00004 1023 ****** 
00005 1024 ****** 
00006 1025 ****** 
 
Aspectos físicos do armazenamento de dados 
Hashing 
Estruturas ou tabelas hash (também chamadas de tabelas de espalhamento) oferecem um 
meio para a localização instantânea de uma chave na tabela, com base apenas em seu 
valor. O espaço físico em disco destinado à tabela é dividido previamente em um número 
fixo de segmentos (também chamados de buckets) numerados e conforme o valor da 
chave, será o segmento em que a linha inteira deverá ser armazenada. Para determinar a 
localização física de uma linha um cálculo deve ser realizado pelo SGBD sobre o valor 
de sua chave, de maneira a obter o número do segmento correspondente. A função que 
mapeia um valor de chave para um segmento é chamada de função hash. A principal 
vantagem dessetipo de estrutura é a rapidez com que um valor é encontrado na tabela, 
mas devido à forma como os dados são gravados no disco, processamentos seqüenciais 
indexados não podem ser beneficiados pelo armazenamento nesse tipo de estrutura. Um 
outro ponto crítico está na definição da função hash, que deve conseguir distribuir as 
chaves de maneira mais uniforme possível, de maneira a não concentrar dados demais em 
certos segmentos em detrimento de outros. Uma discussão detalhada a respeito de tabelas 
de espalhamento e algoritmos para funções hash pode ser encontrada em [ZIVIANI, 
1999] e detalhes sobre a aplicação desse tipo de estrutura em bancos de dados são 
apresentados em [SILBERSCHATZ et al., 1999]. Finalmente, nem todos os SGBDs 
permitem que uma tabela seja organizada diretamente na forma de uma estrutura hash 
como mostrado no exemplo a seguir, mas muitos deles permitem que pelo menos um 
índice por tabela tenha esse tipo de armazenamento. É possível também combinar uma 
estrutura de cluster (de tabela ou de índice) com o uso de mapeamentos hash. 
Exemplo: Tabela Agencias do controle bancário 
Agencias 
CdAgencia NmAgencia EndAgencia TelAgencia 
0040 Praça da Republica Praça da Republica, 200 555-4433 
0050 Centro R 15 de Novembro, 800 555-2211 
0060 Prefeitura Av Sao Paulo, 100 555-6612 
Figura 20: Estrutura lógica da tabela com alguns dados de exemplo. 
Aspectos físicos do armazenamento de dados 
 
Chave Hash CdAgencia NmAgencia EndAgencia TelAgencia 
0 0060 Prefeitura Av Sao Paulo, 100 555-6612 
 
 
 
1 0040 Praça da Republica Praça da Republica, 200 555-4433 
 
 
 
2 0050 Centro R 15 de Novembro, 800 555-2211 
 
 
 
Figura 21: Estrutura hash para a tabela Agencias 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 22: Exemplo de função hash para uso com a estrutura da figura 21. 
 
Func Hash3 ( codigo: cadeia ) : int ; 
Var soma: int; 
 numero: cadeia; 
 posicao: int; 
 contador: int; 
 
Inicio 
 contador  1; 
 soma  0 ; 
 Enquanto contador <= Compr( codigo ) Faça 
 Início 
 numero  Subc( codigo, contador, 1 ) ; 
 soma  soma + CadeiaParaInt( numero ) ; 
 contador  contador + 1 ; 
 Fim ; 
 
 posicao  soma Mod 3 ; 
 Retorne posicao ; 
Fim ; 
Processamento de consultas: visão geral 
 Processamento de consultas 
O processamento de uma consulta de banco de dados é realizado pelo SGBD através de 
inúmeros passos, conforme mostra a figura 1. Geralmente a consulta é formalizada pelo 
usuário através de um dialeto SQL. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Figura 1: Estrutura geral de processamento de uma consulta 
Compilação: a consulta submetida pelo usuário é analisada em termos de sua estrutura 
geral, operações requeridas e dos objetos utilizados. Caso haja algum problema na 
formação da instrução, uma mensagem de erro é retornada ao usuário e o processamento 
da consulta é cancelado. Consultas corretamente formuladas podem sofrer algum tipo de 
pré-processamento neste momento, como resolução de visões, por exemplo. 
Rescrita da expressão: o comando original referente à consulta é analisado e rescrito 
numa forma mais adequada ao processamento pelo SGBD. 
Compilação 
Rescrita da 
expressão 
Otimização do plano 
de acesso 
Geração do código 
Execução do código 
Instrução SQL 
Catálogo do 
banco de dados Erro 
Dados + Erro Banco de dados 
Processamento de consultas: visão geral 
Otimização do plano de acesso: com base na versão rescrita da consulta e nas 
informações contidas no catálogo do banco de dados, várias estratégias de acesso aos 
dados são produzidas e avaliadas, sendo uma delas escolhida para ser implementada. 
Geração do código: o plano de acesso selecionado é convertido para um código 
executável (ou interpretável ou pseudo-executável) próprio do SGBD. 
Execução do código: as instruções contidas no plano de acesso são executadas pelo 
SGBD, sob o comando do módulo gerente de transações. Os resultados são enviados ao 
usuário, juntamente com um eventual código de erro. 
Compilação: elementos básicos 
O processo de compilação envolve 3 etapas principais, nas quais se procura identificar a 
estrutura do comando, os elementos que são manipulados e a natureza do processamento 
a ser realizado. Essas etapas são tradicionalmente denominadas por análise léxica, análise 
sintática e análise semântica e serão rapidamente descritas a seguir, sendo que uma 
discussão mais aprofundada sobre cada uma pode ser encontrada em qualquer bom livro 
sobre compiladores, como por exemplo Aho et al (1995). 
Análise léxica 
É também chamada de análise linear ou de scanning, e consiste na identificação dos 
tokens do código, ou seja, no isolamento das diversas palavras ou símbolos utilizados na 
construção da instrução SQL original. É com base nesses elementos que toda a análise 
posterior é realizada. 
Análise sintática 
Esta fase é também chamada de análise hierárquica, de análise gramatical ou, ainda, de 
parsing, e tem por objetivo estabelecer a estrutura lógica do processamento envolvido em 
termos de frases gramaticais, geralmente organizadas em árvores. Eventuais erros na 
formação da expressão são também detectados e reportados nesta fase. 
Análise semântica 
A análise semântica verifica problemas de significado nas frases gramaticais produzidas 
na etapa anterior. Os principais aspectos tratados aqui são a validação dos identificadores 
utilizados (nomes de tabelas, colunas, visões, funções, etc) e a verificação de possíveis 
conflitos de tipos de dados nas operações. Para essa tarefa, o compilador precisa utilizar 
as informações contidas no catálogo do banco de dados, além das definições próprias da 
linguagem de consulta suportada. 
Exemplo de trabalho do módulo compilador do SGBD 
Para ilustrar algumas características do processo de compilação de uma consulta, vamos 
considerar que desejamos obter, com base nas tabelas do controle bancário, a informação 
referente a quais contas corrente (e suas respectivas agências) devem pagar pelo menos 
R$ 5,00 de juros e taxas financeiras decorrentes de saldo negativo. O montante devido é 
calculado com base num valor fixo de R$ 3,00 acrescido de juros de 10% do saldo 
devedor. Vamos assumir ainda, por questão de simplicidade, que a consulta é expressa na 
forma da seguinte expressão de álgebra relacional: 
Processamento de consultas: visão geral 
 NrConta, CdAgencia (  VrSaldo < 0 ^ VrSaldo * -0.1 + 3 > 5 ( contas ) ) 
Essa expressão corresponde ao seguinte plano lógico de consulta: 
 
 
 
 
 
 
 
 
 
Figura 2: Plano lógico da consulta 
Análise léxica 
A expressão fornecida ao compilador é decomposta em tokens, alguns dos quais são 
mostrados no quadro a seguir. 
Lexema Token 
 Operador 
NrConta Identificador 
, Símbolo de pontuação 
CdAgencia Identificador 
 Operador 
VrSaldo Identificador 
< Operador 
0 Constante numérica 
contas Identificador 
Análise sintática 
Uma árvore gramatical é criada relacionando os tokens em frases gramaticais com 
sentido. O predicado da restrição da consulta (a expressão lógica VrSaldo < 0 ^ VrSaldo 
* -0.1 + 3 > 5) pode ser expresso conforme mostra a figura 3. Observe que a ordem de 
precedência das operações encontra-se definida nessa representação, onde o 
processamento ocorre a partir das folhas da árvore em direção à sua raiz. 
 NrConta, CdAgencia 
 VrSaldo < 0 ^ VrSaldo * -0.1 + 3 > 5 
contas 
Processamento de consultas: visão geral 
 
 
 
 
 
 
 
Figura 3: Árvore gramatical para um predicado de consulta 
Convém ressaltar que não apenas o predicado é expresso em uma árvore gramatical, mas 
toda a expressão relacional correspondente. 
Análise semântica 
Com base no contexto sugerido pela árvore gramatical gerada anteriormente, o 
compilador determina que o identificador ‘contas’ deve ser uma tabela ou visão à qual o 
usuário precisa ter direitos de acesso e faz essaverificação no catálogo do banco de 
dados. Os identificadores NrConta, CdAgencia e VrSaldo devem ser colunas do objeto 
‘contas’ e o usuário precisa ter direitos de consulta sobre elas. A verificação desses 
requisitos é feita também através de pesquisa ao catálogo do sistema. Por fim, os tipos 
dos dados dos operandos precisam ser compatíveis com as operações indicadas, e para 
isso os valores das constantes são analisados, bem como o tipo definido para a coluna 
VrSaldo no banco de dados. 
Heurísticas do processamento de consultas 
O processamento de uma consulta compilada com êxito envolve a produção de um plano 
de execução ou plano de acesso, que especifica exatamente o que deve ser realizado para 
a obtenção do resultado final. Um plano de execução deve indicar a ordem em que as 
diversas operações relacionais serão executadas, a ordem de acesso às tabelas, os índices 
que serão utilizados, os bloqueios (locks) necessários sobre os dados, as modalidades de 
junção indicadas para cada caso, bem como estratégias adicionais a serem adotadas, 
como recursos de paralelismo e pipelining de operações e o emprego de tabelas 
temporárias, por exemplo. 
Nesta fase, questões de desempenho são analisadas e resolvidas, buscando-se encontrar 
soluções computacionalmente mais econômicas. Para isso, procura-se minimizar o 
volume de dados manipulado e o número de operações de acesso a disco requeridas, o 
que é conseguido através do emprego de algumas regras heurísticas clássicas, tais como 
executar as seleções e projeções antes e rescrever as consultas considerando a 
equivalência entre operações relacionais. 
 ̂
< 
0 VrSaldo 
> 
5 + 
3 
VrSaldo -0.01 
* 
Processamento de consultas: visão geral 
Equivalência entre operações relacionais 
Existe um grande número de relações de equivalência matemática entre operações 
relacionais e, mesmo, entre operações não-relacionais. Algumas dessas relações são 
triviais, como por exemplo (A + B)  (B + A) enquanto que outras são menos óbvias, 
sendo que seu reconhecimento por parte do módulo otimizador do SGBD viabiliza 
interessantes substituições nas consultas originalmente submetidas para processamento, 
que podem proporcionar ganhos significativos de desempenho durante sua execução. 
Algumas dessas equivalências são citadas rapidamente a seguir. 
a. Comutatividade e encadeamento (“cascata”) de restrições 
P1 ^ P2 (r)  P1 (P2 (r))  P2 (P1 (r)) 
b. Associatividade da junção natural 
(r1 |x| r2) |x| r3  r1 |x| (r2 |x| r3) 
c. Comutatividade da junção natural 
r1 |x| r2  r2 |x| r1 
d. Comutatividade da união 
r1  r2  r2  r1 
e. Encadeamento (“cascata”) de projeções 
 L1 ( L2 (...(R))   L1(R) 
f. Comutatividade entre seleções e projeções 
 A ( C (R))   C ( A(R)) 
g. Comutatividade entre seleções e junções 
 C (R |x| S)  ( C(R)) |x| S 
h. Comutatividade entre projeções e junções 
 L(R |x| S)   A(R) |x|  B (S) 
i. Idempotência da união 
r1  r1  r1 
j. Outras equivalências interessantes 
P (r1  r2)  P (r1)  P (r2) 
P (r1  r2)  P (r1)  r2  P (r1)  P (r2) 
(r1  r2)  r3  r1  (r2  r3) 
Processamento de consultas: visão geral 
Exemplo didático de rescrita de uma consulta 
Para ilustrar um caso de rescrita de uma consulta para fins de processamento posterior, 
vamos supor uma instrução solicitando o nome de todos os funcionários do departamento 
chamado ‘ADMINISTRAÇÃO’ que recebem salário superior a $500,00. As tabelas 
disponíveis no banco de dados são: 
funcionarios (NrMatric, NmFunc, DtAdm, Sexo, CdCargo, CdDepto) 
cargos (CdCargo, NmCargo, VrSalario) 
deptos (CdDepto, NmDepto, Ramal) 
 
Para esse banco de dados, a consulta pode ser escrita utilizando o seguinte código SQL: 
SELECT NmFunc 
 FROM cargos c, funcionarios f, deptos d 
 WHERE f.CdCargo = c.CdCargo 
 AND f.CdDepto = d.CdDepto 
 AND NmDepto = 'ADMINISTRACAO' 
 AND VrSalario > 500 ; 
A expressão de álgebra relacional correspondente seria: 
 NmFunc (  f.CdCargo = c.CdCargo ^ ( c (cargos) x  f (funcionarios) x  d (deptos) ) ) 
f.CdDepto = d.CdDepto ^ 
NmDepto = 'ADMINISTRACAO' ^ 
VrSalario > 500 
A preparação dessa consulta envolve a sua validação, verificando possíveis erros de 
sintaxe ou de semântica, por meio do módulo compilador, e sua rescrita, adotando 
algumas heurísticas para a otimização do código e regras de equivalência entre 
expressões, realizadas pelo módulo otimizador. Esse processo de rescrita envolve 
diversas etapas, que podem variar conforme o produto SGBD utilizado, sendo que os 
passos mostrados a seguir foram adaptados a partir de [ELMASRI, 2000] e procuram 
representar de maneira didática os seus aspectos principais. As várias operações 
relacionais a serem realizadas são apresentadas na forma de uma árvore, como é comum 
ocorrer ao se trabalhar com compiladores, de maneira que o processamento requerido 
inicia-se a partir de suas folhas, terminando na raiz. 
Passo 1: Produzir a árvore canônica para a consulta 
 
Existe um conjunto muito vasto de expressões relacionais que podem ser formadas. 
Como já vimos anteriormente, muitas dessas expressões são equivalentes, ou seja, 
representam, a rigor, a mesma consulta. Dentro desse conjunto de todas as expressões 
possíveis existe um subconjunto, bem menor que o primeiro, que contém uma única 
expressão para cada consulta possível. As expressões que fazem parte desse subconjunto 
mínimo de expressões são chamadas de formas canônicas, e são adotadas para simplificar 
o processo de análise do otimizador. Toda consulta submetida ao SGBD é inicialmente 
reduzida à sua forma canônica, expressa em uma linguagem de consulta interna do 
Processamento de consultas: visão geral 
gerenciador e que, para fins deste exemplo, será assumida como sendo a álgebra 
relacional. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Obs.: Calcular o número total de linhas processado se este plano de execução for 
adotado. Supor que a tabela funcionarios possui 10 linhas, a tabela cargos, 6 linhas e a 
tabela deptos, 4 linhas. 
 
Passo 2: Antecipar as restrições, desmembrando-as 
 
Um dos princípios gerais da otimização de consultas é procurar sempre manipular o 
menor volume de dados possível para produzir os resultados solicitados pela consulta. 
Realizar inicialmente todas as restrições possíveis, antes de qualquer junção ou produto 
cartesiano, reduz o número de linhas a serem manipuladas nas etapas intermediárias, 
sendo que geralmente essa redução é dramática. Em nosso exemplo, algumas restrições 
podem ser realizadas inicialmente, e foram colocadas nos níveis inferiores da árvore. 
 
 NmFunc 
 c cargos 
 f funcionarios 
 d deptos 
 f.CdCargo = c.CdCargo ^ f.CdDepto = d.CdDepto ^ VrSalario > 500 ^ NmDepto = 'ADMINISTRACAO' 
c f 
x d 
x 
Processamento de consultas: visão geral 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Obs.: Calcular o número total de linhas processado se este plano de execução for 
adotado. Supor que a tabela funcionarios possui 10 linhas, a tabela cargos, 6 linhas e a 
tabela deptos, 4 linhas. 
 
 NmFunc 
 c cargos 
 f funcionarios 
 d deptos 
 f.CdDepto = d.CdDepto 
x 
 NmDepto = 'ADMINISTRACAO' 
d 
 f.CdCargo = c.CdCargo 
f 
x 
c 
 VrSalario > 500 
Processamento de consultas: visão geral 
Passo 3: Colocar a restrição mais restritiva em primeiro lugar 
 
Em uma situação normal, espera-se que haja um número maior de linhas referentes a 
cargos com VrSalario > 500 (que é uma inigualdade) do que linhas de departamentos 
onde o valor da coluna NmDepto seja igual à constante ‘ADMINISTRACAO’. Inclusive, 
é de se supor que essa coluna seja única, não permitindo valores duplicados. Com isso, 
qualquer comparação de igualdade sobre essa coluna deve retornar no máximo uma linha. 
Portanto, restrições como essa, se forem executadas antes das outras, vão gerar umnúmero menor de combinações com as outras tabelas nas etapas seguintes. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 NmFunc 
 c cargos 
 f funcionarios 
 d deptos 
 f.CdCargo = c.CdCargo 
x 
c 
 VrSalario > 500  f.CdDepto = d.CdDepto 
 NmDepto = 'ADMINISTRACAO' 
d 
f 
x 
Processamento de consultas: visão geral 
 
Obs.: Calcular o número total de linhas processado se este plano de execução for 
adotado. Supor que a tabela funcionarios possui 10 linhas, a tabela cargos, 6 linhas e a 
tabela deptos, 4 linhas. 
 
Passo 4: Introduzir junções quando apropriado 
 
Combinações de produtos cartesianos com restrições correspondentes a equações de 
junção devem ser substituídas por operações de junção, que costumam ter 
implementações internas mais eficientes. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 NmFunc 
 c cargos 
 f funcionarios 
 d deptos 
|x| f.CdCargo = c.CdCargo 
c 
 VrSalario > 500 
 NmDepto = 'ADMINISTRACAO' 
d 
f 
|x| f.CdDepto = d.CdDepto 
Processamento de consultas: visão geral 
Passo 5: Antecipar as projeções 
 
Assim como antecipar restrições é interessante para diminuir a quantidade de linhas 
processadas, antecipar projeções também contribui para reduzir o volume total de dados 
manipulados já que descarta colunas que não são usadas no processo. Observe que as 
projeções intermediárias contêm tanto as colunas necessárias à projeção final como 
também os atributos de relacionamento necessários às junções subseqüentes. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Obs.: Calcular o número total de linhas processado se este plano de execução for 
adotado. Supor que a tabela funcionarios possui 10 linhas, a tabela cargos, 6 linhas e a 
tabela deptos, 4 linhas. 
 NmFunc 
 c cargos 
 f funcionarios 
 d deptos 
|x| f.CdCargo = c.CdCargo 
c 
 VrSalario > 500 
 c.CdCargo |x| f.CdDepto = d.CdDepto 
 NmDepto = 'ADMINISTRACAO' 
d 
 d.CdDepto 
f 
 NmFunc, f.CdCargo, f.CdDepto 
Geração de planos de execução 
Geração de planos de execução 
Algoritmos para a classificação (ordenação) de dados 
Classificação interna: é aquela em que todos os dados estão na memória principal 
(memória RAM). Existem diversos métodos clássicos para esse fim, como por exemplo, 
seleção direta, bubblesort ou quicksort, que são descritos e avaliados na literatura sobre 
lógica de programação e estruturas de dados, como por exemplo [ZIVIANI, 1999]. 
Classificação externa: é a ordenação de dados que encontram-se armazenados em disco e 
não podem ser carregados em sua totalidade para a memória principal, como 
freqüentemente ocorre nos bancos de dados comerciais, onde o volume de dados em 
determinadas tabelas pode ser muito grande. 
Uma abordagem bastante comum para classificação interna é a chamada Merge-Sort 
[GARCIA-MOLINA et al., 2001; SILBERSCHATZ et al., 1999], que procura dividir o 
conjunto de dados a ser ordenado em partes que caibam na memória principal, ordena 
cada parte através de um método de classificação interna qualquer (geralmente o 
QuickSort) e depois combina (merge) os diversos subconjuntos ordenados de maneira a 
produzir um resultado final totalmente classificado. 
m  CalcSegmentos( R ) ; 
Para i de 1 até m Faça 
Início 
 T  LeSegmento( R, i ) ; 
 OrdenaSegmento( T, Xi ) ; 
Fim ; 
 
Para i de 1 até m Faça 
 Bi  LeBlocoTemp( Xi ) ; 
 
Y  { } ; 
Para j de 1 até n Faça 
Início 
 r  ExtraiMenor( B1 .. Bm ) ; 
Y  Y + r ; 
Fim ; 
 
Observações: 
a) A subrotina CalcSegmentos( <conjunto de dados> ) calcula 
quantos subconjuntos devem ser gerados para o conjunto 
informado, de maneira que cada subconjunto caiba na memória 
disponível no sistema. 
Geração de planos de execução 
b) A subrotina LeSegmento( <conjunto de dados>, <número> ) faz a 
leitura de todo o conteúdo do segmento do conjunto de dados cujo 
número é informado no segundo parâmetro. 
c) A subrotina OrdenaSegmento( <segmento>, <arq. temporário> ) 
aplica um método de classificação interna sobre o segmento e 
grava seus dados ordenados no arquivo temporário indicado. 
d) A subrotina LeBlocoTemp( <arq. temporário> ) retorna um ou 
mais blocos de dados do arquivo temporário indicado e o armazena 
em um buffer de memória específico. 
e) A subrotina ExtraiMenor( <lista de buffers> ) verifica qual é a 
linha de menor valor para a expressão chave de ordenação entre os 
m buffers presentes na memória, elimina essa linha da memória e 
devolve seu valor para a rotina que a chamou. Se o buffer do qual a 
linha foi extraída ficar vazio, uma nova chamada à subrotina 
LeBlocoTemp é realizada para ele. 
f) A operação + indica uma união onde elementos (no caso linhas) 
repetidos são aceitos no resultado final. 
Algoritmos para o processamento de junções 
Existem diversas abordagens para o processamento de junções, sendo que cada uma 
comporta inúmeras variações visando melhorias de desempenho para o tratamento de 
situações específicas. As principais abordagens são denominadas nested loops (laços 
aninhados), merge scan (junção por busca e intercalação) e hash join (junção hash). 
Nested loops: é a abordagem mais simples e de propósito geral, que apresenta um alto 
custo computacional, muitas vezes sendo chamada de método da força bruta [DATE, 
2000]. Uma relação é processada no looping mais externo e a outra no looping mais 
interno, podendo ocorrer ou não o uso de um índice, conforme mostram os algoritmos a 
seguir. 
Sem índice 
T  { } ; 
Para i de 1 até n Faça 
Início 
r  Ri ; 
Para j de 1 até m Faça 
Início 
s  Sj ; 
Se s.ExpChave = r.ExpChave Então 
T  T  ( s * r ) ; 
Fim ; 
Fim ; 
Geração de planos de execução 
Observações: 
a) <var>  <tabela>j indica que o conteúdo da linha localizada na posição j 
da tabela é lido para a variável de memória. 
b) Número de linhas de tabela lidas com esta abordagem: n + n * m. 
 
Com índice 
T  { } ; 
Para i de 1 até n Faça 
Início 
r  Ri ; 
j  Pesq( ÍndiceDeS, r.ExpChave ) ; 
s  Sj ; 
Enquanto s.ExpChave = r.ExpChave Faça 
Início 
T  T  ( s * r ) ; 
j  Prox( ÍndiceDeS ) ; 
s  Sj ; 
Fim ; 
Fim ; 
Observações: 
a) <var>  <tabela>j indica que o conteúdo da linha localizada na posição j 
da tabela é lido para a variável de memória. 
b) A subrotina Pesq( <índice>, <chave> ) faz a busca de um valor chave no 
índice mencionado no primeiro parâmetro, retornando a posição da 
primeira linha com esse valor na tabela. 
c) A subrotina Prox( <conjunto de dados> ) faz a leitura seqüencial da 
próxima linha de uma tabela ou índice. 
d) Número de linhas de tabela lidas com esta abordagem: n + m. 
Merge scan: implementa um balanced line entre as duas relações a serem combinadas, 
que devem estar ordenadas de acordo com os atributos utilizados na expressão de junção. 
É eficiente em situações em que não existem índices adequados para a junção e em que o 
otimizador estima que o número de linhas a serem recuperadas nas duas tabelas é grande. 
Geração de planos de execução 
T  { } ; 
r  R1 ; 
s  S1 ; 
Enquanto r  Null ^ s  Null Faça 
Início 
Chave  Maior( r.ExpChave, s.ExpChave ) ; 
Enquanto s.ExpChave < Chave Faça 
s  Prox( S ) ; 
Enquanto r.ExpChave < Chave Faça 
r  Prox( R ) ; 
j  Pos( r, R ) ; 
Enquanto s.ExpChave = Chave Faça 
Início 
r  Rj ; 
Enquanto r.ExpChave = Chave Faça 
Início 
T  T  ( s * r ) ; 
r  Prox( R ) ; 
Fim ; 
s  Prox( S ) ; 
Fim ; 
Fim ; 
Observações: 
a) <var>  <tabela>j indica que o conteúdo da linha localizada na 
posição j da tabela é lido para a variável de memória. 
b) A subrotina Maior( <expressão1>, <expressão2> ) devolve 
<expressão1> se esta for maior ou igual a <expressão2> ou, caso 
<expressão2> seja maior que <expressão1>, devolve o valor de 
<expressão2>. 
c) A subrotina Pos( <tupla>, <conjunto de dados> ) devolve a 
posição que a tupla informada ocupa no conjunto dedados. 
d) A subrotina Prox( <conjunto de dados> ) faz a leitura seqüencial 
da próxima linha de uma tabela ou índice. 
 
Geração de planos de execução 
Hash join: armazena uma das tabelas na memória principal adotando uma estrutura hash 
com base nos valores de sua chave. Em seguida, gera os resultados fazendo a leitura 
simples (via índice ou não) da tabela remanescente e determinando as correspondências 
com a primeira tabela por meio da aplicação da função hash sobre a coluna chave do 
relacionamento. É uma solução interessante para situações em que uma das tabelas cabe 
totalmente na memória principal. 
b  CalcBuckets( R ) ; 
Para i de 1 até b Faça 
 Bj  { } ; 
 
Para i de 1 até n Faça 
Início 
r  Ri ; 
 j  Hash( r ) ; 
 Bj  Bj  r ; 
Fim ; 
 
T  { } ; 
Para i de 1 até m Faça 
Início 
s  Si ; 
j  Hash( s ) ; 
r  PesqBucket( s, Bj ) ; 
T  T  ( s * r ) ; 
Fim ; 
Observações: 
a) A subrotina CalcBuckets( <tabela> ) determina o número de 
buckets necessários para armazenar o conteúdo da tabela em uma 
estrutura hash na memória e seleciona uma função hash para fazer 
o mapeamento correspondente. 
b) <var>  <tabela>j indica que o conteúdo da linha localizada na 
posição j da tabela é lido para a variável de memória. 
c) A subrotina Hash( <tupla> ) recebe uma tupla e calcula o número 
do bucket correspondente à chave dessa tupla. 
d) A subrotina PesqBucket( <tupla>, <bucket> ) pesquisa e retorna 
uma tupla dentro de um bucket que possua correspondência com a 
chave da tupla fornecida no primeiro parâmetro. 
 
Geração de planos de execução 
Elementos que afetam a eficiência de um plano de execução 
 volume de dados a serem processados 
 algoritmos disponíveis 
 existência de estatísticas atualizadas 
 organização física dos dados 
 tamanho de página 
 existência de índices, clusters, hashing 
 
Estratégia de seleção de planos baseada em regras 
Nesta abordagem, o otimizador não faz uso de estatísticas, e procura adotar uma solução 
baseada em heurísticas e no custo presumido para o conjunto de operações previsto no 
plano de execução. Em resumo, esta modalidade envolve as seguintes etapas: 
a) Vários planos de execução são gerados 
b) Para cada plano é atribuído um grau de dificuldade, com base na tabela de custos 
estimados dos caminhos de acesso 
c) O plano com menor grau de dificuldade é adotado. 
O quadro a seguir apresenta um ranking dos caminhos de acesso no Oracle em ordem 
crescente de custo presumido, onde quanto maior o grau do caminho de acesso, maior o 
custo estimado para o processamento. Todo o conjunto de regras adotado pelo otimizador 
baseia-se nesse ranking, uma vez que nessa modalidade não se faz uso de estatísticas 
sobre o estado do banco de dados no momento da consulta. 
Geração de planos de execução 
 
Grau Caminho de acesso e exemplos 
1 Uma linha por RowId (“single row by RowId”) 
 
SELECT * 
 FROM Clientes 
 WHERE RowID = ‘00003894024033750001’ 
2 Uma linha por junção no cluster (“single row by cluster join”) 
 
SELECT * 
 FROM Contas c, CliContas cc 
 WHERE c.NrConta = cc.NrConta AND c.NrConta = '1027' 
3 Uma linha por chave hash com coluna única ou chave primária (“Single row 
by hash cluster key with unique or primary key”) 
 
SELECT * 
 FROM Agencias 
 WHERE CdAgencia = ‘0060’ 
4 Uma linha por chave única ou chave primária (“single row by unique or 
primary key”) 
 
SELECT * 
 FROM Clientes 
 WHERE CdCliente = ‘00001’ 
5 Várias linhas por junção em cluster (“cluster join”) 
 
SELECT * 
 FROM Contas c, CliContas cc 
 WHERE c.NrConta = cc.NrConta 
6 Várias linhas através de chave hash (“hash cluster key”) 
 
SELECT * 
 FROM Gerentes 
 WHERE CdAgencia = '0040' ; 
7 Várias linhas, pela chave do cluster indexado (“indexed cluster key”). 
 
SELECT * 
 FROM CliContas 
 WHERE NrConta = '1021' ; 
8 Várias linhas com chave composta (“composite key”) 
 
SELECT * 
 FROM Gerentes 
 WHERE TpGerente = 'C' AND NmGerente LIKE 'J%' ; 
9 Índice de chave não composta (“single column indexes”) 
 
SELECT * 
 FROM Contas 
 WHERE CdAgencia = ‘0060’ 
 
Geração de planos de execução 
 
Grau Caminho de acesso e exemplos 
10 Busca de faixa limitada de valores em coluna indexada (“bounded range 
search on indexed columns”) 
 
SELECT * 
 FROM Movimentos 
 WHERE DtMov BETWEEN ‘01/01/99’ AND ‘31/12/99’ ; 
11 Busca de faixa não limitada em coluna não indexada (“unbounded range 
search on indexed columns”) 
 
SELECT * 
 FROM Movimentos 
 WHERE DtMov > ‘01/01/99’ ; 
12 Junção sort merge (“sort merge join”). Para fins didáticos, é conveniente que 
não haja índices para as colunas da junção. 
 
SELECT NmGerente 
 FROM Gerentes, Clientes 
 WHERE NmGerente = NmCliente ; 
13 Valores máximo ou mínimo em coluna indexada (“Max or min of indexed 
columns”) 
 
SELECT MIN( DtMov ) 
 FROM Movimentos ; 
14 Order by em coluna indexada (“order by on indexed columns”) 
 
SELECT * 
 FROM Movimentos 
 ORDER BY NrConta ; 
15 Acesso seqüencial à tabela ( “full table scan”) 
 
SELECT * 
 FROM Movimentos 
 WHERE VrMov < 50 AND TpMov = ‘C’ ; 
 
Estratégia de seleção de planos baseada em custos 
 conceito e computação de custos 
 estatísticas úteis para a otimização de consultas 
- número de linhas da tabela 
- tamanho da linha 
- número de páginas ocupadas pela tabela 
- número de níveis do índice 
- número de valores distintos para uma coluna 
Geração de planos de execução 
- maior e menor valor para uma coluna 
- seletividade da coluna 
Geração de planos de execução 
Prática de laboratório 
Instruções para atualização de estatísticas no catálogo do banco de dados 
 
Oracle: 
Estatísticas principais ficam armazenadas nas visões ALL_TABLES, 
ALL_TAB_COLUMNS E ALL_INDEXES do catálogo. 
 
ANALYZE TABLE <nome_tabela> COMPUTE STATISTICS ; 
ANALYZE TABLE <nome_tabela> ESTIMATE STATISTICS ; 
ANALYZE TABLE <nome_tabela> DELETE STATISTICS ; 
ANALYZE INDEX <nome_índice> COMPUTE STATISTICS ; 
 
MS-SQL Server: 
As estatísticas são atualizadas automaticamente nas versões mais recentes do SGBD. 
 
UPDATE STATISTICS <nome_tabela> 
UPDATE STATISTICS <nome_tabela> WITH FULLSCAN, ALL 
UPDATE STATISTICS <nome_índice> 
 
DB2: 
RUNSTATS ON TABLE <nome_tabela> WITH DISTRIBUTION AND DETAILED 
INDEX 
 
Utilização do recurso Explain Plan no Oracle 
A instrução Explain Plan permite visualizar o plano de acesso escolhido pelo otimizador 
para processar uma consulta. Os detalhes do plano são armazenados em uma tabela 
chamada Plan_Table, que deve ser criada por meio do script UtlXplan.sql, que 
geralmente fica armazenado na pasta %ORACLE_HOME%\Rdbms\Admin. 
Para analizar o plano de uma consulta, emite-se o comando Explain Plan, conforme a 
sintaxe a seguir: 
 EXPLAIN PLAN 
 SET STATEMENT_ID = <Rótulo para consulta> 
 INTO PLAN_TABLE 
 FOR 
 <instrução SQL> ; 
O rótulo da consulta é um texto livre de até 30 caracteres que será utilizado para 
identificá- la posteriormente para visualizar o plano de acesso. 
Exemplo: 
EXPLAIN PLAN 
SET STATEMENT_ID = 'MovData' 
INTO PLAN_TABLE 
FOR 
 SELECT * FROM Movimentos WHERE DtMov > '01/01/99' ; 
Geração de planos de execução 
Com isso, o otimizador definirá um plano de acesso e o registrará na plan table, 
indicando que ele se refere a uma consulta chamada ‘MovData’. Para cada etapa do plano 
é inserida uma linha nessa tabela de resultados e para visualizarmos esse conteúdo é 
necessário fazer um SELECT sobre a plan table, como no exemplo a seguir: 
SELECT LPAD( ' ', 2 * Level ) || Operation 
 || ' ' || Options || ' ' || Object_Name || ' ' 
 || DECODE( Optimizer, NULL, ' ', Optimizer ) || ' ' 
 || DECODE( Cost, NULL, ' ', ' Custo = ' || Cost 
 || ' linhas esperadas = ' || Cardinality ) Plano 
FROM Plan_Table 
START WITH ID = 0 AND Statement_ID = 'MOVDATA' 
CONNECT BY PRIOR ID = Parent_ID AND Statement_ID = 'MOVDATA'; 
Observe que o valor para a coluna Statement_ID é aquele rótulo informado na instrução 
Explain Plan, e que esse valor é armazenado em maiúsculas na plan table. O resultado é 
exibido de maneira a indicar as operações mais externas próximas à margem esquerda da 
tela e as mais internas, deslocadas para a direita, conforme mostra o exemplo: 
PLANO 
----------------------------------------------------------------------- 
 SELECT STATEMENT CHOOSE 
 NESTED LOOPS 
 TABLE ACCESS BY ROWID CONTAS 
 INDEX UNIQUE SCAN CO_PK_NRCONTA 
 TABLE ACCESS CLUSTER CLICONTAS 
Esse resultado indica o algoritmo de junção adotado (Nested loops, no caso), a ordem e a 
forma pela qual as tabelas são acessadas e os índices que são utilizados, permitindo ao 
analista verificar se a estratégia de processamento adotada corresponde ao esperado. Em 
resumo, o processo de análise pode ser resumido graficamente conforme mostra a figura 
a seguir. 
Comando 
Explain Plan 
Geração do 
Plano de 
Execução Instrução 
SQL DML + 
Statement_Id 
 
Catálogo do 
Banco de Dados 
Índices, 
Tabelas, 
Chaves 
 
Plan_Table 
Visualização 
Plan_Table 
Resultado da 
Análise + 
Statement_ID 
Análise + 
Statement_ID 
Level 
Statement Execution Plan 
Optimizer 
Relatório da 
Análise 
Geração de planos de execução 
Fornecendo dicas ao otimizador 
Oracle: 
Forçando a utilização de um índice: 
SELECT /*+ INDEX( movimentos mv_ix_dtmov ) */ NrMov, VrMov, TpMov 
 FROM Movimentos 
 WHERE NrConta = '1021' AND DtMov = '01/09/96' 
 ORDER BY DtMov ; 
Forçando a leitura direta da tabela: 
SELECT /*+ FULL(Clicontas) */ * 
 FROM CliContas 
 WHERE NrConta = '1021' ; 
 
Interbase: 
Forçando a utilização de um índice: 
SELECT NrMov, VrMov, TpMov 
 FROM Movimentos 
 WHERE NrConta = ‘1021’ AND DtMov = ‘01/09/96’ 
 ORDER BY DtMov ; PLAN( Movimentos INDEX( MV_IX_DTMOV ) ) 
 
MS-SQL Server: 
Forçando a utilização de um índice: 
SELECT NrMov, VrMov, TpMov 
 FROM Movimentos ( index = mv_ix_dtmov ) 
 WHERE NrConta = ‘1021’ AND DtMov = ‘01/09/96’ 
 ORDER BY DtMov 
 
 
 
 
Referências bibliográficas 
AHO, Alfred V.; SETHI, Ravi & ULLMAN, Jeffrey D. Compiladores: Princípios, Técnicas 
e Ferramentas. Rio de Janeiro: Guanabara Koogan, 1995. 344 p. 
BROBOWSKI, Steven M. Dominando o Oracle 7. São Paulo: Makron Books, 1995. 
COREY, Michael; ABBEY, Michael; ABRAMSON, Ian & TAUB, Ben. Oracle 8i Data 
Warehouse. Rio de Janeiro: Campus, 2001. 817 p. 
DATE, C.J. 2000. Introdução a Sistemas de Bancos de Dados. 3a Ed. Rio de Janeiro: 
Campus. 873 p. 
DATE, C.J. Introdução a sistemas de bancos de dados. Rio de Janeiro: Campus, 1991. 674 
p. 
ELMASRI, Ramez e NAVATHE, Shamkant B. 2000. Fundalmentals of database systems. 
Reading: Addison Wesley. 955 p. 
GARCIA-MOLINA, Hector; ULLMAN, Jeffrey D. e WIDOM, Jennifer. 2001. 
Implementação de sistemas de bancos de dados. Rio de Janeiro: Campus. 685 p. 
HIPSLEY, Paul. Developing Client / Server Applications with Oracle Developer / 2000. 
Indianapolis: SAMS Publishing, 1996. 
KORTH, H.F. & SILBERSCHATZ A. Sistema de Banco de Dados. 2ª Ed. Rev. São Paulo: 
Makron Books, 1995. 
LONEY, Kevin & THERIAULT, Marlene. Oracle 8i: O manual do DBA. Rio de Janeiro: 
Campus, 2000, 972 p. 
MELO, Rubens N. et al. Banco de Dados em Aplicações Cliente-Servidor. Rio de Janeiro: 
Livraria e Editora InfoBook, 1997. 
SILBERSCHATZ, Avi; KORTH, Henry; SUDARSHAN S. Sistema de Banco de Dados. 3a 
ed. São Paulo: Makron Books, 1999. 778 p. 
SPENIK, Mark & SLEDGE, Orryn. Microsoft SQL ServerTM 2000 DBA: Guia de 
sobrevivência. Rio de Janeiro: Campus, 2001, 771 p. 
TANENBAUM, Andrew S. Sistemas operacionais modernos. Rio de Janeiro: Prentice-Hall 
do Brasil, 1995, 493 p. 
Tuning de Consultas. Apostila do curso empresarial 2, ministrado durante o XVI SBBD da 
SBC em outubro de 2001 no IME, Rio de Janeiro, pelo professor Paulo Guerra. 
WHALEN, Edward. Oracle: Performance Tuning and Optimization. Indianapolis: SAMS 
Publishing, 1996. 
YONG, Chu Shao. Banco de Dados: Organização, sistemas e administração. São Paulo: 
Atlas, 1983. 398 p. 
ZIVIANI, Nivio. Projeto de algoritmos com implementações em Pascal e C. 4a Ed. São 
Paulo: Pioneira, 1999, 267 p.