Algoritmos para Seleção Simples

AULA 18Profa. Sandra de Amo

GBC053 – BCC2013-1

Seleção com condição simplesSELECT *

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. Em geral o custo total =

log2M + K onde K = número de páginas satisfazendo a condição da

consulta.

R sem índice, mas ordenada por ACusto de encontrar o número de páginas X satisfazendo a

condição de seleção Condição (A = a)

Se A é chave de R então X = 1 Se A não é chave de R e se a distribuição dos valores de A for

uniforme: X = M/Val, onde Val = núm. de valores do atributo A

Condição (A > a) Supondo uma distribuição uniforme dos valores do atributo A Seja K = porcentagem dos valores de A correspondendo aos valores > a Temos então: X = K*M

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 A – agrupado Condiçã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 >

aComo o índice é agrupado basta : encontrar a primeira página P1 contendo registro com A >a Seja pgId = identificador da página P1 Número de páginas de dados a serem lidas: p.I

I = num. de pag. 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 índices

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 pelo page-id do campo rid as entradas do arquivo de indice que verificam a condição de seleção

Entrada do indice = < chave, page-id, slot-id> Custo = número de páginas contendo tuplas com A

> a

3, (2,3)

4, (5,7)

4, (2,15)

5, (5,7)

7, (4,9)

9, (1,3)

Páginas de dados apontadas pelo indice1,3,6

R tem índice B+ tree em A – Não agrupado Condição de seleção : A > 10

(9,a,b)

(10,a1,b1)

(15, c, d)

(3,x1, y1)

(4,x2,y2)

pgId = 1 pgId = 2 pgId = 3 pgId = 4 pgId = 5

(10,x1, y1)

9, (4,12)

10, (3,10)

10, (1,1)

15, (6,7)

15, (1,9)

15, (3,3)

18, (6,12)

18, (3,10)

pgId = 6

(15,x3, y3)

(18,x4, y4)

(7,a2,b2)

(9,a3,b3)

(4,a4,b4)

(5,a5,b5)

(15,x5, y5)

(18,x6, y6)

Exercício para entregar Calcular o custo de:

Select * From R where A = a nos seguintes casos:

Indice agrupado, B+ tree, denso 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

R tem índice B+ tree em Aesparso – agrupado - Condição de seleção : A = 38

18SELECT * FROM RWHERE A = 38

Indice Esparso e agrupado

Pid = 8Pid = 7

40

3* 15* 21* 33* 45* 56*

<21, a5, b5>

<21, a7, b7>

<23, a2, b2>

<25, a3, b3>

<30, a4, b4>

<33, a0, b0>

<38, a8, b8>

<33, a1, b1>

<38, a8, b8>

CUSTO = 2 páginas de Indice (i1 e i2) + 1 pág. dados (d2) = 3 I/Os

Quando o índice é esparso épreciso carregar a página de dados(no caso pg de Pid=8) e fazer buscabinária para encontrar o registro(caso a chave não estiver no indice)Se a chave estiver no indice, encontra-se o registro de dados diretamente pelo seu rid

i1

i2

d2

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: aproximadamente 10% dos nomes satisfazem

R.name < ‘C%’(na verdade são (1/13)% = 7,7%) 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 N = número de páginas do arquivo de índice correspondendo à

condição de seleção 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 páginas do

arquivo de indice correspondendo a valores satisfazendo a condição de seleção e do 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 (isto é, as páginas contendo entradas satisfazendo a condição de seleção), pode-se recuperar estas tuplas em 5 I/Os.

Logo, o custo total é de 2 + 5 + custo da ordenação.