Índices em Banco de Dados

Prévia do material em texto

Índices	(index)	
Prof.	Daniel	de	Oliveira	
danielcmo@ic.uff.br	
Projeto	de	Banco	de	Dados	para	
Sistemas	de	Informação	
Introdução	
Query	em	ling.	de	alto	nível	(SQL)	
Scanner		
e	Parser	
OGmizador		
Consultas	
RunGme	
DB	Processor	
Scanner		
e	Parser	
Forma	intermediária	da	query	
Plano	de	execução	
Código	para	executar	a	query	
Resultado	da	Query	
Introdução	
Query	em	ling.	de	alto	nível	(SQL)	
Scanner		
e	Parser	
OGmizador		
Consultas	
RunGme	
DB	Processor	
Scanner		
e	Parser	
Forma	intermediária	da	query	
Plano	de	execução	
Código	para	executar	a	query	
Resultado	da	Query	
4 
Índices	
•  São	 estruturas	 de	 dados	 (arquivos)	 adicionais	 àquelas	 contendo	
os	registros	de	dados	
•  Provêm	caminhos	de	acesso	alternaGvos	aos	registros	sem	afetar	
a	disposição	Ssica	dos	registros	no	arquivo	
•  Um	índice	acelera	a	recuperação	de	registros	baseada	no	campo	
de	indexação	
–  Campo	 de	 indexação	 ou	 campo	 chave:	 atributos	 indexadores	 usados	 para	
construir	o	índice	e	para	encontrar	o	end.	do	registro	buscado.	
–  Chave	 de	 busca:	 outro	 termo	 u:lizado	 para	 fazer	 referência	 ao	 conjunto	 de	
campos	usado	para	 indexação	de	um	arquivo.	Não	confundir	com	o	conceito	de	
chave.	
–  A	 princípio,	 qualquer	 subconjunto	 de	 campos	 do	 registro	 de	 um	 arquivo	 pode	
compor	uma	chave	de	busca	para	construção	de	um	índice	sobre	tal	arquivo.	
Índices	
5 
Índices	
 Estrutura de dados interna ao SGBD que permite acesso mais 
rápido às informações do banco. 
Exemplo (simplificado): 
1 SMITH 
2 JONES 
4 CLARK 
3 BLAKE 
5 ADAMS 
Endereço (Bloco) Nome 
Índice sobre o atributo Nome de Fornecedor 
ATENAS 30 ADAMS F5 
LONDRES 20 CLARK F4 
PARIS 30 BLAKE F3 
PARIS 10 JONES F2 
LONDRES 20 SMITH F1 
CIDADE STATUS NOME CODIGO Fornecedor 
6 
Índices	
•  Vantagens:	
– Acesso	mais	rápido	ao	registro	quando	a	procura	é	
sobre	campo	indexado.	
– Menos	E/S:	arquivo	de	índice	menor	que	o	arquivo	
de	dados.	
•  Desvantagens:	
–  Inclusão,	exclusão	e	alteração	ficam	mais	lentas.	
– Mais	espaço	de	armazenamento.	
7 
Tipos	de	Índices	
•  Ind.	Primário	x	Ind.	Secundário	
•  Índice	Denso	x	Índice	não	Denso	(Esparso)	
•  Índices	InverGdos	
Tipos	de	Índices	
8 
Tipos	de	Índices	
•  Um	 Índice	 Primário	 é	 construído	 sobre	 o	 campo-chave	 de	
classificação	de	um	arquivo	ordenado	de	registros		
–  Lembrando	 que:	 campo-chave	 de	 classificação	 é	 o	 campo	 usado	 para	
ordenar	fisicamente	os	registros	do	arquivo	no	disco,	e	cada	registro	deve	
possuir	um	valor	único	para	o	campo	
•  Um	 Índice	 Secundário	 é	 	 construído	 sobre	 quaisquer	 outros	
campos	que	não	os	de	ordenação	Ssica	do	arquivo.	
9 
•  Um Índice Denso possui uma entrada no índice para cada 
registro no arquivo de dados. 
•  Os registros podem estar armazenados em qualquer ordem no 
arquivo. 
•  Um Índice Não Denso (índice esparso) consiste num 
índice para blocos ou páginas do arquivo, cada um dos 
quais contendo um grupo de registros. 
•  Os registros precisam estar organizados segundo o atributo 
indexador. 
Tipos	de	Índices	Tipos	de	Índices	
10 
Índices	Primários	
•  Registros	com	2	campos:		
–  Campo	de	mesmo	domínio	da	chave	de	classificação	do	arquivo	de	dados		
–  Ponteiro	para	um	bloco	de	disco	(end.	bloco)	
•  Uma	entrada	de	índice	para	cada	bloco	
–  Em	cada	entrada	do	 índice,	o	valor	do	campo	chave	contém	o	valor	do	
mesmo	campo	no	primeiro	registro	do	bloco	–	registro	âncora.	
–  No.	de	entradas	do	índice	=	No.	de	blocos	que	ocupa	o	arquivo		
–  É	um	índice	esparso	
–  Precisa	de	muito	menos	blocos	que	o	arquivo	que	indexa,	portanto	uma	
busca	 binária	 em	 um	 arquivo	 de	 índices	 exige	muito	menos	 acessos	 a	
blocos	
11 
12 
Exemplo	1	–	Sem	Índices	
 
•  r = 30.000 registros 
•  bloco B = 1.024 bytes. 
•  registro R = 100 bytes (reg. tamanho fixo) 
•  bfr(fator de blocagem) = B/R = 1024/100 = 10 
registros por bloco 
•  número total de blocos: b = r/bfr = 30000/10 = 
3000 blocos 
•  Uma busca binária no arquivo necessitaria 
aproximadamente log2b = log2 3000 = 12 acessos ao 
bloco (supondo arquivo ordenado). 
•  Uma busca linear, precisaria, no pior caso, de 3000 
acessos (registro desejado no último bloco) 
Cálculo	de	Acessos	–	Sem	Índice	
13 
Exemplo	2	–	com	Índice	Primário	
	
•  Cont.	Exemplo	1	
•  chave	de	ordenação:	V	=	9	bytes	
•  ponteiro	(para	arquivo)	:	P	=	6	bytes,	
•  cada	entrada	no	índice	:Ri	=	9	+	6	=	15	bytes;		
•  fator	de	blocagem	para	o	índice	bfri	=	 	B/Ri	 	=	 	1024/15	 	=	68	entradas	
por	bloco.		
•  n0	total	de	entradas	no	índice	=	n0	de	blocos	do	arq.	dados:	 	⎡ri/bfri⎤	 	=		
3000/68		=	45	blocos.		
	
UGlizando	 pesquisa	 binária	 no	 índice:	 log2	 bi	 	 =	 ⎡log2	 45⎤	 =	 6	 acessos	 a	
bloco.		
				pesquisa	do	registro	usando	o	índice:	6	+	1	=	7	acessos	(acesso	
adicional	ao	bloco	no	arquivo	de	dados),	contra	12	da	pesquisa	binária	
sobre	o	arquivo	de	dados.	
Cálculo	de	Acessos	–	Com	Índice	
14 
Índices	Secundários	
•  Podem	haver	vários	para	um	mesmo	arquivo	
•  Estrutura	similar	aos	outros	Gpos:	2	campos	
•  Pode	ser	construído		
–  sobre	chave-candidata	–	valor	único	por	registro	
•  Uma	entrada	para	cada	entrada	do	índice	(índice	denso),	pois	como	
o	 arquivo	 não	 está	 ordenado	por	 chave-candidata,	 não	 podem	 ser	
uGlizadas	âncoras	de	bloco	
•  Como	há	um	maior	 número	de	 entradas,	 então	é	maior	 tempo	de	
busca	em	relação	ao	índice	primário	
•  Mas	comparaGvamente	ao	arquivo	não	indexado,	o	ganho	é	maior,	
pois	sem	o	índice	seria	necessário	realizar	uma	busca	linear	
15 
Índices	InverGdos	
	Emp(nome,sexo,	est._civil,	....)	
•  Existe	um	índice	secundário	sobre	o	20	e	30	
atributos	de	Emp,	p/	os	quais	o	valor	do	
atributo	existe.	
•  Consiste	de	um	conj.	de	pares	palavra	(chave	
de	pesquisa)-ponteiro,	de	tal	forma	que	o	
índice	aponta	p/	as	ocorrências	onde	aquele	
valor	ocorre	(=Verd)	
16 
Exemplo	
feminino 
Claudia.... 
 
 
Beatriz... 
divorciado 
Paulo.... 
17	
Exemplo:		“Sailors	and	Boats”	
•  Informações	devem	ser	capturadas	e	
armazenadas	sobre	marinheiros	(sailors),	barcos	
(boats)	e	as	reservas	que	associam	um	
marinheiro	a	um	barco	(ReservaGon)	
–  Sailor (id:int, name:string, rating:int, age:int, 
base:string) 
–  Boat (id:int, name:string, colour:string, 
base:string) 
–  Reservation (sid:int, bid:int, day:date)			
18	
Índices	Criados	AutomaGcamente	
•  Em	cada	relação,	o	SGBD	cria	um	índice	B-tree	para	a	chave	
primária	
–  As	B-trees	se	mantém	balanceadas	sempre	que	um	elemento	é	
adicionado	ou	reGrado	
–  Assim,	criaremos	índices	nas	seguintes	tabelas	e	campos:	
•  Sailor,	id	
•  Boat,	id	
•  ReservaGons,	índice	composto	em	sid,	bid	e	day	
•  Adicionalmente,	o	SGBD	cria	um	índice	para	cada	UNIQUE	
CONSTRAINT	
19	
Índice	Composto	
•  Se	a	chave	consiste	de	mais	de	um	campo,	o	
índice	é	chamado	de	índice	composto	
–  i.e.	um	índice	para	diversos	atributos	
•  Um	índice	composto	é	ordenado	
lexicograficamente	de	acordo	com	a	ordem	dos	
atributos	
– E.g	para	a	chave	composta	(name,age),	teremos:	
(Kelly,	22)	<	(Kelly,	63)	<	(Smith,	18)	<	(Smith,36)	
– Lembrar	que	é	diferente	do	índice	(age,	name)	
20	
Índices	Secundários	
•  Criar	índices	secundários	para	todos	os	
campos	que	são	buscados	frequentemente	
– Campos	que	estão	na	cláusula	WHERE,	e	não	no	
SELECT	
	
•  Neste	caso,	o	usuário	tem	que	criar	o	índice	
explicitamente,	como	será	apresentado	no	
próximo	slide	
	
21	
Índices	Criados	Explicitamente	
•  Um	índice	
–  Possui	um	nome	
–  Deve	ser	criado	sobre	um	conjunto	de	atributos	
existentes	
–  Pode	ser	DROPado•  Exemplos	
–  CREATE INDEX sailor_name_idx 
 ON Sailor(name); 
–  DROP INDEX sailor_name_idx; 
–  CREATE INDEX sailor_name_and_age_idx 
 ON Sailor(name, age) 
22	
UGlizando	CREATE	INDEX	(1)		
•  O	CREATE	INDEX	cria	um	índice	ordenado	sobre	a	tabela	
explicitada.		
•  Uma	vez	que	um	índice	é	criado,	ele	não	é	referenciado	em	
uma	consulta	SQL	a	não	ser	que	seja	para	validá-lo	(VALIDATE	
INDEX)	ou	excluí-lo	(DROP	INDEX).	
•  Não	podemos	criar	índice	sobre	views.		
–  Adicionar	índices	nas	tabelas	que	são	base	para	a	view	
23	
UGlizando	CREATE	INDEX	(2)	
•  O	owner	de	um	índice	é	sempre	o	mesmo	owner	
da	tabela.	
•  O	nome	do	índice	deve	ser	único	para	cada	
owner	
–  Não	se	pode	criar	um	índice	caso	a	tabela	esteja	em	
uso!	
–  O	commando	CREATE	INDEX	pode	ser	extremamente	
demorado.	O	SGBD	não	processa	NENHUMA	
requisição	enquanto	que	o	índice	não	tenha	sido	
criado		
24	
Overheads	vs	Desempenho	
•  Existe	um	overhead	que	deve	ser	considerado	na	
manutenção	de	índices	secundários.	
–  O	índice	deve	ser	atualizado	sempre	que	os	dados	da	
tabela	o	forem	
–  O	índice	ocupa	espaço	em	disco	
	
•  O	DBA	deve	desempenhar	seu	papel	e	tentar	
achar	um	“meio	termo”	entre	overhead	e	
desempenho	
–  “Faster	data	retrieval”	
25	
Quando	criamos	índices	secundários	(1)	
•  Adicionar	um	índice	para	a	chave	estrangeira	que	é	
frequentemente	acessada	
–  e.g.	bid	em	ReservaGons,	se	nós	precisamos	frequentemente	
saber	o	nome	do	barco	que	está	em	outra	tabela	
•  Adicionar	um	índice	para	um	atributo	qualquer	que	é	usado	
frequentemente	em	buscas	
–  e.g.	day	em	ReservaGons	(quais	reservas	temos	para	hoje	ou	
para	amanhã?)	
–  e.g.	name	em	Sailor	(qual	a	nota	para	um	marinheiro	chamado	
‘Daniel’?).		
–  Lembrar	que	pessoas	normais	pesquisam	por	nome	e	não	por	
ID…	
	
26	
Quando	criamos	índices	secundários	(2)	
•  Adicionar	um	índice	secundário	para	atributos	
referenciados	nas	cláusulas	order	by,	group	by,	
min,	max,	avg	
–  e.g.	age	em	Sailor	se	precisamos	saber	as	idades	em	
ordem	crescente	
•  Adicionar	um	índice	secundário	composto	que	
possa	prover	todos	os	detalhes	frequentemente	
requisitados	pela	consulta	sem	ter	que	“varrer”	a	
tabela	toda	
–  E.g.	raGng	e	age	em	Sailor	se	a	query	frequente	é:	
SELECT rating, AVG(age) FROM Sailor 
GROUP BY rating; 
27	
Quando	NÃO	criar	um	índice		
•  Se	a	tabela	é	pequena	–	poucos	registros	
•  Se	a	estrutura	da	tabela	é	alterada	
frequentemente	
–  drop	index,		
–  update		
–  create	index	
	
•  Se	o	atributo	que	faz	parte	do	índice	retorna	uma	
grande	proporção	de	registros	
–  e.g.	atributo	sexo	que	só	pode	ser	F	our	M.