Optimização - 1

Optimização de perguntas

1 Processamento de selecções

2 Processamento de junções

3 Manipulação algébrica

Optimização - 2

Parâmetros dos dados

representação de relações em memória: colecção de registos tuplos empacotados em blocos de disco exclusivos da relação tuplos dispersos por blocos que contêm tuplos de várias relações,

possivelmente associadas

definições para uma relação R TR : número de tuplos em R

BR : número de blocos capazes de conter R (se estiver empacotada)

TR/BR : número de tuplos por bloco

• Sistema de armazenamento com blocos de 1024 bytes• R com TR=1 000 000 de tuplos de 100 bytes cada• BR= 100 000

Optimização - 3

Custo de uma operação

Custo em processamento de dados = número de blocos transferidos (lidos ou escritos) entre a memória secundária e a principal

número de acessos de bloco à memória secundária para percorrer uma relação depende organização física escolhida min: BR; max: TR ou mais se não se souber que blocos contêm os registos

índices: optimizam selecções se R possuir índice em A, assume-se que o custo de A=c(R) é

aproximadamente o número de blocos que contenham tuplos com A=c (ignora-se os acessos destinados a ler o próprio índice)

Optimização - 4

Índices

índices agrupadores (clustering) - ex: índices primários (ISAM) número de tuplos com A=c: N; custo: N*BR/TR

índices não agrupadores - ex: árvore-B usada como índice denso sobre atributos não chave custo: N, pois só por coincidência dois tuplos estarão no mesmo bloco

tamanho da imagem de um índice num atributo A de R, IR.A, é o número de valores diferentes que A toma em R assumindo valores equiprováveis, o custo da selecção A=c(R) é

índice não agrupador: TR/IA

índice agrupador: BR/IA

Optimização - 5

Optimização de selecções

Exemplo do System R Problema: processar uma pergunta da forma

SELECT A1, …, An

FROM R

WHERE C1 AND C2 AND …;

Ci’s podem ser disjunções, negações, inclusões, etc., mas não conjunções

Ci casa com um índice sobre A se Ci for da forma A=c; System R tende a usar este índice para obter os tuplos e aplicar em seguida as outras condições

as relações podem estar armazenadas por chave primária ou numa estrutura encaixada

Optimização - 6

Exemplo das Encomendas

BD de Encomendas tem três relaçõesCLIENTES( Cnome, Cmorada, Balanco )

ENCOMENDAS( E#, Data, Cnome )

LINHAS( E#, Item, Quantidade )

armazenamento encaixado (CLIENTES(ENCOMENDAS(LINHAS)*)*)*

índice em LINHAS.E# é agrupador, apesar de alguns registos de encomendas e de clientes aparecerem pelo meio

índices nos outros atributos de LINHAS e das outras relações são não agrupadores

cliente1enc1lin1lin2lin3enc2lin4lin5lin6lin7cliente2enc3lin8

cliente3enc4lin9lin10enc5lin11lin12lin13lin14lin15cliente4enc6lin16

bloco1 bloco2

Optimização - 7

Algoritmo para perguntas simples

abordagem baseada em enumeração de casos, estimação de custos das alternativas viáveis e escolha da mais barata

estratégias usar um Ci para obter os tuplos e seleccioná-los pelas outras condições

examinar todos os tuplos de R e ver quais satisfazem todas as condições

Algoritmo entrada: pergunta SQL (da forma indicada acima) e informação sobre

índices, valores de T e B e tamanhos das imagens dos índices saída: forma de computar a resposta à pergunta método:considerar todas as alternativas indicadas abaixo que sejam

viáveis, analisando os vários casos possíveis para cada uma delas; escolher a de menor custo

Optimização - 8

Alternativas a considerar

1 Obter os tuplos de R que satisfaçam uma condição da forma A=c que case com um índice agrupador existente. Custo estimado= B/IA.

2 Usar um índice agrupador num atributo A, tal que uma das condições seja da forma A c, com <, <=, > ou >=, para obter os tuplos de R. Custo estimado= B/2.

3 Índice não agrupador que case com A=c. Custo= T/IA.4 Se a relação estiver armazenada isolada, ler todos os tuplos. Custo= B.5 Se a relação não estiver isolada, mas existir um índice agrupador (mesmo

que não case com nenhum Ci, ler todos os tuplos. Custo=B.6 Se existir um índice não agrupador sobre A e uma condição A c, com

<, <=, > ou >=, usar esse índice para obter os tuplos de R. Custo= T/2.7 Usar um qualquer índice não agrupador para obter os tuplos de R. Custo=T.8 Percorrer todos os blocos que possam conter tuplos de R. Custo>=T.

Optimização - 9

Exemplo

Relativamente à BD de Encomendas SELECT E#

FROM linhas

WHERE quantidade >=5 AND item=‘Broa’;

existe índice agrupador para LINHAS em E# e índices não agrupadores em Item e Quantidade; existem 1000 tuplos de LINHAS com 10 tuplos por bloco; tamanho da imagem de Item é 50

Estimativa de custos (T=1000, B=T/10=100, I=50) (1) e (2) não aplicável (3) T/I= 1000/50=20 (4) não aplicável se relação armazenada com encomendas (5) B=100 (6) Quantidade>=5: T/2=500 (7) e (8) custo >T=1000