Algoritmos para SeleçãoAULA 23

Profa. Sandra de AmoGBC053 – BCC

Seleção com condição simplesSELECT *FROM RWHERE R.A op ‘a’

op: =, < , > , ≤ , ≥

Tamanho de R = M páginasNú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*

33 63

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*

33 63

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 > aIndice 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 + 1000 = 1004 + 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/OsB = 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.

Condições Gerais de Seleção SELECT *FROM RWHERE (R.A op ‘a’ OR R.A op ‘a1) AND (R.B op ‘b’ OR R.B op ‘b1’)

op: =, < , > , ≤ , ≥

Tamanho de R = M páginasNúmero de tuplas por página = Pr

Condição de seleção em FNC (A11 op a11 OR ... OR An1 op an1) AND

(A12 op a12 OR ... OR An2 op an2) AND .... AND (A1k op a1k OR ... OR Ank op ank)

Exemplo: (day < 8/9/2002 OR R.name = ‘Joe’) AND

(R.id = 5 OR R.name = ‘Joe’)

Caso 1: sem OR Solução 1 : um só índice

Criar índice para atributo que aparece na condição de seleção, com maior “seletividade”

utilizar este índice para obter os registros satisfazendo a condição da chave do índice

A medida que se recupera as tuplas satisfazendo esta condição elimina-se as tuplas que não satisfazem alguma das outras condições.

Caso 1: sem OR Solução 2: diversos índices

Utiliza-se diversos indices, sobre alguns atributos aparecendo na condição de seleção.

Para cada condição Ai = ai recupera-se as páginas do arquivo de indice satisfazendo esta condição.

Ordena-se as entradas de cada índice pelo page-id Faz-se a intersecção das entradas com os mesmos page-ids Recupera-se as tuplas contidas nas páginas indicadas pelos

page-ids e elimina-se aquelas que não satisfazem as outras condições da seleção (para as quais não foram considerados indices).

Registros do Indice 1 satisfazendo a condição de seleção : Chave > 1, ordenados pelo page_id

2, (1,3)

7, (1,7)

3, (1,15)6, (2,10)4, (7,10)

15, (8,3)

18, (8,7)

10, (9,15)17, (9,11)5, (17,10)

4, (1,3)

4, (1,7)

7, (4,15)6, (5,10)8, (7,10)

7, (8,3)

12, (11,7)

5, (15,15)10, (16,11)9, (17,9)

Páginas de dados apontadas: 1, 2, 7, 8, 9, 17

Registros do Indice 2 satisfazendo a condição de seleção : Chave ≥ 4, ordenados pelo page_id

Páginas de dados apontadas: 1, 4, 5, 7, 8, 11,15,16,17

Páginas que podem conter registros de dados satisfazendoàs duas condições simultaneamente: 1, 7, 8, 17

Só estas páginas de dados serão carregadas no buffer !!

Exemplo Condição:

day < 8/9/2002 AND R.id = 5 AND S.age > 35 Usando B+tree em day recupera-se o conjunto das

entradas E1 com day < 8/9/2002 Usando um indice Hash em R.id recupera-se o conjunto de

entradas E2 com R.id = 5 Ordena-se cada conjunto de entradas pelo page-ids Considera-se a intersecção das entradas pelos rids

<a1,p1,s1> ε E1 e <a2, p1, s7> ε E2 então <a1,p1,s1> e <a2, p1, s7> entram na intersecção

Recupera-se as tuplas do banco de dados, através das entradas contidas na intersecção.

Caso 2 : com OR A = a1 OR B = b1

Indice em A, não há indice em B Melhor solução : scan (o indice em A não ajuda nada)

(A = a1 OR B = b1) AND C = c1 Indice em A, não há indice em B, indice em C Melhor solução: utilizar o indice em C

A = a1 OR B = b1 Indice em A, indice em B Melhor solução:

recupera-se as entradas no arquivo de indice para A = a1 : recupera-se as entradas no arquivo de indice para B = b1 : Faz-se a união destes dois conjuntos de entradas Ordena-se este conjunto pelo page-id

Registros do Indice 1 satisfazendo a condição de seleção : Chave > 1, ordenados pelo page_id

2, (1,3)

7, (1,7)

3, (1,15)6, (2,10)4, (7,10)

15, (8,3)

18, (8,7)

10, (9,15)17, (9,11)5, (17,10)

4, (1,3)

4, (1,7)

7, (4,15)6, (5,10)8, (7,10)

7, (8,3)

12, (11,7)

5, (15,15)10, (16,11)9, (17,9)

Páginas de dados apontadas: 1, 2, 7, 8, 9, 17

Registros do Indice 2 satisfazendo a condição de seleção : Chave ≥ 4, ordenados pelo page_id

Páginas de dados apontadas: 1, 4, 5, 7, 8, 11,15,16,17

Páginas que podem conter registros de dados satisfazendouma das duas condições: 1,2,4,5,7,8,9,11,15,16,17

Só estas páginas de dados serão carregadas no buffer !!