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 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 !!