Algoritmos para Seleção Simples

AULA 16Profa. Sandra de Amo

GBC053 – BCC2012-2

SeleçãoSELECT *

FROM R

WHERE R.A op ‘a’

op: =, < , > , ≤ , ≥

Tamanho de R = M páginas

Número de tuplas por página = Pr

R não ordenada, não tem índice em A Melhor solução = scan da relação R Custo = M I/Os

R sem índice, mas ordenada por A Busca binária até encontrar a primeira tupla da resposta.

Custo da busca = log2M = log21000 = 10 I/Os Scan de R a partir desta tupla para recuperar o resto das

tuplas que casam. Custo : depende do número de tuplas que satisfazem a condição da

resposta. Se A é chave de R e op é a igualdade: custo = 1 Se A não é chave de R , op é a igualdade, as tuplas com valores

iguais do atributo A cabem em X páginas (distribuição uniforme) então Custo = X

Em geral Custo total = log2M + custo de escanear o restante da relação R.

R com índice Indice = B-Tree

Custo para encontrar a folha inicial satisfazendo a condição de seleção = 3 a 4 I/Os

Custo de recuperar as entradas de DADOS satisfazendo a condição de seleção

Custo depende de : Do número de tuplas de DADOS qualificadas Se o índice é agrupado ou não

R tem índice B+ tree em ACondição de seleção : A > a

40

5120

20* 27* 33* 37* 46*40* 51* 55* 63* 97*

3363

10* 15*

SELECT * FROM RWHERE A > 34

<37, a0, b0>

<40, a1, b1>

<46, a2, b2>

<51, a3, b3>

<55, a4, b4>

Indice agrupado (e esparso) <63, a0, b0>

<97, a1, b1>

<99, a2, b2>

<101, a3, b3>

<102, a4, b4>

<110, a0, b0>

<120, a1, b1>

<122, a2, b2>

<200, a3, b3>

<239, a4, b4>

R tem índice B+ tree em A, Condição de seleção : A > aÍndice é agrupado Custo = 2 a 4 I/Os até encontrar a primeira entrada do arquivo de índice. Custo de recuperar todas as tuplas no banco de dados satisfazendo a

condição A > a As tuplas satisfazendo a condição de seleção estão contidas em p.I

páginas, onde I = número de páginas do arquivo de índice contendo entradas

com chave A > a p = fator que relaciona o tamanho de um registro de DADOS e

um registro de indice 1 registro de dados = p registros de indices

Custo Total de recuperar todas as tuplas: 4 + p.I

R tem índice B+ tree em ACondição de seleção : A > a

40

5120

20* 27* 33* 37* 46*40* 51* 55* 63* 97*

3363

10* 15*

SELECT * FROM RWHERE A > 34

<37, a0, b0>

<51, a1, b1>

Indice não agrupado(e denso)

<55, a5, b5>

<46, a2, b2>

<40, a0, b0>

<63, a3, b3>

Pid = 10 Pid = 7

<20, a5, b5>

<33, a7, b7>

<15, a2, b2>

<10, a3, b3>

<97, a4, b4>

Pid = 2Pid = 1

<27, a8, b8>

R tem índice B+ tree em A, Condição de seleção: A > a

Indice não agrupado: Custo de recuperar todas as tuplas no banco de dados após

encontrar a primeira entrada no arquivo de indice pode ser igual ao número de tuplas satisfazendo a condição A > a

Solução: ordenar as entradas do arquivo de indice pelo page-id do campo * Entrada do indice = < chave, page-id, slot-id> Custo = número de páginas contendo tuplas com A > a

Exercício (1a Prova) Calcular o custo da consulta SELECT * FROM R WHERE R.A > 38

Resposta = 29 I/Os

Exercício Calcular o custo de:

Select * From R where A = anos seguintes casos:

Indice agrupado, B+ tree Indice não agrupado (e denso !!) , B+ tree

Observação: Análise os casos em que A é chave primária de R e

quando não é chave primária de R

Exemplo

Select * From R where R.name < ‘C%’ M = número de páginas de R = 1000 100 tuplas por página 100.000 tuplas em R Nomes são uniformemente distribuídos com relação à

letra inicial. 26 letras no alfabeto Portanto: 10% dos nomes satisfazem R.name < ‘C%’ 10000 tuplas satisfazem R.name < ‘C%’ 100 páginas contendo tuplas satisfazendo R.name < ‘C%’ N = número de páginas do arquivo de índice com R.name < ‘C%’

Exemplo – continuação Custo da busca usando o índice B-Tree

B+tree agrupado: 4 + 100 = 104 I/Os B+tree não-agrupado (pior caso) : 4 + N + 10000 = 10004

+ N I/Os B+tree não-agrupado com arquivo de índice ordenado

pelo page-id 4 + (custo de carregar e ordenar as N páginas do

arquivo de índice pelo page-id) + (custo de ler as 100 páginas de dados) = 104 + 2N([logB-1 N/B] + 1)

Custo da busca usando um Scan 1000 I/Os

ConclusãoB+tree não-agrupado: dependendo do número N de tuplas

satisfazendo a condição de seleção, distribuição destas tuplas nas páginas de dados e o espaço disponível no buffer, a melhor solução é não utilizar o índice e fazer um simples scan do arquivo.

Exemplo:B = 3, N = 10: Custo = 104 + 2.10.([1,74] + 1) = 104 + 20.3 = 164 I/Os

B = 3, N = 100 : Custo = 104 + 2.100([5,07] + 1) = 104+200.(6 + 1) = 104 + 1400 = 1504 I/Os

Custo de 1 Scan de R = 1000 I/Os

R tem indice Hash em A Condição de seleção : A = a Custo de se localizar a página do bucket no arquivo

de índice: 1 a 2 I/Os (depende se há diretório de ponteiros)

Custo para se obter as tuplas satisfazendo a condição de seleção: depende se o índice é agrupado ou não. Se A = chave de R: custo = 1 I/O

ExemploSelect * From R where R.name = ‘Joe’M = número de páginas de R = 1000100 tuplas com R.name = ‘Joe’ Custo de se encontrar o bucket correspondente a ‘Joe’ no

índice = 1 a 2 I/O Custo de se obter as tuplas no banco de dados = varia de 1 a

100 I/Os (caso o indice não for agrupado) Se as 100 tuplas estão espalhadas em 5 páginas, ordenando-se o

indice pelo page-id, pode-se recuperar estas tuplas em 5 I/Os. Logo, o custo total é de 2 + 5 + custo da ordenação.