Processamento e Otimização de Consultas

Mdulo VI: Processamento e

Otimizao de Consultas

(Aulas 1-5)

Clodis Boscarioli

Banco de Dados I

2007

Agenda:

O Processador de Consultas:

Conceitos Principais.

Algoritmos usados para implementar operaes algbricas;

Otimizao Baseada em Custo;

Otimizao Heurstica;

Comentrios sobre otimizao no PostgreSQL.

Viso Geral de um SGBD

SGBD

Usurios

Dicionriode dados

Interface comaplicaes

Programas deaplicaes

Consultas(queries)

Esquema de Banco de Dados

Usuriosnavegantes

Programadoresde aplicaes

Usuriossofisticados

Administra-dores de BD

Processadorde consultas

Gerenciadorde memria

Gerenciadorde transaes

Gerenciador de buffer

Gerenciadorde arquivos

InterpretadorDDL

CompiladorDML

Pr-compiladorde comandosDML

Programas deaplicaes em cdigo objeto

Componentes de execuode consultas

Armazenamento

em disco ndices

Arquivos dedados

Dados estatsticos BD

Processar consultas envolve: Traduzir consultas expressas em linguagens de alto nvel (como SQL) em expresses que podem ser implementadas no nvel fsico do sistema de banco de dados (nvel de tabelas);

Otimizar a expresso destas consultas; Avaliar a base de dados de acordo com as diretrizes da consulta, para fornecer o resultado.

Processamento de Consultas

Processamento de Consultas

Consulta SQL

adequada para uso humano;

No adequada ao processamento pelo SGBD:

No descreve uma seqncia de passos (procedimento) a ser seguida;

No descreve uma estratgia eficiente para a implementao de cada passo no que tange o acesso em nvel fsico (arquivos do BD).

Cabe ao SGBD deve se preocupar com este processamento mdulo Processador de Consultas.

Mdulo Processador de Consultas

Objetivo: Otimizao do processamento de uma consulta

Traduo, transformao e gerao de uma estratgia (plano) de execuo;

Estratgia de acesso: Considera algoritmos predefinidos para implementao de passos do processamento e estimativas sobre os dados.

O esforo valido, pois quase sempre

Tx

Passos no Processamento de Consultas

ConsultaExpresso algbricarelacional

Plano de execuo

Sada daconsulta

Analisadorsintticoe tradutor

Avaliador

Otimizador

Dados Metadados


Plano de execuo

Sada daconsulta


Avaliador

Otimizador

Dados Metadados

Anlise lxica- clusulas SQL e nomes vlidos.

Anlise sinttica- validao da gramtica.

Anlise semntica- nomes usados de acordo com a estrutura

do esquema. Converso para uma rvore algbrica

da consulta



Plano de execuo

Sada daconsulta


Avaliador

Otimizador

Dados Metadados

Definio de uma rvore de consulta equivalente

- chega ao mesmo resultado- processa de forma mais eficiente

Fase chamada de Otimizao AlgbricaOtimizao Algbrica



Plano de execuo

Sada daconsulta


Avaliador

Otimizador

Dados Metadados

Anlise de alternativas de definio de

estratgias de acesso

- escolha de algoritmos para implementao de operaes- existncia de ndices- estimativas sobre os dados(tamanho de tabelas, seletividade, ...)



Plano de execuo

Sada daconsulta


Avaliador

Otimizador

Dados Metadados

FOCO:

OTIMIZADOR DE

CONSULTA


Exemplo Introdutrio

Suponha a consulta:select saldofrom contawhere saldo < 2500;

Esta pode ser traduzida nas duas expresses algbricas relacionais diferentes:

saldo < 2500 ( saldo (conta))

saldo ( saldo < 2500(conta))

Alm desta variao, possvel executar cada operao algbrica relacional usando um entre diversos algoritmos diferentes. Por exemplo: Para executar a seleo, podemos procurar em todas as tuplas de conta a fim de encontrar as tuplas com saldo menor 2.500.

Se um ndice rvore-B+ estiver disponvel no atributo saldo, podemos usar o ndice em vez de localizar as tuplas.

necessrio prover as expresses algbricas de anotaes que permitam especificar como sero avaliadas.

Exemplo Introdutrio

Uma operao algbrica relacional anotada com instrues sobre como ser avaliada chamada de avaliao primitiva.

Vria avaliaes primitivas podem ser agrupadas em pipeline, e executadas em paralelo.

Uma seqncia de operaes primitivas um plano de execuo de consulta ou plano de avaliao de consulta.

Exemplo Introdutrio

saldo

saldo < 2500 (use ndice 1)

conta

Uma vez escolhido o plano de consulta, a consulta avaliada com aquele plano e o resultado da consulta produzido

Exemplo Introdutrio

Otimizao de Consultas

Existem 2 tcnicas bsicas para otimizao de consultas:

As baseadas em heursticas para a ordenao de acesso ao banco de dados, que participaro da estratgia de acesso;

e as que estimam sistematicamente o custo de estratgias de execuo diferentes e escolhem o

plano de execuo com o menor custo estimado.

Catlogo de Informaes para Estimativa de Custo

nr: o nmero de tuplas na relao r;

br: o nmero de blocos que contm tuplas da relao r;

sr: o tamanho em bytes de uma tupla da relao r;

fr: o fator de bloco da relao r, ou seja, o nmero de tuplas da relao r que cabe em um bloco;

V(A,r): o nmero de valores distintos que aparecem na relao r para o atributo A. Esse valor igual ao tamanho (em nmero de tuplas) de A(r). Se A uma chave para a relao r, V(A,r) nr.

SC(A,r): a cardinalidade de seleo (seletividade) do atributo A da relao r.

Dados uma relao r e um atributo A da relao, SC(A,r) o nmero mdio de registros que satisfazem uma condio de igualdade no atributo A, dado que pelo menos um registro satisfaz a condio de igualdade.

Exemplo: SC(A,r) = 1 se A um atributo-chave de r; Para um atributo que no chave, estimamos que os valores distintos de V(A,r) so distribudos uniformemente entre as tuplas, produzindo SC(A,r) = (nr / V(A,r))


As duas ltimas estatsticas podem ser estendidas de forma a valer para um conjunto de atributos, ao invs de valer para apenas um atributo.

Se as tuplas da relao r estiverem armazenadas fisicamente juntas em um arquivo, a seguinte equao vlida:

Br = [nr, fr]


Informaes sobre ndices: fi: o fan-out (nmero de ponteiros) mdio dos ns internos do ndice i para ndices estruturados em rvore, como rvores B+;

HTi: o nmero de nveis no ndice i, ou seja, a altura do ndice i.

LBi: o nmero de blocos de ndice de nvel mais baixo no ndice i, ou seja, o nmero de blocos no nvel de folha do ndice (o nmero de blocos que contm os registros folha de um ndice).


As variveis estatsticas so usadas para estimar o tamanho do resultado e o custo para vrias operaes e algoritmos.

A estimativa de custo do algoritmo A EA.

Para manter as estatsticas precisas, toda vez que uma relao for modificada tem-se que atualizar as estatsticas. Contudo, a maioria do sistema no atualiza as estatsticas em todas as modificaes. Atualiza-as periodicamente.

Quanto mais informaes forem utilizadas para estimar o custo da consulta e quanto mais precisas forem essas informaes, melhores sero as estimativas de custo.


Medidas do Custo de uma Consulta

O custo de uma consulta pode ser estimado de diversas formas:

Por acessos a disco; Por tempo de uso da CPU; Pelo tempo de comunicao nos BD paralelos e/ou distribudos;

O tempo de execuo de um plano poderia ser usado para estimar o custo da consulta, contudo em grandes sistemas de BD, utiliza-se o nmero de acessos a disco, porque estes estabelecem o tempo crtico de execuo do plano (j que so lentos quando comparados s operaes realizadas em memria).

Para simplificar nossos clculos assumiremos que todas as transferncias de blocos (do disco para memria) tm o mesmo custo. Desconsideraremos o tempo de latncia e o tempo de busca. Tambm desconsideramos o custo de escrever o resultado final de uma operao de volta para o disco.

Os custos dos algoritmos dependem significativamente do tamanho do buffer na memria principal. No melhor caso, todos os dados podem ser lidos para o buffer e o disco no precisa ser acessado novamente. No pior caso, supomos que o buffer pode manter apenas alguns blocos de dados aproximadamente um bloco por relao. Geralmente faremos a suposio do pior caso.

Medidas do Custo de uma Consulta

Operao de Seleo

a varredura de arquivos: o operador de mais baixo nvel para se ter acesso aos dados.

So algoritmos de procura que localizam e recuperam os registros que esto de acordo com uma condio de seleo.

Tem-se vrios algoritmos diferentes, que variam de acordo com a complexidade da seleo e o uso ou no de ndices.

Exemplo de algoritmos usados na implementao do operador select:

Busca Linear (ou fora bruta); Busca Binria; Utilizao de ndice primrio (atributo chave); Utilizao de ndice primrio para recuperar mltiplosregistros (atributo chave);

Utilizao de um ndice cluster para recuperarmltiplos registros (atributo no chave);

Utilizao de um ndice secundrio (rvore B+) emuma comparao de igualdade;

Busca para selees complexas

Operao de Seleo

Busca para selees complexas:

Se uma condio de uma instruo select uma condio conjuntiva ou seja, formada por diversas condies simples conectadas pelo conectivo lgico AND, o SGBD pode usar os seguintes mtodos:

Seleo conjuntiva utilizando um ndice individual; Seleo conjuntiva utilizando um ndice composto; Seleo conjuntiva por meio da interseo de registros.

Operao de Seleo

Busca para selees complexas:

Se uma condio de uma instruo select uma condio disjuntiva ou seja, formada por diversas condies simples conectadas pelo conectivo lgico OR, a otimizao mais simples.

Pouca otimizao pode ser feita, pois os registros que satisfazem a condio disjuntiva so a unio dos registros que satisfazem as condies individuais.

Operao de Seleo

Veremos dois deles (os bsicos):

Aquele que envolve uma Busca Linear; Aquele que envolve uma Busca Binria.

Considere uma operao de seleo em uma relao cujas tuplas so armazenadas juntas em um nico arquivo.

Operao de Seleo

Seleo por Busca Linear A1

Em uma busca linear, cada bloco de arquivo varrido e todos os registros so testados para verificar se satisfazem a condio de seleo.

Como todos os blocos precisam ser lidos, EA1 = br.

No caso da seleo ser aplicada em um atributo-chave, podemos supor que a metade dos blocos varrida antes de o registro ser encontrado, ponto no qual a varredura termina. A estimativa ento ser EA1 = (br/2).

Seleo por Busca Binria A2

Se o arquivo ordenado em um atributo e a condio de seleo uma comparao de igualdade neste atributo, podemos usar uma busca binria para localizar os registros que satisfazem a seleo.

Neste caso, a estimativa :

EA2 = [log2(br)] + [SC(A,r)/fr] -1

O primeiro termo [log2(br)] contabiliza o custo para localizar a primeira tupla por meio da busca binria nos blocos;

O nmero total de registros que satisfaro a seleo SC(A,r), e esses registros ocuparo [SC(A,r)/fr] blocos, dos quais um j havia sido recuperado (por isso o -1).

Se a condio de igualdade estiver em um atributo-chave, ento SC(A,r) = 1, e a estimativa se reduz a EA2 = [log(br)].

Clculo do Custo da Busca Binria

Acesso aos blocos: Primeiro acesso (ao bloco central) no encontro o registro

procurado; Segundo acesso (ao bloco central do lado esquerdo ou direito) .... At o pior caso (nono acesso), o registro encontrando na

ltima diviso disponvel (ou no encontrado).

Para 500 blocos: 500 250 125 62,5 31,25 15,62 7,8 3,9

1,9 (nove divises)

Clculo: log2(500) = 9 29 = 516 (=~ 500)

Exemplo de Seleo por Busca Binria

Suponha as seguintes informaes estatsticas para uma relao conta:

fconta = 20 (ou seja, 20 tuplas de conta cabem em um nico bloco);

V(nome_agncia, conta) = 50 (ou seja, existem 50 agncias com nomes diferentes);

V(saldo, conta) = 500 (ou seja, existe 500 valores diferentes desaldos nesta relao);

nconta = 10.000 (ou seja, a relao conta possui 10.000 tuplas).

Considere a consulta: nome_agncia = Perryridge (conta)

Exemplo de Seleo por Busca Binria

Como a relao tem 10.000 tuplas, e cada bloco mantm 20 tuplas, o nmero de blocos bconta = 500 (10.000/20);

Uma varredura de arquivo simples faria 500 acessos a blocos, supondo que o atributo da condio no fosse atributo-chave. Seno, seriam em mdia 250 acessos;

Suponha que conta esteja ordenado por nome_agncia.

Como V(nome_agncia, conta) = 50, esperamos que 10.000/50=200 tuplas da relao conta pertenam agncia Perryridge;

Essas tuplas caberiam em 200/20 = 10 blocos;

Uma busca binria para encontra o primeiro registro [log2(500)] = 9;

Assim o custo total seria: 9 + 10 1 = 18 acessos a bloco.

A otimizao de consulta para uma operao SELECT necessria principalmente em condies de seleoconjuntiva, sempre que mais de um dos atributosenvolvidos nas condies possurem um caminho de acesso.

O otimizador deve escolher o caminho de acesso querecupera o menor nmero de registros (gera blocos de respostas menores), de maneira mais eficiente.

As selees que separam o menor nmero de tuplasdevem ser realizadas primeiro.

Na escolha entre mltiplas opes o otimizadorconsidera tambm a seletividade de cada condio.

Operao de Seleo

A ordenao bastante importante, uma vez que o algoritmo utilizado:

Na implementao do order by. Como um componente-chave nos algoritmos de sort-merge usado no join, union e intersection e emalgoritmos de eliminao de duplicatas para a operao project.

A ordenao pode ser evitada se um ndice apropriadoexistir de forma a permitir o acesso ordenado aosregistros.

Classificao

Classificao

Formas de ordenao:

Lgica: construo de um ndice na chave de classificao, o qual ser usado para ler a relao na ordem de classificao. A leitura de tuplas na ordem de classificao pode conduzir a um acesso de disco para cada tupla.

Fsica: as tuplas so gravadas de forma ordenada no disco.

Classificao

O problema de classificao pode ser tratado sob duas condies:

Quando a relao cabe completamente na memria principal: Tcnicas padres de classificao (quicksort entre outras) podem ser usadas.

Quando a relao maior que a memria principal classificao externa: Algoritmo comum: sort-merge externo

Para entend-lo, considere M o nmero de frames de pginas no buffer da memria principal ( o nmero de blocos de disco cujos contedos podem ser colocados no buffer da memria principal).

Ordenao Externa

A ordenao externa adequada para manipulararquivos de registros grandes, que so armazenadosem disco e que no cabem inteiramente na memriaprincipal.

A ordenao nesse algoritmo feita por partes estratgia merge-sort.

Fases: Fase de ordenao; Fase de fuso.

Inicializao:

i 1;j b; (tamanho do arquivo em blocos)k n0; (tamanho do buffer em blocos)m (j/k) (maior inteiro)

Fase de ordenao

Enquanto (i

Fase de fuso: fundir os subarquivos at que reste apenas 1

Inicializao

i 1;p logk-1m ; (p o nmero de passagens da fase de fuso)j m;

enquanto (i

Exemplo no Navathe

Se o nmero de blocos do arquivo = 1024 Se o tamanho do buffer = 5 blocos Na fase de ordenao sero criados 205 subarquivos

204 com 5 blocos e 1 com 4 blocos

Na fase de fuso, em cada uma das 4 passagens, sero gravados, respectivamente:

52 subarquivos 13 subarquivos 04 arquivos 01 arquivo

Nmero de subarquivos / tamanho do buffer -1 bloco

Por que -1?Porque um bloco de buffer fica reservado para armazenar um bloco resultado da fuso.

Sort-merge Externo (Korth)

1. Vrias classificaes temporrias so executadas:

i = 0;repeat

leia M blocos da relao, ou o resto da relao, aquilo que for menor;ordene a parte da relao que est na memria;escreva os dados ordenados no arquivo temporrio Ri;i = i + 1;

until o fim da relao

Sort-merge Externo2. Faz-se o merge nos arquivos temporrios. Suponha, por enquanto, que

o nmero total de temporrios, N, seja menor do que M, de forma que se consiga alocar um frame de pgina para um bloco de cada arquivo temporrio e h espao para manter uma pgina de resultado.

leia um bloco de cada um dos N arquivos Ri, para uma pgina de bufferna memria;

repeat

escolha a primeira tupla (na ordem de classificao) entre todas as pginas do buffer;escreva a tupla no resultado e apague-a da pgina de buffer;

if a pgina de buffer de qualquer temporrio Ri est vazia and not fim de arquivo (Ri) then leia o prximo bloco de Ri na pgina de buffer;

until todas as pginas de buffer estarem vazias;

Consideraes Geralmente, se a relao muito maior que a memria, pode haver

M ou mais temporrios gerados na primeira fase, e no ser possvel alocar um frame de pgina para cada temporrio durante a fase de merge.

Neste caso, faz-se a operao de merge em mltiplos passos.

Como h memria suficiente para M-1 pginas de buffer de entrada, cada merge ter M-1 temporrios como entrada.

Funcionamento prximo slide.

Exemplo: Suponha agora que apenas um tupla caiba em um bloco (f = 1), e suponha que a memria mantm trs frames de pgina no mximo. Durante os estgios de merge, dois frames de pgina so usados para entrada e um para o resultado.

Funcionamento

Faz-se o merge sobre os primeiros M-1 temporrios (conforme descrito anteriormente) para obter um nico temporrio para o prximo passo;

Faz-se o merge dos prximos M-1 temporrios de forma semelhante, e assim por diante, at que todos os temporrios iniciais tenham sido processados;

Nesse ponto, o nmero de temporrios foi reduzido a um fator de M1;

Se esse nmero reduzido de temporrios ainda maior ou igual a M, outro passo dado, usando os temporrios criados pelo passo anterior;

Esses passos so repetidos tantas vezes quantas forem necessrias, at que o nmero de temporrios seja menor que M;

Ento, um passo final gera o resultado classificado.

Exemplo

g

a

d

c

b

e

r

d

m

p

d

a

24

19

31

33

14

16

16

21

3

2

7

14

a 19

g 24

d 31

b 14

e 16

c 33

d 21

r 16

m 3

a 14

p 2

d 7

a 19

c 33

b 14

d 31

g 24

e 16

a 14

d 21

d 7

m 3

r 16

p 2

a 14

b 14

a 19

c 33

d 21

d 7

d 31

g 24

e 16

m 3

r 16

p 2

Relao inicial

Criar temporrios

Temporrios

Passo 1:de merge

Temporrios

Passo 2:de merge

Resultado classificado

Nmero de Acessos a Disco

Fase de ordenao:

2 * b, onde b o nmero de blocos do arquivo que est sendo ordenado

Cada bloco b ser acessado duas vezes, uma vez para leitura e outra vez para escrita

Fase de fuso:

2 * (b * log Dm nr), onde Dm o nmero de subarquivos fundidos em cada fuso e nr nmero de subarquivos.

O 2 se d por conta da leitura e escrita de cada bloco O termo interno ao parnteses conta quantas vezes cada bloco

ser analisado (lido e escrito)

Operao de Juno equi_join: designao para uma juno da forma r |X|r.A=s.B s, em que A e B

so atributos ou conjuntos de atributos das relaes r e s, respectivamente.

O exemplo usado ser:depositante |X| cliente

Suponha as seguintes informaes de catlogo:

ncliente = 10.000 fcliente = 25, o que implica bcliente = 10.000/25 = 400 ndepositante = 5.000 fdepositante = 50, o que implica bdepositante = 5.000/50 = 100 V(nome_cliente, depositante) = 2.500, o que implica que, em mdia,

cada cliente tem duas contas

Suponha ainda que nome-cliente em depositante seja uma chave estrangeira vinda de cliente

Estimativa do Tamanho das Junes

O produto cartesiano r X s contm nr * ns tuplas. Cada tupla deste produto cartesiano ocupa sr + ss bytes. Assim podemos calcular o tamanho do produto

cartesiano.

Para juno natural ... Sejam r(R) e s(S) duas relaes: Se R S = , ento r |X| s igual a r X s; Se R S uma chave para R, ento sabemos que uma tupla de s ir juntar-se com no mximo uma tupla de r. Assim, o nmero de tuplas na juno no maior que o nmero de tuplas de s.

Se R S uma chave estrangeira para S vinda de R , ento o nmero de tuplas em r |X| s exatamente igual ao nmero de tuplas em s.


No exemplo: depositante |x| cliente, nome_cliente em depositante uma chave estrangeira vinda de cliente.

O tamanho do resultado exatamente ndepositante, que 5.000;

Com calcular o tamanho da juno quando R S no uma chave para R ou para S?


Suponha que cada valor aparece com probabilidade igual.

Considere uma tupla t de r e suponha R S = {A}.

Estima-se que a tupla t produz

ns / V(A,s)

tuplas em r |X| s, uma vez que esse o nmero mdio de tuplas em s com um determinado valor para os atributos A.

Considerando todas as tuplas em r, estima-se que h

nr * ns / V(A, s)

tuplas em r |X| s.


Observe que se invertermos os papis de r e s, as estimativas resultariam em valores diferentes se V(A,r) V(A,s).

Se isso acontece, h a probabilidade de haver tuplas pendentes que no participam da juno . A estimativa mais baixa ser, provavelmente, a mais precisa.

Tcnicas mais sofisticadas para a estimativa do tamanho da juno devem ser usadas se a hiptese de distribuio uniforme no puder ser considerada.


Calculando a estimativa do tamanho para depositante |X| clientes, sem utilizar informaes sobre chaves entrangeiras.

Como V(nome_cliente, depositante) = 2.500 e V(nome_cliente, cliente) = 10.000, as duas estimativas que obtemos so:

(10.000 * 5.000) / 2.500 = 20.000(5.000 * 10.000)/10.000 = 5.000

Juno de Lao Aninhado

for each tupla tr in r do begin

for each tupla ts in s do begin

teste o par (tr, ts) para ver se satisfazem a condio de juno;se satisfizerem, adicione tr.ts ao resultado

endend

r: relao externas: relao internatr.ts : tupla obtida concatenando os valores dos atributos das tuplas tr e

ts

Juno de Lao Aninhado Este algoritmo no requer ndices e pode ser usado seja qual for a

condio de juno.

um algoritmo caro j que examina todos os pares de tuplas nas duas relaes. O nmero de pares de tuplas a ser considerado nr * ns (para cada registro r tem-se que executar uma varredura completa em s).

No pior caso o buffer pode manter apenas um bloco de cada relao, e um total de nr * bs + br acessos blocos sero necessrios (ou seja, os blocos da relao r (br) so lidos uma vez por ocasio do lao mais externo e, os blocos da relao s (bs) so lidos para cada vez que uma tupla de r precisa ser comparada com todas as tuplas de s por ocasio do lao mais interno)

No melhor caso, h espao suficiente para que ambas as relaes caibam na memria, assim cada bloco ter de ser lido somente uma vez, conseqentemente, apenas br + bs acessos blocos sero necessrios.

Note que, se a relao menor couber completamente na memria, melhor usar essa relao como a mais interna.

Exemplo

Considere a juno natural de depositante e cliente. Suponha que no existem ndices para estas relaes. Suponha que depositante a relao mais externa e cliente a relao mais interna.

5.000 * 10.000 tuplas sero examinadas.

Pior caso: 5.000 * 400 + 100 = 2.000.100 acessos disco.

Melhor caso: 400 + 100 = 500 acessos disco.

Trocando as relaes dos laos internos e externos: 10.000 * 100 + 400: 1.000.400 acessos disco.

Merge-juno (Korth)

Sejam r(R) e s(S) relaes cuja juno natural ser calculada, e seja R S a notao para seus atributos em comum.

Suponha que ambas as relaes estejam classificadas nos atributos R S.

A juno destas relaes pode ser feita por meio de um merge.

pr := endereo da primeira tupla de r;ps := endereo da primeira tupla de s;

while (ps nulo and pr nulo) do

begin

ts := tupla para qual ps aponta;Ss := {ts};configure ps para apontar para a prxima tupla de s;acabou := false;

while (not acabou and ps nulo) dobegin

ts := tupla para qual ps aponta;if (ts[AtribJuno] = ts[AtribJuno])then begin

Ss = Ss {ts};configure ps para apontar para a prxima tupla de s; end

else acabou := verdadeiro;end;

// permanece varrendo s enquanto as tuplas contiverem valores iguais para o atributo de juno, e as coloca em uma relao auxiliar.

tr := tupla para a qual pr aponta;

while ( pr nulo and tr[AtribJuno] < ts[AtribJuno]) dobegin

configure pr para apontar para a prxima tupla de r;tr := tupla para qual pr aponta;

end

// percorre r enquanto no encontrar uma tupla com um valor no atributo de juno igual ou maior ao valor no atributo de juno das tuplas de s que esto na relao auxiliar

while (pr nulo and tr[AtribJuno] = ts[AtribJuno]) dobegin

for each rs in Ss dobegin

adicione ts.tr ao resultado;end

configure pr para apontar para a prxima tupla de r;tr := tupla para a qual pr aponta;

end;

// encontrando a tupla de r que deve ser juntar s tuplas de Ss, realiza a concatenao das tuplas, percorrendo r para ver se existem outras a serem concatenadas.

End;

Merge-juno

Suponha depositante |x| cliente. Com o atributo de juno sendo o nome do cliente. As relaes j esto ordenadas neste atributo.

O custo da juno 400 + 100 = 500 acessos disco.

Caso a exigncia de S caber em memria principal no puder ser atendida, um algoritmo de juno parte deve ser executado para juno tr Ss.

Caso as relaes no estejam ordenadas mas possuam ndices, o merge-juno pode ser executado usando os ndices.

Se os registros de R e S estiverem classificados (ordenados) fisicamente pelos atributos de juno A e B, respectivamente, poderemos implementar a juno da maneira mais eficientepossvel.

Ambos os arquivos so varridos simultaneamente na ordem dos atributos de juno, fazendo a correspondncia dos registros quepossuem os mesmos valores para A e B.

Se os arquivos no estiverem classificados, eles devero ser classificados primeiro por meio de uma ordenao externa.

Pares de blocos de arquivos so ordenadamente copiados parabuffers de memria, e os registros de cada arquivos so varridosapenas uma vez (a menos que A e B no sejam atributos chaves e, nesse caso, o mtodo precisa ser modificado).

ndices proporcionam a capacidade de acessar (varrer) os registrosna ordem dos atributos de juno, mas os registros de fato estofisicamente espalhados pelos blocos do arquivo.

Juno Sort-merge (Navathe)

Juno Sort-merge

A seguir, um esboo do algoritmo para Juno, Projeo, Unio, Interseo e Diferena por meio de sort-merge, quando R possui n tuplas e S possui m tuplas.

T R |X| A=B S

Ordenar as n tuplas de R baseando-se no atributo A;Ordenar as m tuplas de S baseando-se no atributo B;

Inicializar i 1 , j 1;Enquanto (i

{ (* Ri[A] = Sj[B], portanto realizamos o output de uma tupla: resultado

da juno*)output a tupla combinada em T;

(* output outras tuplas correspondentes a Ri se houver*)l j + 1;enquanto (l

T (R)

Criar uma tupla t[] em T para cada tupla t de R;

(*T contm o resultado da projeo ANTES da eliminao de duplicatas*)

Se incluir uma chave de Rento T T;

Seno{

ordenar as tuplas de Tinicializar i 1, j 2;enquanto i

T R SOrdenar as tuplas de R e S utilizando os mesmos e nicos atributos de ordenao;

Inicializar i 1; j 1;Enquanto (i

T R S

Ordenar as tuplas de R e S utilizando os mesmos e nicos atributos de ordenao;


T R - SOrdenar as tuplas de R e S utilizando os mesmos e nicos atributos de ordenao;


Merge-juno - Consideraes

Em relao ao algoritmo apresentado por (Korth): O algoritmo exige que a relao auxiliar caiba na memria principal. Modificaes no algoritmo devem ser feitas caso essa exigncia no possa ser atendida.

Dado que as relaes esto na ordem de classificao, as tuplascom o mesmo valor nos atributos de juno esto em ordem consecutiva. Assim, cada tupla na ordem de classificao precisa ser lida somente uma vez, e, como resultado, cada bloco tambm lido somente uma vez.

Em relao ao algoritmo do Navathe, tem-se que assumir queconjuntos de tuplas com o mesmo valor no atributo de junoprecisam estar carregadas na memria ao mesmo tempo;

Ento, para ambos, o nmero de acessos disco igual soma donmero de blocos em ambos as relaes, br + bs.

Implementao do Outer Join

A juno externa pode ser obtida por meio da modificao dos algoritmos de juno, como a juno de laos aninhados, sort-merge ou de juno hash;

Ou, de forma alternativa e simplificada, por meio da execuo de uma combinao de operadores da lgebra relacional.

Por exemplo, considere a consulta:

select unome, pnome, dnome

from empregado left outer join departamento ondno=dnumero;

Essa operao de juno externa equivalente seguinte seqncia de operaoes da lgebra relacional:


Calcule a juno interna entre as tabelas.

Temp1 unome, pnome, dnome (empregado |X| departamento)

Encontre as tuplas de empregado que no aparecem no resultado da juno.

Temp2 unome, pnome (empregado) - unome, pnome (Temp1)


Complete cada tupla da relao Temp2 com valor nullpara o campo dnome.

Temp2 Temp2 X NULL

Aplique a operao union em Temp1 e Temp2 para produzir o resultado do left outer join.

Resultado Temp1 Temp2

O custo dessa juno externa a soma dos custos da juno interna, das projees e da unio realizadas.


Junes Complexas

Juno com condio conjuntiva:r |X| ... s

As junes nas condies individuais podem ser resolvidas, por exemplo, pelo algoritmo de juno por laos aninhados:

r |X| s, r |X| s, r |X| s e assim por diante.

A juno global por ser realizada calculando, primeiro o resultado de uma dessas junes mais simples e depois testando (a esse resultado) as tuplas produzidas pelas outras junes.

1 2 n

1 2 n

Junes Complexas

Juno com condio disjuntiva:

r |X| ... s

Neste caso, a juno pode ser calculada como a unio dos registros nas junes individuais.

1 2 n

Suponha r1 r2 ... rn em que as junes esto expressas sem ordem. Com n = 3, h 12 ordens de juno diferentes:

r1 (r2 r3)r2 (r1 r3)r3 (r1 r2)r1 (r3 r2)r2 (r3 r1)r3 (r2 r1)(r2 r3) r1(r1 r3) r2(r1 r2) r3(r3 r2) r1(r3 r1) r2(r2 r1) r3

Junes Complexas

Em geral, com n relaes, h (2(n-1))! / (n-1)! Ordens de juno diferentes. Exemplos: Com n = 5 o n 1680 e com n = 7, o n 665.280.

Felizmente, no necessrio gerar todas as expresses equivalentes a uma determinada expresso.

Uma desvantagem da otimizao baseada no custo o custo da prpria otimizao.

Junes Complexas

Duas rvores de consulta (juno) profundas

esquerda

Junes Complexas

O otimizador escolher a rvore que possuir o menor custo estimado.

Com rvores profundas a esquerda, o filho direita considerado ser a relao interna, para o caso da execuo de laos aninhados.

A idia-chave sob o ponto de vista do otimizadorem relao ordem das junes encontrar uma ordem que ir reduzir o tamanho dos resultados intermedirios.

Junes Complexas

Junes Complexas

Considere uma juno envolvendo trs relaes:emprstimo |X| depositante |X| cliente

Neste caso, alm da escolha da estratgia para o processamento da juno, tem-se ainda que escolher qual juno calcular primeiro. Vejamos algumas estratgias:

Estratgia 1: calcule a juno depositante |X| cliente usando qualquer tcnicas. Usando o resultado intermedirio, calcule: emprstimo |X| (depositante |X| cliente);

Estratgia 2: faa como na Estratgia 1, mas calcule primeiro emprstimo |X| depositante, e ento faa a juno do resultado com cliente.

Outra ordem de junes pode ser feita.

Junes Complexas

Estratgia 3: Em vez de executar duas junes, execute o par de junes, da seguinte forma: Construa dois ndices:

Um para o nmero_emprstimo em emprstimo;

Um para o nome_cliente em cliente.

Considere cada tupla t em depositante. Para cada t, procure as tuplas correspondentes em cliente e as tuplascorrespondentes em emprstimo.

Assim, cada tupla de depositante examinada exatamente uma vez.

O custo relativo desse procedimento depende da forma como as relaes esto armazenadas, da distribuio de valores dentro das colunas e da presena de ndices.

Eliminao de Duplicidade

Pode-se implementar a eliminao de duplicidade usando a classificao.

As tuplas idnticas aparecero adjacentes umas s outras aps a classificao, e todas, exceto uma cpia, podem ser removidas.

No sort-merge, as duplicatas encontradas enquanto um temporrio est sendo criado podem ser removidas antes que ele seja escritono disco, reduzindo, assim, o nmero de transferncias de blocos.

Assim, pode-se dizer que o custo de eliminar as duplicatas o custo de classificar uma relao.

Devido ao custo relativamente alto da eliminao de duplicidade, as linguagens de consulta comerciais exigem um pedido explcito do usurio para remover duplicatas; caso contrrio, as duplicatas so mantidas.

Operao de Projeo

Pode-se executar a projeo por meio da execuo da projeo em cada tupla, resultando uma relao que poderia ter registros duplicados, e ento, remover os registros duplicados.

Se os atributos na lista de projeo incluem as chaves da relao (primria e/ou candidatas), nenhuma duplicata existir.

O tamanho de um projeo da forma A(r) calculado como V(A,r), uma vez que a projeo elimina as duplicatas.

Transformaes de Expresses Relacionais

Uma consulta pode ser expressa de diversas maneiras diferentes, com diferentes custos de avaliao.

Equivalncia de Expresses;

Regras de Equivalncia;

Exemplos de Transformaes;

Ordenamento de Junes.

Otimizao Algbrica

Objetivo do passo de transformao

Entrada: rvore da consulta inicial;

Sada: rvore da consulta otimizada (pode manter a mesma rvore).

Base:

Regras de equivalncia algbrica Devem ser conhecidas pelo otimizador para que possam ser geradas transformaes vlidas.

Algoritmo de otimizao algbrica Indica a ordem de aplicao das regras e de outros processamentos de otimizao.

Equivalncia de Expresses

Considerando as tabelas a seguir e suas instncias, encontre os nomes de todos os clientes que possuem uma conta em qualquer agncia localizada no Brooklyn.

nome_cliente ( cidade_agncia = Brooklyn (agncia |X| (conta |X| depositante)))

Para resolver esta expresso, seguindo a forma como ela est escrita, necessrio criar uma relao intermediria grande (a juno das trs relaes, como posto no slide 86).

710000BrooklynBrighton

370000RyeNorth Town

30000BenningtonPownal

8000000HorseneckRound Hill

40000HorseneckMianus

170000HorseneckPerrydige

210000Palo AltoRedwood

900000BrooklynDowntown

fundoscidade_agncianome_agncia

StamfordWalnutGreen

BrooklynSenatorBrooks

WoodsideSand HillGlenn

Palo AltoAlmaJohnson

PittsfieldSpringAdams

PrincetonNassauWilliams

StamfordPutnamTurner

PittfieldParkLindsay

RyeNorthCurry

HarrisonMainHayes

RyeNorthSmith

HarrisonMainJones

cidade_clienterua_clientenome_cliente

A-222Lindsay

A-217Jones

A-201Johnson

A-305Turner

A-102Hayes

A-215Smith

A-101Johnson

nmero_contanome_cliente

agncia

depositante

cliente

750A-217Bringhton

700A-222Redwood

900A-201Bringhton

350A-305Round Hill

400A-102Perryridge

700A-215Mianus

500A-101Downtown

saldonmero_contanome_agncia

conta

Juno (conta |X| depositante)

750A-217Bringhton

700A-222Redwood

900A-201Bringhton

350A-305Round Hill

400A-102Perryridge

700A-215Mianus

500A-101Downtown




8000000HorseneckRound Hill

170000HorseneckPerrydige

40000HorseneckMianus

210000Palo AltoRedwood



A-217Jones

A-222Lindsay

A-201Johson

A-305Turner

A-102Hayes

A-215Smith

A-101Johnson


Juno (agncia |X| (conta |X| depositante))

750A-217Bringhton

700A-222Redwood

900A-201Bringhton

350A-305Round Hill

400A-102Perryridge

700A-215Mianus

500A-101Downtown


Jones

Lindsay

Johson

Turner

Hayes

Smith

Johnson

nome_cliente

Entretanto, somente as tuplas que pertencem s agncias localizadas no Brooklyn so interessantes.

Reescrevendo a consulta, consegue-se eliminar a necessidade de considerar as tuplas que no tm cidade_agncia = Brooklyn, reduzindo o tamanho do resultado intermedirio:

nome_cliente (( cidade_agncia = Brooklyn (agncia)) |X| (conta |X| depositante))


Juno (conta |X| depositante)

750A-217Bringhton

700A-222Redwood

900A-201Bringhton

350A-305Round Hill

400A-102Perryridge

700A-215Mianus

500A-101Downtown


A-217Jones

A-222Lindsay

A-201Johnson

A-305Turner

A-102Hayes

A-215Smith

A-101Johnson


cidade_agncia = Brooklyn (agncia)




750A-217Bringhton

900A-201Bringhton

500A-101Downtown


(cidade_agncia = Brooklyn (agncia)) |X| (conta |X| depositante)

710000BrooklynJones

710000BrooklynJohnson

900000BrooklynJohnson

fundoscidade_agncianome_cliente


nome_cliente

cidade_agncia = Brooklyn

|X|

agncia |X|

conta depositante

(a) rvore da expresso inicial

nome_cliente

cidade_agncia = Brooklyn

|X|

agncia

|X|

conta depositante

(b) rvore da expresso transformada


Dada uma expresso de lgebra relacional, funo do otimizador de consulta propor um plano de avaliao da consulta que gere o mesmo resultado da expresso fornecida e que seja uma maneira menos onerosa de gerar o resultado (ou que, pelo menos, no seja muito mais cara que a maneira mais barata).

Para isso o otimizador precisa gerar planos alternativos que produzam o mesmo resultado da expresso dada e escolher o menos caro.

Uma regra de equivalncia diz que expresses de duas formas so equivalentes se podemos transformar uma na outra preservando a equivalncia.

Preservar a equivalncia significa que as relaes geradas pelasduas expresses tm o mesmo conjunto de atributos e contm o mesmo conjunto de tuplas, embora seus atributos possam estar ordenados de forma diferente.

As regras de equivalncia so usadas pelo otimizador para transformar expresses em outras logicamente equivalentes.

Assuma que:

: denota predicados; L: denotas listas de atributos; E: denota expresses da lgebra relacional.

Regras de Equivalncia Algbrica

1. Operaes de seleo conjuntivas podem ser quebradas em uma seqncia de selees individuais (cascata de ).

1 2 (E) = 1 ( 2 (E))

2. Operaes de seleo so comutativas.

1 ( 2 (E)) = 2 ( 1 (E))

3. Apenas as operaes finais em uma seqncia de operaes de projeo so necessrias, as outras podem ser omitidas (cascata de ).

L1 ( L2 (...( Ln(E))...)) = L1(E)


4. Selees podem ser combinadas com produtos cartesianos e junes teta.

(E1 X E2) = E1 |X| E2

5. Operaes de juno teta so comutativas.

E1 |X| E2 = E2 |X| E1

6. Operaes de juno natural so associativas.

(E1 |X| E2) |X| E3 = E1 |X| (E2 |X| E3)

7. Comutatividade de e |X| (ou X): similar 6.



8. Comutatividade de Operaes de Conjunto

R S S R e

R S S R

- A operao no comutativa.

9. Associatividade de Operaes Produtrias e de Conjunto (X)

(R X S) X T R X (S X T)

- Por X entenda-se: X ou X ou ou ou .- A operao no associativa.


9. Associatividade de Operaes Produtrias e de Conjunto (X)

(R X S) X T R X (S X T)

Observao: Predicados de juno devem ser devidamente ajustados na associatividade de operaes produtrias. Exemplo: Seja 1 um predicado sobre atributos de R e S, 2 um predicado sobre atributos de S e T, e 3 um predicado sobre atributos de R e T. Ento,

(R X 1 S) X 2 3 T R X 1 3 (S X 2 T)


10. Comutatividade de Seleo e Operaes de Conjunto ()

11. Comutatividade de Projeo e Unio

c (R S) (c (R)) (c (S))- Por entenda-se: ou ou

listaAtributos (R S) (listaAtributos (R)) (listaAtributos (S))

- As operaes e no so comutativas.


12. Fuso de Selees e Operaes Produtrias

(a) c (R X S) R X = c S ou

(b) c (R X S) R S ou

(c) R X = c S R S

c

c

Exemplos de TransformaesExemplo 1:

nome_cliente ( cidade_agncia = Brooklyn (agncia |X| (conta |X| depositante)))nome_cliente (( cidade_agncia = Brooklyn (agncia)) |X| (conta |X| depositante))

Exemplo 2:nome_cliente ( cidade_agncia = Brooklyn saldo > 1000 (agncia |X| (conta |X| depositante)))nome_cliente ( cidade_agncia = Brooklyn saldo > 1000 ((agncia |X| conta) |X| depositante))nome_cliente ( cidade_agncia = Brooklyn saldo > 1000 (agncia |X| conta)) |X| depositante)

Exemplo3: Examinando uma subexpresso interna:cidade_agncia = Brooklyn saldo > 1000 (agncia |X| conta))cidade_agncia = Brooklyn ( saldo > 1000 (agncia |X| conta))cidade_agncia = Brooklyn (agncia) |X| saldo > 1000 (conta)

Exemplo 4: Usando projeesnome_cliente (( cidade_agncia = Brooklyn (agncia) |X| conta) |X| depositante)

nome_cliente((nmero_conta(( cidade_agncia = Brooklyn (agncia)) |X| conta)) |X| depositante)

Ordenando Junes Uma boa ordenao de operaes de juno importante para reduzir o tamanho

dos resultados intermedirios.

nome_cliente (( cidade_agncia = Brooklyn (agncia)) |X| conta |X| depositante)

Poderamos executar conta |X| depositante primeiro e, ento, fazer a juno do resultado com:

cidade_agncia = Brooklyn (agncia).

Entretanto, conta |X| depositante provavelmente uma relao grande, j que contm uma tupla para cada conta. Em contrapartida,

cidade_agncia = Brooklyn (agncia) |X| conta

, provavelmente, uma relao pequena.

Para confirmar, observe que, como o banco tem um grande nmero de agncias amplamente distribudas, provvel que apenas uma frao pequena dos clientes do banco tenha conta em agncias localizadas no Brooklyn. Assim, a expresso precedente resulta em uma tupla para cada conta mantida em uma agncia localizada no Brooklyn. Ento, a relao temporria que precisa ser armazenada menor que a que se obteria fazendo primeiro conta |X| depositante.

Otimizao Heurstica

Uma rvore de consulta pode ser transformada passo a passo em outra rvore de consulta mais eficiente.

Entretanto preciso assegurar que os passos de transformao sempre levem a uma rvore de consultaequivalente.

Determinadas regras de transformao preservam essaequivalncia.

Passo1: A regra 1, ao ser usada, quebra quaisquer

operaes SELECT com condies conjuntivas emuma cascata de operaes SELECT, permitindoum maior grau de liberdade para transferiroperaes SELECT para ramos diferentes e abaixo na rvore.

Passo2: Usando as regras 2, 4, 6, e 10 relativas

comutatividade do SELECT com outras operaes, move cada operao SELECT o mais longe parabaixo na rvores, que forem permitido pelosatributos envolvidos na condio de seleo.

Algoritmo de Otimizao Algbrica

Passo 3:

Usando as regras 5 e 9, relativas comutatividade e associatividade de operaes binrias, rearraja osns folhas da rvore utilizando o seguinte critrio: Posiciona as relaes do n folha com operaes de SELECT mais restritivas, de forma que elas possam ser executadas o quanto antes.


Passo 4:

Usando a regra 12, combina uma operao de PRODUTO CARTESIANO com uma operaoSELECT subseqente na rvore, gerando umaoperao JOIN se a condio representa umacondio de juno.

Passo 5:

Usando as regras 3, 4, 7 e 11, relativas cascata de PROJECT e comutao de PROJECT com outrasoperaes, quebra e transfere as listas de atributosde projeo para baixo na rvore.


Passo 6:

Identifica subrvores que representam grupos de operaes que podem ser executadas por um nicoalgoritmo (execues em pipeline).

Como exemplo, considere a consulta:

select unomefrom Empregado, Trabalha_Em, Projetowhere pnome = Aquarius and pnumero = pno and

essn = ssn and datanasc > 31-12-1957;


Passos na converso de uma rvore de consulta durante a otimizao heurstica. (a) rvore de consulta inicial (cannica) para a consulta. (b) Transferncia das operaes SELECT para baixo na rvore de consulta. (continua)

Exemplo:

Passos na converso de uma rvore de consulta durante a otimizao heurstica. (c) Aplicao, em primeiro lugar, da operao SELECT mais restritiva. (d) Substituindo PRODUTO CARTESIANO e SELECT por operaes JOIN.

Exemplo:

Passos na converso de uma rvore de consulta durante a otimizao heurstica. (e) Transferncia das operaes PROJECT para baixo na rvore de consulta.

Exemplo:

A Escolha de Planos de Avaliao

A gerao de expresses apenas parte do processo de otimizao de consultas.

Um plano de avaliao define exatamente qual algoritmo ser usado para cada operao e como a execuo das operaes coordenada.

nome_cliente (classificar para remover duplicatas)

|X| (hash-juno)

|X| (merge_juno) depositante

cidade_agncia = Brooklyn saldo < 1000(use o ndice 1) (use a varredura linear)

agncia conta

Interao de Tcnicas de Avaliao

Um modo de escolher um plano de avaliao para uma expresso de consulta simplesmente escolher o algoritmo mais barato para avaliar cada operao. E, olhando para os nveis da rvore, escolhe-se qualquer ordenamento para a execuo das operaes, desde que as operaes nas camadas mais baixas da rvore sejam executadas antes das operaes nas camadas mais altas.

Entretanto, essa estratgia pode no ser a melhor. Embora uma merge-juno, sob certas condies, possa ser mais cara que uma hash-juno, ela consegue prover um resultado classificado que torna mais barata a avaliao de uma operao posterior (como uma eliminao de duplicatas ou uma outra merge-juno).

Para escolher o melhor algoritmo global, se deve considerar at mesmo os algoritmos que no so os melhores para as operaes individuais.

Abordagens para escolha do melhor plano de avaliao: Baseada no custo de todos os planos; Heurstica.

Otimizao Baseada em Custo

O otimizador baseado no custo gera uma faixa de planos de avaliao a partir de uma determinada consulta usando as regras de equivalncia e escolhe aquele de menor custo.

Para uma consulta complexa, o nmero de planos diferentes por ser muito grande.

Diferentes tcnicas podem ser usadas para diminuir o nmero de planos a serem avaliados:

Quando se examina os planos para uma expresso, possvel terminar aps examinar apenas uma parte da expresso, se for determinado que o plano mais barato para aquela parte j est mais caro que a avaliao mais barata para uma expresso completa j examinada.

Otimizao Heurstica

Regras heurstica so utilizadas para transformar consultas da lgebra relacional;

No otimizador heurstico, a estratgia mais eficiente para cada operao escolhida.

Estrutura dos Otimizadores de Consulta

Na prtica, a maioria dos otimizadores de consultas combinam estratgias baseadas em custo com estratgias heursticas.

Alguns SGBDs consideram a probabilidade de j haver no buffer a pgina que contm o dado que se est precisando (isso mais um dado estatstico e pode resultar em estimativas de custos menores).

possvel usar a estratgia heursticas de dividir as consultasem sub-consultas que no utilizem mais de duas tabelas.

Transforma consultas em SQL em outras consultas em SQL que utilizam junes onde for possvel facilita a transformao da consulta em SQL em uma consulta em lgebra relacional.

Otimizao em PostgreSQL

Seguem alguns breves comentrios sobre otimizao e desempenho em PostgreSQL.

Para otimizao e desempenho, PostgreSQL utiliza-se dos comandos vacuum, analyze e explain.

VACUUM O comando Vacuum tanto recupera espao em disco, quanto otimiza o desempenho do banco e previne contra perda de dados muito antigos, devido ao recomeo do ID das transaes. Portanto, deve ser utilizado constantemente, pois tambm atualiza as estatsticas dos dados utilizados pelo planejador de comandos.

Na linha de comando:

vacuumdb -faze ou vacuumdb -fazq.


Exemplo de uso do vacuum:

Em uma tabela:

VACUUM VERBOSE ANALYZE nometabela;

Em um banco de dados completo:

Somente VACUUM ou VACUUM FULL ANALYZE;

Recomendaes:

Para a maioria das instalaes executar o comando VACUUM ANALYZE para todo o banco de dados, de vez em quando, em horrio de pouca utilizao.

Quando for excluda a maioria dos registros de uma tabela, sugere-se a execuo do comando VACUUM FULL. Contudo, este comando gera um forte bloqueio nas tabelas em que executado.


ANALYZE O comando ANALYZE coleta estatsticas sobre o contedo das tabelas do banco de dados e armazena os resultados na tabela do sistema pg_statistic. Posteriormente, o planejador de comandos utiliza estas estatsticas para ajudar a determinar o plano de execuo mais eficiente. Caso estas estatsticas no sejam atualizadas com freqncia, pode ser comprometido o desempenho do banco de dados, por uma escolha errada do plano de execuo dos comandos.

Normalmente, operaes DELETE ou UPDATE no removem os registros automaticamente (somente aps a execuo do vacuum isso acontece).


No PostgreSQL, pode ser utilizado o comando explain para ver o plano (conjunto executvel de instrues) criado pelo sistema para qualquer comando.

O comando explain traz informaes sobre custo, como tamanho da tupla, custo estimado de execuo, entre outros.

Exemplo de uso do explain:

EXPLAIN SELECT * FROM NOMETABELA;


EXPLAIN ANALYZE Executa a consulta e mostra o tempo real acumulado dentro de cada n do plano de execuo, junto com os custos estimados que o comando explain simples mostraria.


Referncias Bibliogrficas

Sistemas de Banco de Dados. (Cap. 12) Abraham Silberchatz, Henry F. Korth e S. Sudarshan. 3 Edio. Makron Books, 1999.

Sistemas de Banco de Dados. (Cap. 15) RamezElsmari, Shamkant B. Navathe. 4 Edio. Pearson Addison Wesley, 2005.

Manuais do PostgreSQL.

Documents

Processamento e Otimização de Consultas